Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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