Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeadStoreElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -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~++20200917111122+b03c2b8395b/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b=. -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-09-17-195756-12974-1 -x c++ /build/llvm-toolchain-snapshot-12~++20200917111122+b03c2b8395b/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(false), 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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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~++20200917111122+b03c2b8395b/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 M is an intrisnic that does not read or write memory.
1523bool isNoopIntrinsic(MemoryUseOrDef *M) {
1524 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(M->getMemoryInst())) {
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~++20200917111122+b03c2b8395b/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))
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 LibFunc LF;
1705 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
1706 switch (LF) {
1707 case LibFunc_strcpy:
1708 case LibFunc_strncpy:
1709 case LibFunc_strcat:
1710 case LibFunc_strncat:
1711 return {MemoryLocation(CB->getArgOperand(0))};
1712 default:
1713 break;
1714 }
1715 }
1716 switch (CB->getIntrinsicID()) {
1717 case Intrinsic::init_trampoline:
1718 return {MemoryLocation(CB->getArgOperand(0))};
1719 case Intrinsic::masked_store:
1720 return {MemoryLocation::getForArgument(CB, 1, TLI)};
1721 default:
1722 break;
1723 }
1724 return None;
1725 }
1726
1727 return MemoryLocation::getOrNone(I);
1728 }
1729
1730 /// Returns true if \p UseInst completely overwrites \p DefLoc
1731 /// (stored by \p DefInst).
1732 bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *DefInst,
1733 Instruction *UseInst) {
1734 // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
1735 // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
1736 // MemoryDef.
1737 if (!UseInst->mayWriteToMemory())
1738 return false;
1739
1740 if (auto *CB = dyn_cast<CallBase>(UseInst))
1741 if (CB->onlyAccessesInaccessibleMemory())
1742 return false;
1743
1744 int64_t InstWriteOffset, DepWriteOffset;
1745 if (auto CC = getLocForWriteEx(UseInst))
1746 return isOverwrite(UseInst, DefInst, *CC, DefLoc, DL, TLI, DepWriteOffset,
1747 InstWriteOffset, BatchAA, &F) == OW_Complete;
1748 return false;
1749 }
1750
1751 /// Returns true if \p Def is not read before returning from the function.
1752 bool isWriteAtEndOfFunction(MemoryDef *Def) {
1753 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)
1754 << *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)
1755 << ") 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)
;
1756
1757 auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
1758 if (!MaybeLoc) {
1759 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)
;
1760 return false;
1761 }
1762
1763 SmallVector<MemoryAccess *, 4> WorkList;
1764 SmallPtrSet<MemoryAccess *, 8> Visited;
1765 auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
1766 if (!Visited.insert(Acc).second)
1767 return;
1768 for (Use &U : Acc->uses())
1769 WorkList.push_back(cast<MemoryAccess>(U.getUser()));
1770 };
1771 PushMemUses(Def);
1772 for (unsigned I = 0; I < WorkList.size(); I++) {
1773 if (WorkList.size() >= MemorySSAScanLimit) {
1774 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit exploration limit.\n"; }
} while (false)
;
1775 return false;
1776 }
1777
1778 MemoryAccess *UseAccess = WorkList[I];
1779 // Simply adding the users of MemoryPhi to the worklist is not enough,
1780 // because we might miss read clobbers in different iterations of a loop,
1781 // for example.
1782 // TODO: Add support for phi translation to handle the loop case.
1783 if (isa<MemoryPhi>(UseAccess))
1784 return false;
1785
1786 // TODO: Checking for aliasing is expensive. Consider reducing the amount
1787 // of times this is called and/or caching it.
1788 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1789 if (isReadClobber(*MaybeLoc, UseInst)) {
1790 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit read clobber " <<
*UseInst << ".\n"; } } while (false)
;
1791 return false;
1792 }
1793
1794 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1795 PushMemUses(UseDef);
1796 }
1797 return true;
1798 }
1799
1800 /// If \p I is a memory terminator like llvm.lifetime.end or free, return a
1801 /// pair with the MemoryLocation terminated by \p I and a boolean flag
1802 /// indicating whether \p I is a free-like call.
1803 Optional<std::pair<MemoryLocation, bool>>
1804 getLocForTerminator(Instruction *I) const {
1805 uint64_t Len;
1806 Value *Ptr;
1807 if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
1808 m_Value(Ptr))))
1809 return {std::make_pair(MemoryLocation(Ptr, Len), false)};
1810
1811 if (auto *CB = dyn_cast<CallBase>(I)) {
1812 if (isFreeCall(I, &TLI))
1813 return {std::make_pair(MemoryLocation(CB->getArgOperand(0)), true)};
1814 }
1815
1816 return None;
1817 }
1818
1819 /// Returns true if \p I is a memory terminator instruction like
1820 /// llvm.lifetime.end or free.
1821 bool isMemTerminatorInst(Instruction *I) const {
1822 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1823 return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
1824 isFreeCall(I, &TLI);
1825 }
1826
1827 /// Returns true if \p MaybeTerm is a memory terminator for the same
1828 /// underlying object as \p DefLoc.
1829 bool isMemTerminator(MemoryLocation DefLoc, Instruction *MaybeTerm) {
1830 Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1831 getLocForTerminator(MaybeTerm);
1832
1833 if (!MaybeTermLoc)
1834 return false;
1835
1836 // If the terminator is a free-like call, all accesses to the underlying
1837 // object can be considered terminated.
1838 if (MaybeTermLoc->second)
1839 DefLoc = MemoryLocation(getUnderlyingObject(DefLoc.Ptr));
1840 return BatchAA.isMustAlias(MaybeTermLoc->first, DefLoc);
1841 }
1842
1843 // Returns true if \p Use may read from \p DefLoc.
1844 bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) {
1845 // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1846 // treated as read clobber.
1847 if (auto SI = dyn_cast<StoreInst>(UseInst))
1848 return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
1849
1850 if (!UseInst->mayReadFromMemory())
1851 return false;
1852
1853 if (auto *CB = dyn_cast<CallBase>(UseInst))
1854 if (CB->onlyAccessesInaccessibleMemory())
1855 return false;
1856
1857 // NOTE: For calls, the number of stores removed could be slightly improved
1858 // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
1859 // be expensive compared to the benefits in practice. For now, avoid more
1860 // expensive analysis to limit compile-time.
1861 return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
1862 }
1863
1864 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1865 /// loop. In particular, this guarantees that it only references a single
1866 /// MemoryLocation during execution of the containing function.
1867 bool IsGuaranteedLoopInvariant(Value *Ptr) {
1868 auto IsGuaranteedLoopInvariantBase = [this](Value *Ptr) {
1869 Ptr = Ptr->stripPointerCasts();
1870 if (auto *I = dyn_cast<Instruction>(Ptr)) {
1871 if (isa<AllocaInst>(Ptr))
1872 return true;
1873
1874 if (isAllocLikeFn(I, &TLI))
1875 return true;
1876
1877 return false;
1878 }
1879 return true;
1880 };
1881
1882 Ptr = Ptr->stripPointerCasts();
1883 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
1884 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
1885 GEP->hasAllConstantIndices();
1886 }
1887 return IsGuaranteedLoopInvariantBase(Ptr);
1888 }
1889
1890 // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
1891 // no read access between them or on any other path to a function exit block
1892 // if \p DefLoc is not accessible after the function returns. If there is no
1893 // such MemoryDef, return None. The returned value may not (completely)
1894 // overwrite \p DefLoc. Currently we bail out when we encounter an aliasing
1895 // MemoryUse (read).
1896 Optional<MemoryAccess *>
1897 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1898 MemoryLocation DefLoc, const Value *DefUO, CheckCache &Cache,
1899 unsigned &ScanLimit, unsigned &WalkerStepLimit,
1900 bool IsMemTerm, unsigned &PartialLimit) {
1901 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1902 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
1903 return None;
1904 }
1905
1906 MemoryAccess *Current = StartAccess;
1907 Instruction *KillingI = KillingDef->getMemoryInst();
1908 bool StepAgain;
1909 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)
;
1910
1911 // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1912 do {
1913 StepAgain = false;
1914 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)
1915 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)
1916 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)
1917 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)
1918 << ")";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)
1919 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)
1920 })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)
;
1921
1922 // Reached TOP.
1923 if (MSSA.isLiveOnEntryDef(Current)) {
1924 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found LiveOnEntryDef\n"; }
} while (false)
;
1925 return None;
1926 }
1927
1928 // Cost of a step. Accesses in the same block are more likely to be valid
1929 // candidates for elimination, hence consider them cheaper.
1930 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1931 ? MemorySSASameBBStepCost
1932 : MemorySSAOtherBBStepCost;
1933 if (WalkerStepLimit <= StepCost) {
1934 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit walker step limit\n";
} } while (false)
;
1935 return None;
1936 }
1937 WalkerStepLimit -= StepCost;
1938
1939 // Return for MemoryPhis. They cannot be eliminated directly and the
1940 // caller is responsible for traversing them.
1941 if (isa<MemoryPhi>(Current)) {
1942 LLVM_DEBUG(dbgs() << " ... found MemoryPhi\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found MemoryPhi\n"; } } while
(false)
;
1943 return Current;
1944 }
1945
1946 // Below, check if CurrentDef is a valid candidate to be eliminated by
1947 // KillingDef. If it is not, check the next candidate.
1948 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1949 Instruction *CurrentI = CurrentDef->getMemoryInst();
1950
1951 if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO))) {
1952 StepAgain = true;
1953 Current = CurrentDef->getDefiningAccess();
1954 continue;
1955 }
1956
1957 // Before we try to remove anything, check for any extra throwing
1958 // instructions that block us from DSEing
1959 if (mayThrowBetween(KillingI, CurrentI, DefUO)) {
1960 LLVM_DEBUG(dbgs() << " ... skip, may throw!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, may throw!\n"; } } while
(false)
;
1961 return None;
1962 }
1963
1964 // Check for anything that looks like it will be a barrier to further
1965 // removal
1966 if (isDSEBarrier(DefUO, CurrentI)) {
1967 LLVM_DEBUG(dbgs() << " ... skip, barrier\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, barrier\n"; } } while
(false)
;
1968 return None;
1969 }
1970
1971 // If Current is known to be on path that reads DefLoc or is a read
1972 // clobber, bail out, as the path is not profitable. We skip this check
1973 // for intrinsic calls, because the code knows how to handle memcpy
1974 // intrinsics.
1975 if (!isa<IntrinsicInst>(CurrentI) &&
1976 (Cache.KnownReads.contains(Current) ||
1977 isReadClobber(DefLoc, CurrentI))) {
1978 Cache.KnownReads.insert(Current);
1979 return None;
1980 }
1981
1982 // Quick check if there are direct uses that are read-clobbers.
1983 if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {
1984 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1985 return !MSSA.dominates(StartAccess, UseOrDef) &&
1986 isReadClobber(DefLoc, UseOrDef->getMemoryInst());
1987 return false;
1988 })) {
1989 Cache.KnownReads.insert(Current);
1990 LLVM_DEBUG(dbgs() << " ... found a read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found a read clobber\n"; }
} while (false)
;
1991 return None;
1992 }
1993
1994 // If Current cannot be analyzed or is not removable, check the next
1995 // candidate.
1996 if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI)) {
1997 StepAgain = true;
1998 Current = CurrentDef->getDefiningAccess();
1999 continue;
2000 }
2001
2002 // If Current does not have an analyzable write location, skip it
2003 auto CurrentLoc = getLocForWriteEx(CurrentI);
2004 if (!CurrentLoc) {
2005 StepAgain = true;
2006 Current = CurrentDef->getDefiningAccess();
2007 continue;
2008 }
2009
2010 if (IsMemTerm) {
2011 // If the killing def is a memory terminator (e.g. lifetime.end), check
2012 // the next candidate if the current Current does not write the same
2013 // underlying object as the terminator.
2014 const Value *NIUnd = getUnderlyingObject(CurrentLoc->Ptr);
2015 if (DefUO != NIUnd) {
2016 StepAgain = true;
2017 Current = CurrentDef->getDefiningAccess();
2018 }
2019 continue;
2020 } else {
2021 // AliasAnalysis does not account for loops. Limit elimination to
2022 // candidates for which we can guarantee they always store to the same
2023 // memory location and not multiple locations in a loop.
2024 if (Current->getBlock() != KillingDef->getBlock() &&
2025 !IsGuaranteedLoopInvariant(const_cast<Value *>(CurrentLoc->Ptr))) {
2026 StepAgain = true;
2027 Current = CurrentDef->getDefiningAccess();
2028 WalkerStepLimit -= 1;
2029 continue;
2030 }
2031
2032 int64_t InstWriteOffset, DepWriteOffset;
2033 auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
2034 DepWriteOffset, InstWriteOffset, BatchAA, &F);
2035 // If Current does not write to the same object as KillingDef, check
2036 // the next candidate.
2037 if (OR == OW_Unknown) {
2038 StepAgain = true;
2039 Current = CurrentDef->getDefiningAccess();
2040 } else if (OR == OW_MaybePartial) {
2041 // If KillingDef only partially overwrites Current, check the next
2042 // candidate if the partial step limit is exceeded. This aggressively
2043 // limits the number of candidates for partial store elimination,
2044 // which are less likely to be removable in the end.
2045 if (PartialLimit <= 1) {
2046 StepAgain = true;
2047 Current = CurrentDef->getDefiningAccess();
2048 WalkerStepLimit -= 1;
2049 continue;
2050 }
2051 PartialLimit -= 1;
2052 }
2053 }
2054 } while (StepAgain);
2055
2056 // Accesses to objects accessible after the function returns can only be
2057 // eliminated if the access is killed along all paths to the exit. Collect
2058 // the blocks with killing (=completely overwriting MemoryDefs) and check if
2059 // they cover all paths from EarlierAccess to any function exit.
2060 SmallPtrSet<Instruction *, 16> KillingDefs;
2061 KillingDefs.insert(KillingDef->getMemoryInst());
2062 MemoryAccess *EarlierAccess = Current;
2063 Instruction *EarlierMemInst =
2064 cast<MemoryDef>(EarlierAccess)->getMemoryInst();
2065 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)
2066 << *EarlierMemInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*EarlierAccess << " (" << *EarlierMemInst <<
")\n"; } } while (false)
;
2067
2068 SmallSetVector<MemoryAccess *, 32> WorkList;
2069 auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
2070 for (Use &U : Acc->uses())
2071 WorkList.insert(cast<MemoryAccess>(U.getUser()));
2072 };
2073 PushMemUses(EarlierAccess);
2074
2075 // Optimistically collect all accesses for reads. If we do not find any
2076 // read clobbers, add them to the cache.
2077 SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
2078 if (!EarlierMemInst->mayReadFromMemory())
2079 KnownNoReads.insert(EarlierAccess);
2080 // Check if EarlierDef may be read.
2081 for (unsigned I = 0; I < WorkList.size(); I++) {
2082 MemoryAccess *UseAccess = WorkList[I];
2083
2084 LLVM_DEBUG(dbgs() << " " << *UseAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " " << *UseAccess; } } while
(false)
;
2085 // Bail out if the number of accesses to check exceeds the scan limit.
2086 if (ScanLimit < (WorkList.size() - I)) {
2087 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
2088 return None;
2089 }
2090 --ScanLimit;
2091 NumDomMemDefChecks++;
2092
2093 // Check if we already visited this access.
2094 if (Cache.isKnownNoRead(UseAccess)) {
2095 LLVM_DEBUG(dbgs() << " ... skip, discovered that " << *UseAccessdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, discovered that " <<
*UseAccess << " is safe earlier.\n"; } } while (false)
2096 << " is safe earlier.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, discovered that " <<
*UseAccess << " is safe earlier.\n"; } } while (false)
;
2097 continue;
2098 }
2099 if (Cache.isKnownRead(UseAccess)) {
2100 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)
2101 << " 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)
;
2102 return None;
2103 }
2104 KnownNoReads.insert(UseAccess);
2105
2106 if (isa<MemoryPhi>(UseAccess)) {
2107 if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
2108 return DT.properlyDominates(KI->getParent(),
2109 UseAccess->getBlock());
2110 })) {
2111 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)
;
2112 continue;
2113 }
2114 LLVM_DEBUG(dbgs() << "\n ... adding PHI uses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... adding PHI uses\n"; } }
while (false)
;
2115 PushMemUses(UseAccess);
2116 continue;
2117 }
2118
2119 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
2120 LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *UseInst << ")\n"
; } } while (false)
;
2121
2122 if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {
2123 return DT.dominates(KI, UseInst);
2124 })) {
2125 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)
;
2126 continue;
2127 }
2128
2129 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess))) {
2130 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... adding uses of intrinsic\n"
; } } while (false)
;
2131 PushMemUses(UseAccess);
2132 continue;
2133 }
2134
2135 // A memory terminator kills all preceeding MemoryDefs and all succeeding
2136 // MemoryAccesses. We do not have to check it's users.
2137 if (isMemTerminator(DefLoc, UseInst))
2138 continue;
2139
2140 if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
2141 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found throwing instruction\n"
; } } while (false)
;
2142 Cache.KnownReads.insert(UseAccess);
2143 Cache.KnownReads.insert(StartAccess);
2144 Cache.KnownReads.insert(EarlierAccess);
2145 return None;
2146 }
2147
2148 // Uses which may read the original MemoryDef mean we cannot eliminate the
2149 // original MD. Stop walk.
2150 if (isReadClobber(DefLoc, UseInst)) {
2151 LLVM_DEBUG(dbgs() << " ... found read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found read clobber\n"; } }
while (false)
;
2152 Cache.KnownReads.insert(UseAccess);
2153 Cache.KnownReads.insert(StartAccess);
2154 Cache.KnownReads.insert(EarlierAccess);
2155 return None;
2156 }
2157
2158 // For the KillingDef and EarlierAccess we only have to check if it reads
2159 // the memory location.
2160 // TODO: It would probably be better to check for self-reads before
2161 // calling the function.
2162 if (KillingDef == UseAccess || EarlierAccess == UseAccess) {
2163 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)
;
2164 continue;
2165 }
2166
2167 // Check all uses for MemoryDefs, except for defs completely overwriting
2168 // the original location. Otherwise we have to check uses of *all*
2169 // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
2170 // miss cases like the following
2171 // 1 = Def(LoE) ; <----- EarlierDef stores [0,1]
2172 // 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
2173 // Use(2) ; MayAlias 2 *and* 1, loads [0, 3].
2174 // (The Use points to the *first* Def it may alias)
2175 // 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
2176 // stores [0,1]
2177 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
2178 if (isCompleteOverwrite(DefLoc, KillingI, UseInst)) {
2179 if (!isInvisibleToCallerAfterRet(DefUO) &&
2180 UseAccess != EarlierAccess) {
2181 BasicBlock *MaybeKillingBlock = UseInst->getParent();
2182 if (PostOrderNumbers.find(MaybeKillingBlock)->second <
2183 PostOrderNumbers.find(EarlierAccess->getBlock())->second) {
2184
2185 LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
2186 << " ... found killing def " << *UseInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
;
2187 KillingDefs.insert(UseInst);
2188 }
2189 }
2190 } else
2191 PushMemUses(UseDef);
2192 }
2193 }
2194
2195 // For accesses to locations visible after the function returns, make sure
2196 // that the location is killed (=overwritten) along all paths from
2197 // EarlierAccess to the exit.
2198 if (!isInvisibleToCallerAfterRet(DefUO)) {
2199 SmallPtrSet<BasicBlock *, 16> KillingBlocks;
2200 for (Instruction *KD : KillingDefs)
2201 KillingBlocks.insert(KD->getParent());
2202 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~++20200917111122+b03c2b8395b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2203, __PRETTY_FUNCTION__))
2203 "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~++20200917111122+b03c2b8395b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2203, __PRETTY_FUNCTION__))
;
2204
2205 // Find the common post-dominator of all killing blocks.
2206 BasicBlock *CommonPred = *KillingBlocks.begin();
2207 for (auto I = std::next(KillingBlocks.begin()), E = KillingBlocks.end();
2208 I != E; I++) {
2209 if (!CommonPred)
2210 break;
2211 CommonPred = PDT.findNearestCommonDominator(CommonPred, *I);
2212 }
2213
2214 // If CommonPred is in the set of killing blocks, just check if it
2215 // post-dominates EarlierAccess.
2216 if (KillingBlocks.count(CommonPred)) {
2217 if (PDT.dominates(CommonPred, EarlierAccess->getBlock()))
2218 return {EarlierAccess};
2219 return None;
2220 }
2221
2222 // If the common post-dominator does not post-dominate EarlierAccess,
2223 // there is a path from EarlierAccess to an exit not going through a
2224 // killing block.
2225 if (PDT.dominates(CommonPred, EarlierAccess->getBlock())) {
2226 SetVector<BasicBlock *> WorkList;
2227
2228 // If CommonPred is null, there are multiple exits from the function.
2229 // They all have to be added to the worklist.
2230 if (CommonPred)
2231 WorkList.insert(CommonPred);
2232 else
2233 for (BasicBlock *R : PDT.roots())
2234 WorkList.insert(R);
2235
2236 NumCFGTries++;
2237 // Check if all paths starting from an exit node go through one of the
2238 // killing blocks before reaching EarlierAccess.
2239 for (unsigned I = 0; I < WorkList.size(); I++) {
2240 NumCFGChecks++;
2241 BasicBlock *Current = WorkList[I];
2242 if (KillingBlocks.count(Current))
2243 continue;
2244 if (Current == EarlierAccess->getBlock())
2245 return None;
2246
2247 // EarlierAccess is reachable from the entry, so we don't have to
2248 // explore unreachable blocks further.
2249 if (!DT.isReachableFromEntry(Current))
2250 continue;
2251
2252 for (BasicBlock *Pred : predecessors(Current))
2253 WorkList.insert(Pred);
2254
2255 if (WorkList.size() >= MemorySSAPathCheckLimit)
2256 return None;
2257 }
2258 NumCFGSuccess++;
2259 return {EarlierAccess};
2260 }
2261 return None;
2262 }
2263
2264 // No aliasing MemoryUses of EarlierAccess found, EarlierAccess is
2265 // potentially dead.
2266 Cache.KnownNoReads.insert(KnownNoReads.begin(), KnownNoReads.end());
2267 return {EarlierAccess};
2268 }
2269
2270 // Delete dead memory defs
2271 void deleteDeadInstruction(Instruction *SI) {
2272 MemorySSAUpdater Updater(&MSSA);
2273 SmallVector<Instruction *, 32> NowDeadInsts;
2274 NowDeadInsts.push_back(SI);
2275 --NumFastOther;
2276
2277 while (!NowDeadInsts.empty()) {
2278 Instruction *DeadInst = NowDeadInsts.pop_back_val();
2279 ++NumFastOther;
2280
2281 // Try to preserve debug information attached to the dead instruction.
2282 salvageDebugInfo(*DeadInst);
2283 salvageKnowledge(DeadInst);
2284
2285 // Remove the Instruction from MSSA.
2286 if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
2287 if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
2288 SkipStores.insert(MD);
2289 }
2290 Updater.removeMemoryAccess(MA);
2291 }
2292
2293 auto I = IOLs.find(DeadInst->getParent());
2294 if (I != IOLs.end())
2295 I->second.erase(DeadInst);
2296 // Remove its operands
2297 for (Use &O : DeadInst->operands())
2298 if (Instruction *OpI = dyn_cast<Instruction>(O)) {
2299 O = nullptr;
2300 if (isInstructionTriviallyDead(OpI, &TLI))
2301 NowDeadInsts.push_back(OpI);
2302 }
2303
2304 DeadInst->eraseFromParent();
2305 }
2306 }
2307
2308 // Check for any extra throws between SI and NI that block DSE. This only
2309 // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
2310 // throw are handled during the walk from one def to the next.
2311 bool mayThrowBetween(Instruction *SI, Instruction *NI,
2312 const Value *SILocUnd) {
2313 // First see if we can ignore it by using the fact that SI is an
2314 // alloca/alloca like object that is not visible to the caller during
2315 // execution of the function.
2316 if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd))
2317 return false;
2318
2319 if (SI->getParent() == NI->getParent())
2320 return ThrowingBlocks.count(SI->getParent());
2321 return !ThrowingBlocks.empty();
2322 }
2323
2324 // Check if \p NI acts as a DSE barrier for \p SI. The following instructions
2325 // act as barriers:
2326 // * A memory instruction that may throw and \p SI accesses a non-stack
2327 // object.
2328 // * Atomic stores stronger that monotonic.
2329 bool isDSEBarrier(const Value *SILocUnd, Instruction *NI) {
2330 // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
2331 // like object that does not escape.
2332 if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd))
2333 return true;
2334
2335 // If NI is an atomic load/store stronger than monotonic, do not try to
2336 // eliminate/reorder it.
2337 if (NI->isAtomic()) {
2338 if (auto *LI = dyn_cast<LoadInst>(NI))
2339 return isStrongerThanMonotonic(LI->getOrdering());
2340 if (auto *SI = dyn_cast<StoreInst>(NI))
2341 return isStrongerThanMonotonic(SI->getOrdering());
2342 if (auto *ARMW = dyn_cast<AtomicRMWInst>(NI))
2343 return isStrongerThanMonotonic(ARMW->getOrdering());
2344 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(NI))
2345 return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
2346 isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
2347 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~++20200917111122+b03c2b8395b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2347)
;
2348 }
2349 return false;
2350 }
2351
2352 /// Eliminate writes to objects that are not visible in the caller and are not
2353 /// accessed before returning from the function.
2354 bool eliminateDeadWritesAtEndOfFunction() {
2355 bool MadeChange = false;
2356 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2357 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2358 << "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)
;
2359 for (int I = MemDefs.size() - 1; I >= 0; I--) {
2360 MemoryDef *Def = MemDefs[I];
2361 if (SkipStores.find(Def) != SkipStores.end() ||
2362 !isRemovable(Def->getMemoryInst()))
2363 continue;
2364
2365 Instruction *DefI = Def->getMemoryInst();
2366 SmallVector<const Value *, 4> Pointers;
2367 auto DefLoc = getLocForWriteEx(DefI);
2368 if (!DefLoc)
2369 continue;
2370
2371 // NOTE: Currently eliminating writes at the end of a function is limited
2372 // to MemoryDefs with a single underlying object, to save compile-time. In
2373 // practice it appears the case with multiple underlying objects is very
2374 // uncommon. If it turns out to be important, we can use
2375 // getUnderlyingObjects here instead.
2376 const Value *UO = getUnderlyingObject(DefLoc->Ptr);
2377 if (!UO || !isInvisibleToCallerAfterRet(UO))
2378 continue;
2379
2380 if (isWriteAtEndOfFunction(Def)) {
2381 // See through pointer-to-pointer bitcasts
2382 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)
2383 "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)
;
2384 deleteDeadInstruction(DefI);
2385 ++NumFastStores;
2386 MadeChange = true;
2387 }
2388 }
2389 return MadeChange;
2390 }
2391
2392 /// \returns true if \p Def is a no-op store, either because it
2393 /// directly stores back a loaded value or stores zero to a calloced object.
2394 bool storeIsNoop(MemoryDef *Def, MemoryLocation DefLoc, const Value *DefUO) {
2395 StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
2396 if (!Store)
2397 return false;
2398
2399 if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
2400 if (LoadI->getPointerOperand() == Store->getOperand(1)) {
2401 auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
2402 // If both accesses share the same defining access, no instructions
2403 // between them can modify the memory location.
2404 return LoadAccess == Def->getDefiningAccess();
2405 }
2406 }
2407
2408 Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
2409 if (StoredConstant && StoredConstant->isNullValue()) {
2410 auto *DefUOInst = dyn_cast<Instruction>(DefUO);
2411 if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
2412 auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
2413 // If UnderlyingDef is the clobbering access of Def, no instructions
2414 // between them can modify the memory location.
2415 auto *ClobberDef =
2416 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
2417 return UnderlyingDef == ClobberDef;
2418 }
2419 }
2420 return false;
2421 }
2422};
2423
2424bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
2425 MemorySSA &MSSA, DominatorTree &DT,
2426 PostDominatorTree &PDT,
2427 const TargetLibraryInfo &TLI) {
2428 bool MadeChange = false;
2429
2430 DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
2431 // For each store:
2432 for (unsigned I = 0; I < State.MemDefs.size(); I++) {
2433 MemoryDef *KillingDef = State.MemDefs[I];
2434 if (State.SkipStores.count(KillingDef))
2435 continue;
2436 Instruction *SI = KillingDef->getMemoryInst();
2437
2438 auto MaybeSILoc = State.getLocForWriteEx(SI);
2439 if (State.isMemTerminatorInst(SI))
2440 MaybeSILoc = State.getLocForTerminator(SI).map(
2441 [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
2442 else
2443 MaybeSILoc = State.getLocForWriteEx(SI);
2444
2445 if (!MaybeSILoc) {
2446 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)
2447 << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
<< *SI << "\n"; } } while (false)
;
2448 continue;
2449 }
2450 MemoryLocation SILoc = *MaybeSILoc;
2451 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~++20200917111122+b03c2b8395b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2451, __PRETTY_FUNCTION__))
;
2452 const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr);
2453
2454 // Check if the store is a no-op.
2455 if (isRemovable(SI) && State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
2456 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)
;
2457 State.deleteDeadInstruction(SI);
2458 NumRedundantStores++;
2459 MadeChange = true;
2460 continue;
2461 }
2462
2463 MemoryAccess *Current = KillingDef;
Value stored to 'Current' during its initialization is never read
2464 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)
2465 << *KillingDef << " (" << *SI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *SI << ")\n"
; } } while (false)
;
2466
2467 unsigned ScanLimit = MemorySSAScanLimit;
2468 unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
2469 unsigned PartialLimit = MemorySSAPartialStoreLimit;
2470 // Worklist of MemoryAccesses that may be killed by KillingDef.
2471 SetVector<MemoryAccess *> ToCheck;
2472 ToCheck.insert(KillingDef->getDefiningAccess());
2473
2474 if (!SILocUnd)
2475 continue;
2476 bool IsMemTerm = State.isMemTerminatorInst(SI);
2477 DSEState::CheckCache Cache;
2478 // Check if MemoryAccesses in the worklist are killed by KillingDef.
2479 for (unsigned I = 0; I < ToCheck.size(); I++) {
2480 Current = ToCheck[I];
2481 if (State.SkipStores.count(Current))
2482 continue;
2483
2484 Optional<MemoryAccess *> Next = State.getDomMemoryDef(
2485 KillingDef, Current, SILoc, SILocUnd, Cache, ScanLimit,
2486 WalkerStepLimit, IsMemTerm, PartialLimit);
2487
2488 if (!Next) {
2489 LLVM_DEBUG(dbgs() << " finished walk\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " finished walk\n"; } } while (false
)
;
2490 continue;
2491 }
2492
2493 MemoryAccess *EarlierAccess = *Next;
2494 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)
;
2495 if (isa<MemoryPhi>(EarlierAccess)) {
2496 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)
;
2497 for (Value *V : cast<MemoryPhi>(EarlierAccess)->incoming_values()) {
2498 MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
2499 BasicBlock *IncomingBlock = IncomingAccess->getBlock();
2500 BasicBlock *PhiBlock = EarlierAccess->getBlock();
2501
2502 // We only consider incoming MemoryAccesses that come before the
2503 // MemoryPhi. Otherwise we could discover candidates that do not
2504 // strictly dominate our starting def.
2505 if (State.PostOrderNumbers[IncomingBlock] >
2506 State.PostOrderNumbers[PhiBlock])
2507 ToCheck.insert(IncomingAccess);
2508 }
2509 continue;
2510 }
2511 MemoryDef *NextDef = dyn_cast<MemoryDef>(EarlierAccess);
2512 Instruction *NI = NextDef->getMemoryInst();
2513 LLVM_DEBUG(dbgs() << " (" << *NI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *NI << ")\n"; }
} while (false)
;
2514 ToCheck.insert(NextDef->getDefiningAccess());
2515 NumGetDomMemoryDefPassed++;
2516
2517 if (!DebugCounter::shouldExecute(MemorySSACounter))
2518 continue;
2519
2520 MemoryLocation NILoc = *State.getLocForWriteEx(NI);
2521
2522 if (IsMemTerm) {
2523 const Value *NIUnd = getUnderlyingObject(NILoc.Ptr);
2524 if (SILocUnd != NIUnd)
2525 continue;
2526 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)
2527 << "\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)
;
2528 State.deleteDeadInstruction(NI);
2529 ++NumFastStores;
2530 MadeChange = true;
2531 } else {
2532 // Check if NI overwrites SI.
2533 int64_t InstWriteOffset, DepWriteOffset;
2534 OverwriteResult OR =
2535 isOverwrite(SI, NI, SILoc, NILoc, State.DL, TLI, DepWriteOffset,
2536 InstWriteOffset, State.BatchAA, &F);
2537 if (OR == OW_MaybePartial) {
2538 auto Iter = State.IOLs.insert(
2539 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2540 NI->getParent(), InstOverlapIntervalsTy()));
2541 auto &IOL = Iter.first->second;
2542 OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
2543 NI, IOL);
2544 }
2545
2546 if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
2547 auto *Earlier = dyn_cast<StoreInst>(NI);
2548 auto *Later = dyn_cast<StoreInst>(SI);
2549 // We are re-using tryToMergePartialOverlappingStores, which requires
2550 // Earlier to domiante Later.
2551 // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2552 if (Earlier && Later && DT.dominates(Earlier, Later)) {
2553 if (Constant *Merged = tryToMergePartialOverlappingStores(
2554 Earlier, Later, InstWriteOffset, DepWriteOffset, State.DL,
2555 State.BatchAA, &DT)) {
2556
2557 // Update stored value of earlier store to merged constant.
2558 Earlier->setOperand(0, Merged);
2559 ++NumModifiedStores;
2560 MadeChange = true;
2561
2562 // Remove later store and remove any outstanding overlap intervals
2563 // for the updated store.
2564 State.deleteDeadInstruction(Later);
2565 auto I = State.IOLs.find(Earlier->getParent());
2566 if (I != State.IOLs.end())
2567 I->second.erase(Earlier);
2568 break;
2569 }
2570 }
2571 }
2572
2573 if (OR == OW_Complete) {
2574 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)
2575 << "\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)
;
2576 State.deleteDeadInstruction(NI);
2577 ++NumFastStores;
2578 MadeChange = true;
2579 }
2580 }
2581 }
2582 }
2583
2584 if (EnablePartialOverwriteTracking)
2585 for (auto &KV : State.IOLs)
2586 MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
2587
2588 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2589 return MadeChange;
2590}
2591} // end anonymous namespace
2592
2593//===----------------------------------------------------------------------===//
2594// DSE Pass
2595//===----------------------------------------------------------------------===//
2596PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
2597 AliasAnalysis &AA = AM.getResult<AAManager>(F);
2598 const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2599 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
2600
2601 bool Changed = false;
2602 if (EnableMemorySSA) {
2603 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2604 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
2605
2606 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2607 } else {
2608 MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
2609
2610 Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
2611 }
2612
2613#ifdef LLVM_ENABLE_STATS1
2614 if (AreStatisticsEnabled())
2615 for (auto &I : instructions(F))
2616 NumRemainingStores += isa<StoreInst>(&I);
2617#endif
2618
2619 if (!Changed)
2620 return PreservedAnalyses::all();
2621
2622 PreservedAnalyses PA;
2623 PA.preserveSet<CFGAnalyses>();
2624 PA.preserve<GlobalsAA>();
2625 if (EnableMemorySSA)
2626 PA.preserve<MemorySSAAnalysis>();
2627 else
2628 PA.preserve<MemoryDependenceAnalysis>();
2629 return PA;
2630}
2631
2632namespace {
2633
2634/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
2635class DSELegacyPass : public FunctionPass {
2636public:
2637 static char ID; // Pass identification, replacement for typeid
2638
2639 DSELegacyPass() : FunctionPass(ID) {
2640 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
2641 }
2642
2643 bool runOnFunction(Function &F) override {
2644 if (skipFunction(F))
2645 return false;
2646
2647 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2648 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2649 const TargetLibraryInfo &TLI =
2650 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2651
2652 bool Changed = false;
2653 if (EnableMemorySSA) {
2654 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2655 PostDominatorTree &PDT =
2656 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2657
2658 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2659 } else {
2660 MemoryDependenceResults &MD =
2661 getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
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 return Changed;
2673 }
2674
2675 void getAnalysisUsage(AnalysisUsage &AU) const override {
2676 AU.setPreservesCFG();
2677 AU.addRequired<AAResultsWrapperPass>();
2678 AU.addRequired<TargetLibraryInfoWrapperPass>();
2679 AU.addPreserved<GlobalsAAWrapperPass>();
2680 AU.addRequired<DominatorTreeWrapperPass>();
2681 AU.addPreserved<DominatorTreeWrapperPass>();
2682
2683 if (EnableMemorySSA) {
2684 AU.addRequired<PostDominatorTreeWrapperPass>();
2685 AU.addRequired<MemorySSAWrapperPass>();
2686 AU.addPreserved<PostDominatorTreeWrapperPass>();
2687 AU.addPreserved<MemorySSAWrapperPass>();
2688 } else {
2689 AU.addRequired<MemoryDependenceWrapperPass>();
2690 AU.addPreserved<MemoryDependenceWrapperPass>();
2691 }
2692 }
2693};
2694
2695} // end anonymous namespace
2696
2697char DSELegacyPass::ID = 0;
2698
2699INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2700 false)static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2701INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2702INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
2703INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
2704INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
2705INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
2706INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
2707INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2708INITIALIZE_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)); }
2709 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)); }
2710
2711FunctionPass *llvm::createDeadStoreEliminationPass() {
2712 return new DSELegacyPass();
2713}