Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name DeadStoreElimination.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar -I include -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -ferror-limit 19 -fvisibility-inlines-hidden -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-26-234817-15343-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1//===- DeadStoreElimination.cpp - MemorySSA Backed 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// The code below implements dead store elimination using MemorySSA. It uses
10// the following general approach: given a MemoryDef, walk upwards to find
11// clobbering MemoryDefs that may be killed by the starting def. Then check
12// that there are no uses that may read the location of the original MemoryDef
13// in between both MemoryDefs. A bit more concretely:
14//
15// For all MemoryDefs StartDef:
16// 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking
17// upwards.
18// 2. Check that there are no reads between MaybeDeadAccess and the StartDef by
19// checking all uses starting at MaybeDeadAccess and walking until we see
20// StartDef.
21// 3. For each found CurrentDef, check that:
22// 1. There are no barrier instructions between CurrentDef and StartDef (like
23// throws or stores with ordering constraints).
24// 2. StartDef is executed whenever CurrentDef is executed.
25// 3. StartDef completely overwrites CurrentDef.
26// 4. Erase CurrentDef from the function and MemorySSA.
27//
28//===----------------------------------------------------------------------===//
29
30#include "llvm/Transforms/Scalar/DeadStoreElimination.h"
31#include "llvm/ADT/APInt.h"
32#include "llvm/ADT/DenseMap.h"
33#include "llvm/ADT/MapVector.h"
34#include "llvm/ADT/PostOrderIterator.h"
35#include "llvm/ADT/SetVector.h"
36#include "llvm/ADT/SmallPtrSet.h"
37#include "llvm/ADT/SmallVector.h"
38#include "llvm/ADT/Statistic.h"
39#include "llvm/ADT/StringRef.h"
40#include "llvm/Analysis/AliasAnalysis.h"
41#include "llvm/Analysis/CaptureTracking.h"
42#include "llvm/Analysis/GlobalsModRef.h"
43#include "llvm/Analysis/LoopInfo.h"
44#include "llvm/Analysis/MemoryBuiltins.h"
45#include "llvm/Analysis/MemoryLocation.h"
46#include "llvm/Analysis/MemorySSA.h"
47#include "llvm/Analysis/MemorySSAUpdater.h"
48#include "llvm/Analysis/MustExecute.h"
49#include "llvm/Analysis/PostDominators.h"
50#include "llvm/Analysis/TargetLibraryInfo.h"
51#include "llvm/Analysis/ValueTracking.h"
52#include "llvm/IR/Argument.h"
53#include "llvm/IR/BasicBlock.h"
54#include "llvm/IR/Constant.h"
55#include "llvm/IR/Constants.h"
56#include "llvm/IR/DataLayout.h"
57#include "llvm/IR/Dominators.h"
58#include "llvm/IR/Function.h"
59#include "llvm/IR/IRBuilder.h"
60#include "llvm/IR/InstIterator.h"
61#include "llvm/IR/InstrTypes.h"
62#include "llvm/IR/Instruction.h"
63#include "llvm/IR/Instructions.h"
64#include "llvm/IR/IntrinsicInst.h"
65#include "llvm/IR/Intrinsics.h"
66#include "llvm/IR/LLVMContext.h"
67#include "llvm/IR/Module.h"
68#include "llvm/IR/PassManager.h"
69#include "llvm/IR/PatternMatch.h"
70#include "llvm/IR/Value.h"
71#include "llvm/InitializePasses.h"
72#include "llvm/Pass.h"
73#include "llvm/Support/Casting.h"
74#include "llvm/Support/CommandLine.h"
75#include "llvm/Support/Debug.h"
76#include "llvm/Support/DebugCounter.h"
77#include "llvm/Support/ErrorHandling.h"
78#include "llvm/Support/MathExtras.h"
79#include "llvm/Support/raw_ostream.h"
80#include "llvm/Transforms/Scalar.h"
81#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
82#include "llvm/Transforms/Utils/BuildLibCalls.h"
83#include "llvm/Transforms/Utils/Local.h"
84#include <algorithm>
85#include <cassert>
86#include <cstddef>
87#include <cstdint>
88#include <iterator>
89#include <map>
90#include <utility>
91
92using namespace llvm;
93using namespace PatternMatch;
94
95#define DEBUG_TYPE"dse" "dse"
96
97STATISTIC(NumRemainingStores, "Number of stores remaining after DSE")static llvm::Statistic NumRemainingStores = {"dse", "NumRemainingStores"
, "Number of stores remaining after DSE"}
;
98STATISTIC(NumRedundantStores, "Number of redundant stores deleted")static llvm::Statistic NumRedundantStores = {"dse", "NumRedundantStores"
, "Number of redundant stores deleted"}
;
99STATISTIC(NumFastStores, "Number of stores deleted")static llvm::Statistic NumFastStores = {"dse", "NumFastStores"
, "Number of stores deleted"}
;
100STATISTIC(NumFastOther, "Number of other instrs removed")static llvm::Statistic NumFastOther = {"dse", "NumFastOther",
"Number of other instrs removed"}
;
101STATISTIC(NumCompletePartials, "Number of stores dead by later partials")static llvm::Statistic NumCompletePartials = {"dse", "NumCompletePartials"
, "Number of stores dead by later partials"}
;
102STATISTIC(NumModifiedStores, "Number of stores modified")static llvm::Statistic NumModifiedStores = {"dse", "NumModifiedStores"
, "Number of stores modified"}
;
103STATISTIC(NumCFGChecks, "Number of stores modified")static llvm::Statistic NumCFGChecks = {"dse", "NumCFGChecks",
"Number of stores modified"}
;
104STATISTIC(NumCFGTries, "Number of stores modified")static llvm::Statistic NumCFGTries = {"dse", "NumCFGTries", "Number of stores modified"
}
;
105STATISTIC(NumCFGSuccess, "Number of stores modified")static llvm::Statistic NumCFGSuccess = {"dse", "NumCFGSuccess"
, "Number of stores modified"}
;
106STATISTIC(NumGetDomMemoryDefPassed,static llvm::Statistic NumGetDomMemoryDefPassed = {"dse", "NumGetDomMemoryDefPassed"
, "Number of times a valid candidate is returned from getDomMemoryDef"
}
107 "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"
}
;
108STATISTIC(NumDomMemDefChecks,static llvm::Statistic NumDomMemDefChecks = {"dse", "NumDomMemDefChecks"
, "Number iterations check for reads in getDomMemoryDef"}
109 "Number iterations check for reads in getDomMemoryDef")static llvm::Statistic NumDomMemDefChecks = {"dse", "NumDomMemDefChecks"
, "Number iterations check for reads in getDomMemoryDef"}
;
110
111DEBUG_COUNTER(MemorySSACounter, "dse-memoryssa",static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
)
112 "Controls which MemoryDefs are eliminated.")static const unsigned MemorySSACounter = DebugCounter::registerCounter
("dse-memoryssa", "Controls which MemoryDefs are eliminated."
)
;
113
114static cl::opt<bool>
115EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking",
116 cl::init(true), cl::Hidden,
117 cl::desc("Enable partial-overwrite tracking in DSE"));
118
119static cl::opt<bool>
120EnablePartialStoreMerging("enable-dse-partial-store-merging",
121 cl::init(true), cl::Hidden,
122 cl::desc("Enable partial store merging in DSE"));
123
124static cl::opt<unsigned>
125 MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden,
126 cl::desc("The number of memory instructions to scan for "
127 "dead store elimination (default = 150)"));
128static cl::opt<unsigned> MemorySSAUpwardsStepLimit(
129 "dse-memoryssa-walklimit", cl::init(90), cl::Hidden,
130 cl::desc("The maximum number of steps while walking upwards to find "
131 "MemoryDefs that may be killed (default = 90)"));
132
133static cl::opt<unsigned> MemorySSAPartialStoreLimit(
134 "dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden,
135 cl::desc("The maximum number candidates that only partially overwrite the "
136 "killing MemoryDef to consider"
137 " (default = 5)"));
138
139static cl::opt<unsigned> MemorySSADefsPerBlockLimit(
140 "dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden,
141 cl::desc("The number of MemoryDefs we consider as candidates to eliminated "
142 "other stores per basic block (default = 5000)"));
143
144static cl::opt<unsigned> MemorySSASameBBStepCost(
145 "dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden,
146 cl::desc(
147 "The cost of a step in the same basic block as the killing MemoryDef"
148 "(default = 1)"));
149
150static cl::opt<unsigned>
151 MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5),
152 cl::Hidden,
153 cl::desc("The cost of a step in a different basic "
154 "block than the killing MemoryDef"
155 "(default = 5)"));
156
157static cl::opt<unsigned> MemorySSAPathCheckLimit(
158 "dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden,
159 cl::desc("The maximum number of blocks to check when trying to prove that "
160 "all paths to an exit go through a killing block (default = 50)"));
161
162//===----------------------------------------------------------------------===//
163// Helper functions
164//===----------------------------------------------------------------------===//
165using OverlapIntervalsTy = std::map<int64_t, int64_t>;
166using InstOverlapIntervalsTy = DenseMap<Instruction *, OverlapIntervalsTy>;
167
168/// Does this instruction write some memory? This only returns true for things
169/// that we can analyze with other helpers below.
170static bool hasAnalyzableMemoryWrite(Instruction *I,
171 const TargetLibraryInfo &TLI) {
172 if (isa<StoreInst>(I))
173 return true;
174 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
175 switch (II->getIntrinsicID()) {
176 default:
177 return false;
178 case Intrinsic::memset:
179 case Intrinsic::memmove:
180 case Intrinsic::memcpy:
181 case Intrinsic::memcpy_inline:
182 case Intrinsic::memcpy_element_unordered_atomic:
183 case Intrinsic::memmove_element_unordered_atomic:
184 case Intrinsic::memset_element_unordered_atomic:
185 case Intrinsic::init_trampoline:
186 case Intrinsic::lifetime_end:
187 case Intrinsic::masked_store:
188 return true;
189 }
190 }
191 if (auto *CB = dyn_cast<CallBase>(I)) {
192 LibFunc LF;
193 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
194 switch (LF) {
195 case LibFunc_strcpy:
196 case LibFunc_strncpy:
197 case LibFunc_strcat:
198 case LibFunc_strncat:
199 return true;
200 default:
201 return false;
202 }
203 }
204 }
205 return false;
206}
207
208/// Return a Location stored to by the specified instruction. If isRemovable
209/// returns true, this function and getLocForRead completely describe the memory
210/// operations for this instruction.
211static MemoryLocation getLocForWrite(Instruction *Inst,
212 const TargetLibraryInfo &TLI) {
213 if (StoreInst *SI
7.1
'SI' is null
7.1
'SI' is null
= dyn_cast<StoreInst>(Inst))
7
Assuming 'Inst' is not a 'StoreInst'
8
Taking false branch
214 return MemoryLocation::get(SI);
215
216 // memcpy/memmove/memset.
217 if (auto *MI
9.1
'MI' is null
9.1
'MI' is null
= dyn_cast<AnyMemIntrinsic>(Inst))
9
Assuming 'Inst' is not a 'AnyMemIntrinsic'
10
Taking false branch
218 return MemoryLocation::getForDest(MI);
219
220 if (IntrinsicInst *II
11.1
'II' is non-null
11.1
'II' is non-null
= dyn_cast<IntrinsicInst>(Inst)) {
11
Assuming 'Inst' is a 'IntrinsicInst'
12
Taking true branch
221 switch (II->getIntrinsicID()) {
13
Control jumps to the 'default' case at line 222
222 default:
223 return MemoryLocation(); // Unhandled intrinsic.
14
Calling default constructor for 'MemoryLocation'
16
Returning from default constructor for 'MemoryLocation'
224 case Intrinsic::init_trampoline:
225 return MemoryLocation::getAfter(II->getArgOperand(0));
226 case Intrinsic::masked_store:
227 return MemoryLocation::getForArgument(II, 1, TLI);
228 case Intrinsic::lifetime_end: {
229 uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
230 return MemoryLocation(II->getArgOperand(1), Len);
231 }
232 }
233 }
234 if (auto *CB = dyn_cast<CallBase>(Inst))
235 // All the supported TLI functions so far happen to have dest as their
236 // first argument.
237 return MemoryLocation::getAfter(CB->getArgOperand(0));
238 return MemoryLocation();
239}
240
241/// If the value of this instruction and the memory it writes to is unused, may
242/// we delete this instruction?
243static bool isRemovable(Instruction *I) {
244 // Don't remove volatile/atomic stores.
245 if (StoreInst *SI = dyn_cast<StoreInst>(I))
246 return SI->isUnordered();
247
248 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
249 switch (II->getIntrinsicID()) {
250 default: llvm_unreachable("doesn't pass 'hasAnalyzableMemoryWrite' predicate")::llvm::llvm_unreachable_internal("doesn't pass 'hasAnalyzableMemoryWrite' predicate"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 250)
;
251 case Intrinsic::lifetime_end:
252 // Never remove dead lifetime_end's, e.g. because it is followed by a
253 // free.
254 return false;
255 case Intrinsic::init_trampoline:
256 // Always safe to remove init_trampoline.
257 return true;
258 case Intrinsic::memset:
259 case Intrinsic::memmove:
260 case Intrinsic::memcpy:
261 case Intrinsic::memcpy_inline:
262 // Don't remove volatile memory intrinsics.
263 return !cast<MemIntrinsic>(II)->isVolatile();
264 case Intrinsic::memcpy_element_unordered_atomic:
265 case Intrinsic::memmove_element_unordered_atomic:
266 case Intrinsic::memset_element_unordered_atomic:
267 case Intrinsic::masked_store:
268 return true;
269 }
270 }
271
272 // note: only get here for calls with analyzable writes - i.e. libcalls
273 if (auto *CB = dyn_cast<CallBase>(I))
274 return CB->use_empty();
275
276 return false;
277}
278
279/// Returns true if the end of this instruction can be safely shortened in
280/// length.
281static bool isShortenableAtTheEnd(Instruction *I) {
282 // Don't shorten stores for now
283 if (isa<StoreInst>(I))
284 return false;
285
286 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
287 switch (II->getIntrinsicID()) {
288 default: return false;
289 case Intrinsic::memset:
290 case Intrinsic::memcpy:
291 case Intrinsic::memcpy_element_unordered_atomic:
292 case Intrinsic::memset_element_unordered_atomic:
293 // Do shorten memory intrinsics.
294 // FIXME: Add memmove if it's also safe to transform.
295 return true;
296 }
297 }
298
299 // Don't shorten libcalls calls for now.
300
301 return false;
302}
303
304/// Returns true if the beginning of this instruction can be safely shortened
305/// in length.
306static bool isShortenableAtTheBeginning(Instruction *I) {
307 // FIXME: Handle only memset for now. Supporting memcpy/memmove should be
308 // easily done by offsetting the source address.
309 return isa<AnyMemSetInst>(I);
310}
311
312static uint64_t getPointerSize(const Value *V, const DataLayout &DL,
313 const TargetLibraryInfo &TLI,
314 const Function *F) {
315 uint64_t Size;
316 ObjectSizeOpts Opts;
317 Opts.NullIsUnknownSize = NullPointerIsDefined(F);
318
319 if (getObjectSize(V, Size, DL, &TLI, Opts))
320 return Size;
321 return MemoryLocation::UnknownSize;
322}
323
324namespace {
325
326enum OverwriteResult {
327 OW_Begin,
328 OW_Complete,
329 OW_End,
330 OW_PartialEarlierWithFullLater,
331 OW_MaybePartial,
332 OW_Unknown
333};
334
335} // end anonymous namespace
336
337/// Check if two instruction are masked stores that completely
338/// overwrite one another. More specifically, \p KillingI has to
339/// overwrite \p DeadI.
340static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,
341 const Instruction *DeadI,
342 BatchAAResults &AA) {
343 const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
344 const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
345 if (KillingII == nullptr || DeadII == nullptr)
346 return OW_Unknown;
347 if (KillingII->getIntrinsicID() != Intrinsic::masked_store ||
348 DeadII->getIntrinsicID() != Intrinsic::masked_store)
349 return OW_Unknown;
350 // Pointers.
351 Value *KillingPtr = KillingII->getArgOperand(1)->stripPointerCasts();
352 Value *DeadPtr = DeadII->getArgOperand(1)->stripPointerCasts();
353 if (KillingPtr != DeadPtr && !AA.isMustAlias(KillingPtr, DeadPtr))
354 return OW_Unknown;
355 // Masks.
356 // TODO: check that KillingII's mask is a superset of the DeadII's mask.
357 if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
358 return OW_Unknown;
359 return OW_Complete;
360}
361
362/// Return 'OW_Complete' if a store to the 'KillingLoc' location completely
363/// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the
364/// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin'
365/// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.
366/// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was
367/// overwritten by a killing (smaller) store which doesn't write outside the big
368/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
369/// NOTE: This function must only be called if both \p KillingLoc and \p
370/// DeadLoc belong to the same underlying object with valid \p KillingOff and
371/// \p DeadOff.
372static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc,
373 const MemoryLocation &DeadLoc,
374 int64_t KillingOff, int64_t DeadOff,
375 Instruction *DeadI,
376 InstOverlapIntervalsTy &IOL) {
377 const uint64_t KillingSize = KillingLoc.Size.getValue();
378 const uint64_t DeadSize = DeadLoc.Size.getValue();
379 // We may now overlap, although the overlap is not complete. There might also
380 // be other incomplete overlaps, and together, they might cover the complete
381 // dead store.
382 // Note: The correctness of this logic depends on the fact that this function
383 // is not even called providing DepWrite when there are any intervening reads.
384 if (EnablePartialOverwriteTracking &&
385 KillingOff < int64_t(DeadOff + DeadSize) &&
386 int64_t(KillingOff + KillingSize) >= DeadOff) {
387
388 // Insert our part of the overlap into the map.
389 auto &IM = IOL[DeadI];
390 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") KillingLoc [" << KillingOff << ", "
<< int64_t(KillingOff + KillingSize) << ")\n"; }
} while (false)
391 << int64_t(DeadOff + DeadSize) << ") KillingLoc ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") KillingLoc [" << KillingOff << ", "
<< int64_t(KillingOff + KillingSize) << ")\n"; }
} while (false)
392 << KillingOff << ", " << int64_t(KillingOff + KillingSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") KillingLoc [" << KillingOff << ", "
<< int64_t(KillingOff + KillingSize) << ")\n"; }
} while (false)
393 << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") KillingLoc [" << KillingOff << ", "
<< int64_t(KillingOff + KillingSize) << ")\n"; }
} while (false)
;
394
395 // Make sure that we only insert non-overlapping intervals and combine
396 // adjacent intervals. The intervals are stored in the map with the ending
397 // offset as the key (in the half-open sense) and the starting offset as
398 // the value.
399 int64_t KillingIntStart = KillingOff;
400 int64_t KillingIntEnd = KillingOff + KillingSize;
401
402 // Find any intervals ending at, or after, KillingIntStart which start
403 // before KillingIntEnd.
404 auto ILI = IM.lower_bound(KillingIntStart);
405 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
406 // This existing interval is overlapped with the current store somewhere
407 // in [KillingIntStart, KillingIntEnd]. Merge them by erasing the existing
408 // intervals and adjusting our start and end.
409 KillingIntStart = std::min(KillingIntStart, ILI->second);
410 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
411 ILI = IM.erase(ILI);
412
413 // Continue erasing and adjusting our end in case other previous
414 // intervals are also overlapped with the current store.
415 //
416 // |--- dead 1 ---| |--- dead 2 ---|
417 // |------- killing---------|
418 //
419 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
420 assert(ILI->second > KillingIntStart && "Unexpected interval")(static_cast <bool> (ILI->second > KillingIntStart
&& "Unexpected interval") ? void (0) : __assert_fail
("ILI->second > KillingIntStart && \"Unexpected interval\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 420, __extension__ __PRETTY_FUNCTION__))
;
421 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
422 ILI = IM.erase(ILI);
423 }
424 }
425
426 IM[KillingIntEnd] = KillingIntStart;
427
428 ILI = IM.begin();
429 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
430 LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") Composite KillingLoc [" << ILI->second
<< ", " << ILI->first << ")\n"; } } while
(false)
431 << DeadOff << ", " << int64_t(DeadOff + DeadSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") Composite KillingLoc [" << ILI->second
<< ", " << ILI->first << ")\n"; } } while
(false)
432 << ") Composite KillingLoc [" << ILI->second << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") Composite KillingLoc [" << ILI->second
<< ", " << ILI->first << ")\n"; } } while
(false)
433 << ILI->first << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") Composite KillingLoc [" << ILI->second
<< ", " << ILI->first << ")\n"; } } while
(false)
;
434 ++NumCompletePartials;
435 return OW_Complete;
436 }
437 }
438
439 // Check for a dead store which writes to all the memory locations that
440 // the killing store writes to.
441 if (EnablePartialStoreMerging && KillingOff >= DeadOff &&
442 int64_t(DeadOff + DeadSize) > KillingOff &&
443 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
444 LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOffdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite a dead load ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") by a killing store [" << KillingOff <<
", " << int64_t(KillingOff + KillingSize) << ")\n"
; } } while (false)
445 << ", " << int64_t(DeadOff + DeadSize)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite a dead load ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") by a killing store [" << KillingOff <<
", " << int64_t(KillingOff + KillingSize) << ")\n"
; } } while (false)
446 << ") by a killing store [" << KillingOff << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite a dead load ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") by a killing store [" << KillingOff <<
", " << int64_t(KillingOff + KillingSize) << ")\n"
; } } while (false)
447 << int64_t(KillingOff + KillingSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Partial overwrite a dead load ["
<< DeadOff << ", " << int64_t(DeadOff + DeadSize
) << ") by a killing store [" << KillingOff <<
", " << int64_t(KillingOff + KillingSize) << ")\n"
; } } while (false)
;
448 // TODO: Maybe come up with a better name?
449 return OW_PartialEarlierWithFullLater;
450 }
451
452 // Another interesting case is if the killing store overwrites the end of the
453 // dead store.
454 //
455 // |--dead--|
456 // |-- killing --|
457 //
458 // In this case we may want to trim the size of dead store to avoid
459 // generating stores to addresses which will definitely be overwritten killing
460 // store.
461 if (!EnablePartialOverwriteTracking &&
462 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
463 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
464 return OW_End;
465
466 // Finally, we also need to check if the killing store overwrites the
467 // beginning of the dead store.
468 //
469 // |--dead--|
470 // |-- killing --|
471 //
472 // In this case we may want to move the destination address and trim the size
473 // of dead store to avoid generating stores to addresses which will definitely
474 // be overwritten killing store.
475 if (!EnablePartialOverwriteTracking &&
476 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
477 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&(static_cast <bool> (int64_t(KillingOff + KillingSize) <
int64_t(DeadOff + DeadSize) && "Expect to be handled as OW_Complete"
) ? void (0) : __assert_fail ("int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 478, __extension__ __PRETTY_FUNCTION__))
478 "Expect to be handled as OW_Complete")(static_cast <bool> (int64_t(KillingOff + KillingSize) <
int64_t(DeadOff + DeadSize) && "Expect to be handled as OW_Complete"
) ? void (0) : __assert_fail ("int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) && \"Expect to be handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 478, __extension__ __PRETTY_FUNCTION__))
;
479 return OW_Begin;
480 }
481 // Otherwise, they don't completely overlap.
482 return OW_Unknown;
483}
484
485/// Returns true if the memory which is accessed by the second instruction is not
486/// modified between the first and the second instruction.
487/// Precondition: Second instruction must be dominated by the first
488/// instruction.
489static bool
490memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI,
491 BatchAAResults &AA, const DataLayout &DL,
492 DominatorTree *DT) {
493 // Do a backwards scan through the CFG from SecondI to FirstI. Look for
494 // instructions which can modify the memory location accessed by SecondI.
495 //
496 // While doing the walk keep track of the address to check. It might be
497 // different in different basic blocks due to PHI translation.
498 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
499 SmallVector<BlockAddressPair, 16> WorkList;
500 // Keep track of the address we visited each block with. Bail out if we
501 // visit a block with different addresses.
502 DenseMap<BasicBlock *, Value *> Visited;
503
504 BasicBlock::iterator FirstBBI(FirstI);
505 ++FirstBBI;
506 BasicBlock::iterator SecondBBI(SecondI);
507 BasicBlock *FirstBB = FirstI->getParent();
508 BasicBlock *SecondBB = SecondI->getParent();
509 MemoryLocation MemLoc;
510 if (auto *MemSet = dyn_cast<MemSetInst>(SecondI))
511 MemLoc = MemoryLocation::getForDest(MemSet);
512 else
513 MemLoc = MemoryLocation::get(SecondI);
514
515 auto *MemLocPtr = const_cast<Value *>(MemLoc.Ptr);
516
517 // Start checking the SecondBB.
518 WorkList.push_back(
519 std::make_pair(SecondBB, PHITransAddr(MemLocPtr, DL, nullptr)));
520 bool isFirstBlock = true;
521
522 // Check all blocks going backward until we reach the FirstBB.
523 while (!WorkList.empty()) {
524 BlockAddressPair Current = WorkList.pop_back_val();
525 BasicBlock *B = Current.first;
526 PHITransAddr &Addr = Current.second;
527 Value *Ptr = Addr.getAddr();
528
529 // Ignore instructions before FirstI if this is the FirstBB.
530 BasicBlock::iterator BI = (B == FirstBB ? FirstBBI : B->begin());
531
532 BasicBlock::iterator EI;
533 if (isFirstBlock) {
534 // Ignore instructions after SecondI if this is the first visit of SecondBB.
535 assert(B == SecondBB && "first block is not the store block")(static_cast <bool> (B == SecondBB && "first block is not the store block"
) ? void (0) : __assert_fail ("B == SecondBB && \"first block is not the store block\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 535, __extension__ __PRETTY_FUNCTION__))
;
536 EI = SecondBBI;
537 isFirstBlock = false;
538 } else {
539 // It's not SecondBB or (in case of a loop) the second visit of SecondBB.
540 // In this case we also have to look at instructions after SecondI.
541 EI = B->end();
542 }
543 for (; BI != EI; ++BI) {
544 Instruction *I = &*BI;
545 if (I->mayWriteToMemory() && I != SecondI)
546 if (isModSet(AA.getModRefInfo(I, MemLoc.getWithNewPtr(Ptr))))
547 return false;
548 }
549 if (B != FirstBB) {
550 assert(B != &FirstBB->getParent()->getEntryBlock() &&(static_cast <bool> (B != &FirstBB->getParent()->
getEntryBlock() && "Should not hit the entry block because SI must be dominated by LI"
) ? 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-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 551, __extension__ __PRETTY_FUNCTION__))
551 "Should not hit the entry block because SI must be dominated by LI")(static_cast <bool> (B != &FirstBB->getParent()->
getEntryBlock() && "Should not hit the entry block because SI must be dominated by LI"
) ? 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-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 551, __extension__ __PRETTY_FUNCTION__))
;
552 for (BasicBlock *Pred : predecessors(B)) {
553 PHITransAddr PredAddr = Addr;
554 if (PredAddr.NeedsPHITranslationFromBlock(B)) {
555 if (!PredAddr.IsPotentiallyPHITranslatable())
556 return false;
557 if (PredAddr.PHITranslateValue(B, Pred, DT, false))
558 return false;
559 }
560 Value *TranslatedPtr = PredAddr.getAddr();
561 auto Inserted = Visited.insert(std::make_pair(Pred, TranslatedPtr));
562 if (!Inserted.second) {
563 // We already visited this block before. If it was with a different
564 // address - bail out!
565 if (TranslatedPtr != Inserted.first->second)
566 return false;
567 // ... otherwise just skip it.
568 continue;
569 }
570 WorkList.push_back(std::make_pair(Pred, PredAddr));
571 }
572 }
573 }
574 return true;
575}
576
577static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,
578 uint64_t &DeadSize, int64_t KillingStart,
579 uint64_t KillingSize, bool IsOverwriteEnd) {
580 auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
581 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
582
583 // We assume that memet/memcpy operates in chunks of the "largest" native
584 // type size and aligned on the same value. That means optimal start and size
585 // of memset/memcpy should be modulo of preferred alignment of that type. That
586 // is it there is no any sense in trying to reduce store size any further
587 // since any "extra" stores comes for free anyway.
588 // On the other hand, maximum alignment we can achieve is limited by alignment
589 // of initial store.
590
591 // TODO: Limit maximum alignment by preferred (or abi?) alignment of the
592 // "largest" native type.
593 // Note: What is the proper way to get that value?
594 // Should TargetTransformInfo::getRegisterBitWidth be used or anything else?
595 // PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);
596
597 int64_t ToRemoveStart = 0;
598 uint64_t ToRemoveSize = 0;
599 // Compute start and size of the region to remove. Make sure 'PrefAlign' is
600 // maintained on the remaining store.
601 if (IsOverwriteEnd) {
602 // Calculate required adjustment for 'KillingStart' in order to keep
603 // remaining store size aligned on 'PerfAlign'.
604 uint64_t Off =
605 offsetToAlignment(uint64_t(KillingStart - DeadStart), PrefAlign);
606 ToRemoveStart = KillingStart + Off;
607 if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))
608 return false;
609 ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);
610 } else {
611 ToRemoveStart = DeadStart;
612 assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&(static_cast <bool> (KillingSize >= uint64_t(DeadStart
- KillingStart) && "Not overlapping accesses?") ? void
(0) : __assert_fail ("KillingSize >= uint64_t(DeadStart - KillingStart) && \"Not overlapping accesses?\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 613, __extension__ __PRETTY_FUNCTION__))
613 "Not overlapping accesses?")(static_cast <bool> (KillingSize >= uint64_t(DeadStart
- KillingStart) && "Not overlapping accesses?") ? void
(0) : __assert_fail ("KillingSize >= uint64_t(DeadStart - KillingStart) && \"Not overlapping accesses?\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 613, __extension__ __PRETTY_FUNCTION__))
;
614 ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);
615 // Calculate required adjustment for 'ToRemoveSize'in order to keep
616 // start of the remaining store aligned on 'PerfAlign'.
617 uint64_t Off = offsetToAlignment(ToRemoveSize, PrefAlign);
618 if (Off != 0) {
619 if (ToRemoveSize <= (PrefAlign.value() - Off))
620 return false;
621 ToRemoveSize -= PrefAlign.value() - Off;
622 }
623 assert(isAligned(PrefAlign, ToRemoveSize) &&(static_cast <bool> (isAligned(PrefAlign, ToRemoveSize)
&& "Should preserve selected alignment") ? void (0) :
__assert_fail ("isAligned(PrefAlign, ToRemoveSize) && \"Should preserve selected alignment\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 624, __extension__ __PRETTY_FUNCTION__))
624 "Should preserve selected alignment")(static_cast <bool> (isAligned(PrefAlign, ToRemoveSize)
&& "Should preserve selected alignment") ? void (0) :
__assert_fail ("isAligned(PrefAlign, ToRemoveSize) && \"Should preserve selected alignment\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 624, __extension__ __PRETTY_FUNCTION__))
;
625 }
626
627 assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove")(static_cast <bool> (ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove"
) ? void (0) : __assert_fail ("ToRemoveSize > 0 && \"Shouldn't reach here if nothing to remove\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 627, __extension__ __PRETTY_FUNCTION__))
;
628 assert(DeadSize > ToRemoveSize && "Can't remove more than original size")(static_cast <bool> (DeadSize > ToRemoveSize &&
"Can't remove more than original size") ? void (0) : __assert_fail
("DeadSize > ToRemoveSize && \"Can't remove more than original size\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 628, __extension__ __PRETTY_FUNCTION__))
;
629
630 uint64_t NewSize = DeadSize - ToRemoveSize;
631 if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
632 // When shortening an atomic memory intrinsic, the newly shortened
633 // length must remain an integer multiple of the element size.
634 const uint32_t ElementSize = AMI->getElementSizeInBytes();
635 if (0 != NewSize % ElementSize)
636 return false;
637 }
638
639 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") << ": " << *DeadI
<< "\n KILLER [" << ToRemoveStart << ", "
<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n"
; } } while (false)
640 << (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
<< "\n KILLER [" << ToRemoveStart << ", "
<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n"
; } } while (false)
641 << "\n KILLER [" << ToRemoveStart << ", "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
<< "\n KILLER [" << ToRemoveStart << ", "
<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n"
; } } while (false)
642 << int64_t(ToRemoveStart + ToRemoveSize) << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n OW " <<
(IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
<< "\n KILLER [" << ToRemoveStart << ", "
<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n"
; } } while (false)
;
643
644 Value *DeadWriteLength = DeadIntrinsic->getLength();
645 Value *TrimmedLength = ConstantInt::get(DeadWriteLength->getType(), NewSize);
646 DeadIntrinsic->setLength(TrimmedLength);
647 DeadIntrinsic->setDestAlignment(PrefAlign);
648
649 if (!IsOverwriteEnd) {
650 Value *OrigDest = DeadIntrinsic->getRawDest();
651 Type *Int8PtrTy =
652 Type::getInt8PtrTy(DeadIntrinsic->getContext(),
653 OrigDest->getType()->getPointerAddressSpace());
654 Value *Dest = OrigDest;
655 if (OrigDest->getType() != Int8PtrTy)
656 Dest = CastInst::CreatePointerCast(OrigDest, Int8PtrTy, "", DeadI);
657 Value *Indices[1] = {
658 ConstantInt::get(DeadWriteLength->getType(), ToRemoveSize)};
659 Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(
660 Type::getInt8Ty(DeadIntrinsic->getContext()), Dest, Indices, "", DeadI);
661 NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());
662 if (NewDestGEP->getType() != OrigDest->getType())
663 NewDestGEP = CastInst::CreatePointerCast(NewDestGEP, OrigDest->getType(),
664 "", DeadI);
665 DeadIntrinsic->setDest(NewDestGEP);
666 }
667
668 // Finally update start and size of dead access.
669 if (!IsOverwriteEnd)
670 DeadStart += ToRemoveSize;
671 DeadSize = NewSize;
672
673 return true;
674}
675
676static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap,
677 int64_t &DeadStart, uint64_t &DeadSize) {
678 if (IntervalMap.empty() || !isShortenableAtTheEnd(DeadI))
679 return false;
680
681 OverlapIntervalsTy::iterator OII = --IntervalMap.end();
682 int64_t KillingStart = OII->second;
683 uint64_t KillingSize = OII->first - KillingStart;
684
685 assert(OII->first - KillingStart >= 0 && "Size expected to be positive")(static_cast <bool> (OII->first - KillingStart >=
0 && "Size expected to be positive") ? void (0) : __assert_fail
("OII->first - KillingStart >= 0 && \"Size expected to be positive\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 685, __extension__ __PRETTY_FUNCTION__))
;
686
687 if (KillingStart > DeadStart &&
688 // Note: "KillingStart - KillingStart" is known to be positive due to
689 // preceding check.
690 (uint64_t)(KillingStart - DeadStart) < DeadSize &&
691 // Note: "DeadSize - (uint64_t)(KillingStart - DeadStart)" is known to
692 // be non negative due to preceding checks.
693 KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {
694 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
695 true)) {
696 IntervalMap.erase(OII);
697 return true;
698 }
699 }
700 return false;
701}
702
703static bool tryToShortenBegin(Instruction *DeadI,
704 OverlapIntervalsTy &IntervalMap,
705 int64_t &DeadStart, uint64_t &DeadSize) {
706 if (IntervalMap.empty() || !isShortenableAtTheBeginning(DeadI))
707 return false;
708
709 OverlapIntervalsTy::iterator OII = IntervalMap.begin();
710 int64_t KillingStart = OII->second;
711 uint64_t KillingSize = OII->first - KillingStart;
712
713 assert(OII->first - KillingStart >= 0 && "Size expected to be positive")(static_cast <bool> (OII->first - KillingStart >=
0 && "Size expected to be positive") ? void (0) : __assert_fail
("OII->first - KillingStart >= 0 && \"Size expected to be positive\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 713, __extension__ __PRETTY_FUNCTION__))
;
714
715 if (KillingStart <= DeadStart &&
716 // Note: "DeadStart - KillingStart" is known to be non negative due to
717 // preceding check.
718 KillingSize > (uint64_t)(DeadStart - KillingStart)) {
719 // Note: "KillingSize - (uint64_t)(DeadStart - DeadStart)" is known to
720 // be positive due to preceding checks.
721 assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&(static_cast <bool> (KillingSize - (uint64_t)(DeadStart
- KillingStart) < DeadSize && "Should have been handled as OW_Complete"
) ? void (0) : __assert_fail ("KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 722, __extension__ __PRETTY_FUNCTION__))
722 "Should have been handled as OW_Complete")(static_cast <bool> (KillingSize - (uint64_t)(DeadStart
- KillingStart) < DeadSize && "Should have been handled as OW_Complete"
) ? void (0) : __assert_fail ("KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize && \"Should have been handled as OW_Complete\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 722, __extension__ __PRETTY_FUNCTION__))
;
723 if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
724 false)) {
725 IntervalMap.erase(OII);
726 return true;
727 }
728 }
729 return false;
730}
731
732static bool removePartiallyOverlappedStores(const DataLayout &DL,
733 InstOverlapIntervalsTy &IOL,
734 const TargetLibraryInfo &TLI) {
735 bool Changed = false;
736 for (auto OI : IOL) {
737 Instruction *DeadI = OI.first;
738 MemoryLocation Loc = getLocForWrite(DeadI, TLI);
6
Calling 'getLocForWrite'
17
Returning from 'getLocForWrite'
739 assert(isRemovable(DeadI) && "Expect only removable instruction")(static_cast <bool> (isRemovable(DeadI) && "Expect only removable instruction"
) ? void (0) : __assert_fail ("isRemovable(DeadI) && \"Expect only removable instruction\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 739, __extension__ __PRETTY_FUNCTION__))
;
18
'?' condition is true
740
741 const Value *Ptr = Loc.Ptr->stripPointerCasts();
19
Called C++ object pointer is null
742 int64_t DeadStart = 0;
743 uint64_t DeadSize = Loc.Size.getValue();
744 GetPointerBaseWithConstantOffset(Ptr, DeadStart, DL);
745 OverlapIntervalsTy &IntervalMap = OI.second;
746 Changed |= tryToShortenEnd(DeadI, IntervalMap, DeadStart, DeadSize);
747 if (IntervalMap.empty())
748 continue;
749 Changed |= tryToShortenBegin(DeadI, IntervalMap, DeadStart, DeadSize);
750 }
751 return Changed;
752}
753
754static Constant *
755tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI,
756 int64_t KillingOffset, int64_t DeadOffset,
757 const DataLayout &DL, BatchAAResults &AA,
758 DominatorTree *DT) {
759
760 if (DeadI && isa<ConstantInt>(DeadI->getValueOperand()) &&
761 DL.typeSizeEqualsStoreSize(DeadI->getValueOperand()->getType()) &&
762 KillingI && isa<ConstantInt>(KillingI->getValueOperand()) &&
763 DL.typeSizeEqualsStoreSize(KillingI->getValueOperand()->getType()) &&
764 memoryIsNotModifiedBetween(DeadI, KillingI, AA, DL, DT)) {
765 // If the store we find is:
766 // a) partially overwritten by the store to 'Loc'
767 // b) the killing store is fully contained in the dead one and
768 // c) they both have a constant value
769 // d) none of the two stores need padding
770 // Merge the two stores, replacing the dead store's value with a
771 // merge of both values.
772 // TODO: Deal with other constant types (vectors, etc), and probably
773 // some mem intrinsics (if needed)
774
775 APInt DeadValue = cast<ConstantInt>(DeadI->getValueOperand())->getValue();
776 APInt KillingValue =
777 cast<ConstantInt>(KillingI->getValueOperand())->getValue();
778 unsigned KillingBits = KillingValue.getBitWidth();
779 assert(DeadValue.getBitWidth() > KillingValue.getBitWidth())(static_cast <bool> (DeadValue.getBitWidth() > KillingValue
.getBitWidth()) ? void (0) : __assert_fail ("DeadValue.getBitWidth() > KillingValue.getBitWidth()"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 779, __extension__ __PRETTY_FUNCTION__))
;
780 KillingValue = KillingValue.zext(DeadValue.getBitWidth());
781
782 // Offset of the smaller store inside the larger store
783 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
784 unsigned LShiftAmount =
785 DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits
786 : BitOffsetDiff;
787 APInt Mask = APInt::getBitsSet(DeadValue.getBitWidth(), LShiftAmount,
788 LShiftAmount + KillingBits);
789 // Clear the bits we'll be replacing, then OR with the smaller
790 // store, shifted appropriately.
791 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
792 LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Dead: " << *DeadIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Dead: " <<
*DeadI << "\n Killing: " << *KillingI << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
793 << "\n Killing: " << *KillingIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Dead: " <<
*DeadI << "\n Killing: " << *KillingI << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
794 << "\n Merged Value: " << Merged << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Merge Stores:\n Dead: " <<
*DeadI << "\n Killing: " << *KillingI << "\n Merged Value: "
<< Merged << '\n'; } } while (false)
;
795 return ConstantInt::get(DeadI->getValueOperand()->getType(), Merged);
796 }
797 return nullptr;
798}
799
800namespace {
801// Returns true if \p I is an intrisnic that does not read or write memory.
802bool isNoopIntrinsic(Instruction *I) {
803 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
804 switch (II->getIntrinsicID()) {
805 case Intrinsic::lifetime_start:
806 case Intrinsic::lifetime_end:
807 case Intrinsic::invariant_end:
808 case Intrinsic::launder_invariant_group:
809 case Intrinsic::assume:
810 return true;
811 case Intrinsic::dbg_addr:
812 case Intrinsic::dbg_declare:
813 case Intrinsic::dbg_label:
814 case Intrinsic::dbg_value:
815 llvm_unreachable("Intrinsic should not be modeled in MemorySSA")::llvm::llvm_unreachable_internal("Intrinsic should not be modeled in MemorySSA"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 815)
;
816 default:
817 return false;
818 }
819 }
820 return false;
821}
822
823// Check if we can ignore \p D for DSE.
824bool canSkipDef(MemoryDef *D, bool DefVisibleToCaller,
825 const TargetLibraryInfo &TLI) {
826 Instruction *DI = D->getMemoryInst();
827 // Calls that only access inaccessible memory cannot read or write any memory
828 // locations we consider for elimination.
829 if (auto *CB = dyn_cast<CallBase>(DI))
830 if (CB->onlyAccessesInaccessibleMemory()) {
831 if (isAllocLikeFn(DI, &TLI))
832 return false;
833 return true;
834 }
835 // We can eliminate stores to locations not visible to the caller across
836 // throwing instructions.
837 if (DI->mayThrow() && !DefVisibleToCaller)
838 return true;
839
840 // We can remove the dead stores, irrespective of the fence and its ordering
841 // (release/acquire/seq_cst). Fences only constraints the ordering of
842 // already visible stores, it does not make a store visible to other
843 // threads. So, skipping over a fence does not change a store from being
844 // dead.
845 if (isa<FenceInst>(DI))
846 return true;
847
848 // Skip intrinsics that do not really read or modify memory.
849 if (isNoopIntrinsic(DI))
850 return true;
851
852 return false;
853}
854
855struct DSEState {
856 Function &F;
857 AliasAnalysis &AA;
858 EarliestEscapeInfo EI;
859
860 /// The single BatchAA instance that is used to cache AA queries. It will
861 /// not be invalidated over the whole run. This is safe, because:
862 /// 1. Only memory writes are removed, so the alias cache for memory
863 /// locations remains valid.
864 /// 2. No new instructions are added (only instructions removed), so cached
865 /// information for a deleted value cannot be accessed by a re-used new
866 /// value pointer.
867 BatchAAResults BatchAA;
868
869 MemorySSA &MSSA;
870 DominatorTree &DT;
871 PostDominatorTree &PDT;
872 const TargetLibraryInfo &TLI;
873 const DataLayout &DL;
874 const LoopInfo &LI;
875
876 // Whether the function contains any irreducible control flow, useful for
877 // being accurately able to detect loops.
878 bool ContainsIrreducibleLoops;
879
880 // All MemoryDefs that potentially could kill other MemDefs.
881 SmallVector<MemoryDef *, 64> MemDefs;
882 // Any that should be skipped as they are already deleted
883 SmallPtrSet<MemoryAccess *, 4> SkipStores;
884 // Keep track of all of the objects that are invisible to the caller before
885 // the function returns.
886 // SmallPtrSet<const Value *, 16> InvisibleToCallerBeforeRet;
887 DenseMap<const Value *, bool> InvisibleToCallerBeforeRet;
888 // Keep track of all of the objects that are invisible to the caller after
889 // the function returns.
890 DenseMap<const Value *, bool> InvisibleToCallerAfterRet;
891 // Keep track of blocks with throwing instructions not modeled in MemorySSA.
892 SmallPtrSet<BasicBlock *, 16> ThrowingBlocks;
893 // Post-order numbers for each basic block. Used to figure out if memory
894 // accesses are executed before another access.
895 DenseMap<BasicBlock *, unsigned> PostOrderNumbers;
896
897 /// Keep track of instructions (partly) overlapping with killing MemoryDefs per
898 /// basic block.
899 DenseMap<BasicBlock *, InstOverlapIntervalsTy> IOLs;
900
901 DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT,
902 PostDominatorTree &PDT, const TargetLibraryInfo &TLI,
903 const LoopInfo &LI)
904 : F(F), AA(AA), EI(DT, LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT),
905 PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) {}
906
907 static DSEState get(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
908 DominatorTree &DT, PostDominatorTree &PDT,
909 const TargetLibraryInfo &TLI, const LoopInfo &LI) {
910 DSEState State(F, AA, MSSA, DT, PDT, TLI, LI);
911 // Collect blocks with throwing instructions not modeled in MemorySSA and
912 // alloc-like objects.
913 unsigned PO = 0;
914 for (BasicBlock *BB : post_order(&F)) {
915 State.PostOrderNumbers[BB] = PO++;
916 for (Instruction &I : *BB) {
917 MemoryAccess *MA = MSSA.getMemoryAccess(&I);
918 if (I.mayThrow() && !MA)
919 State.ThrowingBlocks.insert(I.getParent());
920
921 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
922 if (MD && State.MemDefs.size() < MemorySSADefsPerBlockLimit &&
923 (State.getLocForWriteEx(&I) || State.isMemTerminatorInst(&I)))
924 State.MemDefs.push_back(MD);
925 }
926 }
927
928 // Treat byval or inalloca arguments the same as Allocas, stores to them are
929 // dead at the end of the function.
930 for (Argument &AI : F.args())
931 if (AI.hasPassPointeeByValueCopyAttr()) {
932 // For byval, the caller doesn't know the address of the allocation.
933 if (AI.hasByValAttr())
934 State.InvisibleToCallerBeforeRet.insert({&AI, true});
935 State.InvisibleToCallerAfterRet.insert({&AI, true});
936 }
937
938 // Collect whether there is any irreducible control flow in the function.
939 State.ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);
940
941 return State;
942 }
943
944 /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
945 /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
946 /// location (by \p DeadI instruction).
947 /// Return OW_MaybePartial if \p KillingI does not completely overwrite
948 /// \p DeadI, but they both write to the same underlying object. In that
949 /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
950 /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
951 OverwriteResult isOverwrite(const Instruction *KillingI,
952 const Instruction *DeadI,
953 const MemoryLocation &KillingLoc,
954 const MemoryLocation &DeadLoc,
955 int64_t &KillingOff, int64_t &DeadOff) {
956 // AliasAnalysis does not always account for loops. Limit overwrite checks
957 // to dependencies for which we can guarantee they are independent of any
958 // loops they are in.
959 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
960 return OW_Unknown;
961
962 // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
963 // get imprecise values here, though (except for unknown sizes).
964 if (!KillingLoc.Size.isPrecise() || !DeadLoc.Size.isPrecise()) {
965 // In case no constant size is known, try to an IR values for the number
966 // of bytes written and check if they match.
967 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
968 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
969 if (KillingMemI && DeadMemI) {
970 const Value *KillingV = KillingMemI->getLength();
971 const Value *DeadV = DeadMemI->getLength();
972 if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))
973 return OW_Complete;
974 }
975
976 // Masked stores have imprecise locations, but we can reason about them
977 // to some extent.
978 return isMaskedStoreOverwrite(KillingI, DeadI, BatchAA);
979 }
980
981 const uint64_t KillingSize = KillingLoc.Size.getValue();
982 const uint64_t DeadSize = DeadLoc.Size.getValue();
983
984 // Query the alias information
985 AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);
986
987 // If the start pointers are the same, we just have to compare sizes to see if
988 // the killing store was larger than the dead store.
989 if (AAR == AliasResult::MustAlias) {
990 // Make sure that the KillingSize size is >= the DeadSize size.
991 if (KillingSize >= DeadSize)
992 return OW_Complete;
993 }
994
995 // If we hit a partial alias we may have a full overwrite
996 if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
997 int32_t Off = AAR.getOffset();
998 if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)
999 return OW_Complete;
1000 }
1001
1002 // Check to see if the killing store is to the entire object (either a
1003 // global, an alloca, or a byval/inalloca argument). If so, then it clearly
1004 // overwrites any other store to the same object.
1005 const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
1006 const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
1007 const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
1008 const Value *KillingUndObj = getUnderlyingObject(KillingPtr);
1009
1010 // If we can't resolve the same pointers to the same object, then we can't
1011 // analyze them at all.
1012 if (DeadUndObj != KillingUndObj)
1013 return OW_Unknown;
1014
1015 // If the KillingI store is to a recognizable object, get its size.
1016 uint64_t KillingUndObjSize = getPointerSize(KillingUndObj, DL, TLI, &F);
1017 if (KillingUndObjSize != MemoryLocation::UnknownSize)
1018 if (KillingUndObjSize == KillingSize && KillingUndObjSize >= DeadSize)
1019 return OW_Complete;
1020
1021 // Okay, we have stores to two completely different pointers. Try to
1022 // decompose the pointer into a "base + constant_offset" form. If the base
1023 // pointers are equal, then we can reason about the two stores.
1024 DeadOff = 0;
1025 KillingOff = 0;
1026 const Value *DeadBasePtr =
1027 GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);
1028 const Value *KillingBasePtr =
1029 GetPointerBaseWithConstantOffset(KillingPtr, KillingOff, DL);
1030
1031 // If the base pointers still differ, we have two completely different
1032 // stores.
1033 if (DeadBasePtr != KillingBasePtr)
1034 return OW_Unknown;
1035
1036 // The killing access completely overlaps the dead store if and only if
1037 // both start and end of the dead one is "inside" the killing one:
1038 // |<->|--dead--|<->|
1039 // |-----killing------|
1040 // Accesses may overlap if and only if start of one of them is "inside"
1041 // another one:
1042 // |<->|--dead--|<-------->|
1043 // |-------killing--------|
1044 // OR
1045 // |-------dead-------|
1046 // |<->|---killing---|<----->|
1047 //
1048 // We have to be careful here as *Off is signed while *.Size is unsigned.
1049
1050 // Check if the dead access starts "not before" the killing one.
1051 if (DeadOff >= KillingOff) {
1052 // If the dead access ends "not after" the killing access then the
1053 // dead one is completely overwritten by the killing one.
1054 if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1055 return OW_Complete;
1056 // If start of the dead access is "before" end of the killing access
1057 // then accesses overlap.
1058 else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)
1059 return OW_MaybePartial;
1060 }
1061 // If start of the killing access is "before" end of the dead access then
1062 // accesses overlap.
1063 else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {
1064 return OW_MaybePartial;
1065 }
1066
1067 // Can reach here only if accesses are known not to overlap. There is no
1068 // dedicated code to indicate no overlap so signal "unknown".
1069 return OW_Unknown;
1070 }
1071
1072 bool isInvisibleToCallerAfterRet(const Value *V) {
1073 if (isa<AllocaInst>(V))
1074 return true;
1075 auto I = InvisibleToCallerAfterRet.insert({V, false});
1076 if (I.second) {
1077 if (!isInvisibleToCallerBeforeRet(V)) {
1078 I.first->second = false;
1079 } else {
1080 auto *Inst = dyn_cast<Instruction>(V);
1081 if (Inst && isAllocLikeFn(Inst, &TLI))
1082 I.first->second = !PointerMayBeCaptured(V, true, false);
1083 }
1084 }
1085 return I.first->second;
1086 }
1087
1088 bool isInvisibleToCallerBeforeRet(const Value *V) {
1089 if (isa<AllocaInst>(V))
1090 return true;
1091 auto I = InvisibleToCallerBeforeRet.insert({V, false});
1092 if (I.second) {
1093 auto *Inst = dyn_cast<Instruction>(V);
1094 if (Inst && isAllocLikeFn(Inst, &TLI))
1095 // NOTE: This could be made more precise by PointerMayBeCapturedBefore
1096 // with the killing MemoryDef. But we refrain from doing so for now to
1097 // limit compile-time and this does not cause any changes to the number
1098 // of stores removed on a large test set in practice.
1099 I.first->second = !PointerMayBeCaptured(V, false, true);
1100 }
1101 return I.first->second;
1102 }
1103
1104 Optional<MemoryLocation> getLocForWriteEx(Instruction *I) const {
1105 if (!I->mayWriteToMemory())
1106 return None;
1107
1108 if (auto *MTI = dyn_cast<AnyMemIntrinsic>(I))
1109 return {MemoryLocation::getForDest(MTI)};
1110
1111 if (auto *CB = dyn_cast<CallBase>(I)) {
1112 // If the functions may write to memory we do not know about, bail out.
1113 if (!CB->onlyAccessesArgMemory() &&
1114 !CB->onlyAccessesInaccessibleMemOrArgMem())
1115 return None;
1116
1117 LibFunc LF;
1118 if (TLI.getLibFunc(*CB, LF) && TLI.has(LF)) {
1119 switch (LF) {
1120 case LibFunc_strcpy:
1121 case LibFunc_strncpy:
1122 case LibFunc_strcat:
1123 case LibFunc_strncat:
1124 return {MemoryLocation::getAfter(CB->getArgOperand(0))};
1125 default:
1126 break;
1127 }
1128 }
1129 switch (CB->getIntrinsicID()) {
1130 case Intrinsic::init_trampoline:
1131 return {MemoryLocation::getAfter(CB->getArgOperand(0))};
1132 case Intrinsic::masked_store:
1133 return {MemoryLocation::getForArgument(CB, 1, TLI)};
1134 default:
1135 break;
1136 }
1137 return None;
1138 }
1139
1140 return MemoryLocation::getOrNone(I);
1141 }
1142
1143 /// Returns true if \p UseInst completely overwrites \p DefLoc
1144 /// (stored by \p DefInst).
1145 bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
1146 Instruction *UseInst) {
1147 // UseInst has a MemoryDef associated in MemorySSA. It's possible for a
1148 // MemoryDef to not write to memory, e.g. a volatile load is modeled as a
1149 // MemoryDef.
1150 if (!UseInst->mayWriteToMemory())
1151 return false;
1152
1153 if (auto *CB = dyn_cast<CallBase>(UseInst))
1154 if (CB->onlyAccessesInaccessibleMemory())
1155 return false;
1156
1157 int64_t InstWriteOffset, DepWriteOffset;
1158 if (auto CC = getLocForWriteEx(UseInst))
1159 return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,
1160 DepWriteOffset) == OW_Complete;
1161 return false;
1162 }
1163
1164 /// Returns true if \p Def is not read before returning from the function.
1165 bool isWriteAtEndOfFunction(MemoryDef *Def) {
1166 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)
1167 << *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)
1168 << ") 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)
;
1169
1170 auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
1171 if (!MaybeLoc) {
1172 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)
;
1173 return false;
1174 }
1175
1176 SmallVector<MemoryAccess *, 4> WorkList;
1177 SmallPtrSet<MemoryAccess *, 8> Visited;
1178 auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
1179 if (!Visited.insert(Acc).second)
1180 return;
1181 for (Use &U : Acc->uses())
1182 WorkList.push_back(cast<MemoryAccess>(U.getUser()));
1183 };
1184 PushMemUses(Def);
1185 for (unsigned I = 0; I < WorkList.size(); I++) {
1186 if (WorkList.size() >= MemorySSAScanLimit) {
1187 LLVM_DEBUG(dbgs() << " ... hit exploration limit.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit exploration limit.\n"; }
} while (false)
;
1188 return false;
1189 }
1190
1191 MemoryAccess *UseAccess = WorkList[I];
1192 // Simply adding the users of MemoryPhi to the worklist is not enough,
1193 // because we might miss read clobbers in different iterations of a loop,
1194 // for example.
1195 // TODO: Add support for phi translation to handle the loop case.
1196 if (isa<MemoryPhi>(UseAccess))
1197 return false;
1198
1199 // TODO: Checking for aliasing is expensive. Consider reducing the amount
1200 // of times this is called and/or caching it.
1201 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1202 if (isReadClobber(*MaybeLoc, UseInst)) {
1203 LLVM_DEBUG(dbgs() << " ... hit read clobber " << *UseInst << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit read clobber " <<
*UseInst << ".\n"; } } while (false)
;
1204 return false;
1205 }
1206
1207 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1208 PushMemUses(UseDef);
1209 }
1210 return true;
1211 }
1212
1213 /// If \p I is a memory terminator like llvm.lifetime.end or free, return a
1214 /// pair with the MemoryLocation terminated by \p I and a boolean flag
1215 /// indicating whether \p I is a free-like call.
1216 Optional<std::pair<MemoryLocation, bool>>
1217 getLocForTerminator(Instruction *I) const {
1218 uint64_t Len;
1219 Value *Ptr;
1220 if (match(I, m_Intrinsic<Intrinsic::lifetime_end>(m_ConstantInt(Len),
1221 m_Value(Ptr))))
1222 return {std::make_pair(MemoryLocation(Ptr, Len), false)};
1223
1224 if (auto *CB = dyn_cast<CallBase>(I)) {
1225 if (isFreeCall(I, &TLI))
1226 return {std::make_pair(MemoryLocation::getAfter(CB->getArgOperand(0)),
1227 true)};
1228 }
1229
1230 return None;
1231 }
1232
1233 /// Returns true if \p I is a memory terminator instruction like
1234 /// llvm.lifetime.end or free.
1235 bool isMemTerminatorInst(Instruction *I) const {
1236 IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
1237 return (II && II->getIntrinsicID() == Intrinsic::lifetime_end) ||
1238 isFreeCall(I, &TLI);
1239 }
1240
1241 /// Returns true if \p MaybeTerm is a memory terminator for \p Loc from
1242 /// instruction \p AccessI.
1243 bool isMemTerminator(const MemoryLocation &Loc, Instruction *AccessI,
1244 Instruction *MaybeTerm) {
1245 Optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1246 getLocForTerminator(MaybeTerm);
1247
1248 if (!MaybeTermLoc)
1249 return false;
1250
1251 // If the terminator is a free-like call, all accesses to the underlying
1252 // object can be considered terminated.
1253 if (getUnderlyingObject(Loc.Ptr) !=
1254 getUnderlyingObject(MaybeTermLoc->first.Ptr))
1255 return false;
1256
1257 auto TermLoc = MaybeTermLoc->first;
1258 if (MaybeTermLoc->second) {
1259 const Value *LocUO = getUnderlyingObject(Loc.Ptr);
1260 return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
1261 }
1262 int64_t InstWriteOffset = 0;
1263 int64_t DepWriteOffset = 0;
1264 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1265 DepWriteOffset) == OW_Complete;
1266 }
1267
1268 // Returns true if \p Use may read from \p DefLoc.
1269 bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
1270 if (isNoopIntrinsic(UseInst))
1271 return false;
1272
1273 // Monotonic or weaker atomic stores can be re-ordered and do not need to be
1274 // treated as read clobber.
1275 if (auto SI = dyn_cast<StoreInst>(UseInst))
1276 return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
1277
1278 if (!UseInst->mayReadFromMemory())
1279 return false;
1280
1281 if (auto *CB = dyn_cast<CallBase>(UseInst))
1282 if (CB->onlyAccessesInaccessibleMemory())
1283 return false;
1284
1285 // NOTE: For calls, the number of stores removed could be slightly improved
1286 // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
1287 // be expensive compared to the benefits in practice. For now, avoid more
1288 // expensive analysis to limit compile-time.
1289 return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
1290 }
1291
1292 /// Returns true if a dependency between \p Current and \p KillingDef is
1293 /// guaranteed to be loop invariant for the loops that they are in. Either
1294 /// because they are known to be in the same block, in the same loop level or
1295 /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation
1296 /// during execution of the containing function.
1297 bool isGuaranteedLoopIndependent(const Instruction *Current,
1298 const Instruction *KillingDef,
1299 const MemoryLocation &CurrentLoc) {
1300 // If the dependency is within the same block or loop level (being careful
1301 // of irreducible loops), we know that AA will return a valid result for the
1302 // memory dependency. (Both at the function level, outside of any loop,
1303 // would also be valid but we currently disable that to limit compile time).
1304 if (Current->getParent() == KillingDef->getParent())
1305 return true;
1306 const Loop *CurrentLI = LI.getLoopFor(Current->getParent());
1307 if (!ContainsIrreducibleLoops && CurrentLI &&
1308 CurrentLI == LI.getLoopFor(KillingDef->getParent()))
1309 return true;
1310 // Otherwise check the memory location is invariant to any loops.
1311 return isGuaranteedLoopInvariant(CurrentLoc.Ptr);
1312 }
1313
1314 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1315 /// loop. In particular, this guarantees that it only references a single
1316 /// MemoryLocation during execution of the containing function.
1317 bool isGuaranteedLoopInvariant(const Value *Ptr) {
1318 auto IsGuaranteedLoopInvariantBase = [this](const Value *Ptr) {
1319 Ptr = Ptr->stripPointerCasts();
1320 if (auto *I = dyn_cast<Instruction>(Ptr)) {
1321 if (isa<AllocaInst>(Ptr))
1322 return true;
1323
1324 if (isAllocLikeFn(I, &TLI))
1325 return true;
1326
1327 return false;
1328 }
1329 return true;
1330 };
1331
1332 Ptr = Ptr->stripPointerCasts();
1333 if (auto *I = dyn_cast<Instruction>(Ptr)) {
1334 if (I->getParent()->isEntryBlock())
1335 return true;
1336 }
1337 if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
1338 return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
1339 GEP->hasAllConstantIndices();
1340 }
1341 return IsGuaranteedLoopInvariantBase(Ptr);
1342 }
1343
1344 // Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
1345 // with no read access between them or on any other path to a function exit
1346 // block if \p KillingLoc is not accessible after the function returns. If
1347 // there is no such MemoryDef, return None. The returned value may not
1348 // (completely) overwrite \p KillingLoc. Currently we bail out when we
1349 // encounter an aliasing MemoryUse (read).
1350 Optional<MemoryAccess *>
1351 getDomMemoryDef(MemoryDef *KillingDef, MemoryAccess *StartAccess,
1352 const MemoryLocation &KillingLoc, const Value *KillingUndObj,
1353 unsigned &ScanLimit, unsigned &WalkerStepLimit,
1354 bool IsMemTerm, unsigned &PartialLimit) {
1355 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1356 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
1357 return None;
1358 }
1359
1360 MemoryAccess *Current = StartAccess;
1361 Instruction *KillingI = KillingDef->getMemoryInst();
1362 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)
;
1363
1364 // Find the next clobbering Mod access for DefLoc, starting at StartAccess.
1365 Optional<MemoryLocation> CurrentLoc;
1366 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1367 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)
1368 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)
1369 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)
1370 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)
1371 << ")";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)
1372 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)
1373 })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)
;
1374
1375 // Reached TOP.
1376 if (MSSA.isLiveOnEntryDef(Current)) {
1377 LLVM_DEBUG(dbgs() << " ... found LiveOnEntryDef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found LiveOnEntryDef\n"; }
} while (false)
;
1378 return None;
1379 }
1380
1381 // Cost of a step. Accesses in the same block are more likely to be valid
1382 // candidates for elimination, hence consider them cheaper.
1383 unsigned StepCost = KillingDef->getBlock() == Current->getBlock()
1384 ? MemorySSASameBBStepCost
1385 : MemorySSAOtherBBStepCost;
1386 if (WalkerStepLimit <= StepCost) {
1387 LLVM_DEBUG(dbgs() << " ... hit walker step limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... hit walker step limit\n";
} } while (false)
;
1388 return None;
1389 }
1390 WalkerStepLimit -= StepCost;
1391
1392 // Return for MemoryPhis. They cannot be eliminated directly and the
1393 // caller is responsible for traversing them.
1394 if (isa<MemoryPhi>(Current)) {
1395 LLVM_DEBUG(dbgs() << " ... found MemoryPhi\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found MemoryPhi\n"; } } while
(false)
;
1396 return Current;
1397 }
1398
1399 // Below, check if CurrentDef is a valid candidate to be eliminated by
1400 // KillingDef. If it is not, check the next candidate.
1401 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1402 Instruction *CurrentI = CurrentDef->getMemoryInst();
1403
1404 if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(KillingUndObj),
1405 TLI))
1406 continue;
1407
1408 // Before we try to remove anything, check for any extra throwing
1409 // instructions that block us from DSEing
1410 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1411 LLVM_DEBUG(dbgs() << " ... skip, may throw!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, may throw!\n"; } } while
(false)
;
1412 return None;
1413 }
1414
1415 // Check for anything that looks like it will be a barrier to further
1416 // removal
1417 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1418 LLVM_DEBUG(dbgs() << " ... skip, barrier\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skip, barrier\n"; } } while
(false)
;
1419 return None;
1420 }
1421
1422 // If Current is known to be on path that reads DefLoc or is a read
1423 // clobber, bail out, as the path is not profitable. We skip this check
1424 // for intrinsic calls, because the code knows how to handle memcpy
1425 // intrinsics.
1426 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1427 return None;
1428
1429 // Quick check if there are direct uses that are read-clobbers.
1430 if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {
1431 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1432 return !MSSA.dominates(StartAccess, UseOrDef) &&
1433 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1434 return false;
1435 })) {
1436 LLVM_DEBUG(dbgs() << " ... found a read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found a read clobber\n"; }
} while (false)
;
1437 return None;
1438 }
1439
1440 // If Current cannot be analyzed or is not removable, check the next
1441 // candidate.
1442 if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI))
1443 continue;
1444
1445 // If Current does not have an analyzable write location, skip it
1446 CurrentLoc = getLocForWriteEx(CurrentI);
1447 if (!CurrentLoc)
1448 continue;
1449
1450 // AliasAnalysis does not account for loops. Limit elimination to
1451 // candidates for which we can guarantee they always store to the same
1452 // memory location and not located in different loops.
1453 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1454 LLVM_DEBUG(dbgs() << " ... not guaranteed loop independent\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... not guaranteed loop independent\n"
; } } while (false)
;
1455 WalkerStepLimit -= 1;
1456 continue;
1457 }
1458
1459 if (IsMemTerm) {
1460 // If the killing def is a memory terminator (e.g. lifetime.end), check
1461 // the next candidate if the current Current does not write the same
1462 // underlying object as the terminator.
1463 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))
1464 continue;
1465 } else {
1466 int64_t KillingOffset = 0;
1467 int64_t DeadOffset = 0;
1468 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1469 KillingOffset, DeadOffset);
1470 // If Current does not write to the same object as KillingDef, check
1471 // the next candidate.
1472 if (OR == OW_Unknown)
1473 continue;
1474 else if (OR == OW_MaybePartial) {
1475 // If KillingDef only partially overwrites Current, check the next
1476 // candidate if the partial step limit is exceeded. This aggressively
1477 // limits the number of candidates for partial store elimination,
1478 // which are less likely to be removable in the end.
1479 if (PartialLimit <= 1) {
1480 WalkerStepLimit -= 1;
1481 continue;
1482 }
1483 PartialLimit -= 1;
1484 }
1485 }
1486 break;
1487 };
1488
1489 // Accesses to objects accessible after the function returns can only be
1490 // eliminated if the access is dead along all paths to the exit. Collect
1491 // the blocks with killing (=completely overwriting MemoryDefs) and check if
1492 // they cover all paths from MaybeDeadAccess to any function exit.
1493 SmallPtrSet<Instruction *, 16> KillingDefs;
1494 KillingDefs.insert(KillingDef->getMemoryInst());
1495 MemoryAccess *MaybeDeadAccess = Current;
1496 MemoryLocation MaybeDeadLoc = *CurrentLoc;
1497 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1498 LLVM_DEBUG(dbgs() << " Checking for reads of " << *MaybeDeadAccess << " ("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*MaybeDeadAccess << " (" << *MaybeDeadI <<
")\n"; } } while (false)
1499 << *MaybeDeadI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking for reads of " <<
*MaybeDeadAccess << " (" << *MaybeDeadI <<
")\n"; } } while (false)
;
1500
1501 SmallSetVector<MemoryAccess *, 32> WorkList;
1502 auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
1503 for (Use &U : Acc->uses())
1504 WorkList.insert(cast<MemoryAccess>(U.getUser()));
1505 };
1506 PushMemUses(MaybeDeadAccess);
1507
1508 // Check if DeadDef may be read.
1509 for (unsigned I = 0; I < WorkList.size(); I++) {
1510 MemoryAccess *UseAccess = WorkList[I];
1511
1512 LLVM_DEBUG(dbgs() << " " << *UseAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " " << *UseAccess; } } while
(false)
;
1513 // Bail out if the number of accesses to check exceeds the scan limit.
1514 if (ScanLimit < (WorkList.size() - I)) {
1515 LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... hit scan limit\n"; } }
while (false)
;
1516 return None;
1517 }
1518 --ScanLimit;
1519 NumDomMemDefChecks++;
1520
1521 if (isa<MemoryPhi>(UseAccess)) {
1522 if (any_of(KillingDefs, [this, UseAccess](Instruction *KI) {
1523 return DT.properlyDominates(KI->getParent(),
1524 UseAccess->getBlock());
1525 })) {
1526 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)
;
1527 continue;
1528 }
1529 LLVM_DEBUG(dbgs() << "\n ... adding PHI uses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "\n ... adding PHI uses\n"; } }
while (false)
;
1530 PushMemUses(UseAccess);
1531 continue;
1532 }
1533
1534 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1535 LLVM_DEBUG(dbgs() << " (" << *UseInst << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *UseInst << ")\n"
; } } while (false)
;
1536
1537 if (any_of(KillingDefs, [this, UseInst](Instruction *KI) {
1538 return DT.dominates(KI, UseInst);
1539 })) {
1540 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)
;
1541 continue;
1542 }
1543
1544 // A memory terminator kills all preceeding MemoryDefs and all succeeding
1545 // MemoryAccesses. We do not have to check it's users.
1546 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1547 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
1548 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
1549 << " ... skipping, memterminator invalidates following accesses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... skipping, memterminator invalidates following accesses\n"
; } } while (false)
;
1550 continue;
1551 }
1552
1553 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1554 LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... adding uses of intrinsic\n"
; } } while (false)
;
1555 PushMemUses(UseAccess);
1556 continue;
1557 }
1558
1559 if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(KillingUndObj)) {
1560 LLVM_DEBUG(dbgs() << " ... found throwing instruction\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found throwing instruction\n"
; } } while (false)
;
1561 return None;
1562 }
1563
1564 // Uses which may read the original MemoryDef mean we cannot eliminate the
1565 // original MD. Stop walk.
1566 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1567 LLVM_DEBUG(dbgs() << " ... found read clobber\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found read clobber\n"; } }
while (false)
;
1568 return None;
1569 }
1570
1571 // If this worklist walks back to the original memory access (and the
1572 // pointer is not guarenteed loop invariant) then we cannot assume that a
1573 // store kills itself.
1574 if (MaybeDeadAccess == UseAccess &&
1575 !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {
1576 LLVM_DEBUG(dbgs() << " ... found not loop invariant self access\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found not loop invariant self access\n"
; } } while (false)
;
1577 return None;
1578 }
1579 // Otherwise, for the KillingDef and MaybeDeadAccess we only have to check
1580 // if it reads the memory location.
1581 // TODO: It would probably be better to check for self-reads before
1582 // calling the function.
1583 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1584 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)
;
1585 continue;
1586 }
1587
1588 // Check all uses for MemoryDefs, except for defs completely overwriting
1589 // the original location. Otherwise we have to check uses of *all*
1590 // MemoryDefs we discover, including non-aliasing ones. Otherwise we might
1591 // miss cases like the following
1592 // 1 = Def(LoE) ; <----- DeadDef stores [0,1]
1593 // 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
1594 // Use(2) ; MayAlias 2 *and* 1, loads [0, 3].
1595 // (The Use points to the *first* Def it may alias)
1596 // 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
1597 // stores [0,1]
1598 if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1599 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1600 BasicBlock *MaybeKillingBlock = UseInst->getParent();
1601 if (PostOrderNumbers.find(MaybeKillingBlock)->second <
1602 PostOrderNumbers.find(MaybeDeadAccess->getBlock())->second) {
1603 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1604 LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
1605 << " ... found killing def " << *UseInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found killing def " <<
*UseInst << "\n"; } } while (false)
;
1606 KillingDefs.insert(UseInst);
1607 }
1608 } else {
1609 LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found preceeding def " <<
*UseInst << "\n"; } } while (false)
1610 << " ... found preceeding def " << *UseInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " ... found preceeding def " <<
*UseInst << "\n"; } } while (false)
;
1611 return None;
1612 }
1613 } else
1614 PushMemUses(UseDef);
1615 }
1616 }
1617
1618 // For accesses to locations visible after the function returns, make sure
1619 // that the location is dead (=overwritten) along all paths from
1620 // MaybeDeadAccess to the exit.
1621 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1622 SmallPtrSet<BasicBlock *, 16> KillingBlocks;
1623 for (Instruction *KD : KillingDefs)
1624 KillingBlocks.insert(KD->getParent());
1625 assert(!KillingBlocks.empty() &&(static_cast <bool> (!KillingBlocks.empty() && "Expected at least a single killing block"
) ? void (0) : __assert_fail ("!KillingBlocks.empty() && \"Expected at least a single killing block\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1626, __extension__ __PRETTY_FUNCTION__))
1626 "Expected at least a single killing block")(static_cast <bool> (!KillingBlocks.empty() && "Expected at least a single killing block"
) ? void (0) : __assert_fail ("!KillingBlocks.empty() && \"Expected at least a single killing block\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1626, __extension__ __PRETTY_FUNCTION__))
;
1627
1628 // Find the common post-dominator of all killing blocks.
1629 BasicBlock *CommonPred = *KillingBlocks.begin();
1630 for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {
1631 if (!CommonPred)
1632 break;
1633 CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);
1634 }
1635
1636 // If CommonPred is in the set of killing blocks, just check if it
1637 // post-dominates MaybeDeadAccess.
1638 if (KillingBlocks.count(CommonPred)) {
1639 if (PDT.dominates(CommonPred, MaybeDeadAccess->getBlock()))
1640 return {MaybeDeadAccess};
1641 return None;
1642 }
1643
1644 // If the common post-dominator does not post-dominate MaybeDeadAccess,
1645 // there is a path from MaybeDeadAccess to an exit not going through a
1646 // killing block.
1647 if (PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
1648 SetVector<BasicBlock *> WorkList;
1649
1650 // If CommonPred is null, there are multiple exits from the function.
1651 // They all have to be added to the worklist.
1652 if (CommonPred)
1653 WorkList.insert(CommonPred);
1654 else
1655 for (BasicBlock *R : PDT.roots())
1656 WorkList.insert(R);
1657
1658 NumCFGTries++;
1659 // Check if all paths starting from an exit node go through one of the
1660 // killing blocks before reaching MaybeDeadAccess.
1661 for (unsigned I = 0; I < WorkList.size(); I++) {
1662 NumCFGChecks++;
1663 BasicBlock *Current = WorkList[I];
1664 if (KillingBlocks.count(Current))
1665 continue;
1666 if (Current == MaybeDeadAccess->getBlock())
1667 return None;
1668
1669 // MaybeDeadAccess is reachable from the entry, so we don't have to
1670 // explore unreachable blocks further.
1671 if (!DT.isReachableFromEntry(Current))
1672 continue;
1673
1674 for (BasicBlock *Pred : predecessors(Current))
1675 WorkList.insert(Pred);
1676
1677 if (WorkList.size() >= MemorySSAPathCheckLimit)
1678 return None;
1679 }
1680 NumCFGSuccess++;
1681 return {MaybeDeadAccess};
1682 }
1683 return None;
1684 }
1685
1686 // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is
1687 // potentially dead.
1688 return {MaybeDeadAccess};
1689 }
1690
1691 // Delete dead memory defs
1692 void deleteDeadInstruction(Instruction *SI) {
1693 MemorySSAUpdater Updater(&MSSA);
1694 SmallVector<Instruction *, 32> NowDeadInsts;
1695 NowDeadInsts.push_back(SI);
1696 --NumFastOther;
1697
1698 while (!NowDeadInsts.empty()) {
1699 Instruction *DeadInst = NowDeadInsts.pop_back_val();
1700 ++NumFastOther;
1701
1702 // Try to preserve debug information attached to the dead instruction.
1703 salvageDebugInfo(*DeadInst);
1704 salvageKnowledge(DeadInst);
1705
1706 // Remove the Instruction from MSSA.
1707 if (MemoryAccess *MA = MSSA.getMemoryAccess(DeadInst)) {
1708 if (MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
1709 SkipStores.insert(MD);
1710 }
1711
1712 Updater.removeMemoryAccess(MA);
1713 }
1714
1715 auto I = IOLs.find(DeadInst->getParent());
1716 if (I != IOLs.end())
1717 I->second.erase(DeadInst);
1718 // Remove its operands
1719 for (Use &O : DeadInst->operands())
1720 if (Instruction *OpI = dyn_cast<Instruction>(O)) {
1721 O = nullptr;
1722 if (isInstructionTriviallyDead(OpI, &TLI))
1723 NowDeadInsts.push_back(OpI);
1724 }
1725
1726 EI.removeInstruction(DeadInst);
1727 DeadInst->eraseFromParent();
1728 }
1729 }
1730
1731 // Check for any extra throws between \p KillingI and \p DeadI that block
1732 // DSE. This only checks extra maythrows (those that aren't MemoryDef's).
1733 // MemoryDef that may throw are handled during the walk from one def to the
1734 // next.
1735 bool mayThrowBetween(Instruction *KillingI, Instruction *DeadI,
1736 const Value *KillingUndObj) {
1737 // First see if we can ignore it by using the fact that KillingI is an
1738 // alloca/alloca like object that is not visible to the caller during
1739 // execution of the function.
1740 if (KillingUndObj && isInvisibleToCallerBeforeRet(KillingUndObj))
1741 return false;
1742
1743 if (KillingI->getParent() == DeadI->getParent())
1744 return ThrowingBlocks.count(KillingI->getParent());
1745 return !ThrowingBlocks.empty();
1746 }
1747
1748 // Check if \p DeadI acts as a DSE barrier for \p KillingI. The following
1749 // instructions act as barriers:
1750 // * A memory instruction that may throw and \p KillingI accesses a non-stack
1751 // object.
1752 // * Atomic stores stronger that monotonic.
1753 bool isDSEBarrier(const Value *KillingUndObj, Instruction *DeadI) {
1754 // If DeadI may throw it acts as a barrier, unless we are to an
1755 // alloca/alloca like object that does not escape.
1756 if (DeadI->mayThrow() && !isInvisibleToCallerBeforeRet(KillingUndObj))
1757 return true;
1758
1759 // If DeadI is an atomic load/store stronger than monotonic, do not try to
1760 // eliminate/reorder it.
1761 if (DeadI->isAtomic()) {
1762 if (auto *LI = dyn_cast<LoadInst>(DeadI))
1763 return isStrongerThanMonotonic(LI->getOrdering());
1764 if (auto *SI = dyn_cast<StoreInst>(DeadI))
1765 return isStrongerThanMonotonic(SI->getOrdering());
1766 if (auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1767 return isStrongerThanMonotonic(ARMW->getOrdering());
1768 if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1769 return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
1770 isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
1771 llvm_unreachable("other instructions should be skipped in MemorySSA")::llvm::llvm_unreachable_internal("other instructions should be skipped in MemorySSA"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1771)
;
1772 }
1773 return false;
1774 }
1775
1776 /// Eliminate writes to objects that are not visible in the caller and are not
1777 /// accessed before returning from the function.
1778 bool eliminateDeadWritesAtEndOfFunction() {
1779 bool MadeChange = false;
1780 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
1781 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs at the end of the function\n"
; } } while (false)
1782 << "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)
;
1783 for (int I = MemDefs.size() - 1; I >= 0; I--) {
1784 MemoryDef *Def = MemDefs[I];
1785 if (SkipStores.contains(Def) || !isRemovable(Def->getMemoryInst()))
1786 continue;
1787
1788 Instruction *DefI = Def->getMemoryInst();
1789 auto DefLoc = getLocForWriteEx(DefI);
1790 if (!DefLoc)
1791 continue;
1792
1793 // NOTE: Currently eliminating writes at the end of a function is limited
1794 // to MemoryDefs with a single underlying object, to save compile-time. In
1795 // practice it appears the case with multiple underlying objects is very
1796 // uncommon. If it turns out to be important, we can use
1797 // getUnderlyingObjects here instead.
1798 const Value *UO = getUnderlyingObject(DefLoc->Ptr);
1799 if (!UO || !isInvisibleToCallerAfterRet(UO))
1800 continue;
1801
1802 if (isWriteAtEndOfFunction(Def)) {
1803 // See through pointer-to-pointer bitcasts
1804 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)
1805 "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)
;
1806 deleteDeadInstruction(DefI);
1807 ++NumFastStores;
1808 MadeChange = true;
1809 }
1810 }
1811 return MadeChange;
1812 }
1813
1814 /// \returns true if \p Def is a no-op store, either because it
1815 /// directly stores back a loaded value or stores zero to a calloced object.
1816 bool storeIsNoop(MemoryDef *Def, const Value *DefUO) {
1817 StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
1818 MemSetInst *MemSet = dyn_cast<MemSetInst>(Def->getMemoryInst());
1819 Constant *StoredConstant = nullptr;
1820 if (Store)
1821 StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
1822 if (MemSet)
1823 StoredConstant = dyn_cast<Constant>(MemSet->getValue());
1824
1825 if (StoredConstant && StoredConstant->isNullValue()) {
1826 auto *DefUOInst = dyn_cast<Instruction>(DefUO);
1827 if (DefUOInst) {
1828 if (isCallocLikeFn(DefUOInst, &TLI)) {
1829 auto *UnderlyingDef =
1830 cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
1831 // If UnderlyingDef is the clobbering access of Def, no instructions
1832 // between them can modify the memory location.
1833 auto *ClobberDef =
1834 MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
1835 return UnderlyingDef == ClobberDef;
1836 }
1837
1838 if (MemSet) {
1839 if (F.hasFnAttribute(Attribute::SanitizeMemory) ||
1840 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1841 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1842 F.getName() == "calloc")
1843 return false;
1844 auto *Malloc = const_cast<CallInst *>(dyn_cast<CallInst>(DefUOInst));
1845 if (!Malloc)
1846 return false;
1847 auto *InnerCallee = Malloc->getCalledFunction();
1848 if (!InnerCallee)
1849 return false;
1850 LibFunc Func;
1851 if (!TLI.getLibFunc(*InnerCallee, Func) || !TLI.has(Func) ||
1852 Func != LibFunc_malloc)
1853 return false;
1854 if (Malloc->getOperand(0) == MemSet->getLength()) {
1855 if (DT.dominates(Malloc, MemSet) && PDT.dominates(MemSet, Malloc) &&
1856 memoryIsNotModifiedBetween(Malloc, MemSet, BatchAA, DL, &DT)) {
1857 IRBuilder<> IRB(Malloc);
1858 const auto &DL = Malloc->getModule()->getDataLayout();
1859 if (auto *Calloc =
1860 emitCalloc(ConstantInt::get(IRB.getIntPtrTy(DL), 1),
1861 Malloc->getArgOperand(0), IRB, TLI)) {
1862 MemorySSAUpdater Updater(&MSSA);
1863 auto *LastDef = cast<MemoryDef>(
1864 Updater.getMemorySSA()->getMemoryAccess(Malloc));
1865 auto *NewAccess = Updater.createMemoryAccessAfter(
1866 cast<Instruction>(Calloc), LastDef, LastDef);
1867 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1868 Updater.insertDef(NewAccessMD, /*RenameUses=*/true);
1869 Updater.removeMemoryAccess(Malloc);
1870 Malloc->replaceAllUsesWith(Calloc);
1871 Malloc->eraseFromParent();
1872 return true;
1873 }
1874 return false;
1875 }
1876 }
1877 }
1878 }
1879 }
1880
1881 if (!Store)
1882 return false;
1883
1884 if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
1885 if (LoadI->getPointerOperand() == Store->getOperand(1)) {
1886 // Get the defining access for the load.
1887 auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
1888 // Fast path: the defining accesses are the same.
1889 if (LoadAccess == Def->getDefiningAccess())
1890 return true;
1891
1892 // Look through phi accesses. Recursively scan all phi accesses by
1893 // adding them to a worklist. Bail when we run into a memory def that
1894 // does not match LoadAccess.
1895 SetVector<MemoryAccess *> ToCheck;
1896 MemoryAccess *Current =
1897 MSSA.getWalker()->getClobberingMemoryAccess(Def);
1898 // We don't want to bail when we run into the store memory def. But,
1899 // the phi access may point to it. So, pretend like we've already
1900 // checked it.
1901 ToCheck.insert(Def);
1902 ToCheck.insert(Current);
1903 // Start at current (1) to simulate already having checked Def.
1904 for (unsigned I = 1; I < ToCheck.size(); ++I) {
1905 Current = ToCheck[I];
1906 if (auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
1907 // Check all the operands.
1908 for (auto &Use : PhiAccess->incoming_values())
1909 ToCheck.insert(cast<MemoryAccess>(&Use));
1910 continue;
1911 }
1912
1913 // If we found a memory def, bail. This happens when we have an
1914 // unrelated write in between an otherwise noop store.
1915 assert(isa<MemoryDef>(Current) &&(static_cast <bool> (isa<MemoryDef>(Current) &&
"Only MemoryDefs should reach here.") ? void (0) : __assert_fail
("isa<MemoryDef>(Current) && \"Only MemoryDefs should reach here.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1916, __extension__ __PRETTY_FUNCTION__))
1916 "Only MemoryDefs should reach here.")(static_cast <bool> (isa<MemoryDef>(Current) &&
"Only MemoryDefs should reach here.") ? void (0) : __assert_fail
("isa<MemoryDef>(Current) && \"Only MemoryDefs should reach here.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1916, __extension__ __PRETTY_FUNCTION__))
;
1917 // TODO: Skip no alias MemoryDefs that have no aliasing reads.
1918 // We are searching for the definition of the store's destination.
1919 // So, if that is the same definition as the load, then this is a
1920 // noop. Otherwise, fail.
1921 if (LoadAccess != Current)
1922 return false;
1923 }
1924 return true;
1925 }
1926 }
1927
1928 return false;
1929 }
1930};
1931
1932static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
1933 DominatorTree &DT, PostDominatorTree &PDT,
1934 const TargetLibraryInfo &TLI,
1935 const LoopInfo &LI) {
1936 bool MadeChange = false;
1937
1938 DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI);
1939 // For each store:
1940 for (unsigned I = 0; I < State.MemDefs.size(); I++) {
1
Assuming the condition is false
2
Loop condition is false. Execution continues on line 2095
1941 MemoryDef *KillingDef = State.MemDefs[I];
1942 if (State.SkipStores.count(KillingDef))
1943 continue;
1944 Instruction *KillingI = KillingDef->getMemoryInst();
1945
1946 Optional<MemoryLocation> MaybeKillingLoc;
1947 if (State.isMemTerminatorInst(KillingI))
1948 MaybeKillingLoc = State.getLocForTerminator(KillingI).map(
1949 [](const std::pair<MemoryLocation, bool> &P) { return P.first; });
1950 else
1951 MaybeKillingLoc = State.getLocForWriteEx(KillingI);
1952
1953 if (!MaybeKillingLoc) {
1954 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 "
<< *KillingI << "\n"; } } while (false)
1955 << *KillingI << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Failed to find analyzable write location for "
<< *KillingI << "\n"; } } while (false)
;
1956 continue;
1957 }
1958 MemoryLocation KillingLoc = *MaybeKillingLoc;
1959 assert(KillingLoc.Ptr && "KillingLoc should not be null")(static_cast <bool> (KillingLoc.Ptr && "KillingLoc should not be null"
) ? void (0) : __assert_fail ("KillingLoc.Ptr && \"KillingLoc should not be null\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp"
, 1959, __extension__ __PRETTY_FUNCTION__))
;
1960 const Value *KillingUndObj = getUnderlyingObject(KillingLoc.Ptr);
1961
1962 MemoryAccess *Current = KillingDef;
1963 LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *KillingI <<
")\n"; } } while (false)
1964 << *KillingDef << " (" << *KillingI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "Trying to eliminate MemoryDefs killed by "
<< *KillingDef << " (" << *KillingI <<
")\n"; } } while (false)
;
1965
1966 unsigned ScanLimit = MemorySSAScanLimit;
1967 unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
1968 unsigned PartialLimit = MemorySSAPartialStoreLimit;
1969 // Worklist of MemoryAccesses that may be killed by KillingDef.
1970 SetVector<MemoryAccess *> ToCheck;
1971
1972 if (KillingUndObj)
1973 ToCheck.insert(KillingDef->getDefiningAccess());
1974
1975 bool Shortend = false;
1976 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
1977 // Check if MemoryAccesses in the worklist are killed by KillingDef.
1978 for (unsigned I = 0; I < ToCheck.size(); I++) {
1979 Current = ToCheck[I];
1980 if (State.SkipStores.count(Current))
1981 continue;
1982
1983 Optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
1984 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
1985 WalkerStepLimit, IsMemTerm, PartialLimit);
1986
1987 if (!MaybeDeadAccess) {
1988 LLVM_DEBUG(dbgs() << " finished walk\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " finished walk\n"; } } while (false
)
;
1989 continue;
1990 }
1991
1992 MemoryAccess *DeadAccess = *MaybeDeadAccess;
1993 LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " Checking if we can kill " <<
*DeadAccess; } } while (false)
;
1994 if (isa<MemoryPhi>(DeadAccess)) {
1995 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)
;
1996 for (Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
1997 MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
1998 BasicBlock *IncomingBlock = IncomingAccess->getBlock();
1999 BasicBlock *PhiBlock = DeadAccess->getBlock();
2000
2001 // We only consider incoming MemoryAccesses that come before the
2002 // MemoryPhi. Otherwise we could discover candidates that do not
2003 // strictly dominate our starting def.
2004 if (State.PostOrderNumbers[IncomingBlock] >
2005 State.PostOrderNumbers[PhiBlock])
2006 ToCheck.insert(IncomingAccess);
2007 }
2008 continue;
2009 }
2010 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2011 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2012 LLVM_DEBUG(dbgs() << " (" << *DeadI << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << " (" << *DeadI << ")\n"
; } } while (false)
;
2013 ToCheck.insert(DeadDefAccess->getDefiningAccess());
2014 NumGetDomMemoryDefPassed++;
2015
2016 if (!DebugCounter::shouldExecute(MemorySSACounter))
2017 continue;
2018
2019 MemoryLocation DeadLoc = *State.getLocForWriteEx(DeadI);
2020
2021 if (IsMemTerm) {
2022 const Value *DeadUndObj = getUnderlyingObject(DeadLoc.Ptr);
2023 if (KillingUndObj != DeadUndObj)
2024 continue;
2025 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DeadIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DeadI << "\n KILLER: " << *KillingI <<
'\n'; } } while (false)
2026 << "\n KILLER: " << *KillingI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DeadI << "\n KILLER: " << *KillingI <<
'\n'; } } while (false)
;
2027 State.deleteDeadInstruction(DeadI);
2028 ++NumFastStores;
2029 MadeChange = true;
2030 } else {
2031 // Check if DeadI overwrites KillingI.
2032 int64_t KillingOffset = 0;
2033 int64_t DeadOffset = 0;
2034 OverwriteResult OR = State.isOverwrite(
2035 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2036 if (OR == OW_MaybePartial) {
2037 auto Iter = State.IOLs.insert(
2038 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2039 DeadI->getParent(), InstOverlapIntervalsTy()));
2040 auto &IOL = Iter.first->second;
2041 OR = isPartialOverwrite(KillingLoc, DeadLoc, KillingOffset,
2042 DeadOffset, DeadI, IOL);
2043 }
2044
2045 if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
2046 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2047 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2048 // We are re-using tryToMergePartialOverlappingStores, which requires
2049 // DeadSI to dominate DeadSI.
2050 // TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
2051 if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {
2052 if (Constant *Merged = tryToMergePartialOverlappingStores(
2053 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2054 State.BatchAA, &DT)) {
2055
2056 // Update stored value of earlier store to merged constant.
2057 DeadSI->setOperand(0, Merged);
2058 ++NumModifiedStores;
2059 MadeChange = true;
2060
2061 Shortend = true;
2062 // Remove killing store and remove any outstanding overlap
2063 // intervals for the updated store.
2064 State.deleteDeadInstruction(KillingSI);
2065 auto I = State.IOLs.find(DeadSI->getParent());
2066 if (I != State.IOLs.end())
2067 I->second.erase(DeadSI);
2068 break;
2069 }
2070 }
2071 }
2072
2073 if (OR == OW_Complete) {
2074 LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DeadIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DeadI << "\n KILLER: " << *KillingI <<
'\n'; } } while (false)
2075 << "\n KILLER: " << *KillingI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove Dead Store:\n DEAD: "
<< *DeadI << "\n KILLER: " << *KillingI <<
'\n'; } } while (false)
;
2076 State.deleteDeadInstruction(DeadI);
2077 ++NumFastStores;
2078 MadeChange = true;
2079 }
2080 }
2081 }
2082
2083 // Check if the store is a no-op.
2084 if (!Shortend && isRemovable(KillingI) &&
2085 State.storeIsNoop(KillingDef, KillingUndObj)) {
2086 LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *KillingIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove No-Op Store:\n DEAD: "
<< *KillingI << '\n'; } } while (false)
2087 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dse")) { dbgs() << "DSE: Remove No-Op Store:\n DEAD: "
<< *KillingI << '\n'; } } while (false)
;
2088 State.deleteDeadInstruction(KillingI);
2089 NumRedundantStores++;
2090 MadeChange = true;
2091 continue;
2092 }
2093 }
2094
2095 if (EnablePartialOverwriteTracking)
3
Assuming the condition is true
4
Taking true branch
2096 for (auto &KV : State.IOLs)
2097 MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
5
Calling 'removePartiallyOverlappedStores'
2098
2099 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2100 return MadeChange;
2101}
2102} // end anonymous namespace
2103
2104//===----------------------------------------------------------------------===//
2105// DSE Pass
2106//===----------------------------------------------------------------------===//
2107PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
2108 AliasAnalysis &AA = AM.getResult<AAManager>(F);
2109 const TargetLibraryInfo &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2110 DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
2111 MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2112 PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
2113 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
2114
2115 bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
2116
2117#ifdef LLVM_ENABLE_STATS1
2118 if (AreStatisticsEnabled())
2119 for (auto &I : instructions(F))
2120 NumRemainingStores += isa<StoreInst>(&I);
2121#endif
2122
2123 if (!Changed)
2124 return PreservedAnalyses::all();
2125
2126 PreservedAnalyses PA;
2127 PA.preserveSet<CFGAnalyses>();
2128 PA.preserve<MemorySSAAnalysis>();
2129 PA.preserve<LoopAnalysis>();
2130 return PA;
2131}
2132
2133namespace {
2134
2135/// A legacy pass for the legacy pass manager that wraps \c DSEPass.
2136class DSELegacyPass : public FunctionPass {
2137public:
2138 static char ID; // Pass identification, replacement for typeid
2139
2140 DSELegacyPass() : FunctionPass(ID) {
2141 initializeDSELegacyPassPass(*PassRegistry::getPassRegistry());
2142 }
2143
2144 bool runOnFunction(Function &F) override {
2145 if (skipFunction(F))
2146 return false;
2147
2148 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2149 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2150 const TargetLibraryInfo &TLI =
2151 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2152 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2153 PostDominatorTree &PDT =
2154 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2155 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2156
2157 bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI);
2158
2159#ifdef LLVM_ENABLE_STATS1
2160 if (AreStatisticsEnabled())
2161 for (auto &I : instructions(F))
2162 NumRemainingStores += isa<StoreInst>(&I);
2163#endif
2164
2165 return Changed;
2166 }
2167
2168 void getAnalysisUsage(AnalysisUsage &AU) const override {
2169 AU.setPreservesCFG();
2170 AU.addRequired<AAResultsWrapperPass>();
2171 AU.addRequired<TargetLibraryInfoWrapperPass>();
2172 AU.addPreserved<GlobalsAAWrapperPass>();
2173 AU.addRequired<DominatorTreeWrapperPass>();
2174 AU.addPreserved<DominatorTreeWrapperPass>();
2175 AU.addRequired<PostDominatorTreeWrapperPass>();
2176 AU.addRequired<MemorySSAWrapperPass>();
2177 AU.addPreserved<PostDominatorTreeWrapperPass>();
2178 AU.addPreserved<MemorySSAWrapperPass>();
2179 AU.addRequired<LoopInfoWrapperPass>();
2180 AU.addPreserved<LoopInfoWrapperPass>();
2181 }
2182};
2183
2184} // end anonymous namespace
2185
2186char DSELegacyPass::ID = 0;
2187
2188INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false,static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2189 false)static void *initializeDSELegacyPassPassOnce(PassRegistry &
Registry) {
2190INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2191INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry);
2192INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
2193INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
2194INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
2195INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
2196INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2197INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
2198INITIALIZE_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)); }
2199 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)); }
2200
2201FunctionPass *llvm::createDeadStoreEliminationPass() {
2202 return new DSELegacyPass();
2203}

/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/Analysis/MemoryLocation.h

1//===- MemoryLocation.h - Memory location descriptions ----------*- C++ -*-===//
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/// \file
9/// This file provides utility analysis objects describing memory locations.
10/// These are used both by the Alias Analysis infrastructure and more
11/// specialized memory analysis layers.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ANALYSIS_MEMORYLOCATION_H
16#define LLVM_ANALYSIS_MEMORYLOCATION_H
17
18#include "llvm/ADT/DenseMapInfo.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/IR/Metadata.h"
21#include "llvm/Support/TypeSize.h"
22
23namespace llvm {
24
25class CallBase;
26class Instruction;
27class LoadInst;
28class StoreInst;
29class MemTransferInst;
30class MemIntrinsic;
31class AtomicCmpXchgInst;
32class AtomicMemTransferInst;
33class AtomicMemIntrinsic;
34class AtomicRMWInst;
35class AnyMemTransferInst;
36class AnyMemIntrinsic;
37class TargetLibraryInfo;
38class VAArgInst;
39
40// Represents the size of a MemoryLocation. Logically, it's an
41// Optional<uint63_t> that also carries a bit to represent whether the integer
42// it contains, N, is 'precise'. Precise, in this context, means that we know
43// that the area of storage referenced by the given MemoryLocation must be
44// precisely N bytes. An imprecise value is formed as the union of two or more
45// precise values, and can conservatively represent all of the values unioned
46// into it. Importantly, imprecise values are an *upper-bound* on the size of a
47// MemoryLocation.
48//
49// Concretely, a precise MemoryLocation is (%p, 4) in
50// store i32 0, i32* %p
51//
52// Since we know that %p must be at least 4 bytes large at this point.
53// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
54// at the memcpy in
55//
56// %n = select i1 %foo, i64 1, i64 4
57// call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
58// i1 false)
59//
60// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
61// we'll ever actually do so.
62//
63// If asked to represent a pathologically large value, this will degrade to
64// None.
65class LocationSize {
66 enum : uint64_t {
67 BeforeOrAfterPointer = ~uint64_t(0),
68 AfterPointer = BeforeOrAfterPointer - 1,
69 MapEmpty = BeforeOrAfterPointer - 2,
70 MapTombstone = BeforeOrAfterPointer - 3,
71 ImpreciseBit = uint64_t(1) << 63,
72
73 // The maximum value we can represent without falling back to 'unknown'.
74 MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
75 };
76
77 uint64_t Value;
78
79 // Hack to support implicit construction. This should disappear when the
80 // public LocationSize ctor goes away.
81 enum DirectConstruction { Direct };
82
83 constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
84
85 static_assert(AfterPointer & ImpreciseBit,
86 "AfterPointer is imprecise by definition.");
87 static_assert(BeforeOrAfterPointer & ImpreciseBit,
88 "BeforeOrAfterPointer is imprecise by definition.");
89
90public:
91 // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
92 // to make it more obvious at the callsite the kind of size that they're
93 // providing.
94 //
95 // Since the overwhelming majority of users of this provide precise values,
96 // this assumes the provided value is precise.
97 constexpr LocationSize(uint64_t Raw)
98 : Value(Raw > MaxValue ? AfterPointer : Raw) {}
99
100 static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
101 static LocationSize precise(TypeSize Value) {
102 if (Value.isScalable())
103 return afterPointer();
104 return precise(Value.getFixedSize());
105 }
106
107 static LocationSize upperBound(uint64_t Value) {
108 // You can't go lower than 0, so give a precise result.
109 if (LLVM_UNLIKELY(Value == 0)__builtin_expect((bool)(Value == 0), false))
110 return precise(0);
111 if (LLVM_UNLIKELY(Value > MaxValue)__builtin_expect((bool)(Value > MaxValue), false))
112 return afterPointer();
113 return LocationSize(Value | ImpreciseBit, Direct);
114 }
115 static LocationSize upperBound(TypeSize Value) {
116 if (Value.isScalable())
117 return afterPointer();
118 return upperBound(Value.getFixedSize());
119 }
120
121 /// Any location after the base pointer (but still within the underlying
122 /// object).
123 constexpr static LocationSize afterPointer() {
124 return LocationSize(AfterPointer, Direct);
125 }
126
127 /// Any location before or after the base pointer (but still within the
128 /// underlying object).
129 constexpr static LocationSize beforeOrAfterPointer() {
130 return LocationSize(BeforeOrAfterPointer, Direct);
131 }
132
133 // Sentinel values, generally used for maps.
134 constexpr static LocationSize mapTombstone() {
135 return LocationSize(MapTombstone, Direct);
136 }
137 constexpr static LocationSize mapEmpty() {
138 return LocationSize(MapEmpty, Direct);
139 }
140
141 // Returns a LocationSize that can correctly represent either `*this` or
142 // `Other`.
143 LocationSize unionWith(LocationSize Other) const {
144 if (Other == *this)
145 return *this;
146
147 if (Value == BeforeOrAfterPointer || Other.Value == BeforeOrAfterPointer)
148 return beforeOrAfterPointer();
149 if (Value == AfterPointer || Other.Value == AfterPointer)
150 return afterPointer();
151
152 return upperBound(std::max(getValue(), Other.getValue()));
153 }
154
155 bool hasValue() const {
156 return Value != AfterPointer && Value != BeforeOrAfterPointer;
157 }
158 uint64_t getValue() const {
159 assert(hasValue() && "Getting value from an unknown LocationSize!")(static_cast <bool> (hasValue() && "Getting value from an unknown LocationSize!"
) ? void (0) : __assert_fail ("hasValue() && \"Getting value from an unknown LocationSize!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/Analysis/MemoryLocation.h"
, 159, __extension__ __PRETTY_FUNCTION__))
;
160 return Value & ~ImpreciseBit;
161 }
162
163 // Returns whether or not this value is precise. Note that if a value is
164 // precise, it's guaranteed to not be unknown.
165 bool isPrecise() const {
166 return (Value & ImpreciseBit) == 0;
167 }
168
169 // Convenience method to check if this LocationSize's value is 0.
170 bool isZero() const { return hasValue() && getValue() == 0; }
171
172 /// Whether accesses before the base pointer are possible.
173 bool mayBeBeforePointer() const { return Value == BeforeOrAfterPointer; }
174
175 bool operator==(const LocationSize &Other) const {
176 return Value == Other.Value;
177 }
178
179 bool operator!=(const LocationSize &Other) const {
180 return !(*this == Other);
181 }
182
183 // Ordering operators are not provided, since it's unclear if there's only one
184 // reasonable way to compare:
185 // - values that don't exist against values that do, and
186 // - precise values to imprecise values
187
188 void print(raw_ostream &OS) const;
189
190 // Returns an opaque value that represents this LocationSize. Cannot be
191 // reliably converted back into a LocationSize.
192 uint64_t toRaw() const { return Value; }
193};
194
195inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
196 Size.print(OS);
197 return OS;
198}
199
200/// Representation for a specific memory location.
201///
202/// This abstraction can be used to represent a specific location in memory.
203/// The goal of the location is to represent enough information to describe
204/// abstract aliasing, modification, and reference behaviors of whatever
205/// value(s) are stored in memory at the particular location.
206///
207/// The primary user of this interface is LLVM's Alias Analysis, but other
208/// memory analyses such as MemoryDependence can use it as well.
209class MemoryLocation {
210public:
211 /// UnknownSize - This is a special value which can be used with the
212 /// size arguments in alias queries to indicate that the caller does not
213 /// know the sizes of the potential memory references.
214 enum : uint64_t { UnknownSize = ~UINT64_C(0)0UL };
215
216 /// The address of the start of the location.
217 const Value *Ptr;
218
219 /// The maximum size of the location, in address-units, or
220 /// UnknownSize if the size is not known.
221 ///
222 /// Note that an unknown size does not mean the pointer aliases the entire
223 /// virtual address space, because there are restrictions on stepping out of
224 /// one object and into another. See
225 /// http://llvm.org/docs/LangRef.html#pointeraliasing
226 LocationSize Size;
227
228 /// The metadata nodes which describes the aliasing of the location (each
229 /// member is null if that kind of information is unavailable).
230 AAMDNodes AATags;
231
232 void print(raw_ostream &OS) const { OS << *Ptr << " " << Size << "\n"; }
233
234 /// Return a location with information about the memory reference by the given
235 /// instruction.
236 static MemoryLocation get(const LoadInst *LI);
237 static MemoryLocation get(const StoreInst *SI);
238 static MemoryLocation get(const VAArgInst *VI);
239 static MemoryLocation get(const AtomicCmpXchgInst *CXI);
240 static MemoryLocation get(const AtomicRMWInst *RMWI);
241 static MemoryLocation get(const Instruction *Inst) {
242 return *MemoryLocation::getOrNone(Inst);
243 }
244 static Optional<MemoryLocation> getOrNone(const Instruction *Inst);
245
246 /// Return a location representing the source of a memory transfer.
247 static MemoryLocation getForSource(const MemTransferInst *MTI);
248 static MemoryLocation getForSource(const AtomicMemTransferInst *MTI);
249 static MemoryLocation getForSource(const AnyMemTransferInst *MTI);
250
251 /// Return a location representing the destination of a memory set or
252 /// transfer.
253 static MemoryLocation getForDest(const MemIntrinsic *MI);
254 static MemoryLocation getForDest(const AtomicMemIntrinsic *MI);
255 static MemoryLocation getForDest(const AnyMemIntrinsic *MI);
256
257 /// Return a location representing a particular argument of a call.
258 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
259 const TargetLibraryInfo *TLI);
260 static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx,
261 const TargetLibraryInfo &TLI) {
262 return getForArgument(Call, ArgIdx, &TLI);
263 }
264
265 /// Return a location that may access any location after Ptr, while remaining
266 /// within the underlying object.
267 static MemoryLocation getAfter(const Value *Ptr,
268 const AAMDNodes &AATags = AAMDNodes()) {
269 return MemoryLocation(Ptr, LocationSize::afterPointer(), AATags);
270 }
271
272 /// Return a location that may access any location before or after Ptr, while
273 /// remaining within the underlying object.
274 static MemoryLocation
275 getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags = AAMDNodes()) {
276 return MemoryLocation(Ptr, LocationSize::beforeOrAfterPointer(), AATags);
277 }
278
279 // Return the exact size if the exact size is known at compiletime,
280 // otherwise return MemoryLocation::UnknownSize.
281 static uint64_t getSizeOrUnknown(const TypeSize &T) {
282 return T.isScalable() ? UnknownSize : T.getFixedSize();
283 }
284
285 MemoryLocation()
286 : Ptr(nullptr), Size(LocationSize::beforeOrAfterPointer()), AATags() {}
15
Null pointer value stored to 'Loc.Ptr'
287
288 explicit MemoryLocation(const Value *Ptr, LocationSize Size,
289 const AAMDNodes &AATags = AAMDNodes())
290 : Ptr(Ptr), Size(Size), AATags(AATags) {}
291
292 MemoryLocation getWithNewPtr(const Value *NewPtr) const {
293 MemoryLocation Copy(*this);
294 Copy.Ptr = NewPtr;
295 return Copy;
296 }
297
298 MemoryLocation getWithNewSize(LocationSize NewSize) const {
299 MemoryLocation Copy(*this);
300 Copy.Size = NewSize;
301 return Copy;
302 }
303
304 MemoryLocation getWithoutAATags() const {
305 MemoryLocation Copy(*this);
306 Copy.AATags = AAMDNodes();
307 return Copy;
308 }
309
310 bool operator==(const MemoryLocation &Other) const {
311 return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
312 }
313};
314
315// Specialize DenseMapInfo.
316template <> struct DenseMapInfo<LocationSize> {
317 static inline LocationSize getEmptyKey() {
318 return LocationSize::mapEmpty();
319 }
320 static inline LocationSize getTombstoneKey() {
321 return LocationSize::mapTombstone();
322 }
323 static unsigned getHashValue(const LocationSize &Val) {
324 return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
325 }
326 static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
327 return LHS == RHS;
328 }
329};
330
331template <> struct DenseMapInfo<MemoryLocation> {
332 static inline MemoryLocation getEmptyKey() {
333 return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
334 DenseMapInfo<LocationSize>::getEmptyKey());
335 }
336 static inline MemoryLocation getTombstoneKey() {
337 return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
338 DenseMapInfo<LocationSize>::getTombstoneKey());
339 }
340 static unsigned getHashValue(const MemoryLocation &Val) {
341 return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
342 DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^
343 DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
344 }
345 static bool isEqual(const MemoryLocation &LHS, const MemoryLocation &RHS) {
346 return LHS == RHS;
347 }
348};
349}
350
351#endif