Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeadStoreElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-12/lib/clang/12.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/build-llvm/include -I /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac=. -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-24-172238-38865-1 -x c++ /build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/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), LocationSize::unknown());
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), LocationSize::unknown());
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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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~++20201124111112+7b5254223ac/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 LocationSize::unknown());
833 SmallVector<BasicBlock *, 16> Blocks;
834 Blocks.push_back(F->getParent());
835
836 while (!Blocks.empty()) {
837 BasicBlock *BB = Blocks.pop_back_val();
838 Instruction *InstPt = BB->getTerminator();
839 if (BB == F->getParent()) InstPt = F;
840
841 MemDepResult Dep =
842 MD->getPointerDependencyFrom(Loc, false, InstPt->getIterator(), BB);
843 while (Dep.isDef() || Dep.isClobber()) {
844 Instruction *Dependency = Dep.getInst();
845 if (!hasAnalyzableMemoryWrite(Dependency, *TLI) ||
846 !isRemovable(Dependency))
847 break;
848
849 Value *DepPointer =
850 getUnderlyingObject(getStoredPointerOperand(Dependency, *TLI));
851
852 // Check for aliasing.
853 if (!AA->isMustAlias(F->getArgOperand(0), DepPointer))
854 break;
855
856 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)
857 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)
858 << *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)
;
859
860 // DCE instructions only used to calculate that store.
861 BasicBlock::iterator BBI(Dependency);
862 deleteDeadInstruction(Dependency, &BBI, *MD, *TLI, IOL,
863 ThrowableInst);
864 ++NumFastStores;
865 MadeChange = true;
866
867 // Inst's old Dependency is now deleted. Compute the next dependency,
868 // which may also be dead, as in
869 // s[0] = 0;
870 // s[1] = 0; // This has just been deleted.
871 // free(s);
872 Dep = MD->getPointerDependencyFrom(Loc, false, BBI, BB);
873 }
874
875 if (Dep.isNonLocal())
876 findUnconditionalPreds(Blocks, BB, DT);
877 }
878
879 return MadeChange;
880}
881
882/// Check to see if the specified location may alias any of the stack objects in
883/// the DeadStackObjects set. If so, they become live because the location is
884/// being loaded.
885static void removeAccessedObjects(const MemoryLocation &LoadedLoc,
886 SmallSetVector<const Value *, 16> &DeadStackObjects,
887 const DataLayout &DL, AliasAnalysis *AA,
888 const TargetLibraryInfo *TLI,
889 const Function *F) {
890 const Value *UnderlyingPointer = getUnderlyingObject(LoadedLoc.Ptr);
891
892 // A constant can't be in the dead pointer set.
893 if (isa<Constant>(UnderlyingPointer))
894 return;
895
896 // If the kill pointer can be easily reduced to an alloca, don't bother doing
897 // extraneous AA queries.
898 if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) {
899 DeadStackObjects.remove(UnderlyingPointer);
900 return;
901 }
902
903 // Remove objects that could alias LoadedLoc.
904 DeadStackObjects.remove_if([&](const Value *I) {
905 // See if the loaded location could alias the stack location.
906 MemoryLocation StackLoc(I, getPointerSize(I, DL, *TLI, F));
907 return !AA->isNoAlias(StackLoc, LoadedLoc);
908 });
909}
910
911/// Remove dead stores to stack-allocated locations in the function end block.
912/// Ex:
913/// %A = alloca i32
914/// ...
915/// store i32 1, i32* %A
916/// ret void
917static bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA,
918 MemoryDependenceResults *MD,
919 const TargetLibraryInfo *TLI,
920 InstOverlapIntervalsTy &IOL,
921 MapVector<Instruction *, bool> &ThrowableInst) {
922 bool MadeChange = false;
923
924 // Keep track of all of the stack objects that are dead at the end of the
925 // function.
926 SmallSetVector<const Value*, 16> DeadStackObjects;
927
928 // Find all of the alloca'd pointers in the entry block.
929 BasicBlock &Entry = BB.getParent()->front();
930 for (Instruction &I : Entry) {
931 if (isa<AllocaInst>(&I))
932 DeadStackObjects.insert(&I);
933
934 // Okay, so these are dead heap objects, but if the pointer never escapes
935 // then it's leaked by this function anyways.
936 else if (isAllocLikeFn(&I, TLI) && !PointerMayBeCaptured(&I, true, true))
937 DeadStackObjects.insert(&I);
938 }
939
940 // Treat byval or inalloca arguments the same, stores to them are dead at the
941 // end of the function.
942 for (Argument &AI : BB.getParent()->args())
943 if (AI.hasPassPointeeByValueCopyAttr())
944 DeadStackObjects.insert(&AI);
945
946 const DataLayout &DL = BB.getModule()->getDataLayout();
947
948 // Scan the basic block backwards
949 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
950 --BBI;
951
952 // If we find a store, check to see if it points into a dead stack value.
953 if (hasAnalyzableMemoryWrite(&*BBI, *TLI) && isRemovable(&*BBI)) {
954 // See through pointer-to-pointer bitcasts
955 SmallVector<const Value *, 4> Pointers;
956 getUnderlyingObjects(getStoredPointerOperand(&*BBI, *TLI), Pointers);
957
958 // Stores to stack values are valid candidates for removal.
959 bool AllDead = true;
960 for (const Value *Pointer : Pointers)
961 if (!DeadStackObjects.count(Pointer)) {
962 AllDead = false;
963 break;
964 }
965
966 if (AllDead) {
967 Instruction *Dead = &*BBI;
968
969 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)
970 << *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)
971 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)
972 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)
973 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)
974 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)
975 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)
976 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)
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 } 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)
979 << '\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)
;
980
981 // DCE instructions only used to calculate that store.
982 deleteDeadInstruction(Dead, &BBI, *MD, *TLI, IOL, ThrowableInst,
983 &DeadStackObjects);
984 ++NumFastStores;
985 MadeChange = true;
986 continue;
987 }
988 }
989
990 // Remove any dead non-memory-mutating instructions.
991 if (isInstructionTriviallyDead(&*BBI, TLI)) {
992 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)
993 << *&*BBI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Removing trivially dead instruction:\n DEAD: "
<< *&*BBI << '\n'; } } while (false)
;
994 deleteDeadInstruction(&*BBI, &BBI, *MD, *TLI, IOL, ThrowableInst,
995 &DeadStackObjects);
996 ++NumFastOther;
997 MadeChange = true;
998 continue;
999 }
1000
1001 if (isa<AllocaInst>(BBI)) {
1002 // Remove allocas from the list of dead stack objects; there can't be
1003 // any references before the definition.
1004 DeadStackObjects.remove(&*BBI);
1005 continue;
1006 }
1007
1008 if (auto *Call = dyn_cast<CallBase>(&*BBI)) {
1009 // Remove allocation function calls from the list of dead stack objects;
1010 // there can't be any references before the definition.
1011 if (isAllocLikeFn(&*BBI, TLI))
1012 DeadStackObjects.remove(&*BBI);
1013
1014 // If this call does not access memory, it can't be loading any of our
1015 // pointers.
1016 if (AA->doesNotAccessMemory(Call))
1017 continue;
1018
1019 // If the call might load from any of our allocas, then any store above
1020 // the call is live.
1021 DeadStackObjects.remove_if([&](const Value *I) {
1022 // See if the call site touches the value.
1023 return isRefSet(AA->getModRefInfo(
1024 Call, I, getPointerSize(I, DL, *TLI, BB.getParent())));
1025 });
1026
1027 // If all of the allocas were clobbered by the call then we're not going
1028 // to find anything else to process.
1029 if (DeadStackObjects.empty())
1030 break;
1031
1032 continue;
1033 }
1034
1035 // We can remove the dead stores, irrespective of the fence and its ordering
1036 // (release/acquire/seq_cst). Fences only constraints the ordering of
1037 // already visible stores, it does not make a store visible to other
1038 // threads. So, skipping over a fence does not change a store from being
1039 // dead.
1040 if (isa<FenceInst>(*BBI))
1041 continue;
1042
1043 MemoryLocation LoadedLoc;
1044
1045 // If we encounter a use of the pointer, it is no longer considered dead
1046 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
1047 if (!L->isUnordered()) // Be conservative with atomic/volatile load
1048 break;
1049 LoadedLoc = MemoryLocation::get(L);
1050 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
1051 LoadedLoc = MemoryLocation::get(V);
1052 } else if (!BBI->mayReadFromMemory()) {
1053 // Instruction doesn't read memory. Note that stores that weren't removed
1054 // above will hit this case.
1055 continue;
1056 } else {
1057 // Unknown inst; assume it clobbers everything.
1058 break;
1059 }
1060
1061 // Remove any allocas from the DeadPointer set that are loaded, as this
1062 // makes any stores above the access live.
1063 removeAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI, BB.getParent());
1064
1065 // If all of the allocas were clobbered by the access then we're not going
1066 // to find anything else to process.
1067 if (DeadStackObjects.empty())
1068 break;
1069 }
1070
1071 return MadeChange;
1072}
1073
1074static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierOffset,
1075 int64_t &EarlierSize, int64_t LaterOffset,
1076 int64_t LaterSize, bool IsOverwriteEnd) {
1077 // TODO: base this on the target vector size so that if the earlier
1078 // store was too small to get vector writes anyway then its likely
1079 // a good idea to shorten it
1080 // Power of 2 vector writes are probably always a bad idea to optimize
1081 // as any store/memset/memcpy is likely using vector instructions so
1082 // shortening it to not vector size is likely to be slower
1083 auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);
1084 unsigned EarlierWriteAlign = EarlierIntrinsic->getDestAlignment();
1085 if (!IsOverwriteEnd)
1086 LaterOffset = int64_t(LaterOffset + LaterSize);
1087
1088 if (!(isPowerOf2_64(LaterOffset) && EarlierWriteAlign <= LaterOffset) &&
1089 !((EarlierWriteAlign != 0) && LaterOffset % EarlierWriteAlign == 0))
1090 return false;
1091
1092 int64_t NewLength = IsOverwriteEnd
1093 ? LaterOffset - EarlierOffset
1094 : EarlierSize - (LaterOffset - EarlierOffset);
1095
1096 if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {
1097 // When shortening an atomic memory intrinsic, the newly shortened
1098 // length must remain an integer multiple of the element size.
1099 const uint32_t ElementSize = AMI->getElementSizeInBytes();
1100 if (0 != NewLength % ElementSize)
1101 return false;
1102 }
1103
1104 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)
1105 << (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)
1106 << *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)
1107 << ", " << 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)
;
1108
1109 Value *EarlierWriteLength = EarlierIntrinsic->getLength();
1110 Value *TrimmedLength =
1111 ConstantInt::get(EarlierWriteLength->getType(), NewLength);
1112 EarlierIntrinsic->setLength(TrimmedLength);
1113
1114 EarlierSize = NewLength;
1115 if (!IsOverwriteEnd) {
1116 int64_t OffsetMoved = (LaterOffset - EarlierOffset);
1117 Value *Indices[1] = {
1118 ConstantInt::get(EarlierWriteLength->getType(), OffsetMoved)};
1119 GetElementPtrInst *NewDestGEP = GetElementPtrInst::CreateInBounds(
1120 EarlierIntrinsic->getRawDest()->getType()->getPointerElementType(),
1121 EarlierIntrinsic->getRawDest(), Indices, "", EarlierWrite);
1122 NewDestGEP->setDebugLoc(EarlierIntrinsic->getDebugLoc());
1123 EarlierIntrinsic->setDest(NewDestGEP);
1124 EarlierOffset = EarlierOffset + OffsetMoved;
1125 }
1126 return true;
1127}
1128
1129static bool tryToShortenEnd(Instruction *EarlierWrite,
1130 OverlapIntervalsTy &IntervalMap,
1131 int64_t &EarlierStart, int64_t &EarlierSize) {
1132 if (IntervalMap.empty() || !isShortenableAtTheEnd(EarlierWrite))
1133 return false;
1134
1135 OverlapIntervalsTy::iterator OII = --IntervalMap.end();
1136 int64_t LaterStart = OII->second;
1137 int64_t LaterSize = OII->first - LaterStart;
1138
1139 if (LaterStart > EarlierStart && LaterStart < EarlierStart + EarlierSize &&
1140 LaterStart + LaterSize >= EarlierStart + EarlierSize) {
1141 if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
1142 LaterSize, true)) {
1143 IntervalMap.erase(OII);
1144 return true;
1145 }
1146 }
1147 return false;
1148}
1149
1150static bool tryToShortenBegin(Instruction *EarlierWrite,
1151 OverlapIntervalsTy &IntervalMap,
1152 int64_t &EarlierStart, int64_t &EarlierSize) {
1153 if (IntervalMap.empty() || !isShortenableAtTheBeginning(EarlierWrite))
1154 return false;
1155
1156 OverlapIntervalsTy::iterator OII = IntervalMap.begin();
1157 int64_t LaterStart = OII->second;
1158 int64_t LaterSize = OII->first - LaterStart;
1159
1160 if (LaterStart <= EarlierStart && LaterStart + LaterSize > EarlierStart) {
1161 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1162, __PRETTY_FUNCTION__))
1162 "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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1162, __PRETTY_FUNCTION__))
;
1163 if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,
1164 LaterSize, false)) {
1165 IntervalMap.erase(OII);
1166 return true;
1167 }
1168 }
1169 return false;
1170}
1171
1172static bool removePartiallyOverlappedStores(const DataLayout &DL,
1173 InstOverlapIntervalsTy &IOL,
1174 const TargetLibraryInfo &TLI) {
1175 bool Changed = false;
1176 for (auto OI : IOL) {
1177 Instruction *EarlierWrite = OI.first;
1178 MemoryLocation Loc = getLocForWrite(EarlierWrite, TLI);
1179 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1179, __PRETTY_FUNCTION__))
;
1180
1181 const Value *Ptr = Loc.Ptr->stripPointerCasts();
1182 int64_t EarlierStart = 0;
1183 int64_t EarlierSize = int64_t(Loc.Size.getValue());
1184 GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);
1185 OverlapIntervalsTy &IntervalMap = OI.second;
1186 Changed |=
1187 tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1188 if (IntervalMap.empty())
1189 continue;
1190 Changed |=
1191 tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
1192 }
1193 return Changed;
1194}
1195
1196static bool eliminateNoopStore(Instruction *Inst, BasicBlock::iterator &BBI,
1197 AliasAnalysis *AA, MemoryDependenceResults *MD,
1198 const DataLayout &DL,
1199 const TargetLibraryInfo *TLI,
1200 InstOverlapIntervalsTy &IOL,
1201 MapVector<Instruction *, bool> &ThrowableInst,
1202 DominatorTree *DT) {
1203 // Must be a store instruction.
1204 StoreInst *SI = dyn_cast<StoreInst>(Inst);
1205 if (!SI)
1206 return false;
1207
1208 // If we're storing the same value back to a pointer that we just loaded from,
1209 // then the store can be removed.
1210 if (LoadInst *DepLoad = dyn_cast<LoadInst>(SI->getValueOperand())) {
1211 if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
1212 isRemovable(SI) &&
1213 memoryIsNotModifiedBetween(DepLoad, SI, *AA, DL, DT)) {
1214
1215 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)
1216 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)
1217 << *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)
;
1218
1219 deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
1220 ++NumRedundantStores;
1221 return true;
1222 }
1223 }
1224
1225 // Remove null stores into the calloc'ed objects
1226 Constant *StoredConstant = dyn_cast<Constant>(SI->getValueOperand());
1227 if (StoredConstant && StoredConstant->isNullValue() && isRemovable(SI)) {
1228 Instruction *UnderlyingPointer =
1229 dyn_cast<Instruction>(getUnderlyingObject(SI->getPointerOperand()));
1230
1231 if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) &&
1232 memoryIsNotModifiedBetween(UnderlyingPointer, SI, *AA, DL, DT)) {
1233 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)
1234 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)
1235 << *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)
;
1236
1237 deleteDeadInstruction(SI, &BBI, *MD, *TLI, IOL, ThrowableInst);
1238 ++NumRedundantStores;
1239 return true;
1240 }
1241 }
1242 return false;
1243}
1244
1245template <typename AATy>
1246static Constant *tryToMergePartialOverlappingStores(
1247 StoreInst *Earlier, StoreInst *Later, int64_t InstWriteOffset,
1248 int64_t DepWriteOffset, const DataLayout &DL, AATy &AA, DominatorTree *DT) {
1249
1250 if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
1251 DL.typeSizeEqualsStoreSize(Earlier->getValueOperand()->getType()) &&
1252 Later && isa<ConstantInt>(Later->getValueOperand()) &&
1253 DL.typeSizeEqualsStoreSize(Later->getValueOperand()->getType()) &&
1254 memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {
1255 // If the store we find is:
1256 // a) partially overwritten by the store to 'Loc'
1257 // b) the later store is fully contained in the earlier one and
1258 // c) they both have a constant value
1259 // d) none of the two stores need padding
1260 // Merge the two stores, replacing the earlier store's value with a
1261 // merge of both values.
1262 // TODO: Deal with other constant types (vectors, etc), and probably
1263 // some mem intrinsics (if needed)
1264
1265 APInt EarlierValue =
1266 cast<ConstantInt>(Earlier->getValueOperand())->getValue();
1267 APInt LaterValue = cast<ConstantInt>(Later->getValueOperand())->getValue();
1268 unsigned LaterBits = LaterValue.getBitWidth();
1269 assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth())((EarlierValue.getBitWidth() > LaterValue.getBitWidth()) ?
static_cast<void> (0) : __assert_fail ("EarlierValue.getBitWidth() > LaterValue.getBitWidth()"
, "/build/llvm-toolchain-snapshot-12~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1269, __PRETTY_FUNCTION__))
;
1270 LaterValue = LaterValue.zext(EarlierValue.getBitWidth());
1271
1272 // Offset of the smaller store inside the larger store
1273 unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;
1274 unsigned LShiftAmount = DL.isBigEndian() ? EarlierValue.getBitWidth() -
1275 BitOffsetDiff - LaterBits
1276 : BitOffsetDiff;
1277 APInt Mask = APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,
1278 LShiftAmount + LaterBits);
1279 // Clear the bits we'll be replacing, then OR with the smaller
1280 // store, shifted appropriately.
1281 APInt Merged = (EarlierValue & ~Mask) | (LaterValue << LShiftAmount);
1282 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)
1283 << "\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)
1284 << "\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)
;
1285 return ConstantInt::get(Earlier->getValueOperand()->getType(), Merged);
1286 }
1287 return nullptr;
1288}
1289
1290static bool eliminateDeadStores(BasicBlock &BB, AliasAnalysis *AA,
1291 MemoryDependenceResults *MD, DominatorTree *DT,
1292 const TargetLibraryInfo *TLI) {
1293 const DataLayout &DL = BB.getModule()->getDataLayout();
1294 bool MadeChange = false;
1295
1296 MapVector<Instruction *, bool> ThrowableInst;
1297
1298 // A map of interval maps representing partially-overwritten value parts.
1299 InstOverlapIntervalsTy IOL;
1300
1301 // Do a top-down walk on the BB.
1302 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
1303 // Handle 'free' calls specially.
1304 if (CallInst *F = isFreeCall(&*BBI, TLI)) {
1305 MadeChange |= handleFree(F, AA, MD, DT, TLI, IOL, ThrowableInst);
1306 // Increment BBI after handleFree has potentially deleted instructions.
1307 // This ensures we maintain a valid iterator.
1308 ++BBI;
1309 continue;
1310 }
1311
1312 Instruction *Inst = &*BBI++;
1313
1314 if (Inst->mayThrow()) {
1315 ThrowableInst[Inst] = true;
1316 continue;
1317 }
1318
1319 // Check to see if Inst writes to memory. If not, continue.
1320 if (!hasAnalyzableMemoryWrite(Inst, *TLI))
1321 continue;
1322
1323 // eliminateNoopStore will update in iterator, if necessary.
1324 if (eliminateNoopStore(Inst, BBI, AA, MD, DL, TLI, IOL,
1325 ThrowableInst, DT)) {
1326 MadeChange = true;
1327 continue;
1328 }
1329
1330 // If we find something that writes memory, get its memory dependence.
1331 MemDepResult InstDep = MD->getDependency(Inst);
1332
1333 // Ignore any store where we can't find a local dependence.
1334 // FIXME: cross-block DSE would be fun. :)
1335 if (!InstDep.isDef() && !InstDep.isClobber())
1336 continue;
1337
1338 // Figure out what location is being stored to.
1339 MemoryLocation Loc = getLocForWrite(Inst, *TLI);
1340
1341 // If we didn't get a useful location, fail.
1342 if (!Loc.Ptr)
1343 continue;
1344
1345 // Loop until we find a store we can eliminate or a load that
1346 // invalidates the analysis. Without an upper bound on the number of
1347 // instructions examined, this analysis can become very time-consuming.
1348 // However, the potential gain diminishes as we process more instructions
1349 // without eliminating any of them. Therefore, we limit the number of
1350 // instructions we look at.
1351 auto Limit = MD->getDefaultBlockScanLimit();
1352 while (InstDep.isDef() || InstDep.isClobber()) {
1353 // Get the memory clobbered by the instruction we depend on. MemDep will
1354 // skip any instructions that 'Loc' clearly doesn't interact with. If we
1355 // end up depending on a may- or must-aliased load, then we can't optimize
1356 // away the store and we bail out. However, if we depend on something
1357 // that overwrites the memory location we *can* potentially optimize it.
1358 //
1359 // Find out what memory location the dependent instruction stores.
1360 Instruction *DepWrite = InstDep.getInst();
1361 if (!hasAnalyzableMemoryWrite(DepWrite, *TLI))
1362 break;
1363 MemoryLocation DepLoc = getLocForWrite(DepWrite, *TLI);
1364 // If we didn't get a useful location, or if it isn't a size, bail out.
1365 if (!DepLoc.Ptr)
1366 break;
1367
1368 // Find the last throwable instruction not removed by call to
1369 // deleteDeadInstruction.
1370 Instruction *LastThrowing = nullptr;
1371 if (!ThrowableInst.empty())
1372 LastThrowing = ThrowableInst.back().first;
1373
1374 // Make sure we don't look past a call which might throw. This is an
1375 // issue because MemoryDependenceAnalysis works in the wrong direction:
1376 // it finds instructions which dominate the current instruction, rather than
1377 // instructions which are post-dominated by the current instruction.
1378 //
1379 // If the underlying object is a non-escaping memory allocation, any store
1380 // to it is dead along the unwind edge. Otherwise, we need to preserve
1381 // the store.
1382 if (LastThrowing && DepWrite->comesBefore(LastThrowing)) {
1383 const Value *Underlying = getUnderlyingObject(DepLoc.Ptr);
1384 bool IsStoreDeadOnUnwind = isa<AllocaInst>(Underlying);
1385 if (!IsStoreDeadOnUnwind) {
1386 // We're looking for a call to an allocation function
1387 // where the allocation doesn't escape before the last
1388 // throwing instruction; PointerMayBeCaptured
1389 // reasonably fast approximation.
1390 IsStoreDeadOnUnwind = isAllocLikeFn(Underlying, TLI) &&
1391 !PointerMayBeCaptured(Underlying, false, true);
1392 }
1393 if (!IsStoreDeadOnUnwind)
1394 break;
1395 }
1396
1397 // If we find a write that is a) removable (i.e., non-volatile), b) is
1398 // completely obliterated by the store to 'Loc', and c) which we know that
1399 // 'Inst' doesn't load from, then we can remove it.
1400 // Also try to merge two stores if a later one only touches memory written
1401 // to by the earlier one.
1402 if (isRemovable(DepWrite) &&
1403 !isPossibleSelfRead(Inst, Loc, DepWrite, *TLI, *AA)) {
1404 int64_t InstWriteOffset, DepWriteOffset;
1405 OverwriteResult OR = isOverwrite(Inst, DepWrite, Loc, DepLoc, DL, *TLI,
1406 DepWriteOffset, InstWriteOffset, *AA,
1407 BB.getParent());
1408 if (OR == OW_MaybePartial)
1409 OR = isPartialOverwrite(Loc, DepLoc, DepWriteOffset, InstWriteOffset,
1410 DepWrite, IOL);
1411
1412 if (OR == OW_Complete) {
1413 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)
1414 << "\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)
;
1415
1416 // Delete the store and now-dead instructions that feed it.
1417 deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
1418 ThrowableInst);
1419 ++NumFastStores;
1420 MadeChange = true;
1421
1422 // We erased DepWrite; start over.
1423 InstDep = MD->getDependency(Inst);
1424 continue;
1425 } else if ((OR == OW_End && isShortenableAtTheEnd(DepWrite)) ||
1426 ((OR == OW_Begin &&
1427 isShortenableAtTheBeginning(DepWrite)))) {
1428 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1430, __PRETTY_FUNCTION__))
1429 "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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1430, __PRETTY_FUNCTION__))
1430 "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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1430, __PRETTY_FUNCTION__))
;
1431 // The overwrite result is known, so these must be known, too.
1432 int64_t EarlierSize = DepLoc.Size.getValue();
1433 int64_t LaterSize = Loc.Size.getValue();
1434 bool IsOverwriteEnd = (OR == OW_End);
1435 MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
1436 InstWriteOffset, LaterSize, IsOverwriteEnd);
1437 } else if (EnablePartialStoreMerging &&
1438 OR == OW_PartialEarlierWithFullLater) {
1439 auto *Earlier = dyn_cast<StoreInst>(DepWrite);
1440 auto *Later = dyn_cast<StoreInst>(Inst);
1441 if (Constant *C = tryToMergePartialOverlappingStores(
1442 Earlier, Later, InstWriteOffset, DepWriteOffset, DL, *AA,
1443 DT)) {
1444 auto *SI = new StoreInst(
1445 C, Earlier->getPointerOperand(), false, Earlier->getAlign(),
1446 Earlier->getOrdering(), Earlier->getSyncScopeID(), DepWrite);
1447
1448 unsigned MDToKeep[] = {LLVMContext::MD_dbg, LLVMContext::MD_tbaa,
1449 LLVMContext::MD_alias_scope,
1450 LLVMContext::MD_noalias,
1451 LLVMContext::MD_nontemporal};
1452 SI->copyMetadata(*DepWrite, MDToKeep);
1453 ++NumModifiedStores;
1454
1455 // Delete the old stores and now-dead instructions that feed them.
1456 deleteDeadInstruction(Inst, &BBI, *MD, *TLI, IOL,
1457 ThrowableInst);
1458 deleteDeadInstruction(DepWrite, &BBI, *MD, *TLI, IOL,
1459 ThrowableInst);
1460 MadeChange = true;
1461
1462 // We erased DepWrite and Inst (Loc); start over.
1463 break;
1464 }
1465 }
1466 }
1467
1468 // If this is a may-aliased store that is clobbering the store value, we
1469 // can keep searching past it for another must-aliased pointer that stores
1470 // to the same location. For example, in:
1471 // store -> P
1472 // store -> Q
1473 // store -> P
1474 // we can remove the first store to P even though we don't know if P and Q
1475 // alias.
1476 if (DepWrite == &BB.front()) break;
1477
1478 // Can't look past this instruction if it might read 'Loc'.
1479 if (isRefSet(AA->getModRefInfo(DepWrite, Loc)))
1480 break;
1481
1482 InstDep = MD->getPointerDependencyFrom(Loc, /*isLoad=*/ false,
1483 DepWrite->getIterator(), &BB,
1484 /*QueryInst=*/ nullptr, &Limit);
1485 }
1486 }
1487
1488 if (EnablePartialOverwriteTracking)
1489 MadeChange |= removePartiallyOverlappedStores(DL, IOL, *TLI);
1490
1491 // If this block ends in a return, unwind, or unreachable, all allocas are
1492 // dead at its end, which means stores to them are also dead.
1493 if (BB.getTerminator()->getNumSuccessors() == 0)
1494 MadeChange |= handleEndBlock(BB, AA, MD, TLI, IOL, ThrowableInst);
1495
1496 return MadeChange;
1497}
1498
1499static bool eliminateDeadStores(Function &F, AliasAnalysis *AA,
1500 MemoryDependenceResults *MD, DominatorTree *DT,
1501 const TargetLibraryInfo *TLI) {
1502 bool MadeChange = false;
1503 for (BasicBlock &BB : F)
1504 // Only check non-dead blocks. Dead blocks may have strange pointer
1505 // cycles that will confuse alias analysis.
1506 if (DT->isReachableFromEntry(&BB))
1507 MadeChange |= eliminateDeadStores(BB, AA, MD, DT, TLI);
1508
1509 return MadeChange;
1510}
1511
1512namespace {
1513//=============================================================================
1514// MemorySSA backed dead store elimination.
1515//
1516// The code below implements dead store elimination using MemorySSA. It uses
1517// the following general approach: given a MemoryDef, walk upwards to find
1518// clobbering MemoryDefs that may be killed by the starting def. Then check
1519// that there are no uses that may read the location of the original MemoryDef
1520// in between both MemoryDefs. A bit more concretely:
1521//
1522// For all MemoryDefs StartDef:
1523// 1. Get the next dominating clobbering MemoryDef (EarlierAccess) by walking
1524// upwards.
1525// 2. Check that there are no reads between EarlierAccess and the StartDef by
1526// checking all uses starting at EarlierAccess and walking until we see
1527// StartDef.
1528// 3. For each found CurrentDef, check that:
1529// 1. There are no barrier instructions between CurrentDef and StartDef (like
1530// throws or stores with ordering constraints).
1531// 2. StartDef is executed whenever CurrentDef is executed.
1532// 3. StartDef completely overwrites CurrentDef.
1533// 4. Erase CurrentDef from the function and MemorySSA.
1534
1535// Returns true if \p I is an intrisnic that does not read or write memory.
1536bool isNoopIntrinsic(Instruction *I) {
1537 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1538 switch (II->getIntrinsicID()) {
1539 case Intrinsic::lifetime_start:
1540 case Intrinsic::lifetime_end:
1541 case Intrinsic::invariant_end:
1542 case Intrinsic::launder_invariant_group:
1543 case Intrinsic::assume:
1544 return true;
1545 case Intrinsic::dbg_addr:
1546 case Intrinsic::dbg_declare:
1547 case Intrinsic::dbg_label:
1548 case Intrinsic::dbg_value:
1549 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1549)
;
1550 default:
1551 return false;
1552 }
1553 }
1554 return false;
1555}
1556
1557// Check if we can ignore \p D for DSE.
1558bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller) {
1559 Instruction *DI = D->getMemoryInst();
1560 // Calls that only access inaccessible memory cannot read or write any memory
1561 // locations we consider for elimination.
1562 if (auto *CB = dyn_cast<CallBase>(DI))
1563 if (CB->onlyAccessesInaccessibleMemory())
1564 return true;
1565
1566 // We can eliminate stores to locations not visible to the caller across
1567 // throwing instructions.
1568 if (DI->mayThrow() && !DefVisibleToCaller)
1569 return true;
1570
1571 // We can remove the dead stores, irrespective of the fence and its ordering
1572 // (release/acquire/seq_cst). Fences only constraints the ordering of
1573 // already visible stores, it does not make a store visible to other
1574 // threads. So, skipping over a fence does not change a store from being
1575 // dead.
1576 if (isa<FenceInst>(DI))
1577 return true;
1578
1579 // Skip intrinsics that do not really read or modify memory.
1580 if (isNoopIntrinsic(D->getMemoryInst()))
1581 return true;
1582
1583 return false;
1584}
1585
1586struct DSEState {
1587 Function &F;
1588 AliasAnalysis &AA;
1589
1590 /// The single BatchAA instance that is used to cache AA queries. It will
1591 /// not be invalidated over the whole run. This is safe, because:
1592 /// 1. Only memory writes are removed, so the alias cache for memory
1593 /// locations remains valid.
1594 /// 2. No new instructions are added (only instructions removed), so cached
1595 /// information for a deleted value cannot be accessed by a re-used new
1596 /// value pointer.
1597 BatchAAResults BatchAA;
1598
1599 MemorySSA &MSSA;
1600 DominatorTree &DT;
1601 PostDominatorTree &PDT;
1602 const TargetLibraryInfo &TLI;
1603 const DataLayout &DL;
1604
1605 // All MemoryDefs that potentially could kill other MemDefs.
1606 SmallVector<MemoryDef *, 64> MemDefs;
1607 // Any that should be skipped as they are already deleted
1608 SmallPtrSet<MemoryAccess *, 4> SkipStores;
1609 // Keep track of all of the objects that are invisible to the caller before
1610 // the function returns.
1611 // SmallPtrSet<const Value *, 16> InvisibleToCallerBeforeRet;
1612 DenseMap<const Value *, bool> InvisibleToCallerBeforeRet;
1613 // Keep track of all of the objects that are invisible to the caller after
1614 // the function returns.
1615 DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
1616 // Keep track of blocks with throwing instructions not modeled in MemorySSA.
1617 SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
1618 // Post-order numbers for each basic block. Used to figure out if memory
1619 // accesses are executed before another access.
1620 DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
1621
1622 /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
1623 /// basic block.
1624 DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
1625
1626 struct CheckCache {
1627 SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
1628 SmallPtrSet<MemoryAccess *, 16> KnownReads;
1629
1630 bool isKnownNoRead(MemoryAccess *A) const {
1631 return KnownNoReads.find(A) != KnownNoReads.end();
1632 }
1633 bool isKnownRead(MemoryAccess *A) const {
1634 return KnownReads.find(A) != KnownReads.end();
1635 }
1636 };
1637
1638 DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
1639 PostDominatorTree &PDT, const TargetLibraryInfo &TLI)
1640 : F(F), AA(AA), BatchAA(AA), MSSA(MSSA), DT(DT), PDT(PDT), TLI(TLI),
1641 DL(F.getParent()->getDataLayout()) {}
1642
1643 static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
1644 DominatorTree &DT, PostDominatorTree &PDT,
1645 const TargetLibraryInfo &TLI) {
1646 DSEState State(F, AA, MSSA, DT, PDT, TLI);
1647 // Collect blocks with throwing instructions not modeled in MemorySSA and
1648 // alloc-like objects.
1649 unsigned PO = 0;
1650 for (BasicBlock *BB : post_order(&F)) {
1651 State.PostOrderNumbers[BB] = PO++;
1652 for (Instruction &I : *BB) {
1653 MemoryAccess *MA = MSSA.getMemoryAccess(&I);
1654 if (I.mayThrow() && !MA)
1655 State.ThrowingBlocks.insert(I.getParent());
1656
1657 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
1658 if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
1659 (State.getLocForWriteEx(&I) || State.isMemTerminatorInst(&I)))
1660 State.MemDefs.push_back(MD);
1661 }
1662 }
1663
1664 // Treat byval or inalloca arguments the same as Allocas, stores to them are
1665 // dead at the end of the function.
1666 for (Argument &AI : F.args())
1667 if (AI.hasPassPointeeByValueCopyAttr()) {
1668 // For byval, the caller doesn't know the address of the allocation.
1669 if (AI.hasByValAttr())
1670 State.InvisibleToCallerBeforeRet.insert({&AI, true});
1671 State.InvisibleToCallerAfterRet.insert({&AI, true});
1672 }
1673
1674 return State;
1675 }
1676
1677 bool isInvisibleToCallerAfterRet(const Value *V) {
1678 if (isa<AllocaInst>(V))
1679 return true;
1680 auto I = InvisibleToCallerAfterRet.insert({V, false});
1681 if (I.second) {
1682 if (!isInvisibleToCallerBeforeRet(V)) {
1683 I.first->second = false;
1684 } else {
1685 auto *Inst = dyn_cast<Instruction>(V);
1686 if (Inst && isAllocLikeFn(Inst, &TLI))
1687 I.first->second = !PointerMayBeCaptured(V, true, false);
1688 }
1689 }
1690 return I.first->second;
1691 }
1692
1693 bool isInvisibleToCallerBeforeRet(const Value *V) {
1694 if (isa<AllocaInst>(V))
1695 return true;
1696 auto I = InvisibleToCallerBeforeRet.insert({V, false});
1697 if (I.second) {
1698 auto *Inst = dyn_cast<Instruction>(V);
1699 if (Inst && isAllocLikeFn(Inst, &TLI))
1700 // NOTE: This could be made more precise by PointerMayBeCapturedBefore
1701 // with the killing MemoryDef. But we refrain from doing so for now to
1702 // limit compile-time and this does not cause any changes to the number
1703 // of stores removed on a large test set in practice.
1704 I.first->second = !PointerMayBeCaptured(V, false, true);
1705 }
1706 return I.first->second;
1707 }
1708
1709 Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
1710 if (!I->mayWriteToMemory())
1711 return None;
1712
1713 if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
1714 return {MemoryLocation::getForDest(MTI)};
1715
1716 if (auto *CB = dyn_cast<CallBase>(I)) {
1717 // If the functions may write to memory we do not know about, bail out.
1718 if (!CB->onlyAccessesArgMemory() &&
1719 !CB->onlyAccessesInaccessibleMemOrArgMem())
1720 return None;
1721
1722 LibFunc LF;
1723 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
1724 switch (LF) {
1725 case LibFunc_strcpy:
1726 case LibFunc_strncpy:
1727 case LibFunc_strcat:
1728 case LibFunc_strncat:
1729 return {MemoryLocation(CB->getArgOperand(0),
1730 LocationSize::unknown())};
1731 default:
1732 break;
1733 }
1734 }
1735 switch (CB->getIntrinsicID()) {
1736 case Intrinsic::init_trampoline:
1737 return {MemoryLocation(CB->getArgOperand(0), LocationSize::unknown())};
1738 case Intrinsic::masked_store:
1739 return {MemoryLocation::getForArgument(CB, 1, TLI)};
1740 default:
1741 break;
1742 }
1743 return None;
1744 }
1745
1746 return MemoryLocation::getOrNone(I);
1747 }
1748
1749 /// Returns true if \p UseInst completely overwrites \p DefLoc
1750 /// (stored by \p DefInst).
1751 bool isCompleteOverwrite(MemoryLocation DefLoc, Instruction *DefInst,
1752 Instruction *UseInst) {
1753 // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
1754 // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
1755 // MemoryDef.
1756 if (!UseInst->mayWriteToMemory())
1757 return false;
1758
1759 if (auto *CB = dyn_cast<CallBase>(UseInst))
1760 if (CB->onlyAccessesInaccessibleMemory())
1761 return false;
1762
1763 int64_t InstWriteOffset, DepWriteOffset;
1764 if (auto CC = getLocForWriteEx(UseInst))
1765 return isOverwrite(UseInst, DefInst, *CC, DefLoc, DL, TLI, DepWriteOffset,
1766 InstWriteOffset, BatchAA, &F) == OW_Complete;
1767 return false;
1768 }
1769
1770 /// Returns true if \p Def is not read before returning from the function.
1771 bool isWriteAtEndOfFunction(MemoryDef *Def) {
1772 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)
1773 << *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)
1774 << ") 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)
;
1775
1776 auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
1777 if (!MaybeLoc) {
1778 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)
;
1779 return false;
1780 }
1781
1782 SmallVector<MemoryAccess *, 4> WorkList;
1783 SmallPtrSet<MemoryAccess *, 8> Visited;
1784 auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
1785 if (!Visited.insert(Acc).second)
1786 return;
1787 for (Use &U : Acc->uses())
1788 WorkList.push_back(cast<MemoryAccess>(U.getUser()));
1789 };
1790 PushMemUses(Def);
1791 for (unsigned I = 0; I < WorkList.size(); I++) {
1792 if (WorkList.size() >= MemorySSAScanLimit) {
1793 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit exploration limit.\n"; }
} while (false)
;
1794 return false;
1795 }
1796
1797 MemoryAccess *UseAccess = WorkList[I];
1798 // Simply adding the users of MemoryPhi to the worklist is not enough,
1799 // because we might miss read clobbers in different iterations of a loop,
1800 // for example.
1801 // TODO: Add support for phi translation to handle the loop case.
1802 if (isa<MemoryPhi>(UseAccess))
1803 return false;
1804
1805 // TODO: Checking for aliasing is expensive. Consider reducing the amount
1806 // of times this is called and/or caching it.
1807 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1808 if (isReadClobber(*MaybeLoc, UseInst)) {
1809 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit read clobber " <<
*UseInst << ".\n"; } } while (false)
;
1810 return false;
1811 }
1812
1813 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1814 PushMemUses(UseDef);
1815 }
1816 return true;
1817 }
1818
1819 /// If \p I is a memory terminator like llvm.lifetime.end or free, return a
1820 /// pair with the MemoryLocation terminated by \p I and a boolean flag
1821 /// indicating whether \p I is a free-like call.
1822 Optional<std::pair<MemoryLocation, bool>>
1823 getLocForTerminator(Instruction *I) const {
1824 uint64_t Len;
1825 Value *Ptr;
1826 if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
1827 m_Value(Ptr))))
1828 return {std::make_pair(MemoryLocation(Ptr, Len), false)};
1829
1830 if (auto *CB = dyn_cast<CallBase>(I)) {
1831 if (isFreeCall(I, &TLI))
1832 return {std::make_pair(MemoryLocation(CB->getArgOperand(0),
1833 LocationSize::unknown()),
1834 true)};
1835 }
1836
1837 return None;
1838 }
1839
1840 /// Returns true if \p I is a memory terminator instruction like
1841 /// llvm.lifetime.end or free.
1842 bool isMemTerminatorInst(Instruction *I) const {
1843 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1844 return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
1845 isFreeCall(I, &TLI);
1846 }
1847
1848 /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from
1849 /// instruction \p AccessI.
1850 bool isMemTerminator(MemoryLocation Loc, Instruction *AccessI,
1851 Instruction *MaybeTerm) {
1852 Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1853 getLocForTerminator(MaybeTerm);
1854
1855 if (!MaybeTermLoc)
1856 return false;
1857
1858 // If the terminator is a free-like call, all accesses to the underlying
1859 // object can be considered terminated.
1860 if (getUnderlyingObject(Loc.Ptr) !=
1861 getUnderlyingObject(MaybeTermLoc->first.Ptr))
1862 return false;
1863
1864 auto TermLoc = MaybeTermLoc->first;
1865 if (MaybeTermLoc->second) {
1866 const Value *LocUO = getUnderlyingObject(Loc.Ptr);
1867 return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
1868 }
1869 int64_t InstWriteOffset, DepWriteOffset;
1870 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DL, TLI,
1871 DepWriteOffset, InstWriteOffset, BatchAA,
1872 &F) == OW_Complete;
1873 }
1874
1875 // Returns true if \p Use may read from \p DefLoc.
1876 bool isReadClobber(MemoryLocation DefLoc, Instruction *UseInst) {
1877 if (isNoopIntrinsic(UseInst))
1878 return false;
1879
1880 // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1881 // treated as read clobber.
1882 if (auto SI = dyn_cast<StoreInst>(UseInst))
1883 return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
1884
1885 if (!UseInst->mayReadFromMemory())
1886 return false;
1887
1888 if (auto *CB = dyn_cast<CallBase>(UseInst))
1889 if (CB->onlyAccessesInaccessibleMemory())
1890 return false;
1891
1892 // NOTE: For calls, the number of stores removed could be slightly improved
1893 // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
1894 // be expensive compared to the benefits in practice. For now, avoid more
1895 // expensive analysis to limit compile-time.
1896 return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
1897 }
1898
1899 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1900 /// loop. In particular, this guarantees that it only references a single
1901 /// MemoryLocation during execution of the containing function.
1902 bool IsGuaranteedLoopInvariant(Value *Ptr) {
1903 auto IsGuaranteedLoopInvariantBase = [this](Value *Ptr) {
1904 Ptr = Ptr->stripPointerCasts();
1905 if (auto *I = dyn_cast<Instruction>(Ptr)) {
1906 if (isa<AllocaInst>(Ptr))
1907 return true;
1908
1909 if (isAllocLikeFn(I, &TLI))
1910 return true;
1911
1912 return false;
1913 }
1914 return true;
1915 };
1916
1917 Ptr = Ptr->stripPointerCasts();
1918 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
1919 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
1920 GEP->hasAllConstantIndices();
1921 }
1922 return IsGuaranteedLoopInvariantBase(Ptr);
1923 }
1924
1925 // Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with
1926 // no read access between them or on any other path to a function exit block
1927 // if \p DefLoc is not accessible after the function returns. If there is no
1928 // such MemoryDef, return None. The returned value may not (completely)
1929 // overwrite \p DefLoc. Currently we bail out when we encounter an aliasing
1930 // MemoryUse (read).
1931 Optional<MemoryAccess *>
1932 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1933 MemoryLocation DefLoc, const Value *DefUO, CheckCache &Cache,
1934 unsigned &ScanLimit, unsigned &WalkerStepLimit,
1935 bool IsMemTerm, unsigned &PartialLimit) {
1936 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1937 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
1938 return None;
1939 }
1940
1941 MemoryAccess *Current = StartAccess;
1942 Instruction *KillingI = KillingDef->getMemoryInst();
1943 bool StepAgain;
1944 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)
;
1945
1946 // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1947 do {
1948 StepAgain = false;
1949 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)
1950 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)
1951 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)
1952 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)
1953 << ")";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)
1954 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)
1955 })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)
;
1956
1957 // Reached TOP.
1958 if (MSSA.isLiveOnEntryDef(Current)) {
1959 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found LiveOnEntryDef\n"; }
} while (false)
;
1960 return None;
1961 }
1962
1963 // Cost of a step. Accesses in the same block are more likely to be valid
1964 // candidates for elimination, hence consider them cheaper.
1965 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1966 ? MemorySSASameBBStepCost
1967 : MemorySSAOtherBBStepCost;
1968 if (WalkerStepLimit <= StepCost) {
1969 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit walker step limit\n";
} } while (false)
;
1970 return None;
1971 }
1972 WalkerStepLimit -= StepCost;
1973
1974 // Return for MemoryPhis. They cannot be eliminated directly and the
1975 // caller is responsible for traversing them.
1976 if (isa<MemoryPhi>(Current)) {
1977 LLVM_DEBUG(dbgs() << " ... found MemoryPhi\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found MemoryPhi\n"; } } while
(false)
;
1978 return Current;
1979 }
1980
1981 // Below, check if CurrentDef is a valid candidate to be eliminated by
1982 // KillingDef. If it is not, check the next candidate.
1983 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1984 Instruction *CurrentI = CurrentDef->getMemoryInst();
1985
1986 if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO))) {
1987 StepAgain = true;
1988 Current = CurrentDef->getDefiningAccess();
1989 continue;
1990 }
1991
1992 // Before we try to remove anything, check for any extra throwing
1993 // instructions that block us from DSEing
1994 if (mayThrowBetween(KillingI, CurrentI, DefUO)) {
1995 LLVM_DEBUG(dbgs() << " ... skip, may throw!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, may throw!\n"; } } while
(false)
;
1996 return None;
1997 }
1998
1999 // Check for anything that looks like it will be a barrier to further
2000 // removal
2001 if (isDSEBarrier(DefUO, CurrentI)) {
2002 LLVM_DEBUG(dbgs() << " ... skip, barrier\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, barrier\n"; } } while
(false)
;
2003 return None;
2004 }
2005
2006 // If Current is known to be on path that reads DefLoc or is a read
2007 // clobber, bail out, as the path is not profitable. We skip this check
2008 // for intrinsic calls, because the code knows how to handle memcpy
2009 // intrinsics.
2010 if (!isa<IntrinsicInst>(CurrentI) &&
2011 (Cache.KnownReads.contains(Current) ||
2012 isReadClobber(DefLoc, CurrentI))) {
2013 Cache.KnownReads.insert(Current);
2014 return None;
2015 }
2016
2017 // Quick check if there are direct uses that are read-clobbers.
2018 if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {
2019 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
2020 return !MSSA.dominates(StartAccess, UseOrDef) &&
2021 isReadClobber(DefLoc, UseOrDef->getMemoryInst());
2022 return false;
2023 })) {
2024 Cache.KnownReads.insert(Current);
2025 LLVM_DEBUG(dbgs() << " ... found a read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found a read clobber\n"; }
} while (false)
;
2026 return None;
2027 }
2028
2029 // If Current cannot be analyzed or is not removable, check the next
2030 // candidate.
2031 if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI)) {
2032 StepAgain = true;
2033 Current = CurrentDef->getDefiningAccess();
2034 continue;
2035 }
2036
2037 // If Current does not have an analyzable write location, skip it
2038 auto CurrentLoc = getLocForWriteEx(CurrentI);
2039 if (!CurrentLoc) {
2040 StepAgain = true;
2041 Current = CurrentDef->getDefiningAccess();
2042 continue;
2043 }
2044
2045 if (IsMemTerm) {
2046 // If the killing def is a memory terminator (e.g. lifetime.end), check
2047 // the next candidate if the current Current does not write the same
2048 // underlying object as the terminator.
2049 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
2050 StepAgain = true;
2051 Current = CurrentDef->getDefiningAccess();
2052 }
2053 continue;
2054 } else {
2055 // AliasAnalysis does not account for loops. Limit elimination to
2056 // candidates for which we can guarantee they always store to the same
2057 // memory location and not multiple locations in a loop.
2058 if (Current->getBlock() != KillingDef->getBlock() &&
2059 !IsGuaranteedLoopInvariant(const_cast<Value *>(CurrentLoc->Ptr))) {
2060 StepAgain = true;
2061 Current = CurrentDef->getDefiningAccess();
2062 WalkerStepLimit -= 1;
2063 continue;
2064 }
2065
2066 int64_t InstWriteOffset, DepWriteOffset;
2067 auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc, DL, TLI,
2068 DepWriteOffset, InstWriteOffset, BatchAA, &F);
2069 // If Current does not write to the same object as KillingDef, check
2070 // the next candidate.
2071 if (OR == OW_Unknown) {
2072 StepAgain = true;
2073 Current = CurrentDef->getDefiningAccess();
2074 } else if (OR == OW_MaybePartial) {
2075 // If KillingDef only partially overwrites Current, check the next
2076 // candidate if the partial step limit is exceeded. This aggressively
2077 // limits the number of candidates for partial store elimination,
2078 // which are less likely to be removable in the end.
2079 if (PartialLimit <= 1) {
2080 StepAgain = true;
2081 Current = CurrentDef->getDefiningAccess();
2082 WalkerStepLimit -= 1;
2083 continue;
2084 }
2085 PartialLimit -= 1;
2086 }
2087 }
2088 } while (StepAgain);
2089
2090 // Accesses to objects accessible after the function returns can only be
2091 // eliminated if the access is killed along all paths to the exit. Collect
2092 // the blocks with killing (=completely overwriting MemoryDefs) and check if
2093 // they cover all paths from EarlierAccess to any function exit.
2094 SmallPtrSet<Instruction *, 16> KillingDefs;
2095 KillingDefs.insert(KillingDef->getMemoryInst());
2096 MemoryAccess *EarlierAccess = Current;
2097 Instruction *EarlierMemInst =
2098 cast<MemoryDef>(EarlierAccess)->getMemoryInst();
2099 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)
2100 << *EarlierMemInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*EarlierAccess << " (" << *EarlierMemInst <<
")\n"; } } while (false)
;
2101
2102 SmallSetVector<MemoryAccess *, 32> WorkList;
2103 auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
2104 for (Use &U : Acc->uses())
2105 WorkList.insert(cast<MemoryAccess>(U.getUser()));
2106 };
2107 PushMemUses(EarlierAccess);
2108
2109 // Optimistically collect all accesses for reads. If we do not find any
2110 // read clobbers, add them to the cache.
2111 SmallPtrSet<MemoryAccess *, 16> KnownNoReads;
2112 if (!EarlierMemInst->mayReadFromMemory())
2113 KnownNoReads.insert(EarlierAccess);
2114 // Check if EarlierDef may be read.
2115 for (unsigned I = 0; I < WorkList.size(); I++) {
2116 MemoryAccess *UseAccess = WorkList[I];
2117
2118 LLVM_DEBUG(dbgs() << " " << *UseAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " " << *UseAccess; } } while
(false)
;
2119 // Bail out if the number of accesses to check exceeds the scan limit.
2120 if (ScanLimit < (WorkList.size() - I)) {
2121 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
2122 return None;
2123 }
2124 --ScanLimit;
2125 NumDomMemDefChecks++;
2126
2127 // Check if we already visited this access.
2128 if (Cache.isKnownNoRead(UseAccess)) {
2129 LLVM_DEBUG(dbgs() << " ... skip, discovered that " << *UseAccessdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, discovered that " <<
*UseAccess << " is safe earlier.\n"; } } while (false)
2130 << " is safe earlier.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, discovered that " <<
*UseAccess << " is safe earlier.\n"; } } while (false)
;
2131 continue;
2132 }
2133 if (Cache.isKnownRead(UseAccess)) {
2134 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)
2135 << " 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)
;
2136 return None;
2137 }
2138 KnownNoReads.insert(UseAccess);
2139
2140 if (isa<MemoryPhi>(UseAccess)) {
2141 if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
2142 return DT.properlyDominates(KI->getParent(),
2143 UseAccess->getBlock());
2144 })) {
2145 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)
;
2146 continue;
2147 }
2148 LLVM_DEBUG(dbgs() << "\n ... adding PHI uses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... adding PHI uses\n"; } }
while (false)
;
2149 PushMemUses(UseAccess);
2150 continue;
2151 }
2152
2153 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
2154 LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *UseInst << ")\n"
; } } while (false)
;
2155
2156 if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {
2157 return DT.dominates(KI, UseInst);
2158 })) {
2159 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)
;
2160 continue;
2161 }
2162
2163 // A memory terminator kills all preceeding MemoryDefs and all succeeding
2164 // MemoryAccesses. We do not have to check it's users.
2165 if (isMemTerminator(DefLoc, KillingI, UseInst)) {
2166 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
2167 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
2168 << " ... skipping, memterminator invalidates following accesses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
;
2169 continue;
2170 }
2171
2172 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
2173 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... adding uses of intrinsic\n"
; } } while (false)
;
2174 PushMemUses(UseAccess);
2175 continue;
2176 }
2177
2178 if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {
2179 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found throwing instruction\n"
; } } while (false)
;
2180 Cache.KnownReads.insert(UseAccess);
2181 Cache.KnownReads.insert(StartAccess);
2182 Cache.KnownReads.insert(EarlierAccess);
2183 return None;
2184 }
2185
2186 // Uses which may read the original MemoryDef mean we cannot eliminate the
2187 // original MD. Stop walk.
2188 if (isReadClobber(DefLoc, UseInst)) {
2189 LLVM_DEBUG(dbgs() << " ... found read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found read clobber\n"; } }
while (false)
;
2190 Cache.KnownReads.insert(UseAccess);
2191 Cache.KnownReads.insert(StartAccess);
2192 Cache.KnownReads.insert(EarlierAccess);
2193 return None;
2194 }
2195
2196 // For the KillingDef and EarlierAccess we only have to check if it reads
2197 // the memory location.
2198 // TODO: It would probably be better to check for self-reads before
2199 // calling the function.
2200 if (KillingDef == UseAccess || EarlierAccess == UseAccess) {
2201 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)
;
2202 continue;
2203 }
2204
2205 // Check all uses for MemoryDefs, except for defs completely overwriting
2206 // the original location. Otherwise we have to check uses of *all*
2207 // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
2208 // miss cases like the following
2209 // 1 = Def(LoE) ; <----- EarlierDef stores [0,1]
2210 // 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
2211 // Use(2) ; MayAlias 2 *and* 1, loads [0, 3].
2212 // (The Use points to the *first* Def it may alias)
2213 // 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
2214 // stores [0,1]
2215 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
2216 if (isCompleteOverwrite(DefLoc, KillingI, UseInst)) {
2217 if (!isInvisibleToCallerAfterRet(DefUO) &&
2218 UseAccess != EarlierAccess) {
2219 BasicBlock *MaybeKillingBlock = UseInst->getParent();
2220 if (PostOrderNumbers.find(MaybeKillingBlock)->second <
2221 PostOrderNumbers.find(EarlierAccess->getBlock())->second) {
2222
2223 LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
2224 << " ... found killing def " << *UseInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
;
2225 KillingDefs.insert(UseInst);
2226 }
2227 }
2228 } else
2229 PushMemUses(UseDef);
2230 }
2231 }
2232
2233 // For accesses to locations visible after the function returns, make sure
2234 // that the location is killed (=overwritten) along all paths from
2235 // EarlierAccess to the exit.
2236 if (!isInvisibleToCallerAfterRet(DefUO)) {
2237 SmallPtrSet<BasicBlock *, 16> KillingBlocks;
2238 for (Instruction *KD : KillingDefs)
2239 KillingBlocks.insert(KD->getParent());
2240 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2241, __PRETTY_FUNCTION__))
2241 "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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2241, __PRETTY_FUNCTION__))
;
2242
2243 // Find the common post-dominator of all killing blocks.
2244 BasicBlock *CommonPred = *KillingBlocks.begin();
2245 for (auto I = std::next(KillingBlocks.begin()), E = KillingBlocks.end();
2246 I != E; I++) {
2247 if (!CommonPred)
2248 break;
2249 CommonPred = PDT.findNearestCommonDominator(CommonPred, *I);
2250 }
2251
2252 // If CommonPred is in the set of killing blocks, just check if it
2253 // post-dominates EarlierAccess.
2254 if (KillingBlocks.count(CommonPred)) {
2255 if (PDT.dominates(CommonPred, EarlierAccess->getBlock()))
2256 return {EarlierAccess};
2257 return None;
2258 }
2259
2260 // If the common post-dominator does not post-dominate EarlierAccess,
2261 // there is a path from EarlierAccess to an exit not going through a
2262 // killing block.
2263 if (PDT.dominates(CommonPred, EarlierAccess->getBlock())) {
2264 SetVector<BasicBlock *> WorkList;
2265
2266 // If CommonPred is null, there are multiple exits from the function.
2267 // They all have to be added to the worklist.
2268 if (CommonPred)
2269 WorkList.insert(CommonPred);
2270 else
2271 for (BasicBlock *R : PDT.roots())
2272 WorkList.insert(R);
2273
2274 NumCFGTries++;
2275 // Check if all paths starting from an exit node go through one of the
2276 // killing blocks before reaching EarlierAccess.
2277 for (unsigned I = 0; I < WorkList.size(); I++) {
2278 NumCFGChecks++;
2279 BasicBlock *Current = WorkList[I];
2280 if (KillingBlocks.count(Current))
2281 continue;
2282 if (Current == EarlierAccess->getBlock())
2283 return None;
2284
2285 // EarlierAccess is reachable from the entry, so we don't have to
2286 // explore unreachable blocks further.
2287 if (!DT.isReachableFromEntry(Current))
2288 continue;
2289
2290 for (BasicBlock *Pred : predecessors(Current))
2291 WorkList.insert(Pred);
2292
2293 if (WorkList.size() >= MemorySSAPathCheckLimit)
2294 return None;
2295 }
2296 NumCFGSuccess++;
2297 return {EarlierAccess};
2298 }
2299 return None;
2300 }
2301
2302 // No aliasing MemoryUses of EarlierAccess found, EarlierAccess is
2303 // potentially dead.
2304 Cache.KnownNoReads.insert(KnownNoReads.begin(), KnownNoReads.end());
2305 return {EarlierAccess};
2306 }
2307
2308 // Delete dead memory defs
2309 void deleteDeadInstruction(Instruction *SI) {
2310 MemorySSAUpdater Updater(&MSSA);
2311 SmallVector<Instruction *, 32> NowDeadInsts;
2312 NowDeadInsts.push_back(SI);
2313 --NumFastOther;
2314
2315 while (!NowDeadInsts.empty()) {
2316 Instruction *DeadInst = NowDeadInsts.pop_back_val();
2317 ++NumFastOther;
2318
2319 // Try to preserve debug information attached to the dead instruction.
2320 salvageDebugInfo(*DeadInst);
2321 salvageKnowledge(DeadInst);
2322
2323 // Remove the Instruction from MSSA.
2324 if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
2325 if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
2326 SkipStores.insert(MD);
2327 }
2328 Updater.removeMemoryAccess(MA);
2329 }
2330
2331 auto I = IOLs.find(DeadInst->getParent());
2332 if (I != IOLs.end())
2333 I->second.erase(DeadInst);
2334 // Remove its operands
2335 for (Use &O : DeadInst->operands())
2336 if (Instruction *OpI = dyn_cast<Instruction>(O)) {
2337 O = nullptr;
2338 if (isInstructionTriviallyDead(OpI, &TLI))
2339 NowDeadInsts.push_back(OpI);
2340 }
2341
2342 DeadInst->eraseFromParent();
2343 }
2344 }
2345
2346 // Check for any extra throws between SI and NI that block DSE. This only
2347 // checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may
2348 // throw are handled during the walk from one def to the next.
2349 bool mayThrowBetween(Instruction *SI, Instruction *NI,
2350 const Value *SILocUnd) {
2351 // First see if we can ignore it by using the fact that SI is an
2352 // alloca/alloca like object that is not visible to the caller during
2353 // execution of the function.
2354 if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd))
2355 return false;
2356
2357 if (SI->getParent() == NI->getParent())
2358 return ThrowingBlocks.count(SI->getParent());
2359 return !ThrowingBlocks.empty();
2360 }
2361
2362 // Check if \p NI acts as a DSE barrier for \p SI. The following instructions
2363 // act as barriers:
2364 // * A memory instruction that may throw and \p SI accesses a non-stack
2365 // object.
2366 // * Atomic stores stronger that monotonic.
2367 bool isDSEBarrier(const Value *SILocUnd, Instruction *NI) {
2368 // If NI may throw it acts as a barrier, unless we are to an alloca/alloca
2369 // like object that does not escape.
2370 if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd))
2371 return true;
2372
2373 // If NI is an atomic load/store stronger than monotonic, do not try to
2374 // eliminate/reorder it.
2375 if (NI->isAtomic()) {
2376 if (auto *LI = dyn_cast<LoadInst>(NI))
2377 return isStrongerThanMonotonic(LI->getOrdering());
2378 if (auto *SI = dyn_cast<StoreInst>(NI))
2379 return isStrongerThanMonotonic(SI->getOrdering());
2380 if (auto *ARMW = dyn_cast<AtomicRMWInst>(NI))
2381 return isStrongerThanMonotonic(ARMW->getOrdering());
2382 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(NI))
2383 return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
2384 isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
2385 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2385)
;
2386 }
2387 return false;
2388 }
2389
2390 /// Eliminate writes to objects that are not visible in the caller and are not
2391 /// accessed before returning from the function.
2392 bool eliminateDeadWritesAtEndOfFunction() {
2393 bool MadeChange = false;
2394 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2395 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
2396 << "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)
;
2397 for (int I = MemDefs.size() - 1; I >= 0; I--) {
2398 MemoryDef *Def = MemDefs[I];
2399 if (SkipStores.find(Def) != SkipStores.end() ||
2400 !isRemovable(Def->getMemoryInst()))
2401 continue;
2402
2403 Instruction *DefI = Def->getMemoryInst();
2404 SmallVector<const Value *, 4> Pointers;
2405 auto DefLoc = getLocForWriteEx(DefI);
2406 if (!DefLoc)
2407 continue;
2408
2409 // NOTE: Currently eliminating writes at the end of a function is limited
2410 // to MemoryDefs with a single underlying object, to save compile-time. In
2411 // practice it appears the case with multiple underlying objects is very
2412 // uncommon. If it turns out to be important, we can use
2413 // getUnderlyingObjects here instead.
2414 const Value *UO = getUnderlyingObject(DefLoc->Ptr);
2415 if (!UO || !isInvisibleToCallerAfterRet(UO))
2416 continue;
2417
2418 if (isWriteAtEndOfFunction(Def)) {
2419 // See through pointer-to-pointer bitcasts
2420 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)
2421 "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)
;
2422 deleteDeadInstruction(DefI);
2423 ++NumFastStores;
2424 MadeChange = true;
2425 }
2426 }
2427 return MadeChange;
2428 }
2429
2430 /// \returns true if \p Def is a no-op store, either because it
2431 /// directly stores back a loaded value or stores zero to a calloced object.
2432 bool storeIsNoop(MemoryDef *Def, MemoryLocation DefLoc, const Value *DefUO) {
2433 StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
2434 if (!Store)
2435 return false;
2436
2437 if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
2438 if (LoadI->getPointerOperand() == Store->getOperand(1)) {
2439 // Get the defining access for the load.
2440 auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
2441 // Fast path: the defining accesses are the same.
2442 if (LoadAccess == Def->getDefiningAccess())
2443 return true;
2444
2445 // Look through phi accesses. Recursively scan all phi accesses by
2446 // adding them to a worklist. Bail when we run into a memory def that
2447 // does not match LoadAccess.
2448 SetVector<MemoryAccess *> ToCheck;
2449 MemoryAccess *Current =
2450 MSSA.getWalker()->getClobberingMemoryAccess(Def);
2451 // We don't want to bail when we run into the store memory def. But,
2452 // the phi access may point to it. So, pretend like we've already
2453 // checked it.
2454 ToCheck.insert(Def);
2455 ToCheck.insert(Current);
2456 // Start at current (1) to simulate already having checked Def.
2457 for (unsigned I = 1; I < ToCheck.size(); ++I) {
2458 Current = ToCheck[I];
2459 if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
2460 // Check all the operands.
2461 for (auto &Use : PhiAccess->incoming_values())
2462 ToCheck.insert(cast<MemoryAccess>(&Use));
2463 continue;
2464 }
2465
2466 // If we found a memory def, bail. This happens when we have an
2467 // unrelated write in between an otherwise noop store.
2468 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2469, __PRETTY_FUNCTION__))
2469 "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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2469, __PRETTY_FUNCTION__))
;
2470 // TODO: Skip no alias MemoryDefs that have no aliasing reads.
2471 // We are searching for the definition of the store's destination.
2472 // So, if that is the same definition as the load, then this is a
2473 // noop. Otherwise, fail.
2474 if (LoadAccess != Current)
2475 return false;
2476 }
2477 return true;
2478 }
2479 }
2480
2481 Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
2482 if (StoredConstant && StoredConstant->isNullValue()) {
2483 auto *DefUOInst = dyn_cast<Instruction>(DefUO);
2484 if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
2485 auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
2486 // If UnderlyingDef is the clobbering access of Def, no instructions
2487 // between them can modify the memory location.
2488 auto *ClobberDef =
2489 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
2490 return UnderlyingDef == ClobberDef;
2491 }
2492 }
2493 return false;
2494 }
2495};
2496
2497bool eliminateDeadStoresMemorySSA(Function &F, AliasAnalysis &AA,
2498 MemorySSA &MSSA, DominatorTree &DT,
2499 PostDominatorTree &PDT,
2500 const TargetLibraryInfo &TLI) {
2501 bool MadeChange = false;
2502
2503 DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI);
2504 // For each store:
2505 for (unsigned I = 0; I < State.MemDefs.size(); I++) {
2506 MemoryDef *KillingDef = State.MemDefs[I];
2507 if (State.SkipStores.count(KillingDef))
2508 continue;
2509 Instruction *SI = KillingDef->getMemoryInst();
2510
2511 auto MaybeSILoc = State.getLocForWriteEx(SI);
2512 if (State.isMemTerminatorInst(SI))
2513 MaybeSILoc = State.getLocForTerminator(SI).map(
2514 [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
2515 else
2516 MaybeSILoc = State.getLocForWriteEx(SI);
2517
2518 if (!MaybeSILoc) {
2519 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)
2520 << *SI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
<< *SI << "\n"; } } while (false)
;
2521 continue;
2522 }
2523 MemoryLocation SILoc = *MaybeSILoc;
2524 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~++20201124111112+7b5254223ac/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 2524, __PRETTY_FUNCTION__))
;
2525 const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr);
2526
2527 MemoryAccess *Current = KillingDef;
Value stored to 'Current' during its initialization is never read
2528 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)
2529 << *KillingDef << " (" << *SI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *SI << ")\n"
; } } while (false)
;
2530
2531 unsigned ScanLimit = MemorySSAScanLimit;
2532 unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
2533 unsigned PartialLimit = MemorySSAPartialStoreLimit;
2534 // Worklist of MemoryAccesses that may be killed by KillingDef.
2535 SetVector<MemoryAccess *> ToCheck;
2536
2537 if (SILocUnd)
2538 ToCheck.insert(KillingDef->getDefiningAccess());
2539
2540 bool Shortend = false;
2541 bool IsMemTerm = State.isMemTerminatorInst(SI);
2542 DSEState::CheckCache Cache;
2543 // Check if MemoryAccesses in the worklist are killed by KillingDef.
2544 for (unsigned I = 0; I < ToCheck.size(); I++) {
2545 Current = ToCheck[I];
2546 if (State.SkipStores.count(Current))
2547 continue;
2548
2549 Optional<MemoryAccess *> Next = State.getDomMemoryDef(
2550 KillingDef, Current, SILoc, SILocUnd, Cache, ScanLimit,
2551 WalkerStepLimit, IsMemTerm, PartialLimit);
2552
2553 if (!Next) {
2554 LLVM_DEBUG(dbgs() << " finished walk\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " finished walk\n"; } } while (false
)
;
2555 continue;
2556 }
2557
2558 MemoryAccess *EarlierAccess = *Next;
2559 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)
;
2560 if (isa<MemoryPhi>(EarlierAccess)) {
2561 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)
;
2562 for (Value *V : cast<MemoryPhi>(EarlierAccess)->incoming_values()) {
2563 MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
2564 BasicBlock *IncomingBlock = IncomingAccess->getBlock();
2565 BasicBlock *PhiBlock = EarlierAccess->getBlock();
2566
2567 // We only consider incoming MemoryAccesses that come before the
2568 // MemoryPhi. Otherwise we could discover candidates that do not
2569 // strictly dominate our starting def.
2570 if (State.PostOrderNumbers[IncomingBlock] >
2571 State.PostOrderNumbers[PhiBlock])
2572 ToCheck.insert(IncomingAccess);
2573 }
2574 continue;
2575 }
2576 auto *NextDef = cast<MemoryDef>(EarlierAccess);
2577 Instruction *NI = NextDef->getMemoryInst();
2578 LLVM_DEBUG(dbgs() << " (" << *NI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *NI << ")\n"; }
} while (false)
;
2579 ToCheck.insert(NextDef->getDefiningAccess());
2580 NumGetDomMemoryDefPassed++;
2581
2582 if (!DebugCounter::shouldExecute(MemorySSACounter))
2583 continue;
2584
2585 MemoryLocation NILoc = *State.getLocForWriteEx(NI);
2586
2587 if (IsMemTerm) {
2588 const Value *NIUnd = getUnderlyingObject(NILoc.Ptr);
2589 if (SILocUnd != NIUnd)
2590 continue;
2591 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)
2592 << "\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)
;
2593 State.deleteDeadInstruction(NI);
2594 ++NumFastStores;
2595 MadeChange = true;
2596 } else {
2597 // Check if NI overwrites SI.
2598 int64_t InstWriteOffset, DepWriteOffset;
2599 OverwriteResult OR =
2600 isOverwrite(SI, NI, SILoc, NILoc, State.DL, TLI, DepWriteOffset,
2601 InstWriteOffset, State.BatchAA, &F);
2602 if (OR == OW_MaybePartial) {
2603 auto Iter = State.IOLs.insert(
2604 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2605 NI->getParent(), InstOverlapIntervalsTy()));
2606 auto &IOL = Iter.first->second;
2607 OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,
2608 NI, IOL);
2609 }
2610
2611 if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
2612 auto *Earlier = dyn_cast<StoreInst>(NI);
2613 auto *Later = dyn_cast<StoreInst>(SI);
2614 // We are re-using tryToMergePartialOverlappingStores, which requires
2615 // Earlier to domiante Later.
2616 // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2617 if (Earlier && Later && DT.dominates(Earlier, Later)) {
2618 if (Constant *Merged = tryToMergePartialOverlappingStores(
2619 Earlier, Later, InstWriteOffset, DepWriteOffset, State.DL,
2620 State.BatchAA, &DT)) {
2621
2622 // Update stored value of earlier store to merged constant.
2623 Earlier->setOperand(0, Merged);
2624 ++NumModifiedStores;
2625 MadeChange = true;
2626
2627 Shortend = true;
2628 // Remove later store and remove any outstanding overlap intervals
2629 // for the updated store.
2630 State.deleteDeadInstruction(Later);
2631 auto I = State.IOLs.find(Earlier->getParent());
2632 if (I != State.IOLs.end())
2633 I->second.erase(Earlier);
2634 break;
2635 }
2636 }
2637 }
2638
2639 if (OR == OW_Complete) {
2640 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)
2641 << "\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)
;
2642 State.deleteDeadInstruction(NI);
2643 ++NumFastStores;
2644 MadeChange = true;
2645 }
2646 }
2647 }
2648
2649 // Check if the store is a no-op.
2650 if (!Shortend && isRemovable(SI) &&
2651 State.storeIsNoop(KillingDef, SILoc, SILocUnd)) {
2652 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)
;
2653 State.deleteDeadInstruction(SI);
2654 NumRedundantStores++;
2655 MadeChange = true;
2656 continue;
2657 }
2658 }
2659
2660 if (EnablePartialOverwriteTracking)
2661 for (auto &KV : State.IOLs)
2662 MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
2663
2664 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2665 return MadeChange;
2666}
2667} // end anonymous namespace
2668
2669//===----------------------------------------------------------------------===//
2670// DSE Pass
2671//===----------------------------------------------------------------------===//
2672PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
2673 AliasAnalysis &AA = AM.getResult<AAManager>(F);
2674 const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2675 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
2676
2677 bool Changed = false;
2678 if (EnableMemorySSA) {
2679 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2680 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
2681
2682 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2683 } else {
2684 MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
2685
2686 Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
2687 }
2688
2689#ifdef LLVM_ENABLE_STATS1
2690 if (AreStatisticsEnabled())
2691 for (auto &I : instructions(F))
2692 NumRemainingStores += isa<StoreInst>(&I);
2693#endif
2694
2695 if (!Changed)
2696 return PreservedAnalyses::all();
2697
2698 PreservedAnalyses PA;
2699 PA.preserveSet<CFGAnalyses>();
2700 PA.preserve<GlobalsAA>();
2701 if (EnableMemorySSA)
2702 PA.preserve<MemorySSAAnalysis>();
2703 else
2704 PA.preserve<MemoryDependenceAnalysis>();
2705 return PA;
2706}
2707
2708namespace {
2709
2710/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
2711class DSELegacyPass : public FunctionPass {
2712public:
2713 static char ID; // Pass identification, replacement for typeid
2714
2715 DSELegacyPass() : FunctionPass(ID) {
2716 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
2717 }
2718
2719 bool runOnFunction(Function &F) override {
2720 if (skipFunction(F))
2721 return false;
2722
2723 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2724 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2725 const TargetLibraryInfo &TLI =
2726 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2727
2728 bool Changed = false;
2729 if (EnableMemorySSA) {
2730 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2731 PostDominatorTree &PDT =
2732 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2733
2734 Changed = eliminateDeadStoresMemorySSA(F, AA, MSSA, DT, PDT, TLI);
2735 } else {
2736 MemoryDependenceResults &MD =
2737 getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
2738
2739 Changed = eliminateDeadStores(F, &AA, &MD, &DT, &TLI);
2740 }
2741
2742#ifdef LLVM_ENABLE_STATS1
2743 if (AreStatisticsEnabled())
2744 for (auto &I : instructions(F))
2745 NumRemainingStores += isa<StoreInst>(&I);
2746#endif
2747
2748 return Changed;
2749 }
2750
2751 void getAnalysisUsage(AnalysisUsage &AU) const override {
2752 AU.setPreservesCFG();
2753 AU.addRequired<AAResultsWrapperPass>();
2754 AU.addRequired<TargetLibraryInfoWrapperPass>();
2755 AU.addPreserved<GlobalsAAWrapperPass>();
2756 AU.addRequired<DominatorTreeWrapperPass>();
2757 AU.addPreserved<DominatorTreeWrapperPass>();
2758
2759 if (EnableMemorySSA) {
2760 AU.addRequired<PostDominatorTreeWrapperPass>();
2761 AU.addRequired<MemorySSAWrapperPass>();
2762 AU.addPreserved<PostDominatorTreeWrapperPass>();
2763 AU.addPreserved<MemorySSAWrapperPass>();
2764 } else {
2765 AU.addRequired<MemoryDependenceWrapperPass>();
2766 AU.addPreserved<MemoryDependenceWrapperPass>();
2767 }
2768 }
2769};
2770
2771} // end anonymous namespace
2772
2773char DSELegacyPass::ID = 0;
2774
2775INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2776 false)static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2777INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2778INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
2779INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
2780INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
2781INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
2782INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
2783INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2784INITIALIZE_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)); }
2785 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)); }
2786
2787FunctionPass *llvm::createDeadStoreEliminationPass() {
2788 return new DSELegacyPass();
2789}