Bug Summary

File:llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
Warning:line 1274, column 11
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 -fhalf-no-semantic-interposition -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-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/Scalar -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../x86_64-linux-gnu/include -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/build-llvm/lib/Transforms/Scalar -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-04-05-202135-9119-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

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

/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h

1//===- MemorySSA.h - Build Memory SSA ---------------------------*- 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//
9/// \file
10/// This file exposes an interface to building/using memory SSA to
11/// walk memory instructions using a use/def graph.
12///
13/// Memory SSA class builds an SSA form that links together memory access
14/// instructions such as loads, stores, atomics, and calls. Additionally, it
15/// does a trivial form of "heap versioning" Every time the memory state changes
16/// in the program, we generate a new heap version. It generates
17/// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
18///
19/// As a trivial example,
20/// define i32 @main() #0 {
21/// entry:
22/// %call = call noalias i8* @_Znwm(i64 4) #2
23/// %0 = bitcast i8* %call to i32*
24/// %call1 = call noalias i8* @_Znwm(i64 4) #2
25/// %1 = bitcast i8* %call1 to i32*
26/// store i32 5, i32* %0, align 4
27/// store i32 7, i32* %1, align 4
28/// %2 = load i32* %0, align 4
29/// %3 = load i32* %1, align 4
30/// %add = add nsw i32 %2, %3
31/// ret i32 %add
32/// }
33///
34/// Will become
35/// define i32 @main() #0 {
36/// entry:
37/// ; 1 = MemoryDef(0)
38/// %call = call noalias i8* @_Znwm(i64 4) #3
39/// %2 = bitcast i8* %call to i32*
40/// ; 2 = MemoryDef(1)
41/// %call1 = call noalias i8* @_Znwm(i64 4) #3
42/// %4 = bitcast i8* %call1 to i32*
43/// ; 3 = MemoryDef(2)
44/// store i32 5, i32* %2, align 4
45/// ; 4 = MemoryDef(3)
46/// store i32 7, i32* %4, align 4
47/// ; MemoryUse(3)
48/// %7 = load i32* %2, align 4
49/// ; MemoryUse(4)
50/// %8 = load i32* %4, align 4
51/// %add = add nsw i32 %7, %8
52/// ret i32 %add
53/// }
54///
55/// Given this form, all the stores that could ever effect the load at %8 can be
56/// gotten by using the MemoryUse associated with it, and walking from use to
57/// def until you hit the top of the function.
58///
59/// Each def also has a list of users associated with it, so you can walk from
60/// both def to users, and users to defs. Note that we disambiguate MemoryUses,
61/// but not the RHS of MemoryDefs. You can see this above at %7, which would
62/// otherwise be a MemoryUse(4). Being disambiguated means that for a given
63/// store, all the MemoryUses on its use lists are may-aliases of that store
64/// (but the MemoryDefs on its use list may not be).
65///
66/// MemoryDefs are not disambiguated because it would require multiple reaching
67/// definitions, which would require multiple phis, and multiple memoryaccesses
68/// per instruction.
69//
70//===----------------------------------------------------------------------===//
71
72#ifndef LLVM_ANALYSIS_MEMORYSSA_H
73#define LLVM_ANALYSIS_MEMORYSSA_H
74
75#include "llvm/ADT/DenseMap.h"
76#include "llvm/ADT/GraphTraits.h"
77#include "llvm/ADT/SmallPtrSet.h"
78#include "llvm/ADT/SmallVector.h"
79#include "llvm/ADT/ilist.h"
80#include "llvm/ADT/ilist_node.h"
81#include "llvm/ADT/iterator.h"
82#include "llvm/ADT/iterator_range.h"
83#include "llvm/ADT/simple_ilist.h"
84#include "llvm/Analysis/AliasAnalysis.h"
85#include "llvm/Analysis/MemoryLocation.h"
86#include "llvm/Analysis/PHITransAddr.h"
87#include "llvm/IR/BasicBlock.h"
88#include "llvm/IR/DerivedUser.h"
89#include "llvm/IR/Dominators.h"
90#include "llvm/IR/Module.h"
91#include "llvm/IR/Operator.h"
92#include "llvm/IR/Type.h"
93#include "llvm/IR/Use.h"
94#include "llvm/IR/User.h"
95#include "llvm/IR/Value.h"
96#include "llvm/IR/ValueHandle.h"
97#include "llvm/Pass.h"
98#include "llvm/Support/Casting.h"
99#include "llvm/Support/CommandLine.h"
100#include <algorithm>
101#include <cassert>
102#include <cstddef>
103#include <iterator>
104#include <memory>
105#include <utility>
106
107namespace llvm {
108
109/// Enables memory ssa as a dependency for loop passes.
110extern cl::opt<bool> EnableMSSALoopDependency;
111
112class AllocaInst;
113class Function;
114class Instruction;
115class MemoryAccess;
116class MemorySSAWalker;
117class LLVMContext;
118class raw_ostream;
119
120namespace MSSAHelpers {
121
122struct AllAccessTag {};
123struct DefsOnlyTag {};
124
125} // end namespace MSSAHelpers
126
127enum : unsigned {
128 // Used to signify what the default invalid ID is for MemoryAccess's
129 // getID()
130 INVALID_MEMORYACCESS_ID = -1U
131};
132
133template <class T> class memoryaccess_def_iterator_base;
134using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;
135using const_memoryaccess_def_iterator =
136 memoryaccess_def_iterator_base<const MemoryAccess>;
137
138// The base for all memory accesses. All memory accesses in a block are
139// linked together using an intrusive list.
140class MemoryAccess
141 : public DerivedUser,
142 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
143 public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
144public:
145 using AllAccessType =
146 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
147 using DefsOnlyType =
148 ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
149
150 MemoryAccess(const MemoryAccess &) = delete;
151 MemoryAccess &operator=(const MemoryAccess &) = delete;
152
153 void *operator new(size_t) = delete;
154
155 // Methods for support type inquiry through isa, cast, and
156 // dyn_cast
157 static bool classof(const Value *V) {
158 unsigned ID = V->getValueID();
159 return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
160 }
161
162 BasicBlock *getBlock() const { return Block; }
163
164 void print(raw_ostream &OS) const;
165 void dump() const;
166
167 /// The user iterators for a memory access
168 using iterator = user_iterator;
169 using const_iterator = const_user_iterator;
170
171 /// This iterator walks over all of the defs in a given
172 /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
173 /// MemoryUse/MemoryDef, this walks the defining access.
174 memoryaccess_def_iterator defs_begin();
175 const_memoryaccess_def_iterator defs_begin() const;
176 memoryaccess_def_iterator defs_end();
177 const_memoryaccess_def_iterator defs_end() const;
178
179 /// Get the iterators for the all access list and the defs only list
180 /// We default to the all access list.
181 AllAccessType::self_iterator getIterator() {
182 return this->AllAccessType::getIterator();
183 }
184 AllAccessType::const_self_iterator getIterator() const {
185 return this->AllAccessType::getIterator();
186 }
187 AllAccessType::reverse_self_iterator getReverseIterator() {
188 return this->AllAccessType::getReverseIterator();
189 }
190 AllAccessType::const_reverse_self_iterator getReverseIterator() const {
191 return this->AllAccessType::getReverseIterator();
192 }
193 DefsOnlyType::self_iterator getDefsIterator() {
194 return this->DefsOnlyType::getIterator();
195 }
196 DefsOnlyType::const_self_iterator getDefsIterator() const {
197 return this->DefsOnlyType::getIterator();
198 }
199 DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
200 return this->DefsOnlyType::getReverseIterator();
201 }
202 DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
203 return this->DefsOnlyType::getReverseIterator();
204 }
205
206protected:
207 friend class MemoryDef;
208 friend class MemoryPhi;
209 friend class MemorySSA;
210 friend class MemoryUse;
211 friend class MemoryUseOrDef;
212
213 /// Used by MemorySSA to change the block of a MemoryAccess when it is
214 /// moved.
215 void setBlock(BasicBlock *BB) { Block = BB; }
216
217 /// Used for debugging and tracking things about MemoryAccesses.
218 /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
219 inline unsigned getID() const;
220
221 MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
222 BasicBlock *BB, unsigned NumOperands)
223 : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
224 Block(BB) {}
225
226 // Use deleteValue() to delete a generic MemoryAccess.
227 ~MemoryAccess() = default;
228
229private:
230 BasicBlock *Block;
231};
232
233template <>
234struct ilist_alloc_traits<MemoryAccess> {
235 static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
236};
237
238inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
239 MA.print(OS);
240 return OS;
241}
242
243/// Class that has the common methods + fields of memory uses/defs. It's
244/// a little awkward to have, but there are many cases where we want either a
245/// use or def, and there are many cases where uses are needed (defs aren't
246/// acceptable), and vice-versa.
247///
248/// This class should never be instantiated directly; make a MemoryUse or
249/// MemoryDef instead.
250class MemoryUseOrDef : public MemoryAccess {
251public:
252 void *operator new(size_t) = delete;
253
254 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
void setOperand(unsigned, MemoryAccess*); inline op_iterator
op_begin(); inline const_op_iterator op_begin() const; inline
op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
<int> inline const Use &Op() const; public: inline
unsigned getNumOperands() const
;
255
256 /// Get the instruction that this MemoryUse represents.
257 Instruction *getMemoryInst() const { return MemoryInstruction; }
258
259 /// Get the access that produces the memory state used by this Use.
260 MemoryAccess *getDefiningAccess() const { return getOperand(0); }
261
262 static bool classof(const Value *MA) {
263 return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
264 }
265
266 // Sadly, these have to be public because they are needed in some of the
267 // iterators.
268 inline bool isOptimized() const;
269 inline MemoryAccess *getOptimized() const;
270 inline void setOptimized(MemoryAccess *);
271
272 // Retrieve AliasResult type of the optimized access. Ideally this would be
273 // returned by the caching walker and may go away in the future.
274 Optional<AliasResult> getOptimizedAccessType() const {
275 return isOptimized() ? OptimizedAccessAlias : None;
276 }
277
278 /// Reset the ID of what this MemoryUse was optimized to, causing it to
279 /// be rewalked by the walker if necessary.
280 /// This really should only be called by tests.
281 inline void resetOptimized();
282
283protected:
284 friend class MemorySSA;
285 friend class MemorySSAUpdater;
286
287 MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
288 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
289 unsigned NumOperands)
290 : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
291 MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
292 setDefiningAccess(DMA);
293 }
294
295 // Use deleteValue() to delete a generic MemoryUseOrDef.
296 ~MemoryUseOrDef() = default;
297
298 void setOptimizedAccessType(Optional<AliasResult> AR) {
299 OptimizedAccessAlias = AR;
300 }
301
302 void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
303 Optional<AliasResult> AR = MayAlias) {
304 if (!Optimized) {
305 setOperand(0, DMA);
306 return;
307 }
308 setOptimized(DMA);
309 setOptimizedAccessType(AR);
310 }
311
312private:
313 Instruction *MemoryInstruction;
314 Optional<AliasResult> OptimizedAccessAlias;
315};
316
317/// Represents read-only accesses to memory
318///
319/// In particular, the set of Instructions that will be represented by
320/// MemoryUse's is exactly the set of Instructions for which
321/// AliasAnalysis::getModRefInfo returns "Ref".
322class MemoryUse final : public MemoryUseOrDef {
323public:
324 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
void setOperand(unsigned, MemoryAccess*); inline op_iterator
op_begin(); inline const_op_iterator op_begin() const; inline
op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
<int> inline const Use &Op() const; public: inline
unsigned getNumOperands() const
;
325
326 MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
327 : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
328 /*NumOperands=*/1) {}
329
330 // allocate space for exactly one operand
331 void *operator new(size_t s) { return User::operator new(s, 1); }
332
333 static bool classof(const Value *MA) {
334 return MA->getValueID() == MemoryUseVal;
335 }
336
337 void print(raw_ostream &OS) const;
338
339 void setOptimized(MemoryAccess *DMA) {
340 OptimizedID = DMA->getID();
341 setOperand(0, DMA);
342 }
343
344 bool isOptimized() const {
345 return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
346 }
347
348 MemoryAccess *getOptimized() const {
349 return getDefiningAccess();
350 }
351
352 void resetOptimized() {
353 OptimizedID = INVALID_MEMORYACCESS_ID;
354 }
355
356protected:
357 friend class MemorySSA;
358
359private:
360 static void deleteMe(DerivedUser *Self);
361
362 unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
363};
364
365template <>
366struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
367DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)MemoryUse::op_iterator MemoryUse::op_begin() { return OperandTraits
<MemoryUse>::op_begin(this); } MemoryUse::const_op_iterator
MemoryUse::op_begin() const { return OperandTraits<MemoryUse
>::op_begin(const_cast<MemoryUse*>(this)); } MemoryUse
::op_iterator MemoryUse::op_end() { return OperandTraits<MemoryUse
>::op_end(this); } MemoryUse::const_op_iterator MemoryUse::
op_end() const { return OperandTraits<MemoryUse>::op_end
(const_cast<MemoryUse*>(this)); } MemoryAccess *MemoryUse
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<MemoryUse>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 367, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryUse>::op_begin(const_cast<
MemoryUse*>(this))[i_nocapture].get()); } void MemoryUse::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
{ ((i_nocapture < OperandTraits<MemoryUse>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUse>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 367, __PRETTY_FUNCTION__)); OperandTraits<MemoryUse>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryUse
::getNumOperands() const { return OperandTraits<MemoryUse>
::operands(this); } template <int Idx_nocapture> Use &
MemoryUse::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryUse
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
368
369/// Represents a read-write access to memory, whether it is a must-alias,
370/// or a may-alias.
371///
372/// In particular, the set of Instructions that will be represented by
373/// MemoryDef's is exactly the set of Instructions for which
374/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
375/// Note that, in order to provide def-def chains, all defs also have a use
376/// associated with them. This use points to the nearest reaching
377/// MemoryDef/MemoryPhi.
378class MemoryDef final : public MemoryUseOrDef {
379public:
380 friend class MemorySSA;
381
382 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
void setOperand(unsigned, MemoryAccess*); inline op_iterator
op_begin(); inline const_op_iterator op_begin() const; inline
op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
<int> inline const Use &Op() const; public: inline
unsigned getNumOperands() const
;
383
384 MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
385 unsigned Ver)
386 : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
387 /*NumOperands=*/2),
388 ID(Ver) {}
389
390 // allocate space for exactly two operands
391 void *operator new(size_t s) { return User::operator new(s, 2); }
392
393 static bool classof(const Value *MA) {
394 return MA->getValueID() == MemoryDefVal;
395 }
396
397 void setOptimized(MemoryAccess *MA) {
398 setOperand(1, MA);
399 OptimizedID = MA->getID();
400 }
401
402 MemoryAccess *getOptimized() const {
403 return cast_or_null<MemoryAccess>(getOperand(1));
404 }
405
406 bool isOptimized() const {
407 return getOptimized() && OptimizedID == getOptimized()->getID();
408 }
409
410 void resetOptimized() {
411 OptimizedID = INVALID_MEMORYACCESS_ID;
412 setOperand(1, nullptr);
413 }
414
415 void print(raw_ostream &OS) const;
416
417 unsigned getID() const { return ID; }
418
419private:
420 static void deleteMe(DerivedUser *Self);
421
422 const unsigned ID;
423 unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
424};
425
426template <>
427struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
428DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)MemoryDef::op_iterator MemoryDef::op_begin() { return OperandTraits
<MemoryDef>::op_begin(this); } MemoryDef::const_op_iterator
MemoryDef::op_begin() const { return OperandTraits<MemoryDef
>::op_begin(const_cast<MemoryDef*>(this)); } MemoryDef
::op_iterator MemoryDef::op_end() { return OperandTraits<MemoryDef
>::op_end(this); } MemoryDef::const_op_iterator MemoryDef::
op_end() const { return OperandTraits<MemoryDef>::op_end
(const_cast<MemoryDef*>(this)); } MemoryAccess *MemoryDef
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<MemoryDef>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 428, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryDef>::op_begin(const_cast<
MemoryDef*>(this))[i_nocapture].get()); } void MemoryDef::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
{ ((i_nocapture < OperandTraits<MemoryDef>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 428, __PRETTY_FUNCTION__)); OperandTraits<MemoryDef>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryDef
::getNumOperands() const { return OperandTraits<MemoryDef>
::operands(this); } template <int Idx_nocapture> Use &
MemoryDef::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryDef
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
429
430template <>
431struct OperandTraits<MemoryUseOrDef> {
432 static Use *op_begin(MemoryUseOrDef *MUD) {
433 if (auto *MU = dyn_cast<MemoryUse>(MUD))
434 return OperandTraits<MemoryUse>::op_begin(MU);
435 return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
436 }
437
438 static Use *op_end(MemoryUseOrDef *MUD) {
439 if (auto *MU = dyn_cast<MemoryUse>(MUD))
440 return OperandTraits<MemoryUse>::op_end(MU);
441 return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
442 }
443
444 static unsigned operands(const MemoryUseOrDef *MUD) {
445 if (const auto *MU = dyn_cast<MemoryUse>(MUD))
446 return OperandTraits<MemoryUse>::operands(MU);
447 return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
448 }
449};
450DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)MemoryUseOrDef::op_iterator MemoryUseOrDef::op_begin() { return
OperandTraits<MemoryUseOrDef>::op_begin(this); } MemoryUseOrDef
::const_op_iterator MemoryUseOrDef::op_begin() const { return
OperandTraits<MemoryUseOrDef>::op_begin(const_cast<
MemoryUseOrDef*>(this)); } MemoryUseOrDef::op_iterator MemoryUseOrDef
::op_end() { return OperandTraits<MemoryUseOrDef>::op_end
(this); } MemoryUseOrDef::const_op_iterator MemoryUseOrDef::op_end
() const { return OperandTraits<MemoryUseOrDef>::op_end
(const_cast<MemoryUseOrDef*>(this)); } MemoryAccess *MemoryUseOrDef
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<MemoryUseOrDef>::operands(this) &&
"getOperand() out of range!") ? static_cast<void> (0) :
__assert_fail ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 450, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryUseOrDef>::op_begin(const_cast
<MemoryUseOrDef*>(this))[i_nocapture].get()); } void MemoryUseOrDef
::setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture
) { ((i_nocapture < OperandTraits<MemoryUseOrDef>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryUseOrDef>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 450, __PRETTY_FUNCTION__)); OperandTraits<MemoryUseOrDef
>::op_begin(this)[i_nocapture] = Val_nocapture; } unsigned
MemoryUseOrDef::getNumOperands() const { return OperandTraits
<MemoryUseOrDef>::operands(this); } template <int Idx_nocapture
> Use &MemoryUseOrDef::Op() { return this->OpFrom<
Idx_nocapture>(this); } template <int Idx_nocapture>
const Use &MemoryUseOrDef::Op() const { return this->
OpFrom<Idx_nocapture>(this); }
451
452/// Represents phi nodes for memory accesses.
453///
454/// These have the same semantic as regular phi nodes, with the exception that
455/// only one phi will ever exist in a given basic block.
456/// Guaranteeing one phi per block means guaranteeing there is only ever one
457/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
458/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
459/// a MemoryPhi's operands.
460/// That is, given
461/// if (a) {
462/// store %a
463/// store %b
464/// }
465/// it *must* be transformed into
466/// if (a) {
467/// 1 = MemoryDef(liveOnEntry)
468/// store %a
469/// 2 = MemoryDef(1)
470/// store %b
471/// }
472/// and *not*
473/// if (a) {
474/// 1 = MemoryDef(liveOnEntry)
475/// store %a
476/// 2 = MemoryDef(liveOnEntry)
477/// store %b
478/// }
479/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
480/// end of the branch, and if there are not two phi nodes, one will be
481/// disconnected completely from the SSA graph below that point.
482/// Because MemoryUse's do not generate new definitions, they do not have this
483/// issue.
484class MemoryPhi final : public MemoryAccess {
485 // allocate space for exactly zero operands
486 void *operator new(size_t s) { return User::operator new(s); }
487
488public:
489 /// Provide fast operand accessors
490 DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess)public: inline MemoryAccess *getOperand(unsigned) const; inline
void setOperand(unsigned, MemoryAccess*); inline op_iterator
op_begin(); inline const_op_iterator op_begin() const; inline
op_iterator op_end(); inline const_op_iterator op_end() const
; protected: template <int> inline Use &Op(); template
<int> inline const Use &Op() const; public: inline
unsigned getNumOperands() const
;
491
492 MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
493 : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
494 ReservedSpace(NumPreds) {
495 allocHungoffUses(ReservedSpace);
496 }
497
498 // Block iterator interface. This provides access to the list of incoming
499 // basic blocks, which parallels the list of incoming values.
500 using block_iterator = BasicBlock **;
501 using const_block_iterator = BasicBlock *const *;
502
503 block_iterator block_begin() {
504 return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
505 }
506
507 const_block_iterator block_begin() const {
508 return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
509 }
510
511 block_iterator block_end() { return block_begin() + getNumOperands(); }
512
513 const_block_iterator block_end() const {
514 return block_begin() + getNumOperands();
515 }
516
517 iterator_range<block_iterator> blocks() {
518 return make_range(block_begin(), block_end());
519 }
520
521 iterator_range<const_block_iterator> blocks() const {
522 return make_range(block_begin(), block_end());
523 }
524
525 op_range incoming_values() { return operands(); }
526
527 const_op_range incoming_values() const { return operands(); }
528
529 /// Return the number of incoming edges
530 unsigned getNumIncomingValues() const { return getNumOperands(); }
531
532 /// Return incoming value number x
533 MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
534 void setIncomingValue(unsigned I, MemoryAccess *V) {
535 assert(V && "PHI node got a null value!")((V && "PHI node got a null value!") ? static_cast<
void> (0) : __assert_fail ("V && \"PHI node got a null value!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 535, __PRETTY_FUNCTION__))
;
536 setOperand(I, V);
537 }
538
539 static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
540 static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
541
542 /// Return incoming basic block number @p i.
543 BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
544
545 /// Return incoming basic block corresponding
546 /// to an operand of the PHI.
547 BasicBlock *getIncomingBlock(const Use &U) const {
548 assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?")((this == U.getUser() && "Iterator doesn't point to PHI's Uses?"
) ? static_cast<void> (0) : __assert_fail ("this == U.getUser() && \"Iterator doesn't point to PHI's Uses?\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 548, __PRETTY_FUNCTION__))
;
549 return getIncomingBlock(unsigned(&U - op_begin()));
550 }
551
552 /// Return incoming basic block corresponding
553 /// to value use iterator.
554 BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
555 return getIncomingBlock(I.getUse());
556 }
557
558 void setIncomingBlock(unsigned I, BasicBlock *BB) {
559 assert(BB && "PHI node got a null basic block!")((BB && "PHI node got a null basic block!") ? static_cast
<void> (0) : __assert_fail ("BB && \"PHI node got a null basic block!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 559, __PRETTY_FUNCTION__))
;
560 block_begin()[I] = BB;
561 }
562
563 /// Add an incoming value to the end of the PHI list
564 void addIncoming(MemoryAccess *V, BasicBlock *BB) {
565 if (getNumOperands() == ReservedSpace)
566 growOperands(); // Get more space!
567 // Initialize some new operands.
568 setNumHungOffUseOperands(getNumOperands() + 1);
569 setIncomingValue(getNumOperands() - 1, V);
570 setIncomingBlock(getNumOperands() - 1, BB);
571 }
572
573 /// Return the first index of the specified basic
574 /// block in the value list for this PHI. Returns -1 if no instance.
575 int getBasicBlockIndex(const BasicBlock *BB) const {
576 for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
577 if (block_begin()[I] == BB)
578 return I;
579 return -1;
580 }
581
582 MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
583 int Idx = getBasicBlockIndex(BB);
584 assert(Idx >= 0 && "Invalid basic block argument!")((Idx >= 0 && "Invalid basic block argument!") ? static_cast
<void> (0) : __assert_fail ("Idx >= 0 && \"Invalid basic block argument!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 584, __PRETTY_FUNCTION__))
;
585 return getIncomingValue(Idx);
586 }
587
588 // After deleting incoming position I, the order of incoming may be changed.
589 void unorderedDeleteIncoming(unsigned I) {
590 unsigned E = getNumOperands();
591 assert(I < E && "Cannot remove out of bounds Phi entry.")((I < E && "Cannot remove out of bounds Phi entry."
) ? static_cast<void> (0) : __assert_fail ("I < E && \"Cannot remove out of bounds Phi entry.\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 591, __PRETTY_FUNCTION__))
;
592 // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
593 // itself should be deleted.
594 assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "((E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
"at least 2 values.") ? static_cast<void> (0) : __assert_fail
("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 595, __PRETTY_FUNCTION__))
595 "at least 2 values.")((E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
"at least 2 values.") ? static_cast<void> (0) : __assert_fail
("E >= 2 && \"Cannot only remove incoming values in MemoryPhis with \" \"at least 2 values.\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 595, __PRETTY_FUNCTION__))
;
596 setIncomingValue(I, getIncomingValue(E - 1));
597 setIncomingBlock(I, block_begin()[E - 1]);
598 setOperand(E - 1, nullptr);
599 block_begin()[E - 1] = nullptr;
600 setNumHungOffUseOperands(getNumOperands() - 1);
601 }
602
603 // After deleting entries that satisfy Pred, remaining entries may have
604 // changed order.
605 template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
606 for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
607 if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
608 unorderedDeleteIncoming(I);
609 E = getNumOperands();
610 --I;
611 }
612 assert(getNumOperands() >= 1 &&((getNumOperands() >= 1 && "Cannot remove all incoming blocks in a MemoryPhi."
) ? static_cast<void> (0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 613, __PRETTY_FUNCTION__))
613 "Cannot remove all incoming blocks in a MemoryPhi.")((getNumOperands() >= 1 && "Cannot remove all incoming blocks in a MemoryPhi."
) ? static_cast<void> (0) : __assert_fail ("getNumOperands() >= 1 && \"Cannot remove all incoming blocks in a MemoryPhi.\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 613, __PRETTY_FUNCTION__))
;
614 }
615
616 // After deleting incoming block BB, the incoming blocks order may be changed.
617 void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
618 unorderedDeleteIncomingIf(
619 [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
620 }
621
622 // After deleting incoming memory access MA, the incoming accesses order may
623 // be changed.
624 void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
625 unorderedDeleteIncomingIf(
626 [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
627 }
628
629 static bool classof(const Value *V) {
630 return V->getValueID() == MemoryPhiVal;
631 }
632
633 void print(raw_ostream &OS) const;
634
635 unsigned getID() const { return ID; }
636
637protected:
638 friend class MemorySSA;
639
640 /// this is more complicated than the generic
641 /// User::allocHungoffUses, because we have to allocate Uses for the incoming
642 /// values and pointers to the incoming blocks, all in one allocation.
643 void allocHungoffUses(unsigned N) {
644 User::allocHungoffUses(N, /* IsPhi */ true);
645 }
646
647private:
648 // For debugging only
649 const unsigned ID;
650 unsigned ReservedSpace;
651
652 /// This grows the operand list in response to a push_back style of
653 /// operation. This grows the number of ops by 1.5 times.
654 void growOperands() {
655 unsigned E = getNumOperands();
656 // 2 op PHI nodes are VERY common, so reserve at least enough for that.
657 ReservedSpace = std::max(E + E / 2, 2u);
658 growHungoffUses(ReservedSpace, /* IsPhi */ true);
659 }
660
661 static void deleteMe(DerivedUser *Self);
662};
663
664inline unsigned MemoryAccess::getID() const {
665 assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&(((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
"only memory defs and phis have ids") ? static_cast<void>
(0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 666, __PRETTY_FUNCTION__))
666 "only memory defs and phis have ids")(((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
"only memory defs and phis have ids") ? static_cast<void>
(0) : __assert_fail ("(isa<MemoryDef>(this) || isa<MemoryPhi>(this)) && \"only memory defs and phis have ids\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 666, __PRETTY_FUNCTION__))
;
667 if (const auto *MD = dyn_cast<MemoryDef>(this))
668 return MD->getID();
669 return cast<MemoryPhi>(this)->getID();
670}
671
672inline bool MemoryUseOrDef::isOptimized() const {
673 if (const auto *MD = dyn_cast<MemoryDef>(this))
674 return MD->isOptimized();
675 return cast<MemoryUse>(this)->isOptimized();
676}
677
678inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
679 if (const auto *MD = dyn_cast<MemoryDef>(this))
680 return MD->getOptimized();
681 return cast<MemoryUse>(this)->getOptimized();
682}
683
684inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
685 if (auto *MD = dyn_cast<MemoryDef>(this))
686 MD->setOptimized(MA);
687 else
688 cast<MemoryUse>(this)->setOptimized(MA);
689}
690
691inline void MemoryUseOrDef::resetOptimized() {
692 if (auto *MD = dyn_cast<MemoryDef>(this))
693 MD->resetOptimized();
694 else
695 cast<MemoryUse>(this)->resetOptimized();
696}
697
698template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
699DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)MemoryPhi::op_iterator MemoryPhi::op_begin() { return OperandTraits
<MemoryPhi>::op_begin(this); } MemoryPhi::const_op_iterator
MemoryPhi::op_begin() const { return OperandTraits<MemoryPhi
>::op_begin(const_cast<MemoryPhi*>(this)); } MemoryPhi
::op_iterator MemoryPhi::op_end() { return OperandTraits<MemoryPhi
>::op_end(this); } MemoryPhi::const_op_iterator MemoryPhi::
op_end() const { return OperandTraits<MemoryPhi>::op_end
(const_cast<MemoryPhi*>(this)); } MemoryAccess *MemoryPhi
::getOperand(unsigned i_nocapture) const { ((i_nocapture <
OperandTraits<MemoryPhi>::operands(this) && "getOperand() out of range!"
) ? static_cast<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 699, __PRETTY_FUNCTION__)); return cast_or_null<MemoryAccess
>( OperandTraits<MemoryPhi>::op_begin(const_cast<
MemoryPhi*>(this))[i_nocapture].get()); } void MemoryPhi::
setOperand(unsigned i_nocapture, MemoryAccess *Val_nocapture)
{ ((i_nocapture < OperandTraits<MemoryPhi>::operands
(this) && "setOperand() out of range!") ? static_cast
<void> (0) : __assert_fail ("i_nocapture < OperandTraits<MemoryPhi>::operands(this) && \"setOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 699, __PRETTY_FUNCTION__)); OperandTraits<MemoryPhi>::
op_begin(this)[i_nocapture] = Val_nocapture; } unsigned MemoryPhi
::getNumOperands() const { return OperandTraits<MemoryPhi>
::operands(this); } template <int Idx_nocapture> Use &
MemoryPhi::Op() { return this->OpFrom<Idx_nocapture>
(this); } template <int Idx_nocapture> const Use &MemoryPhi
::Op() const { return this->OpFrom<Idx_nocapture>(this
); }
700
701/// Encapsulates MemorySSA, including all data associated with memory
702/// accesses.
703class MemorySSA {
704public:
705 MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
706
707 // MemorySSA must remain where it's constructed; Walkers it creates store
708 // pointers to it.
709 MemorySSA(MemorySSA &&) = delete;
710
711 ~MemorySSA();
712
713 MemorySSAWalker *getWalker();
714 MemorySSAWalker *getSkipSelfWalker();
715
716 /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
717 /// access associated with it. If passed a basic block gets the memory phi
718 /// node that exists for that block, if there is one. Otherwise, this will get
719 /// a MemoryUseOrDef.
720 MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
721 return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
722 }
723
724 MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
725 return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
726 }
727
728 DominatorTree &getDomTree() const { return *DT; }
729
730 void dump() const;
731 void print(raw_ostream &) const;
732
733 /// Return true if \p MA represents the live on entry value
734 ///
735 /// Loads and stores from pointer arguments and other global values may be
736 /// defined by memory operations that do not occur in the current function, so
737 /// they may be live on entry to the function. MemorySSA represents such
738 /// memory state by the live on entry definition, which is guaranteed to occur
739 /// before any other memory access in the function.
740 inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
741 return MA == LiveOnEntryDef.get();
8
Assuming the condition is false
9
Returning zero, which participates in a condition later
742 }
743
744 inline MemoryAccess *getLiveOnEntryDef() const {
745 return LiveOnEntryDef.get();
746 }
747
748 // Sadly, iplists, by default, owns and deletes pointers added to the
749 // list. It's not currently possible to have two iplists for the same type,
750 // where one owns the pointers, and one does not. This is because the traits
751 // are per-type, not per-tag. If this ever changes, we should make the
752 // DefList an iplist.
753 using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
754 using DefsList =
755 simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
756
757 /// Return the list of MemoryAccess's for a given basic block.
758 ///
759 /// This list is not modifiable by the user.
760 const AccessList *getBlockAccesses(const BasicBlock *BB) const {
761 return getWritableBlockAccesses(BB);
762 }
763
764 /// Return the list of MemoryDef's and MemoryPhi's for a given basic
765 /// block.
766 ///
767 /// This list is not modifiable by the user.
768 const DefsList *getBlockDefs(const BasicBlock *BB) const {
769 return getWritableBlockDefs(BB);
770 }
771
772 /// Given two memory accesses in the same basic block, determine
773 /// whether MemoryAccess \p A dominates MemoryAccess \p B.
774 bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
775
776 /// Given two memory accesses in potentially different blocks,
777 /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
778 bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
779
780 /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
781 /// dominates Use \p B.
782 bool dominates(const MemoryAccess *A, const Use &B) const;
783
784 /// Verify that MemorySSA is self consistent (IE definitions dominate
785 /// all uses, uses appear in the right places). This is used by unit tests.
786 void verifyMemorySSA() const;
787
788 /// Used in various insertion functions to specify whether we are talking
789 /// about the beginning or end of a block.
790 enum InsertionPlace { Beginning, End, BeforeTerminator };
791
792protected:
793 // Used by Memory SSA annotater, dumpers, and wrapper pass
794 friend class MemorySSAAnnotatedWriter;
795 friend class MemorySSAPrinterLegacyPass;
796 friend class MemorySSAUpdater;
797
798 void verifyOrderingDominationAndDefUses(Function &F) const;
799 void verifyDominationNumbers(const Function &F) const;
800 void verifyPrevDefInPhis(Function &F) const;
801
802 // This is used by the use optimizer and updater.
803 AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
804 auto It = PerBlockAccesses.find(BB);
805 return It == PerBlockAccesses.end() ? nullptr : It->second.get();
806 }
807
808 // This is used by the use optimizer and updater.
809 DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
810 auto It = PerBlockDefs.find(BB);
811 return It == PerBlockDefs.end() ? nullptr : It->second.get();
812 }
813
814 // These is used by the updater to perform various internal MemorySSA
815 // machinsations. They do not always leave the IR in a correct state, and
816 // relies on the updater to fixup what it breaks, so it is not public.
817
818 void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
819 void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
820
821 // Rename the dominator tree branch rooted at BB.
822 void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
823 SmallPtrSetImpl<BasicBlock *> &Visited) {
824 renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
825 }
826
827 void removeFromLookups(MemoryAccess *);
828 void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
829 void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
830 InsertionPlace);
831 void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
832 AccessList::iterator);
833 MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
834 const MemoryUseOrDef *Template = nullptr,
835 bool CreationMustSucceed = true);
836
837private:
838 template <class AliasAnalysisType> class ClobberWalkerBase;
839 template <class AliasAnalysisType> class CachingWalker;
840 template <class AliasAnalysisType> class SkipSelfWalker;
841 class OptimizeUses;
842
843 CachingWalker<AliasAnalysis> *getWalkerImpl();
844 void buildMemorySSA(BatchAAResults &BAA);
845
846 void prepareForMoveTo(MemoryAccess *, BasicBlock *);
847 void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
848
849 using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
850 using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
851
852 void markUnreachableAsLiveOnEntry(BasicBlock *BB);
853 MemoryPhi *createMemoryPhi(BasicBlock *BB);
854 template <typename AliasAnalysisType>
855 MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
856 const MemoryUseOrDef *Template = nullptr);
857 void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
858 MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
859 void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
860 void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
861 SmallPtrSetImpl<BasicBlock *> &Visited,
862 bool SkipVisited = false, bool RenameAllUses = false);
863 AccessList *getOrCreateAccessList(const BasicBlock *);
864 DefsList *getOrCreateDefsList(const BasicBlock *);
865 void renumberBlock(const BasicBlock *) const;
866 AliasAnalysis *AA;
867 DominatorTree *DT;
868 Function &F;
869
870 // Memory SSA mappings
871 DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
872
873 // These two mappings contain the main block to access/def mappings for
874 // MemorySSA. The list contained in PerBlockAccesses really owns all the
875 // MemoryAccesses.
876 // Both maps maintain the invariant that if a block is found in them, the
877 // corresponding list is not empty, and if a block is not found in them, the
878 // corresponding list is empty.
879 AccessMap PerBlockAccesses;
880 DefsMap PerBlockDefs;
881 std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
882
883 // Domination mappings
884 // Note that the numbering is local to a block, even though the map is
885 // global.
886 mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
887 mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
888
889 // Memory SSA building info
890 std::unique_ptr<ClobberWalkerBase<AliasAnalysis>> WalkerBase;
891 std::unique_ptr<CachingWalker<AliasAnalysis>> Walker;
892 std::unique_ptr<SkipSelfWalker<AliasAnalysis>> SkipWalker;
893 unsigned NextID;
894};
895
896// Internal MemorySSA utils, for use by MemorySSA classes and walkers
897class MemorySSAUtil {
898protected:
899 friend class GVNHoist;
900 friend class MemorySSAWalker;
901
902 // This function should not be used by new passes.
903 static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
904 AliasAnalysis &AA);
905};
906
907// This pass does eager building and then printing of MemorySSA. It is used by
908// the tests to be able to build, dump, and verify Memory SSA.
909class MemorySSAPrinterLegacyPass : public FunctionPass {
910public:
911 MemorySSAPrinterLegacyPass();
912
913 bool runOnFunction(Function &) override;
914 void getAnalysisUsage(AnalysisUsage &AU) const override;
915
916 static char ID;
917};
918
919/// An analysis that produces \c MemorySSA for a function.
920///
921class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
922 friend AnalysisInfoMixin<MemorySSAAnalysis>;
923
924 static AnalysisKey Key;
925
926public:
927 // Wrap MemorySSA result to ensure address stability of internal MemorySSA
928 // pointers after construction. Use a wrapper class instead of plain
929 // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
930 struct Result {
931 Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
932
933 MemorySSA &getMSSA() { return *MSSA.get(); }
934
935 std::unique_ptr<MemorySSA> MSSA;
936
937 bool invalidate(Function &F, const PreservedAnalyses &PA,
938 FunctionAnalysisManager::Invalidator &Inv);
939 };
940
941 Result run(Function &F, FunctionAnalysisManager &AM);
942};
943
944/// Printer pass for \c MemorySSA.
945class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
946 raw_ostream &OS;
947
948public:
949 explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
950
951 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
952};
953
954/// Verifier pass for \c MemorySSA.
955struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
956 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
957};
958
959/// Legacy analysis pass which computes \c MemorySSA.
960class MemorySSAWrapperPass : public FunctionPass {
961public:
962 MemorySSAWrapperPass();
963
964 static char ID;
965
966 bool runOnFunction(Function &) override;
967 void releaseMemory() override;
968 MemorySSA &getMSSA() { return *MSSA; }
969 const MemorySSA &getMSSA() const { return *MSSA; }
970
971 void getAnalysisUsage(AnalysisUsage &AU) const override;
972
973 void verifyAnalysis() const override;
974 void print(raw_ostream &OS, const Module *M = nullptr) const override;
975
976private:
977 std::unique_ptr<MemorySSA> MSSA;
978};
979
980/// This is the generic walker interface for walkers of MemorySSA.
981/// Walkers are used to be able to further disambiguate the def-use chains
982/// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
983/// you.
984/// In particular, while the def-use chains provide basic information, and are
985/// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
986/// MemoryUse as AliasAnalysis considers it, a user mant want better or other
987/// information. In particular, they may want to use SCEV info to further
988/// disambiguate memory accesses, or they may want the nearest dominating
989/// may-aliasing MemoryDef for a call or a store. This API enables a
990/// standardized interface to getting and using that info.
991class MemorySSAWalker {
992public:
993 MemorySSAWalker(MemorySSA *);
994 virtual ~MemorySSAWalker() = default;
995
996 using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
997
998 /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
999 /// will give you the nearest dominating MemoryAccess that Mod's the location
1000 /// the instruction accesses (by skipping any def which AA can prove does not
1001 /// alias the location(s) accessed by the instruction given).
1002 ///
1003 /// Note that this will return a single access, and it must dominate the
1004 /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
1005 /// this will return the MemoryPhi, not the operand. This means that
1006 /// given:
1007 /// if (a) {
1008 /// 1 = MemoryDef(liveOnEntry)
1009 /// store %a
1010 /// } else {
1011 /// 2 = MemoryDef(liveOnEntry)
1012 /// store %b
1013 /// }
1014 /// 3 = MemoryPhi(2, 1)
1015 /// MemoryUse(3)
1016 /// load %a
1017 ///
1018 /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
1019 /// in the if (a) branch.
1020 MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
1021 MemoryAccess *MA = MSSA->getMemoryAccess(I);
1022 assert(MA && "Handed an instruction that MemorySSA doesn't recognize?")((MA && "Handed an instruction that MemorySSA doesn't recognize?"
) ? static_cast<void> (0) : __assert_fail ("MA && \"Handed an instruction that MemorySSA doesn't recognize?\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1022, __PRETTY_FUNCTION__))
;
1023 return getClobberingMemoryAccess(MA);
1024 }
1025
1026 /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
1027 /// but takes a MemoryAccess instead of an Instruction.
1028 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
1029
1030 /// Given a potentially clobbering memory access and a new location,
1031 /// calling this will give you the nearest dominating clobbering MemoryAccess
1032 /// (by skipping non-aliasing def links).
1033 ///
1034 /// This version of the function is mainly used to disambiguate phi translated
1035 /// pointers, where the value of a pointer may have changed from the initial
1036 /// memory access. Note that this expects to be handed either a MemoryUse,
1037 /// or an already potentially clobbering access. Unlike the above API, if
1038 /// given a MemoryDef that clobbers the pointer as the starting access, it
1039 /// will return that MemoryDef, whereas the above would return the clobber
1040 /// starting from the use side of the memory def.
1041 virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1042 const MemoryLocation &) = 0;
1043
1044 /// Given a memory access, invalidate anything this walker knows about
1045 /// that access.
1046 /// This API is used by walkers that store information to perform basic cache
1047 /// invalidation. This will be called by MemorySSA at appropriate times for
1048 /// the walker it uses or returns.
1049 virtual void invalidateInfo(MemoryAccess *) {}
1050
1051protected:
1052 friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1053 // constructor.
1054 MemorySSA *MSSA;
1055};
1056
1057/// A MemorySSAWalker that does no alias queries, or anything else. It
1058/// simply returns the links as they were constructed by the builder.
1059class DoNothingMemorySSAWalker final : public MemorySSAWalker {
1060public:
1061 // Keep the overrides below from hiding the Instruction overload of
1062 // getClobberingMemoryAccess.
1063 using MemorySSAWalker::getClobberingMemoryAccess;
1064
1065 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1066 MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1067 const MemoryLocation &) override;
1068};
1069
1070using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1071using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1072
1073/// Iterator base class used to implement const and non-const iterators
1074/// over the defining accesses of a MemoryAccess.
1075template <class T>
1076class memoryaccess_def_iterator_base
1077 : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1078 std::forward_iterator_tag, T, ptrdiff_t, T *,
1079 T *> {
1080 using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1081
1082public:
1083 memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1084 memoryaccess_def_iterator_base() = default;
1085
1086 bool operator==(const memoryaccess_def_iterator_base &Other) const {
1087 return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1088 }
1089
1090 // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1091 // block from the operand in constant time (In a PHINode, the uselist has
1092 // both, so it's just subtraction). We provide it as part of the
1093 // iterator to avoid callers having to linear walk to get the block.
1094 // If the operation becomes constant time on MemoryPHI's, this bit of
1095 // abstraction breaking should be removed.
1096 BasicBlock *getPhiArgBlock() const {
1097 MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1098 assert(MP && "Tried to get phi arg block when not iterating over a PHI")((MP && "Tried to get phi arg block when not iterating over a PHI"
) ? static_cast<void> (0) : __assert_fail ("MP && \"Tried to get phi arg block when not iterating over a PHI\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1098, __PRETTY_FUNCTION__))
;
1099 return MP->getIncomingBlock(ArgNo);
1100 }
1101
1102 typename BaseT::iterator::pointer operator*() const {
1103 assert(Access && "Tried to access past the end of our iterator")((Access && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("Access && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1103, __PRETTY_FUNCTION__))
;
1104 // Go to the first argument for phis, and the defining access for everything
1105 // else.
1106 if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1107 return MP->getIncomingValue(ArgNo);
1108 return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1109 }
1110
1111 using BaseT::operator++;
1112 memoryaccess_def_iterator_base &operator++() {
1113 assert(Access && "Hit end of iterator")((Access && "Hit end of iterator") ? static_cast<void
> (0) : __assert_fail ("Access && \"Hit end of iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1113, __PRETTY_FUNCTION__))
;
1114 if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1115 if (++ArgNo >= MP->getNumIncomingValues()) {
1116 ArgNo = 0;
1117 Access = nullptr;
1118 }
1119 } else {
1120 Access = nullptr;
1121 }
1122 return *this;
1123 }
1124
1125private:
1126 T *Access = nullptr;
1127 unsigned ArgNo = 0;
1128};
1129
1130inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
1131 return memoryaccess_def_iterator(this);
1132}
1133
1134inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
1135 return const_memoryaccess_def_iterator(this);
1136}
1137
1138inline memoryaccess_def_iterator MemoryAccess::defs_end() {
1139 return memoryaccess_def_iterator();
1140}
1141
1142inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
1143 return const_memoryaccess_def_iterator();
1144}
1145
1146/// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1147/// and uses in the inverse case.
1148template <> struct GraphTraits<MemoryAccess *> {
1149 using NodeRef = MemoryAccess *;
1150 using ChildIteratorType = memoryaccess_def_iterator;
1151
1152 static NodeRef getEntryNode(NodeRef N) { return N; }
1153 static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
1154 static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1155};
1156
1157template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1158 using NodeRef = MemoryAccess *;
1159 using ChildIteratorType = MemoryAccess::iterator;
1160
1161 static NodeRef getEntryNode(NodeRef N) { return N; }
1162 static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
1163 static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1164};
1165
1166/// Provide an iterator that walks defs, giving both the memory access,
1167/// and the current pointer location, updating the pointer location as it
1168/// changes due to phi node translation.
1169///
1170/// This iterator, while somewhat specialized, is what most clients actually
1171/// want when walking upwards through MemorySSA def chains. It takes a pair of
1172/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1173/// memory location through phi nodes for the user.
1174class upward_defs_iterator
1175 : public iterator_facade_base<upward_defs_iterator,
1176 std::forward_iterator_tag,
1177 const MemoryAccessPair> {
1178 using BaseT = upward_defs_iterator::iterator_facade_base;
1179
1180public:
1181 upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT,
1182 bool *PerformedPhiTranslation = nullptr)
1183 : DefIterator(Info.first), Location(Info.second),
1184 OriginalAccess(Info.first), DT(DT),
1185 PerformedPhiTranslation(PerformedPhiTranslation) {
1186 CurrentPair.first = nullptr;
1187
1188 WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1189 fillInCurrentPair();
1190 }
1191
1192 upward_defs_iterator() { CurrentPair.first = nullptr; }
1193
1194 bool operator==(const upward_defs_iterator &Other) const {
1195 return DefIterator == Other.DefIterator;
1196 }
1197
1198 BaseT::iterator::reference operator*() const {
1199 assert(DefIterator != OriginalAccess->defs_end() &&((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1200, __PRETTY_FUNCTION__))
1200 "Tried to access past the end of our iterator")((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of our iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of our iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1200, __PRETTY_FUNCTION__))
;
1201 return CurrentPair;
1202 }
1203
1204 using BaseT::operator++;
1205 upward_defs_iterator &operator++() {
1206 assert(DefIterator != OriginalAccess->defs_end() &&((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of the iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1207, __PRETTY_FUNCTION__))
1207 "Tried to access past the end of the iterator")((DefIterator != OriginalAccess->defs_end() && "Tried to access past the end of the iterator"
) ? static_cast<void> (0) : __assert_fail ("DefIterator != OriginalAccess->defs_end() && \"Tried to access past the end of the iterator\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1207, __PRETTY_FUNCTION__))
;
1208 ++DefIterator;
1209 if (DefIterator != OriginalAccess->defs_end())
1210 fillInCurrentPair();
1211 return *this;
1212 }
1213
1214 BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1215
1216private:
1217 /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
1218 /// loop. In particular, this guarantees that it only references a single
1219 /// MemoryLocation during execution of the containing function.
1220 bool IsGuaranteedLoopInvariant(Value *Ptr) const;
1221
1222 void fillInCurrentPair() {
1223 CurrentPair.first = *DefIterator;
1224 CurrentPair.second = Location;
1225 if (WalkingPhi && Location.Ptr) {
1226 // Mark size as unknown, if the location is not guaranteed to be
1227 // loop-invariant for any possible loop in the function. Setting the size
1228 // to unknown guarantees that any memory accesses that access locations
1229 // after the pointer are considered as clobbers, which is important to
1230 // catch loop carried dependences.
1231 if (Location.Ptr &&
1232 !IsGuaranteedLoopInvariant(const_cast<Value *>(Location.Ptr)))
1233 CurrentPair.second =
1234 Location.getWithNewSize(LocationSize::beforeOrAfterPointer());
1235 PHITransAddr Translator(
1236 const_cast<Value *>(Location.Ptr),
1237 OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1238
1239 if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1240 DefIterator.getPhiArgBlock(), DT,
1241 true)) {
1242 Value *TransAddr = Translator.getAddr();
1243 if (TransAddr != Location.Ptr) {
1244 CurrentPair.second = CurrentPair.second.getWithNewPtr(TransAddr);
1245
1246 if (TransAddr &&
1247 !IsGuaranteedLoopInvariant(const_cast<Value *>(TransAddr)))
1248 CurrentPair.second = CurrentPair.second.getWithNewSize(
1249 LocationSize::beforeOrAfterPointer());
1250
1251 if (PerformedPhiTranslation)
1252 *PerformedPhiTranslation = true;
1253 }
1254 }
1255 }
1256 }
1257
1258 MemoryAccessPair CurrentPair;
1259 memoryaccess_def_iterator DefIterator;
1260 MemoryLocation Location;
1261 MemoryAccess *OriginalAccess = nullptr;
1262 DominatorTree *DT = nullptr;
1263 bool WalkingPhi = false;
1264 bool *PerformedPhiTranslation = nullptr;
1265};
1266
1267inline upward_defs_iterator
1268upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT,
1269 bool *PerformedPhiTranslation = nullptr) {
1270 return upward_defs_iterator(Pair, &DT, PerformedPhiTranslation);
1271}
1272
1273inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
1274
1275inline iterator_range<upward_defs_iterator>
1276upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
1277 return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
1278}
1279
1280/// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1281/// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1282/// comparing against a null def_chain_iterator, this will compare equal only
1283/// after walking said Phi/liveOnEntry.
1284///
1285/// The UseOptimizedChain flag specifies whether to walk the clobbering
1286/// access chain, or all the accesses.
1287///
1288/// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1289/// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1290/// a phi node. The optimized chain walks the clobbering access of a store.
1291/// So if you are just trying to find, given a store, what the next
1292/// thing that would clobber the same memory is, you want the optimized chain.
1293template <class T, bool UseOptimizedChain = false>
1294struct def_chain_iterator
1295 : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1296 std::forward_iterator_tag, MemoryAccess *> {
1297 def_chain_iterator() : MA(nullptr) {}
1298 def_chain_iterator(T MA) : MA(MA) {}
1299
1300 T operator*() const { return MA; }
1301
1302 def_chain_iterator &operator++() {
1303 // N.B. liveOnEntry has a null defining access.
1304 if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1305 if (UseOptimizedChain && MUD->isOptimized())
1306 MA = MUD->getOptimized();
1307 else
1308 MA = MUD->getDefiningAccess();
1309 } else {
1310 MA = nullptr;
1311 }
1312
1313 return *this;
1314 }
1315
1316 bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1317
1318private:
1319 T MA;
1320};
1321
1322template <class T>
1323inline iterator_range<def_chain_iterator<T>>
1324def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1325#ifdef EXPENSIVE_CHECKS
1326 assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&(((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<
T>()) && "UpTo isn't in the def chain!") ? static_cast
<void> (0) : __assert_fail ("(!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) && \"UpTo isn't in the def chain!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1327, __PRETTY_FUNCTION__))
1327 "UpTo isn't in the def chain!")(((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<
T>()) && "UpTo isn't in the def chain!") ? static_cast
<void> (0) : __assert_fail ("(!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) && \"UpTo isn't in the def chain!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/MemorySSA.h"
, 1327, __PRETTY_FUNCTION__))
;
1328#endif
1329 return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
1330}
1331
1332template <class T>
1333inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
1334 return make_range(def_chain_iterator<T, true>(MA),
1335 def_chain_iterator<T, true>(nullptr));
1336}
1337
1338} // end namespace llvm
1339
1340#endif // LLVM_ANALYSIS_MEMORYSSA_H

/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h

1//===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- 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//
9// This file defines the SmallPtrSet class. See the doxygen comment for
10// SmallPtrSetImplBase for more details on the algorithm used.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_SMALLPTRSET_H
15#define LLVM_ADT_SMALLPTRSET_H
16
17#include "llvm/ADT/EpochTracker.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/ReverseIteration.h"
20#include "llvm/Support/type_traits.h"
21#include <cassert>
22#include <cstddef>
23#include <cstdlib>
24#include <cstring>
25#include <initializer_list>
26#include <iterator>
27#include <utility>
28
29namespace llvm {
30
31/// SmallPtrSetImplBase - This is the common code shared among all the
32/// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one
33/// for small and one for large sets.
34///
35/// Small sets use an array of pointers allocated in the SmallPtrSet object,
36/// which is treated as a simple array of pointers. When a pointer is added to
37/// the set, the array is scanned to see if the element already exists, if not
38/// the element is 'pushed back' onto the array. If we run out of space in the
39/// array, we grow into the 'large set' case. SmallSet should be used when the
40/// sets are often small. In this case, no memory allocation is used, and only
41/// light-weight and cache-efficient scanning is used.
42///
43/// Large sets use a classic exponentially-probed hash table. Empty buckets are
44/// represented with an illegal pointer value (-1) to allow null pointers to be
45/// inserted. Tombstones are represented with another illegal pointer value
46/// (-2), to allow deletion. The hash table is resized when the table is 3/4 or
47/// more. When this happens, the table is doubled in size.
48///
49class SmallPtrSetImplBase : public DebugEpochBase {
50 friend class SmallPtrSetIteratorImpl;
51
52protected:
53 /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
54 const void **SmallArray;
55 /// CurArray - This is the current set of buckets. If equal to SmallArray,
56 /// then the set is in 'small mode'.
57 const void **CurArray;
58 /// CurArraySize - The allocated size of CurArray, always a power of two.
59 unsigned CurArraySize;
60
61 /// Number of elements in CurArray that contain a value or are a tombstone.
62 /// If small, all these elements are at the beginning of CurArray and the rest
63 /// is uninitialized.
64 unsigned NumNonEmpty;
65 /// Number of tombstones in CurArray.
66 unsigned NumTombstones;
67
68 // Helpers to copy and move construct a SmallPtrSet.
69 SmallPtrSetImplBase(const void **SmallStorage,
70 const SmallPtrSetImplBase &that);
71 SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
72 SmallPtrSetImplBase &&that);
73
74 explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
75 : SmallArray(SmallStorage), CurArray(SmallStorage),
76 CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
77 assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&((SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
"Initial size must be a power of two!") ? static_cast<void
> (0) : __assert_fail ("SmallSize && (SmallSize & (SmallSize-1)) == 0 && \"Initial size must be a power of two!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 78, __PRETTY_FUNCTION__))
78 "Initial size must be a power of two!")((SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
"Initial size must be a power of two!") ? static_cast<void
> (0) : __assert_fail ("SmallSize && (SmallSize & (SmallSize-1)) == 0 && \"Initial size must be a power of two!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 78, __PRETTY_FUNCTION__))
;
79 }
80
81 ~SmallPtrSetImplBase() {
82 if (!isSmall())
83 free(CurArray);
84 }
85
86public:
87 using size_type = unsigned;
88
89 SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
90
91 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return size() == 0; }
40
Assuming the condition is true
41
Returning the value 1, which participates in a condition later
92 size_type size() const { return NumNonEmpty - NumTombstones; }
93
94 void clear() {
95 incrementEpoch();
96 // If the capacity of the array is huge, and the # elements used is small,
97 // shrink the array.
98 if (!isSmall()) {
99 if (size() * 4 < CurArraySize && CurArraySize > 32)
100 return shrink_and_clear();
101 // Fill the array with empty markers.
102 memset(CurArray, -1, CurArraySize * sizeof(void *));
103 }
104
105 NumNonEmpty = 0;
106 NumTombstones = 0;
107 }
108
109protected:
110 static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
111
112 static void *getEmptyMarker() {
113 // Note that -1 is chosen to make clear() efficiently implementable with
114 // memset and because it's not a valid pointer value.
115 return reinterpret_cast<void*>(-1);
116 }
117
118 const void **EndPointer() const {
119 return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
120 }
121
122 /// insert_imp - This returns true if the pointer was new to the set, false if
123 /// it was already in the set. This is hidden from the client so that the
124 /// derived class can check that the right type of pointer is passed in.
125 std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
126 if (isSmall()) {
127 // Check to see if it is already in the set.
128 const void **LastTombstone = nullptr;
129 for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
130 APtr != E; ++APtr) {
131 const void *Value = *APtr;
132 if (Value == Ptr)
133 return std::make_pair(APtr, false);
134 if (Value == getTombstoneMarker())
135 LastTombstone = APtr;
136 }
137
138 // Did we find any tombstone marker?
139 if (LastTombstone != nullptr) {
140 *LastTombstone = Ptr;
141 --NumTombstones;
142 incrementEpoch();
143 return std::make_pair(LastTombstone, true);
144 }
145
146 // Nope, there isn't. If we stay small, just 'pushback' now.
147 if (NumNonEmpty < CurArraySize) {
148 SmallArray[NumNonEmpty++] = Ptr;
149 incrementEpoch();
150 return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
151 }
152 // Otherwise, hit the big set case, which will call grow.
153 }
154 return insert_imp_big(Ptr);
155 }
156
157 /// erase_imp - If the set contains the specified pointer, remove it and
158 /// return true, otherwise return false. This is hidden from the client so
159 /// that the derived class can check that the right type of pointer is passed
160 /// in.
161 bool erase_imp(const void * Ptr) {
162 const void *const *P = find_imp(Ptr);
163 if (P == EndPointer())
164 return false;
165
166 const void **Loc = const_cast<const void **>(P);
167 assert(*Loc == Ptr && "broken find!")((*Loc == Ptr && "broken find!") ? static_cast<void
> (0) : __assert_fail ("*Loc == Ptr && \"broken find!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 167, __PRETTY_FUNCTION__))
;
168 *Loc = getTombstoneMarker();
169 NumTombstones++;
170 return true;
171 }
172
173 /// Returns the raw pointer needed to construct an iterator. If element not
174 /// found, this will be EndPointer. Otherwise, it will be a pointer to the
175 /// slot which stores Ptr;
176 const void *const * find_imp(const void * Ptr) const {
177 if (isSmall()) {
178 // Linear search for the item.
179 for (const void *const *APtr = SmallArray,
180 *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
181 if (*APtr == Ptr)
182 return APtr;
183 return EndPointer();
184 }
185
186 // Big set case.
187 auto *Bucket = FindBucketFor(Ptr);
188 if (*Bucket == Ptr)
189 return Bucket;
190 return EndPointer();
191 }
192
193private:
194 bool isSmall() const { return CurArray == SmallArray; }
195
196 std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
197
198 const void * const *FindBucketFor(const void *Ptr) const;
199 void shrink_and_clear();
200
201 /// Grow - Allocate a larger backing store for the buckets and move it over.
202 void Grow(unsigned NewSize);
203
204protected:
205 /// swap - Swaps the elements of two sets.
206 /// Note: This method assumes that both sets have the same small size.
207 void swap(SmallPtrSetImplBase &RHS);
208
209 void CopyFrom(const SmallPtrSetImplBase &RHS);
210 void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
211
212private:
213 /// Code shared by MoveFrom() and move constructor.
214 void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
215 /// Code shared by CopyFrom() and copy constructor.
216 void CopyHelper(const SmallPtrSetImplBase &RHS);
217};
218
219/// SmallPtrSetIteratorImpl - This is the common base class shared between all
220/// instances of SmallPtrSetIterator.
221class SmallPtrSetIteratorImpl {
222protected:
223 const void *const *Bucket;
224 const void *const *End;
225
226public:
227 explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
228 : Bucket(BP), End(E) {
229 if (shouldReverseIterate()) {
230 RetreatIfNotValid();
231 return;
232 }
233 AdvanceIfNotValid();
234 }
235
236 bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
237 return Bucket == RHS.Bucket;
238 }
239 bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
240 return Bucket != RHS.Bucket;
241 }
242
243protected:
244 /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
245 /// that is. This is guaranteed to stop because the end() bucket is marked
246 /// valid.
247 void AdvanceIfNotValid() {
248 assert(Bucket <= End)((Bucket <= End) ? static_cast<void> (0) : __assert_fail
("Bucket <= End", "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 248, __PRETTY_FUNCTION__))
;
249 while (Bucket != End &&
250 (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
251 *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
252 ++Bucket;
253 }
254 void RetreatIfNotValid() {
255 assert(Bucket >= End)((Bucket >= End) ? static_cast<void> (0) : __assert_fail
("Bucket >= End", "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 255, __PRETTY_FUNCTION__))
;
256 while (Bucket != End &&
257 (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
258 Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
259 --Bucket;
260 }
261 }
262};
263
264/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
265template <typename PtrTy>
266class SmallPtrSetIterator : public SmallPtrSetIteratorImpl,
267 DebugEpochBase::HandleBase {
268 using PtrTraits = PointerLikeTypeTraits<PtrTy>;
269
270public:
271 using value_type = PtrTy;
272 using reference = PtrTy;
273 using pointer = PtrTy;
274 using difference_type = std::ptrdiff_t;
275 using iterator_category = std::forward_iterator_tag;
276
277 explicit SmallPtrSetIterator(const void *const *BP, const void *const *E,
278 const DebugEpochBase &Epoch)
279 : SmallPtrSetIteratorImpl(BP, E), DebugEpochBase::HandleBase(&Epoch) {}
280
281 // Most methods are provided by the base class.
282
283 const PtrTy operator*() const {
284 assert(isHandleInSync() && "invalid iterator access!")((isHandleInSync() && "invalid iterator access!") ? static_cast
<void> (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 284, __PRETTY_FUNCTION__))
;
285 if (shouldReverseIterate()) {
286 assert(Bucket > End)((Bucket > End) ? static_cast<void> (0) : __assert_fail
("Bucket > End", "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 286, __PRETTY_FUNCTION__))
;
287 return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
288 }
289 assert(Bucket < End)((Bucket < End) ? static_cast<void> (0) : __assert_fail
("Bucket < End", "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 289, __PRETTY_FUNCTION__))
;
290 return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
291 }
292
293 inline SmallPtrSetIterator& operator++() { // Preincrement
294 assert(isHandleInSync() && "invalid iterator access!")((isHandleInSync() && "invalid iterator access!") ? static_cast
<void> (0) : __assert_fail ("isHandleInSync() && \"invalid iterator access!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/SmallPtrSet.h"
, 294, __PRETTY_FUNCTION__))
;
295 if (shouldReverseIterate()) {
296 --Bucket;
297 RetreatIfNotValid();
298 return *this;
299 }
300 ++Bucket;
301 AdvanceIfNotValid();
302 return *this;
303 }
304
305 SmallPtrSetIterator operator++(int) { // Postincrement
306 SmallPtrSetIterator tmp = *this;
307 ++*this;
308 return tmp;
309 }
310};
311
312/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
313/// power of two (which means N itself if N is already a power of two).
314template<unsigned N>
315struct RoundUpToPowerOfTwo;
316
317/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a
318/// helper template used to implement RoundUpToPowerOfTwo.
319template<unsigned N, bool isPowerTwo>
320struct RoundUpToPowerOfTwoH {
321 enum { Val = N };
322};
323template<unsigned N>
324struct RoundUpToPowerOfTwoH<N, false> {
325 enum {
326 // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets
327 // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
328 Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
329 };
330};
331
332template<unsigned N>
333struct RoundUpToPowerOfTwo {
334 enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
335};
336
337/// A templated base class for \c SmallPtrSet which provides the
338/// typesafe interface that is common across all small sizes.
339///
340/// This is particularly useful for passing around between interface boundaries
341/// to avoid encoding a particular small size in the interface boundary.
342template <typename PtrType>
343class SmallPtrSetImpl : public SmallPtrSetImplBase {
344 using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
345 using PtrTraits = PointerLikeTypeTraits<PtrType>;
346 using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
347
348protected:
349 // Forward constructors to the base.
350 using SmallPtrSetImplBase::SmallPtrSetImplBase;
351
352public:
353 using iterator = SmallPtrSetIterator<PtrType>;
354 using const_iterator = SmallPtrSetIterator<PtrType>;
355 using key_type = ConstPtrType;
356 using value_type = PtrType;
357
358 SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
359
360 /// Inserts Ptr if and only if there is no element in the container equal to
361 /// Ptr. The bool component of the returned pair is true if and only if the
362 /// insertion takes place, and the iterator component of the pair points to
363 /// the element equal to Ptr.
364 std::pair<iterator, bool> insert(PtrType Ptr) {
365 auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
366 return std::make_pair(makeIterator(p.first), p.second);
367 }
368
369 /// Insert the given pointer with an iterator hint that is ignored. This is
370 /// identical to calling insert(Ptr), but allows SmallPtrSet to be used by
371 /// std::insert_iterator and std::inserter().
372 iterator insert(iterator, PtrType Ptr) {
373 return insert(Ptr).first;
374 }
375
376 /// erase - If the set contains the specified pointer, remove it and return
377 /// true, otherwise return false.
378 bool erase(PtrType Ptr) {
379 return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
380 }
381 /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
382 size_type count(ConstPtrType Ptr) const {
383 return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
384 }
385 iterator find(ConstPtrType Ptr) const {
386 return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
387 }
388 bool contains(ConstPtrType Ptr) const {
389 return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
390 }
391
392 template <typename IterT>
393 void insert(IterT I, IterT E) {
394 for (; I != E; ++I)
395 insert(*I);
396 }
397
398 void insert(std::initializer_list<PtrType> IL) {
399 insert(IL.begin(), IL.end());
400 }
401
402 iterator begin() const {
403 if (shouldReverseIterate())
404 return makeIterator(EndPointer() - 1);
405 return makeIterator(CurArray);
406 }
407 iterator end() const { return makeIterator(EndPointer()); }
408
409private:
410 /// Create an iterator that dereferences to same place as the given pointer.
411 iterator makeIterator(const void *const *P) const {
412 if (shouldReverseIterate())
413 return iterator(P == EndPointer() ? CurArray : P + 1, CurArray, *this);
414 return iterator(P, EndPointer(), *this);
415 }
416};
417
418/// Equality comparison for SmallPtrSet.
419///
420/// Iterates over elements of LHS confirming that each value from LHS is also in
421/// RHS, and that no additional values are in RHS.
422template <typename PtrType>
423bool operator==(const SmallPtrSetImpl<PtrType> &LHS,
424 const SmallPtrSetImpl<PtrType> &RHS) {
425 if (LHS.size() != RHS.size())
426 return false;
427
428 for (const auto *KV : LHS)
429 if (!RHS.count(KV))
430 return false;
431
432 return true;
433}
434
435/// Inequality comparison for SmallPtrSet.
436///
437/// Equivalent to !(LHS == RHS).
438template <typename PtrType>
439bool operator!=(const SmallPtrSetImpl<PtrType> &LHS,
440 const SmallPtrSetImpl<PtrType> &RHS) {
441 return !(LHS == RHS);
442}
443
444/// SmallPtrSet - This class implements a set which is optimized for holding
445/// SmallSize or less elements. This internally rounds up SmallSize to the next
446/// power of two if it is not already a power of two. See the comments above
447/// SmallPtrSetImplBase for details of the algorithm.
448template<class PtrType, unsigned SmallSize>
449class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
450 // In small mode SmallPtrSet uses linear search for the elements, so it is
451 // not a good idea to choose this value too high. You may consider using a
452 // DenseSet<> instead if you expect many elements in the set.
453 static_assert(SmallSize <= 32, "SmallSize should be small");
454
455 using BaseT = SmallPtrSetImpl<PtrType>;
456
457 // Make sure that SmallSize is a power of two, round up if not.
458 enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
459 /// SmallStorage - Fixed size storage used in 'small mode'.
460 const void *SmallStorage[SmallSizePowTwo];
461
462public:
463 SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
464 SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
465 SmallPtrSet(SmallPtrSet &&that)
466 : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
467
468 template<typename It>
469 SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
470 this->insert(I, E);
471 }
472
473 SmallPtrSet(std::initializer_list<PtrType> IL)
474 : BaseT(SmallStorage, SmallSizePowTwo) {
475 this->insert(IL.begin(), IL.end());
476 }
477
478 SmallPtrSet<PtrType, SmallSize> &
479 operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
480 if (&RHS != this)
481 this->CopyFrom(RHS);
482 return *this;
483 }
484
485 SmallPtrSet<PtrType, SmallSize> &
486 operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
487 if (&RHS != this)
488 this->MoveFrom(SmallSizePowTwo, std::move(RHS));
489 return *this;
490 }
491
492 SmallPtrSet<PtrType, SmallSize> &
493 operator=(std::initializer_list<PtrType> IL) {
494 this->clear();
495 this->insert(IL.begin(), IL.end());
496 return *this;
497 }
498
499 /// swap - Swaps the elements of two sets.
500 void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
501 SmallPtrSetImplBase::swap(RHS);
502 }
503};
504
505} // end namespace llvm
506
507namespace std {
508
509 /// Implement std::swap in terms of SmallPtrSet swap.
510 template<class T, unsigned N>
511 inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
512 LHS.swap(RHS);
513 }
514
515} // end namespace std
516
517#endif // LLVM_ADT_SMALLPTRSET_H

/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h

1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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//
9// This file contains some templates that are useful if you are working with the
10// STL at all.
11//
12// No library is required when using these functions.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_STLEXTRAS_H
17#define LLVM_ADT_STLEXTRAS_H
18
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/iterator.h"
21#include "llvm/ADT/iterator_range.h"
22#include "llvm/Config/abi-breaking.h"
23#include "llvm/Support/ErrorHandling.h"
24#include <algorithm>
25#include <cassert>
26#include <cstddef>
27#include <cstdint>
28#include <cstdlib>
29#include <functional>
30#include <initializer_list>
31#include <iterator>
32#include <limits>
33#include <memory>
34#include <tuple>
35#include <type_traits>
36#include <utility>
37
38#ifdef EXPENSIVE_CHECKS
39#include <random> // for std::mt19937
40#endif
41
42namespace llvm {
43
44// Only used by compiler if both template types are the same. Useful when
45// using SFINAE to test for the existence of member functions.
46template <typename T, T> struct SameType;
47
48namespace detail {
49
50template <typename RangeT>
51using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
52
53template <typename RangeT>
54using ValueOfRange = typename std::remove_reference<decltype(
55 *std::begin(std::declval<RangeT &>()))>::type;
56
57} // end namespace detail
58
59//===----------------------------------------------------------------------===//
60// Extra additions to <type_traits>
61//===----------------------------------------------------------------------===//
62
63template <typename T>
64struct negation : std::integral_constant<bool, !bool(T::value)> {};
65
66template <typename...> struct conjunction : std::true_type {};
67template <typename B1> struct conjunction<B1> : B1 {};
68template <typename B1, typename... Bn>
69struct conjunction<B1, Bn...>
70 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
71
72template <typename T> struct make_const_ptr {
73 using type =
74 typename std::add_pointer<typename std::add_const<T>::type>::type;
75};
76
77template <typename T> struct make_const_ref {
78 using type = typename std::add_lvalue_reference<
79 typename std::add_const<T>::type>::type;
80};
81
82/// Utilities for detecting if a given trait holds for some set of arguments
83/// 'Args'. For example, the given trait could be used to detect if a given type
84/// has a copy assignment operator:
85/// template<class T>
86/// using has_copy_assign_t = decltype(std::declval<T&>()
87/// = std::declval<const T&>());
88/// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
89namespace detail {
90template <typename...> using void_t = void;
91template <class, template <class...> class Op, class... Args> struct detector {
92 using value_t = std::false_type;
93};
94template <template <class...> class Op, class... Args>
95struct detector<void_t<Op<Args...>>, Op, Args...> {
96 using value_t = std::true_type;
97};
98} // end namespace detail
99
100template <template <class...> class Op, class... Args>
101using is_detected = typename detail::detector<void, Op, Args...>::value_t;
102
103/// Check if a Callable type can be invoked with the given set of arg types.
104namespace detail {
105template <typename Callable, typename... Args>
106using is_invocable =
107 decltype(std::declval<Callable &>()(std::declval<Args>()...));
108} // namespace detail
109
110template <typename Callable, typename... Args>
111using is_invocable = is_detected<detail::is_invocable, Callable, Args...>;
112
113/// This class provides various trait information about a callable object.
114/// * To access the number of arguments: Traits::num_args
115/// * To access the type of an argument: Traits::arg_t<Index>
116/// * To access the type of the result: Traits::result_t
117template <typename T, bool isClass = std::is_class<T>::value>
118struct function_traits : public function_traits<decltype(&T::operator())> {};
119
120/// Overload for class function types.
121template <typename ClassType, typename ReturnType, typename... Args>
122struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
123 /// The number of arguments to this function.
124 enum { num_args = sizeof...(Args) };
125
126 /// The result type of this function.
127 using result_t = ReturnType;
128
129 /// The type of an argument to this function.
130 template <size_t Index>
131 using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
132};
133/// Overload for class function types.
134template <typename ClassType, typename ReturnType, typename... Args>
135struct function_traits<ReturnType (ClassType::*)(Args...), false>
136 : function_traits<ReturnType (ClassType::*)(Args...) const> {};
137/// Overload for non-class function types.
138template <typename ReturnType, typename... Args>
139struct function_traits<ReturnType (*)(Args...), false> {
140 /// The number of arguments to this function.
141 enum { num_args = sizeof...(Args) };
142
143 /// The result type of this function.
144 using result_t = ReturnType;
145
146 /// The type of an argument to this function.
147 template <size_t i>
148 using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
149};
150/// Overload for non-class function type references.
151template <typename ReturnType, typename... Args>
152struct function_traits<ReturnType (&)(Args...), false>
153 : public function_traits<ReturnType (*)(Args...)> {};
154
155//===----------------------------------------------------------------------===//
156// Extra additions to <functional>
157//===----------------------------------------------------------------------===//
158
159template <class Ty> struct identity {
160 using argument_type = Ty;
161
162 Ty &operator()(Ty &self) const {
163 return self;
164 }
165 const Ty &operator()(const Ty &self) const {
166 return self;
167 }
168};
169
170/// An efficient, type-erasing, non-owning reference to a callable. This is
171/// intended for use as the type of a function parameter that is not used
172/// after the function in question returns.
173///
174/// This class does not own the callable, so it is not in general safe to store
175/// a function_ref.
176template<typename Fn> class function_ref;
177
178template<typename Ret, typename ...Params>
179class function_ref<Ret(Params...)> {
180 Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
181 intptr_t callable;
182
183 template<typename Callable>
184 static Ret callback_fn(intptr_t callable, Params ...params) {
185 return (*reinterpret_cast<Callable*>(callable))(
186 std::forward<Params>(params)...);
187 }
188
189public:
190 function_ref() = default;
191 function_ref(std::nullptr_t) {}
192
193 template <typename Callable>
194 function_ref(
195 Callable &&callable,
196 // This is not the copy-constructor.
197 std::enable_if_t<
198 !std::is_same<std::remove_cv_t<std::remove_reference_t<Callable>>,
199 function_ref>::value> * = nullptr,
200 // Functor must be callable and return a suitable type.
201 std::enable_if_t<std::is_void<Ret>::value ||
202 std::is_convertible<decltype(std::declval<Callable>()(
203 std::declval<Params>()...)),
204 Ret>::value> * = nullptr)
205 : callback(callback_fn<typename std::remove_reference<Callable>::type>),
206 callable(reinterpret_cast<intptr_t>(&callable)) {}
207
208 Ret operator()(Params ...params) const {
209 return callback(callable, std::forward<Params>(params)...);
210 }
211
212 explicit operator bool() const { return callback; }
213};
214
215//===----------------------------------------------------------------------===//
216// Extra additions to <iterator>
217//===----------------------------------------------------------------------===//
218
219namespace adl_detail {
220
221using std::begin;
222
223template <typename ContainerTy>
224decltype(auto) adl_begin(ContainerTy &&container) {
225 return begin(std::forward<ContainerTy>(container));
226}
227
228using std::end;
229
230template <typename ContainerTy>
231decltype(auto) adl_end(ContainerTy &&container) {
232 return end(std::forward<ContainerTy>(container));
233}
234
235using std::swap;
236
237template <typename T>
238void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
239 std::declval<T>()))) {
240 swap(std::forward<T>(lhs), std::forward<T>(rhs));
241}
242
243} // end namespace adl_detail
244
245template <typename ContainerTy>
246decltype(auto) adl_begin(ContainerTy &&container) {
247 return adl_detail::adl_begin(std::forward<ContainerTy>(container));
248}
249
250template <typename ContainerTy>
251decltype(auto) adl_end(ContainerTy &&container) {
252 return adl_detail::adl_end(std::forward<ContainerTy>(container));
253}
254
255template <typename T>
256void adl_swap(T &&lhs, T &&rhs) noexcept(
257 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
258 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
259}
260
261/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty.
262template <typename T>
263constexpr bool empty(const T &RangeOrContainer) {
264 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
265}
266
267/// Returns true if the given container only contains a single element.
268template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
269 auto B = std::begin(C), E = std::end(C);
270 return B != E && std::next(B) == E;
271}
272
273/// Return a range covering \p RangeOrContainer with the first N elements
274/// excluded.
275template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) {
276 return make_range(std::next(adl_begin(RangeOrContainer), N),
277 adl_end(RangeOrContainer));
278}
279
280// mapped_iterator - This is a simple iterator adapter that causes a function to
281// be applied whenever operator* is invoked on the iterator.
282
283template <typename ItTy, typename FuncTy,
284 typename FuncReturnTy =
285 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
286class mapped_iterator
287 : public iterator_adaptor_base<
288 mapped_iterator<ItTy, FuncTy>, ItTy,
289 typename std::iterator_traits<ItTy>::iterator_category,
290 typename std::remove_reference<FuncReturnTy>::type> {
291public:
292 mapped_iterator(ItTy U, FuncTy F)
293 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
294
295 ItTy getCurrent() { return this->I; }
296
297 FuncReturnTy operator*() const { return F(*this->I); }
298
299private:
300 FuncTy F;
301};
302
303// map_iterator - Provide a convenient way to create mapped_iterators, just like
304// make_pair is useful for creating pairs...
305template <class ItTy, class FuncTy>
306inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
307 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
308}
309
310template <class ContainerTy, class FuncTy>
311auto map_range(ContainerTy &&C, FuncTy F) {
312 return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
313}
314
315/// Helper to determine if type T has a member called rbegin().
316template <typename Ty> class has_rbegin_impl {
317 using yes = char[1];
318 using no = char[2];
319
320 template <typename Inner>
321 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
322
323 template <typename>
324 static no& test(...);
325
326public:
327 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
328};
329
330/// Metafunction to determine if T& or T has a member called rbegin().
331template <typename Ty>
332struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
333};
334
335// Returns an iterator_range over the given container which iterates in reverse.
336// Note that the container must have rbegin()/rend() methods for this to work.
337template <typename ContainerTy>
338auto reverse(ContainerTy &&C,
339 std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
340 return make_range(C.rbegin(), C.rend());
341}
342
343// Returns a std::reverse_iterator wrapped around the given iterator.
344template <typename IteratorTy>
345std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
346 return std::reverse_iterator<IteratorTy>(It);
347}
348
349// Returns an iterator_range over the given container which iterates in reverse.
350// Note that the container must have begin()/end() methods which return
351// bidirectional iterators for this to work.
352template <typename ContainerTy>
353auto reverse(ContainerTy &&C,
354 std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
355 return make_range(llvm::make_reverse_iterator(std::end(C)),
356 llvm::make_reverse_iterator(std::begin(C)));
357}
358
359/// An iterator adaptor that filters the elements of given inner iterators.
360///
361/// The predicate parameter should be a callable object that accepts the wrapped
362/// iterator's reference type and returns a bool. When incrementing or
363/// decrementing the iterator, it will call the predicate on each element and
364/// skip any where it returns false.
365///
366/// \code
367/// int A[] = { 1, 2, 3, 4 };
368/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
369/// // R contains { 1, 3 }.
370/// \endcode
371///
372/// Note: filter_iterator_base implements support for forward iteration.
373/// filter_iterator_impl exists to provide support for bidirectional iteration,
374/// conditional on whether the wrapped iterator supports it.
375template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
376class filter_iterator_base
377 : public iterator_adaptor_base<
378 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
379 WrappedIteratorT,
380 typename std::common_type<
381 IterTag, typename std::iterator_traits<
382 WrappedIteratorT>::iterator_category>::type> {
383 using BaseT = iterator_adaptor_base<
384 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
385 WrappedIteratorT,
386 typename std::common_type<
387 IterTag, typename std::iterator_traits<
388 WrappedIteratorT>::iterator_category>::type>;
389
390protected:
391 WrappedIteratorT End;
392 PredicateT Pred;
393
394 void findNextValid() {
395 while (this->I != End && !Pred(*this->I))
396 BaseT::operator++();
397 }
398
399 // Construct the iterator. The begin iterator needs to know where the end
400 // is, so that it can properly stop when it gets there. The end iterator only
401 // needs the predicate to support bidirectional iteration.
402 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
403 PredicateT Pred)
404 : BaseT(Begin), End(End), Pred(Pred) {
405 findNextValid();
406 }
407
408public:
409 using BaseT::operator++;
410
411 filter_iterator_base &operator++() {
412 BaseT::operator++();
413 findNextValid();
414 return *this;
415 }
416};
417
418/// Specialization of filter_iterator_base for forward iteration only.
419template <typename WrappedIteratorT, typename PredicateT,
420 typename IterTag = std::forward_iterator_tag>
421class filter_iterator_impl
422 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
423 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
424
425public:
426 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
427 PredicateT Pred)
428 : BaseT(Begin, End, Pred) {}
429};
430
431/// Specialization of filter_iterator_base for bidirectional iteration.
432template <typename WrappedIteratorT, typename PredicateT>
433class filter_iterator_impl<WrappedIteratorT, PredicateT,
434 std::bidirectional_iterator_tag>
435 : public filter_iterator_base<WrappedIteratorT, PredicateT,
436 std::bidirectional_iterator_tag> {
437 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
438 std::bidirectional_iterator_tag>;
439 void findPrevValid() {
440 while (!this->Pred(*this->I))
441 BaseT::operator--();
442 }
443
444public:
445 using BaseT::operator--;
446
447 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
448 PredicateT Pred)
449 : BaseT(Begin, End, Pred) {}
450
451 filter_iterator_impl &operator--() {
452 BaseT::operator--();
453 findPrevValid();
454 return *this;
455 }
456};
457
458namespace detail {
459
460template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
461 using type = std::forward_iterator_tag;
462};
463
464template <> struct fwd_or_bidi_tag_impl<true> {
465 using type = std::bidirectional_iterator_tag;
466};
467
468/// Helper which sets its type member to forward_iterator_tag if the category
469/// of \p IterT does not derive from bidirectional_iterator_tag, and to
470/// bidirectional_iterator_tag otherwise.
471template <typename IterT> struct fwd_or_bidi_tag {
472 using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
473 std::bidirectional_iterator_tag,
474 typename std::iterator_traits<IterT>::iterator_category>::value>::type;
475};
476
477} // namespace detail
478
479/// Defines filter_iterator to a suitable specialization of
480/// filter_iterator_impl, based on the underlying iterator's category.
481template <typename WrappedIteratorT, typename PredicateT>
482using filter_iterator = filter_iterator_impl<
483 WrappedIteratorT, PredicateT,
484 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
485
486/// Convenience function that takes a range of elements and a predicate,
487/// and return a new filter_iterator range.
488///
489/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
490/// lifetime of that temporary is not kept by the returned range object, and the
491/// temporary is going to be dropped on the floor after the make_iterator_range
492/// full expression that contains this function call.
493template <typename RangeT, typename PredicateT>
494iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
495make_filter_range(RangeT &&Range, PredicateT Pred) {
496 using FilterIteratorT =
497 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
498 return make_range(
499 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
500 std::end(std::forward<RangeT>(Range)), Pred),
501 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
502 std::end(std::forward<RangeT>(Range)), Pred));
503}
504
505/// A pseudo-iterator adaptor that is designed to implement "early increment"
506/// style loops.
507///
508/// This is *not a normal iterator* and should almost never be used directly. It
509/// is intended primarily to be used with range based for loops and some range
510/// algorithms.
511///
512/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
513/// somewhere between them. The constraints of these iterators are:
514///
515/// - On construction or after being incremented, it is comparable and
516/// dereferencable. It is *not* incrementable.
517/// - After being dereferenced, it is neither comparable nor dereferencable, it
518/// is only incrementable.
519///
520/// This means you can only dereference the iterator once, and you can only
521/// increment it once between dereferences.
522template <typename WrappedIteratorT>
523class early_inc_iterator_impl
524 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
525 WrappedIteratorT, std::input_iterator_tag> {
526 using BaseT =
527 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
528 WrappedIteratorT, std::input_iterator_tag>;
529
530 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
531
532protected:
533#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
534 bool IsEarlyIncremented = false;
535#endif
536
537public:
538 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
539
540 using BaseT::operator*;
541 decltype(*std::declval<WrappedIteratorT>()) operator*() {
542#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
543 assert(!IsEarlyIncremented && "Cannot dereference twice!")((!IsEarlyIncremented && "Cannot dereference twice!")
? static_cast<void> (0) : __assert_fail ("!IsEarlyIncremented && \"Cannot dereference twice!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 543, __PRETTY_FUNCTION__))
;
544 IsEarlyIncremented = true;
545#endif
546 return *(this->I)++;
547 }
548
549 using BaseT::operator++;
550 early_inc_iterator_impl &operator++() {
551#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
552 assert(IsEarlyIncremented && "Cannot increment before dereferencing!")((IsEarlyIncremented && "Cannot increment before dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("IsEarlyIncremented && \"Cannot increment before dereferencing!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 552, __PRETTY_FUNCTION__))
;
553 IsEarlyIncremented = false;
554#endif
555 return *this;
556 }
557
558 friend bool operator==(const early_inc_iterator_impl &LHS,
559 const early_inc_iterator_impl &RHS) {
560#if LLVM_ENABLE_ABI_BREAKING_CHECKS1
561 assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!")((!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!"
) ? static_cast<void> (0) : __assert_fail ("!LHS.IsEarlyIncremented && \"Cannot compare after dereferencing!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 561, __PRETTY_FUNCTION__))
;
562#endif
563 return (const BaseT &)LHS == (const BaseT &)RHS;
564 }
565};
566
567/// Make a range that does early increment to allow mutation of the underlying
568/// range without disrupting iteration.
569///
570/// The underlying iterator will be incremented immediately after it is
571/// dereferenced, allowing deletion of the current node or insertion of nodes to
572/// not disrupt iteration provided they do not invalidate the *next* iterator --
573/// the current iterator can be invalidated.
574///
575/// This requires a very exact pattern of use that is only really suitable to
576/// range based for loops and other range algorithms that explicitly guarantee
577/// to dereference exactly once each element, and to increment exactly once each
578/// element.
579template <typename RangeT>
580iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
581make_early_inc_range(RangeT &&Range) {
582 using EarlyIncIteratorT =
583 early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
584 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
585 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
586}
587
588// forward declarations required by zip_shortest/zip_first/zip_longest
589template <typename R, typename UnaryPredicate>
590bool all_of(R &&range, UnaryPredicate P);
591template <typename R, typename UnaryPredicate>
592bool any_of(R &&range, UnaryPredicate P);
593
594namespace detail {
595
596using std::declval;
597
598// We have to alias this since inlining the actual type at the usage site
599// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
600template<typename... Iters> struct ZipTupleType {
601 using type = std::tuple<decltype(*declval<Iters>())...>;
602};
603
604template <typename ZipType, typename... Iters>
605using zip_traits = iterator_facade_base<
606 ZipType, typename std::common_type<std::bidirectional_iterator_tag,
607 typename std::iterator_traits<
608 Iters>::iterator_category...>::type,
609 // ^ TODO: Implement random access methods.
610 typename ZipTupleType<Iters...>::type,
611 typename std::iterator_traits<typename std::tuple_element<
612 0, std::tuple<Iters...>>::type>::difference_type,
613 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
614 // inner iterators have the same difference_type. It would fail if, for
615 // instance, the second field's difference_type were non-numeric while the
616 // first is.
617 typename ZipTupleType<Iters...>::type *,
618 typename ZipTupleType<Iters...>::type>;
619
620template <typename ZipType, typename... Iters>
621struct zip_common : public zip_traits<ZipType, Iters...> {
622 using Base = zip_traits<ZipType, Iters...>;
623 using value_type = typename Base::value_type;
624
625 std::tuple<Iters...> iterators;
626
627protected:
628 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
629 return value_type(*std::get<Ns>(iterators)...);
630 }
631
632 template <size_t... Ns>
633 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
634 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
635 }
636
637 template <size_t... Ns>
638 decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
639 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
640 }
641
642public:
643 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
644
645 value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
646
647 const value_type operator*() const {
648 return deref(std::index_sequence_for<Iters...>{});
649 }
650
651 ZipType &operator++() {
652 iterators = tup_inc(std::index_sequence_for<Iters...>{});
653 return *reinterpret_cast<ZipType *>(this);
654 }
655
656 ZipType &operator--() {
657 static_assert(Base::IsBidirectional,
658 "All inner iterators must be at least bidirectional.");
659 iterators = tup_dec(std::index_sequence_for<Iters...>{});
660 return *reinterpret_cast<ZipType *>(this);
661 }
662};
663
664template <typename... Iters>
665struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
666 using Base = zip_common<zip_first<Iters...>, Iters...>;
667
668 bool operator==(const zip_first<Iters...> &other) const {
669 return std::get<0>(this->iterators) == std::get<0>(other.iterators);
670 }
671
672 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
673};
674
675template <typename... Iters>
676class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
677 template <size_t... Ns>
678 bool test(const zip_shortest<Iters...> &other,
679 std::index_sequence<Ns...>) const {
680 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
681 std::get<Ns>(other.iterators)...},
682 identity<bool>{});
683 }
684
685public:
686 using Base = zip_common<zip_shortest<Iters...>, Iters...>;
687
688 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
689
690 bool operator==(const zip_shortest<Iters...> &other) const {
691 return !test(other, std::index_sequence_for<Iters...>{});
692 }
693};
694
695template <template <typename...> class ItType, typename... Args> class zippy {
696public:
697 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
698 using iterator_category = typename iterator::iterator_category;
699 using value_type = typename iterator::value_type;
700 using difference_type = typename iterator::difference_type;
701 using pointer = typename iterator::pointer;
702 using reference = typename iterator::reference;
703
704private:
705 std::tuple<Args...> ts;
706
707 template <size_t... Ns>
708 iterator begin_impl(std::index_sequence<Ns...>) const {
709 return iterator(std::begin(std::get<Ns>(ts))...);
710 }
711 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
712 return iterator(std::end(std::get<Ns>(ts))...);
713 }
714
715public:
716 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
717
718 iterator begin() const {
719 return begin_impl(std::index_sequence_for<Args...>{});
720 }
721 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
722};
723
724} // end namespace detail
725
726/// zip iterator for two or more iteratable types.
727template <typename T, typename U, typename... Args>
728detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
729 Args &&... args) {
730 return detail::zippy<detail::zip_shortest, T, U, Args...>(
731 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
732}
733
734/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
735/// be the shortest.
736template <typename T, typename U, typename... Args>
737detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
738 Args &&... args) {
739 return detail::zippy<detail::zip_first, T, U, Args...>(
740 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
741}
742
743namespace detail {
744template <typename Iter>
745Iter next_or_end(const Iter &I, const Iter &End) {
746 if (I == End)
747 return End;
748 return std::next(I);
749}
750
751template <typename Iter>
752auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
753 std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
754 if (I == End)
755 return None;
756 return *I;
757}
758
759template <typename Iter> struct ZipLongestItemType {
760 using type =
761 llvm::Optional<typename std::remove_const<typename std::remove_reference<
762 decltype(*std::declval<Iter>())>::type>::type>;
763};
764
765template <typename... Iters> struct ZipLongestTupleType {
766 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
767};
768
769template <typename... Iters>
770class zip_longest_iterator
771 : public iterator_facade_base<
772 zip_longest_iterator<Iters...>,
773 typename std::common_type<
774 std::forward_iterator_tag,
775 typename std::iterator_traits<Iters>::iterator_category...>::type,
776 typename ZipLongestTupleType<Iters...>::type,
777 typename std::iterator_traits<typename std::tuple_element<
778 0, std::tuple<Iters...>>::type>::difference_type,
779 typename ZipLongestTupleType<Iters...>::type *,
780 typename ZipLongestTupleType<Iters...>::type> {
781public:
782 using value_type = typename ZipLongestTupleType<Iters...>::type;
783
784private:
785 std::tuple<Iters...> iterators;
786 std::tuple<Iters...> end_iterators;
787
788 template <size_t... Ns>
789 bool test(const zip_longest_iterator<Iters...> &other,
790 std::index_sequence<Ns...>) const {
791 return llvm::any_of(
792 std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
793 std::get<Ns>(other.iterators)...},
794 identity<bool>{});
795 }
796
797 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
798 return value_type(
799 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
800 }
801
802 template <size_t... Ns>
803 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
804 return std::tuple<Iters...>(
805 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
806 }
807
808public:
809 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
810 : iterators(std::forward<Iters>(ts.first)...),
811 end_iterators(std::forward<Iters>(ts.second)...) {}
812
813 value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
814
815 value_type operator*() const {
816 return deref(std::index_sequence_for<Iters...>{});
817 }
818
819 zip_longest_iterator<Iters...> &operator++() {
820 iterators = tup_inc(std::index_sequence_for<Iters...>{});
821 return *this;
822 }
823
824 bool operator==(const zip_longest_iterator<Iters...> &other) const {
825 return !test(other, std::index_sequence_for<Iters...>{});
826 }
827};
828
829template <typename... Args> class zip_longest_range {
830public:
831 using iterator =
832 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>;
833 using iterator_category = typename iterator::iterator_category;
834 using value_type = typename iterator::value_type;
835 using difference_type = typename iterator::difference_type;
836 using pointer = typename iterator::pointer;
837 using reference = typename iterator::reference;
838
839private:
840 std::tuple<Args...> ts;
841
842 template <size_t... Ns>
843 iterator begin_impl(std::index_sequence<Ns...>) const {
844 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
845 adl_end(std::get<Ns>(ts)))...);
846 }
847
848 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
849 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
850 adl_end(std::get<Ns>(ts)))...);
851 }
852
853public:
854 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
855
856 iterator begin() const {
857 return begin_impl(std::index_sequence_for<Args...>{});
858 }
859 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
860};
861} // namespace detail
862
863/// Iterate over two or more iterators at the same time. Iteration continues
864/// until all iterators reach the end. The llvm::Optional only contains a value
865/// if the iterator has not reached the end.
866template <typename T, typename U, typename... Args>
867detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
868 Args &&... args) {
869 return detail::zip_longest_range<T, U, Args...>(
870 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
871}
872
873/// Iterator wrapper that concatenates sequences together.
874///
875/// This can concatenate different iterators, even with different types, into
876/// a single iterator provided the value types of all the concatenated
877/// iterators expose `reference` and `pointer` types that can be converted to
878/// `ValueT &` and `ValueT *` respectively. It doesn't support more
879/// interesting/customized pointer or reference types.
880///
881/// Currently this only supports forward or higher iterator categories as
882/// inputs and always exposes a forward iterator interface.
883template <typename ValueT, typename... IterTs>
884class concat_iterator
885 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
886 std::forward_iterator_tag, ValueT> {
887 using BaseT = typename concat_iterator::iterator_facade_base;
888
889 /// We store both the current and end iterators for each concatenated
890 /// sequence in a tuple of pairs.
891 ///
892 /// Note that something like iterator_range seems nice at first here, but the
893 /// range properties are of little benefit and end up getting in the way
894 /// because we need to do mutation on the current iterators.
895 std::tuple<IterTs...> Begins;
896 std::tuple<IterTs...> Ends;
897
898 /// Attempts to increment a specific iterator.
899 ///
900 /// Returns true if it was able to increment the iterator. Returns false if
901 /// the iterator is already at the end iterator.
902 template <size_t Index> bool incrementHelper() {
903 auto &Begin = std::get<Index>(Begins);
904 auto &End = std::get<Index>(Ends);
905 if (Begin == End)
906 return false;
907
908 ++Begin;
909 return true;
910 }
911
912 /// Increments the first non-end iterator.
913 ///
914 /// It is an error to call this with all iterators at the end.
915 template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
916 // Build a sequence of functions to increment each iterator if possible.
917 bool (concat_iterator::*IncrementHelperFns[])() = {
918 &concat_iterator::incrementHelper<Ns>...};
919
920 // Loop over them, and stop as soon as we succeed at incrementing one.
921 for (auto &IncrementHelperFn : IncrementHelperFns)
922 if ((this->*IncrementHelperFn)())
923 return;
924
925 llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!"
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 925)
;
926 }
927
928 /// Returns null if the specified iterator is at the end. Otherwise,
929 /// dereferences the iterator and returns the address of the resulting
930 /// reference.
931 template <size_t Index> ValueT *getHelper() const {
932 auto &Begin = std::get<Index>(Begins);
933 auto &End = std::get<Index>(Ends);
934 if (Begin == End)
935 return nullptr;
936
937 return &*Begin;
938 }
939
940 /// Finds the first non-end iterator, dereferences, and returns the resulting
941 /// reference.
942 ///
943 /// It is an error to call this with all iterators at the end.
944 template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
945 // Build a sequence of functions to get from iterator if possible.
946 ValueT *(concat_iterator::*GetHelperFns[])() const = {
947 &concat_iterator::getHelper<Ns>...};
948
949 // Loop over them, and return the first result we find.
950 for (auto &GetHelperFn : GetHelperFns)
951 if (ValueT *P = (this->*GetHelperFn)())
952 return *P;
953
954 llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!"
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 954)
;
955 }
956
957public:
958 /// Constructs an iterator from a sequence of ranges.
959 ///
960 /// We need the full range to know how to switch between each of the
961 /// iterators.
962 template <typename... RangeTs>
963 explicit concat_iterator(RangeTs &&... Ranges)
964 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
965
966 using BaseT::operator++;
967
968 concat_iterator &operator++() {
969 increment(std::index_sequence_for<IterTs...>());
970 return *this;
971 }
972
973 ValueT &operator*() const {
974 return get(std::index_sequence_for<IterTs...>());
975 }
976
977 bool operator==(const concat_iterator &RHS) const {
978 return Begins == RHS.Begins && Ends == RHS.Ends;
979 }
980};
981
982namespace detail {
983
984/// Helper to store a sequence of ranges being concatenated and access them.
985///
986/// This is designed to facilitate providing actual storage when temporaries
987/// are passed into the constructor such that we can use it as part of range
988/// based for loops.
989template <typename ValueT, typename... RangeTs> class concat_range {
990public:
991 using iterator =
992 concat_iterator<ValueT,
993 decltype(std::begin(std::declval<RangeTs &>()))...>;
994
995private:
996 std::tuple<RangeTs...> Ranges;
997
998 template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
999 return iterator(std::get<Ns>(Ranges)...);
1000 }
1001 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
1002 return iterator(make_range(std::end(std::get<Ns>(Ranges)),
1003 std::end(std::get<Ns>(Ranges)))...);
1004 }
1005
1006public:
1007 concat_range(RangeTs &&... Ranges)
1008 : Ranges(std::forward<RangeTs>(Ranges)...) {}
1009
1010 iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
1011 iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
1012};
1013
1014} // end namespace detail
1015
1016/// Concatenated range across two or more ranges.
1017///
1018/// The desired value type must be explicitly specified.
1019template <typename ValueT, typename... RangeTs>
1020detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
1021 static_assert(sizeof...(RangeTs) > 1,
1022 "Need more than one range to concatenate!");
1023 return detail::concat_range<ValueT, RangeTs...>(
1024 std::forward<RangeTs>(Ranges)...);
1025}
1026
1027/// A utility class used to implement an iterator that contains some base object
1028/// and an index. The iterator moves the index but keeps the base constant.
1029template <typename DerivedT, typename BaseT, typename T,
1030 typename PointerT = T *, typename ReferenceT = T &>
1031class indexed_accessor_iterator
1032 : public llvm::iterator_facade_base<DerivedT,
1033 std::random_access_iterator_tag, T,
1034 std::ptrdiff_t, PointerT, ReferenceT> {
1035public:
1036 ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
1037 assert(base == rhs.base && "incompatible iterators")((base == rhs.base && "incompatible iterators") ? static_cast
<void> (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1037, __PRETTY_FUNCTION__))
;
1038 return index - rhs.index;
1039 }
1040 bool operator==(const indexed_accessor_iterator &rhs) const {
1041 return base == rhs.base && index == rhs.index;
1042 }
1043 bool operator<(const indexed_accessor_iterator &rhs) const {
1044 assert(base == rhs.base && "incompatible iterators")((base == rhs.base && "incompatible iterators") ? static_cast
<void> (0) : __assert_fail ("base == rhs.base && \"incompatible iterators\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1044, __PRETTY_FUNCTION__))
;
1045 return index < rhs.index;
1046 }
1047
1048 DerivedT &operator+=(ptrdiff_t offset) {
1049 this->index += offset;
1050 return static_cast<DerivedT &>(*this);
1051 }
1052 DerivedT &operator-=(ptrdiff_t offset) {
1053 this->index -= offset;
1054 return static_cast<DerivedT &>(*this);
1055 }
1056
1057 /// Returns the current index of the iterator.
1058 ptrdiff_t getIndex() const { return index; }
1059
1060 /// Returns the current base of the iterator.
1061 const BaseT &getBase() const { return base; }
1062
1063protected:
1064 indexed_accessor_iterator(BaseT base, ptrdiff_t index)
1065 : base(base), index(index) {}
1066 BaseT base;
1067 ptrdiff_t index;
1068};
1069
1070namespace detail {
1071/// The class represents the base of a range of indexed_accessor_iterators. It
1072/// provides support for many different range functionalities, e.g.
1073/// drop_front/slice/etc.. Derived range classes must implement the following
1074/// static methods:
1075/// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
1076/// - Dereference an iterator pointing to the base object at the given
1077/// index.
1078/// * BaseT offset_base(const BaseT &base, ptrdiff_t index)
1079/// - Return a new base that is offset from the provide base by 'index'
1080/// elements.
1081template <typename DerivedT, typename BaseT, typename T,
1082 typename PointerT = T *, typename ReferenceT = T &>
1083class indexed_accessor_range_base {
1084public:
1085 using RangeBaseT =
1086 indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT>;
1087
1088 /// An iterator element of this range.
1089 class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
1090 PointerT, ReferenceT> {
1091 public:
1092 // Index into this iterator, invoking a static method on the derived type.
1093 ReferenceT operator*() const {
1094 return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
1095 }
1096
1097 private:
1098 iterator(BaseT owner, ptrdiff_t curIndex)
1099 : indexed_accessor_iterator<iterator, BaseT, T, PointerT, ReferenceT>(
1100 owner, curIndex) {}
1101
1102 /// Allow access to the constructor.
1103 friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
1104 ReferenceT>;
1105 };
1106
1107 indexed_accessor_range_base(iterator begin, iterator end)
1108 : base(offset_base(begin.getBase(), begin.getIndex())),
1109 count(end.getIndex() - begin.getIndex()) {}
1110 indexed_accessor_range_base(const iterator_range<iterator> &range)
1111 : indexed_accessor_range_base(range.begin(), range.end()) {}
1112 indexed_accessor_range_base(BaseT base, ptrdiff_t count)
1113 : base(base), count(count) {}
1114
1115 iterator begin() const { return iterator(base, 0); }
1116 iterator end() const { return iterator(base, count); }
1117 ReferenceT operator[](size_t Index) const {
1118 assert(Index < size() && "invalid index for value range")((Index < size() && "invalid index for value range"
) ? static_cast<void> (0) : __assert_fail ("Index < size() && \"invalid index for value range\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1118, __PRETTY_FUNCTION__))
;
1119 return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index));
1120 }
1121 ReferenceT front() const {
1122 assert(!empty() && "expected non-empty range")((!empty() && "expected non-empty range") ? static_cast
<void> (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1122, __PRETTY_FUNCTION__))
;
1123 return (*this)[0];
1124 }
1125 ReferenceT back() const {
1126 assert(!empty() && "expected non-empty range")((!empty() && "expected non-empty range") ? static_cast
<void> (0) : __assert_fail ("!empty() && \"expected non-empty range\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1126, __PRETTY_FUNCTION__))
;
1127 return (*this)[size() - 1];
1128 }
1129
1130 /// Compare this range with another.
1131 template <typename OtherT> bool operator==(const OtherT &other) const {
1132 return size() ==
1133 static_cast<size_t>(std::distance(other.begin(), other.end())) &&
1134 std::equal(begin(), end(), other.begin());
1135 }
1136 template <typename OtherT> bool operator!=(const OtherT &other) const {
1137 return !(*this == other);
1138 }
1139
1140 /// Return the size of this range.
1141 size_t size() const { return count; }
1142
1143 /// Return if the range is empty.
1144 bool empty() const { return size() == 0; }
1145
1146 /// Drop the first N elements, and keep M elements.
1147 DerivedT slice(size_t n, size_t m) const {
1148 assert(n + m <= size() && "invalid size specifiers")((n + m <= size() && "invalid size specifiers") ? static_cast
<void> (0) : __assert_fail ("n + m <= size() && \"invalid size specifiers\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1148, __PRETTY_FUNCTION__))
;
1149 return DerivedT(offset_base(base, n), m);
1150 }
1151
1152 /// Drop the first n elements.
1153 DerivedT drop_front(size_t n = 1) const {
1154 assert(size() >= n && "Dropping more elements than exist")((size() >= n && "Dropping more elements than exist"
) ? static_cast<void> (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1154, __PRETTY_FUNCTION__))
;
1155 return slice(n, size() - n);
1156 }
1157 /// Drop the last n elements.
1158 DerivedT drop_back(size_t n = 1) const {
1159 assert(size() >= n && "Dropping more elements than exist")((size() >= n && "Dropping more elements than exist"
) ? static_cast<void> (0) : __assert_fail ("size() >= n && \"Dropping more elements than exist\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/ADT/STLExtras.h"
, 1159, __PRETTY_FUNCTION__))
;
1160 return DerivedT(base, size() - n);
1161 }
1162
1163 /// Take the first n elements.
1164 DerivedT take_front(size_t n = 1) const {
1165 return n < size() ? drop_back(size() - n)
1166 : static_cast<const DerivedT &>(*this);
1167 }
1168
1169 /// Take the last n elements.
1170 DerivedT take_back(size_t n = 1) const {
1171 return n < size() ? drop_front(size() - n)
1172 : static_cast<const DerivedT &>(*this);
1173 }
1174
1175 /// Allow conversion to any type accepting an iterator_range.
1176 template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
1177 RangeT, iterator_range<iterator>>::value>>
1178 operator RangeT() const {
1179 return RangeT(iterator_range<iterator>(*this));
1180 }
1181
1182 /// Returns the base of this range.
1183 const BaseT &getBase() const { return base; }
1184
1185private:
1186 /// Offset the given base by the given amount.
1187 static BaseT offset_base(const BaseT &base, size_t n) {
1188 return n == 0 ? base : DerivedT::offset_base(base, n);
1189 }
1190
1191protected:
1192 indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
1193 indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
1194 indexed_accessor_range_base &
1195 operator=(const indexed_accessor_range_base &) = default;
1196
1197 /// The base that owns the provided range of values.
1198 BaseT base;
1199 /// The size from the owning range.
1200 ptrdiff_t count;
1201};
1202} // end namespace detail
1203
1204/// This class provides an implementation of a range of
1205/// indexed_accessor_iterators where the base is not indexable. Ranges with
1206/// bases that are offsetable should derive from indexed_accessor_range_base
1207/// instead. Derived range classes are expected to implement the following
1208/// static method:
1209/// * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
1210/// - Dereference an iterator pointing to a parent base at the given index.
1211template <typename DerivedT, typename BaseT, typename T,
1212 typename PointerT = T *, typename ReferenceT = T &>
1213class indexed_accessor_range
1214 : public detail::indexed_accessor_range_base<
1215 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1216public:
1217 indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
1218 : detail::indexed_accessor_range_base<
1219 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1220 std::make_pair(base, startIndex), count) {}
1221 using detail::indexed_accessor_range_base<
1222 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
1223 ReferenceT>::indexed_accessor_range_base;
1224
1225 /// Returns the current base of the range.
1226 const BaseT &getBase() const { return this->base.first; }
1227
1228 /// Returns the current start index of the range.
1229 ptrdiff_t getStartIndex() const { return this->base.second; }
1230
1231 /// See `detail::indexed_accessor_range_base` for details.
1232 static std::pair<BaseT, ptrdiff_t>
1233 offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
1234 // We encode the internal base as a pair of the derived base and a start
1235 // index into the derived base.
1236 return std::make_pair(base.first, base.second + index);
1237 }
1238 /// See `detail::indexed_accessor_range_base` for details.
1239 static ReferenceT
1240 dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
1241 ptrdiff_t index) {
1242 return DerivedT::dereference(base.first, base.second + index);
1243 }
1244};
1245
1246/// Given a container of pairs, return a range over the first elements.
1247template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
1248 return llvm::map_range(
1249 std::forward<ContainerTy>(c),
1250 [](decltype((*std::begin(c))) elt) -> decltype((elt.first)) {
1251 return elt.first;
1252 });
1253}
1254
1255/// Given a container of pairs, return a range over the second elements.
1256template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
1257 return llvm::map_range(
1258 std::forward<ContainerTy>(c),
1259 [](decltype((*std::begin(c))) elt) -> decltype((elt.second)) {
1260 return elt.second;
1261 });
1262}
1263
1264//===----------------------------------------------------------------------===//
1265// Extra additions to <utility>
1266//===----------------------------------------------------------------------===//
1267
1268/// Function object to check whether the first component of a std::pair
1269/// compares less than the first component of another std::pair.
1270struct less_first {
1271 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1272 return lhs.first < rhs.first;
1273 }
1274};
1275
1276/// Function object to check whether the second component of a std::pair
1277/// compares less than the second component of another std::pair.
1278struct less_second {
1279 template <typename T> bool operator()(const T &lhs, const T &rhs) const {
1280 return lhs.second < rhs.second;
1281 }
1282};
1283
1284/// \brief Function object to apply a binary function to the first component of
1285/// a std::pair.
1286template<typename FuncTy>
1287struct on_first {
1288 FuncTy func;
1289
1290 template <typename T>
1291 decltype(auto) operator()(const T &lhs, const T &rhs) const {
1292 return func(lhs.first, rhs.first);
1293 }
1294};
1295
1296/// Utility type to build an inheritance chain that makes it easy to rank
1297/// overload candidates.
1298template <int N> struct rank : rank<N - 1> {};
1299template <> struct rank<0> {};
1300
1301/// traits class for checking whether type T is one of any of the given
1302/// types in the variadic list.
1303template <typename T, typename... Ts> struct is_one_of {
1304 static const bool value = false;
1305};
1306
1307template <typename T, typename U, typename... Ts>
1308struct is_one_of<T, U, Ts...> {
1309 static const bool value =
1310 std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
1311};
1312
1313/// traits class for checking whether type T is a base class for all
1314/// the given types in the variadic list.
1315template <typename T, typename... Ts> struct are_base_of {
1316 static const bool value = true;
1317};
1318
1319template <typename T, typename U, typename... Ts>
1320struct are_base_of<T, U, Ts...> {
1321 static const bool value =
1322 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
1323};
1324
1325//===----------------------------------------------------------------------===//
1326// Extra additions for arrays
1327//===----------------------------------------------------------------------===//
1328
1329// We have a copy here so that LLVM behaves the same when using different
1330// standard libraries.
1331template <class Iterator, class RNG>
1332void shuffle(Iterator first, Iterator last, RNG &&g) {
1333 // It would be better to use a std::uniform_int_distribution,
1334 // but that would be stdlib dependent.
1335 typedef
1336 typename std::iterator_traits<Iterator>::difference_type difference_type;
1337 for (auto size = last - first; size > 1; ++first, (void)--size) {
1338 difference_type offset = g() % size;
1339 // Avoid self-assignment due to incorrect assertions in libstdc++
1340 // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828).
1341 if (offset != difference_type(0))
1342 std::iter_swap(first, first + offset);
1343 }
1344}
1345
1346/// Find the length of an array.
1347template <class T, std::size_t N>
1348constexpr inline size_t array_lengthof(T (&)[N]) {
1349 return N;
1350}
1351
1352/// Adapt std::less<T> for array_pod_sort.
1353template<typename T>
1354inline int array_pod_sort_comparator(const void *P1, const void *P2) {
1355 if (std::less<T>()(*reinterpret_cast<const T*>(P1),
1356 *reinterpret_cast<const T*>(P2)))
1357 return -1;
1358 if (std::less<T>()(*reinterpret_cast<const T*>(P2),
1359 *reinterpret_cast<const T*>(P1)))
1360 return 1;
1361 return 0;
1362}
1363
1364/// get_array_pod_sort_comparator - This is an internal helper function used to
1365/// get type deduction of T right.
1366template<typename T>
1367inline int (*get_array_pod_sort_comparator(const T &))
1368 (const void*, const void*) {
1369 return array_pod_sort_comparator<T>;
1370}
1371
1372#ifdef EXPENSIVE_CHECKS
1373namespace detail {
1374
1375inline unsigned presortShuffleEntropy() {
1376 static unsigned Result(std::random_device{}());
1377 return Result;
1378}
1379
1380template <class IteratorTy>
1381inline void presortShuffle(IteratorTy Start, IteratorTy End) {
1382 std::mt19937 Generator(presortShuffleEntropy());
1383 llvm::shuffle(Start, End, Generator);
1384}
1385
1386} // end namespace detail
1387#endif
1388
1389/// array_pod_sort - This sorts an array with the specified start and end
1390/// extent. This is just like std::sort, except that it calls qsort instead of
1391/// using an inlined template. qsort is slightly slower than std::sort, but
1392/// most sorts are not performance critical in LLVM and std::sort has to be
1393/// template instantiated for each type, leading to significant measured code
1394/// bloat. This function should generally be used instead of std::sort where
1395/// possible.
1396///
1397/// This function assumes that you have simple POD-like types that can be
1398/// compared with std::less and can be moved with memcpy. If this isn't true,