Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MemCpyOptimizer.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/MemCpyOptimizer.cpp

/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp

1//===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
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 pass performs various transformations related to eliminating memcpy
10// calls, or transforming sets of stores into memset's.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
15#include "llvm/ADT/DenseSet.h"
16#include "llvm/ADT/None.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/iterator_range.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/GlobalsModRef.h"
24#include "llvm/Analysis/Loads.h"
25#include "llvm/Analysis/MemoryDependenceAnalysis.h"
26#include "llvm/Analysis/MemoryLocation.h"
27#include "llvm/Analysis/MemorySSA.h"
28#include "llvm/Analysis/MemorySSAUpdater.h"
29#include "llvm/Analysis/TargetLibraryInfo.h"
30#include "llvm/Analysis/ValueTracking.h"
31#include "llvm/IR/Argument.h"
32#include "llvm/IR/BasicBlock.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/DerivedTypes.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/Function.h"
38#include "llvm/IR/GetElementPtrTypeIterator.h"
39#include "llvm/IR/GlobalVariable.h"
40#include "llvm/IR/IRBuilder.h"
41#include "llvm/IR/InstrTypes.h"
42#include "llvm/IR/Instruction.h"
43#include "llvm/IR/Instructions.h"
44#include "llvm/IR/IntrinsicInst.h"
45#include "llvm/IR/Intrinsics.h"
46#include "llvm/IR/LLVMContext.h"
47#include "llvm/IR/Module.h"
48#include "llvm/IR/Operator.h"
49#include "llvm/IR/PassManager.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/User.h"
52#include "llvm/IR/Value.h"
53#include "llvm/InitializePasses.h"
54#include "llvm/Pass.h"
55#include "llvm/Support/Casting.h"
56#include "llvm/Support/Debug.h"
57#include "llvm/Support/MathExtras.h"
58#include "llvm/Support/raw_ostream.h"
59#include "llvm/Transforms/Scalar.h"
60#include "llvm/Transforms/Utils/Local.h"
61#include <algorithm>
62#include <cassert>
63#include <cstdint>
64#include <utility>
65
66using namespace llvm;
67
68#define DEBUG_TYPE"memcpyopt" "memcpyopt"
69
70static cl::opt<bool>
71 EnableMemorySSA("enable-memcpyopt-memoryssa", cl::init(true), cl::Hidden,
72 cl::desc("Use MemorySSA-backed MemCpyOpt."));
73
74STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted")static llvm::Statistic NumMemCpyInstr = {"memcpyopt", "NumMemCpyInstr"
, "Number of memcpy instructions deleted"}
;
75STATISTIC(NumMemSetInfer, "Number of memsets inferred")static llvm::Statistic NumMemSetInfer = {"memcpyopt", "NumMemSetInfer"
, "Number of memsets inferred"}
;
76STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy")static llvm::Statistic NumMoveToCpy = {"memcpyopt", "NumMoveToCpy"
, "Number of memmoves converted to memcpy"}
;
77STATISTIC(NumCpyToSet, "Number of memcpys converted to memset")static llvm::Statistic NumCpyToSet = {"memcpyopt", "NumCpyToSet"
, "Number of memcpys converted to memset"}
;
78STATISTIC(NumCallSlot, "Number of call slot optimizations performed")static llvm::Statistic NumCallSlot = {"memcpyopt", "NumCallSlot"
, "Number of call slot optimizations performed"}
;
79
80namespace {
81
82/// Represents a range of memset'd bytes with the ByteVal value.
83/// This allows us to analyze stores like:
84/// store 0 -> P+1
85/// store 0 -> P+0
86/// store 0 -> P+3
87/// store 0 -> P+2
88/// which sometimes happens with stores to arrays of structs etc. When we see
89/// the first store, we make a range [1, 2). The second store extends the range
90/// to [0, 2). The third makes a new range [2, 3). The fourth store joins the
91/// two ranges into [0, 3) which is memset'able.
92struct MemsetRange {
93 // Start/End - A semi range that describes the span that this range covers.
94 // The range is closed at the start and open at the end: [Start, End).
95 int64_t Start, End;
96
97 /// StartPtr - The getelementptr instruction that points to the start of the
98 /// range.
99 Value *StartPtr;
100
101 /// Alignment - The known alignment of the first store.
102 unsigned Alignment;
103
104 /// TheStores - The actual stores that make up this range.
105 SmallVector<Instruction*, 16> TheStores;
106
107 bool isProfitableToUseMemset(const DataLayout &DL) const;
108};
109
110} // end anonymous namespace
111
112bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
113 // If we found more than 4 stores to merge or 16 bytes, use memset.
114 if (TheStores.size() >= 4 || End-Start >= 16) return true;
115
116 // If there is nothing to merge, don't do anything.
117 if (TheStores.size() < 2) return false;
118
119 // If any of the stores are a memset, then it is always good to extend the
120 // memset.
121 for (Instruction *SI : TheStores)
122 if (!isa<StoreInst>(SI))
123 return true;
124
125 // Assume that the code generator is capable of merging pairs of stores
126 // together if it wants to.
127 if (TheStores.size() == 2) return false;
128
129 // If we have fewer than 8 stores, it can still be worthwhile to do this.
130 // For example, merging 4 i8 stores into an i32 store is useful almost always.
131 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
132 // memset will be split into 2 32-bit stores anyway) and doing so can
133 // pessimize the llvm optimizer.
134 //
135 // Since we don't have perfect knowledge here, make some assumptions: assume
136 // the maximum GPR width is the same size as the largest legal integer
137 // size. If so, check to see whether we will end up actually reducing the
138 // number of stores used.
139 unsigned Bytes = unsigned(End-Start);
140 unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
141 if (MaxIntSize == 0)
142 MaxIntSize = 1;
143 unsigned NumPointerStores = Bytes / MaxIntSize;
144
145 // Assume the remaining bytes if any are done a byte at a time.
146 unsigned NumByteStores = Bytes % MaxIntSize;
147
148 // If we will reduce the # stores (according to this heuristic), do the
149 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
150 // etc.
151 return TheStores.size() > NumPointerStores+NumByteStores;
152}
153
154namespace {
155
156class MemsetRanges {
157 using range_iterator = SmallVectorImpl<MemsetRange>::iterator;
158
159 /// A sorted list of the memset ranges.
160 SmallVector<MemsetRange, 8> Ranges;
161
162 const DataLayout &DL;
163
164public:
165 MemsetRanges(const DataLayout &DL) : DL(DL) {}
166
167 using const_iterator = SmallVectorImpl<MemsetRange>::const_iterator;
168
169 const_iterator begin() const { return Ranges.begin(); }
170 const_iterator end() const { return Ranges.end(); }
171 bool empty() const { return Ranges.empty(); }
172
173 void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
174 if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
175 addStore(OffsetFromFirst, SI);
176 else
177 addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
178 }
179
180 void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
181 int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
182
183 addRange(OffsetFromFirst, StoreSize, SI->getPointerOperand(),
184 SI->getAlign().value(), SI);
185 }
186
187 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
188 int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
189 addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getDestAlignment(), MSI);
190 }
191
192 void addRange(int64_t Start, int64_t Size, Value *Ptr,
193 unsigned Alignment, Instruction *Inst);
194};
195
196} // end anonymous namespace
197
198/// Add a new store to the MemsetRanges data structure. This adds a
199/// new range for the specified store at the specified offset, merging into
200/// existing ranges as appropriate.
201void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
202 unsigned Alignment, Instruction *Inst) {
203 int64_t End = Start+Size;
204
205 range_iterator I = partition_point(
206 Ranges, [=](const MemsetRange &O) { return O.End < Start; });
207
208 // We now know that I == E, in which case we didn't find anything to merge
209 // with, or that Start <= I->End. If End < I->Start or I == E, then we need
210 // to insert a new range. Handle this now.
211 if (I == Ranges.end() || End < I->Start) {
212 MemsetRange &R = *Ranges.insert(I, MemsetRange());
213 R.Start = Start;
214 R.End = End;
215 R.StartPtr = Ptr;
216 R.Alignment = Alignment;
217 R.TheStores.push_back(Inst);
218 return;
219 }
220
221 // This store overlaps with I, add it.
222 I->TheStores.push_back(Inst);
223
224 // At this point, we may have an interval that completely contains our store.
225 // If so, just add it to the interval and return.
226 if (I->Start <= Start && I->End >= End)
227 return;
228
229 // Now we know that Start <= I->End and End >= I->Start so the range overlaps
230 // but is not entirely contained within the range.
231
232 // See if the range extends the start of the range. In this case, it couldn't
233 // possibly cause it to join the prior range, because otherwise we would have
234 // stopped on *it*.
235 if (Start < I->Start) {
236 I->Start = Start;
237 I->StartPtr = Ptr;
238 I->Alignment = Alignment;
239 }
240
241 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
242 // is in or right at the end of I), and that End >= I->Start. Extend I out to
243 // End.
244 if (End > I->End) {
245 I->End = End;
246 range_iterator NextI = I;
247 while (++NextI != Ranges.end() && End >= NextI->Start) {
248 // Merge the range in.
249 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
250 if (NextI->End > I->End)
251 I->End = NextI->End;
252 Ranges.erase(NextI);
253 NextI = I;
254 }
255 }
256}
257
258//===----------------------------------------------------------------------===//
259// MemCpyOptLegacyPass Pass
260//===----------------------------------------------------------------------===//
261
262namespace {
263
264class MemCpyOptLegacyPass : public FunctionPass {
265 MemCpyOptPass Impl;
266
267public:
268 static char ID; // Pass identification, replacement for typeid
269
270 MemCpyOptLegacyPass() : FunctionPass(ID) {
271 initializeMemCpyOptLegacyPassPass(*PassRegistry::getPassRegistry());
272 }
273
274 bool runOnFunction(Function &F) override;
275
276private:
277 // This transformation requires dominator postdominator info
278 void getAnalysisUsage(AnalysisUsage &AU) const override {
279 AU.setPreservesCFG();
280 AU.addRequired<AssumptionCacheTracker>();
281 AU.addRequired<DominatorTreeWrapperPass>();
282 AU.addPreserved<DominatorTreeWrapperPass>();
283 AU.addPreserved<GlobalsAAWrapperPass>();
284 AU.addRequired<TargetLibraryInfoWrapperPass>();
285 if (!EnableMemorySSA)
286 AU.addRequired<MemoryDependenceWrapperPass>();
287 AU.addPreserved<MemoryDependenceWrapperPass>();
288 AU.addRequired<AAResultsWrapperPass>();
289 AU.addPreserved<AAResultsWrapperPass>();
290 if (EnableMemorySSA)
291 AU.addRequired<MemorySSAWrapperPass>();
292 AU.addPreserved<MemorySSAWrapperPass>();
293 }
294};
295
296} // end anonymous namespace
297
298char MemCpyOptLegacyPass::ID = 0;
299
300/// The public interface to this file...
301FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOptLegacyPass(); }
302
303INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",static void *initializeMemCpyOptLegacyPassPassOnce(PassRegistry
&Registry) {
304 false, false)static void *initializeMemCpyOptLegacyPassPassOnce(PassRegistry
&Registry) {
305INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
306INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
307INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)initializeMemoryDependenceWrapperPassPass(Registry);
308INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
309INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
310INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)initializeGlobalsAAWrapperPassPass(Registry);
311INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)initializeMemorySSAWrapperPassPass(Registry);
312INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",PassInfo *PI = new PassInfo( "MemCpy Optimization", "memcpyopt"
, &MemCpyOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MemCpyOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMemCpyOptLegacyPassPassFlag
; void llvm::initializeMemCpyOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeMemCpyOptLegacyPassPassFlag
, initializeMemCpyOptLegacyPassPassOnce, std::ref(Registry));
}
313 false, false)PassInfo *PI = new PassInfo( "MemCpy Optimization", "memcpyopt"
, &MemCpyOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MemCpyOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMemCpyOptLegacyPassPassFlag
; void llvm::initializeMemCpyOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeMemCpyOptLegacyPassPassFlag
, initializeMemCpyOptLegacyPassPassOnce, std::ref(Registry));
}
314
315// Check that V is either not accessible by the caller, or unwinding cannot
316// occur between Start and End.
317static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start,
318 Instruction *End) {
319 assert(Start->getParent() == End->getParent() && "Must be in same block")((Start->getParent() == End->getParent() && "Must be in same block"
) ? static_cast<void> (0) : __assert_fail ("Start->getParent() == End->getParent() && \"Must be in same block\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 319, __PRETTY_FUNCTION__))
;
320 if (!Start->getFunction()->doesNotThrow() &&
321 !isa<AllocaInst>(getUnderlyingObject(V))) {
322 for (const Instruction &I :
323 make_range(Start->getIterator(), End->getIterator())) {
324 if (I.mayThrow())
325 return true;
326 }
327 }
328 return false;
329}
330
331void MemCpyOptPass::eraseInstruction(Instruction *I) {
332 if (MSSAU)
333 MSSAU->removeMemoryAccess(I);
334 if (MD)
335 MD->removeInstruction(I);
336 I->eraseFromParent();
337}
338
339// Check for mod or ref of Loc between Start and End, excluding both boundaries.
340// Start and End must be in the same block
341static bool accessedBetween(AliasAnalysis &AA, MemoryLocation Loc,
342 const MemoryUseOrDef *Start,
343 const MemoryUseOrDef *End) {
344 assert(Start->getBlock() == End->getBlock() && "Only local supported")((Start->getBlock() == End->getBlock() && "Only local supported"
) ? static_cast<void> (0) : __assert_fail ("Start->getBlock() == End->getBlock() && \"Only local supported\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 344, __PRETTY_FUNCTION__))
;
345 for (const MemoryAccess &MA :
346 make_range(++Start->getIterator(), End->getIterator())) {
347 if (isModOrRefSet(AA.getModRefInfo(cast<MemoryUseOrDef>(MA).getMemoryInst(),
348 Loc)))
349 return true;
350 }
351 return false;
352}
353
354// Check for mod of Loc between Start and End, excluding both boundaries.
355// Start and End can be in different blocks.
356static bool writtenBetween(MemorySSA *MSSA, MemoryLocation Loc,
357 const MemoryUseOrDef *Start,
358 const MemoryUseOrDef *End) {
359 // TODO: Only walk until we hit Start.
360 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
361 End->getDefiningAccess(), Loc);
362 return !MSSA->dominates(Clobber, Start);
363}
364
365/// When scanning forward over instructions, we look for some other patterns to
366/// fold away. In particular, this looks for stores to neighboring locations of
367/// memory. If it sees enough consecutive ones, it attempts to merge them
368/// together into a memcpy/memset.
369Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
370 Value *StartPtr,
371 Value *ByteVal) {
372 const DataLayout &DL = StartInst->getModule()->getDataLayout();
373
374 // Okay, so we now have a single store that can be splatable. Scan to find
375 // all subsequent stores of the same value to offset from the same pointer.
376 // Join these together into ranges, so we can decide whether contiguous blocks
377 // are stored.
378 MemsetRanges Ranges(DL);
379
380 BasicBlock::iterator BI(StartInst);
381
382 // Keeps track of the last memory use or def before the insertion point for
383 // the new memset. The new MemoryDef for the inserted memsets will be inserted
384 // after MemInsertPoint. It points to either LastMemDef or to the last user
385 // before the insertion point of the memset, if there are any such users.
386 MemoryUseOrDef *MemInsertPoint = nullptr;
387 // Keeps track of the last MemoryDef between StartInst and the insertion point
388 // for the new memset. This will become the defining access of the inserted
389 // memsets.
390 MemoryDef *LastMemDef = nullptr;
391 for (++BI; !BI->isTerminator(); ++BI) {
392 if (MSSAU) {
393 auto *CurrentAcc = cast_or_null<MemoryUseOrDef>(
394 MSSAU->getMemorySSA()->getMemoryAccess(&*BI));
395 if (CurrentAcc) {
396 MemInsertPoint = CurrentAcc;
397 if (auto *CurrentDef = dyn_cast<MemoryDef>(CurrentAcc))
398 LastMemDef = CurrentDef;
399 }
400 }
401
402 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
403 // If the instruction is readnone, ignore it, otherwise bail out. We
404 // don't even allow readonly here because we don't want something like:
405 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
406 if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
407 break;
408 continue;
409 }
410
411 if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
412 // If this is a store, see if we can merge it in.
413 if (!NextStore->isSimple()) break;
414
415 Value *StoredVal = NextStore->getValueOperand();
416
417 // Don't convert stores of non-integral pointer types to memsets (which
418 // stores integers).
419 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
420 break;
421
422 // Check to see if this stored value is of the same byte-splattable value.
423 Value *StoredByte = isBytewiseValue(StoredVal, DL);
424 if (isa<UndefValue>(ByteVal) && StoredByte)
425 ByteVal = StoredByte;
426 if (ByteVal != StoredByte)
427 break;
428
429 // Check to see if this store is to a constant offset from the start ptr.
430 Optional<int64_t> Offset =
431 isPointerOffset(StartPtr, NextStore->getPointerOperand(), DL);
432 if (!Offset)
433 break;
434
435 Ranges.addStore(*Offset, NextStore);
436 } else {
437 MemSetInst *MSI = cast<MemSetInst>(BI);
438
439 if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
440 !isa<ConstantInt>(MSI->getLength()))
441 break;
442
443 // Check to see if this store is to a constant offset from the start ptr.
444 Optional<int64_t> Offset = isPointerOffset(StartPtr, MSI->getDest(), DL);
445 if (!Offset)
446 break;
447
448 Ranges.addMemSet(*Offset, MSI);
449 }
450 }
451
452 // If we have no ranges, then we just had a single store with nothing that
453 // could be merged in. This is a very common case of course.
454 if (Ranges.empty())
455 return nullptr;
456
457 // If we had at least one store that could be merged in, add the starting
458 // store as well. We try to avoid this unless there is at least something
459 // interesting as a small compile-time optimization.
460 Ranges.addInst(0, StartInst);
461
462 // If we create any memsets, we put it right before the first instruction that
463 // isn't part of the memset block. This ensure that the memset is dominated
464 // by any addressing instruction needed by the start of the block.
465 IRBuilder<> Builder(&*BI);
466
467 // Now that we have full information about ranges, loop over the ranges and
468 // emit memset's for anything big enough to be worthwhile.
469 Instruction *AMemSet = nullptr;
470 for (const MemsetRange &Range : Ranges) {
471 if (Range.TheStores.size() == 1) continue;
472
473 // If it is profitable to lower this range to memset, do so now.
474 if (!Range.isProfitableToUseMemset(DL))
475 continue;
476
477 // Otherwise, we do want to transform this! Create a new memset.
478 // Get the starting pointer of the block.
479 StartPtr = Range.StartPtr;
480
481 AMemSet = Builder.CreateMemSet(StartPtr, ByteVal, Range.End - Range.Start,
482 MaybeAlign(Range.Alignment));
483 LLVM_DEBUG(dbgs() << "Replace stores:\n"; for (Instruction *SIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
*SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
(false)
484 : Range.TheStores) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
*SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
(false)
485 << *SI << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
*SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
(false)
486 dbgs() << "With: " << *AMemSet << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Replace stores:\n"; for (Instruction
*SI : Range.TheStores) dbgs() << *SI << '\n'; dbgs
() << "With: " << *AMemSet << '\n'; } } while
(false)
;
487 if (!Range.TheStores.empty())
488 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
489
490 if (MSSAU) {
491 assert(LastMemDef && MemInsertPoint &&((LastMemDef && MemInsertPoint && "Both LastMemDef and MemInsertPoint need to be set"
) ? static_cast<void> (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 492, __PRETTY_FUNCTION__))
492 "Both LastMemDef and MemInsertPoint need to be set")((LastMemDef && MemInsertPoint && "Both LastMemDef and MemInsertPoint need to be set"
) ? static_cast<void> (0) : __assert_fail ("LastMemDef && MemInsertPoint && \"Both LastMemDef and MemInsertPoint need to be set\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 492, __PRETTY_FUNCTION__))
;
493 auto *NewDef =
494 cast<MemoryDef>(MemInsertPoint->getMemoryInst() == &*BI
495 ? MSSAU->createMemoryAccessBefore(
496 AMemSet, LastMemDef, MemInsertPoint)
497 : MSSAU->createMemoryAccessAfter(
498 AMemSet, LastMemDef, MemInsertPoint));
499 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
500 LastMemDef = NewDef;
501 MemInsertPoint = NewDef;
502 }
503
504 // Zap all the stores.
505 for (Instruction *SI : Range.TheStores)
506 eraseInstruction(SI);
507
508 ++NumMemSetInfer;
509 }
510
511 return AMemSet;
512}
513
514// This method try to lift a store instruction before position P.
515// It will lift the store and its argument + that anything that
516// may alias with these.
517// The method returns true if it was successful.
518bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *P, const LoadInst *LI) {
519 // If the store alias this position, early bail out.
520 MemoryLocation StoreLoc = MemoryLocation::get(SI);
521 if (isModOrRefSet(AA->getModRefInfo(P, StoreLoc)))
522 return false;
523
524 // Keep track of the arguments of all instruction we plan to lift
525 // so we can make sure to lift them as well if appropriate.
526 DenseSet<Instruction*> Args;
527 if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand()))
528 if (Ptr->getParent() == SI->getParent())
529 Args.insert(Ptr);
530
531 // Instruction to lift before P.
532 SmallVector<Instruction *, 8> ToLift{SI};
533
534 // Memory locations of lifted instructions.
535 SmallVector<MemoryLocation, 8> MemLocs{StoreLoc};
536
537 // Lifted calls.
538 SmallVector<const CallBase *, 8> Calls;
539
540 const MemoryLocation LoadLoc = MemoryLocation::get(LI);
541
542 for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
543 auto *C = &*I;
544
545 // Make sure hoisting does not perform a store that was not guaranteed to
546 // happen.
547 if (!isGuaranteedToTransferExecutionToSuccessor(C))
548 return false;
549
550 bool MayAlias = isModOrRefSet(AA->getModRefInfo(C, None));
551
552 bool NeedLift = false;
553 if (Args.erase(C))
554 NeedLift = true;
555 else if (MayAlias) {
556 NeedLift = llvm::any_of(MemLocs, [C, this](const MemoryLocation &ML) {
557 return isModOrRefSet(AA->getModRefInfo(C, ML));
558 });
559
560 if (!NeedLift)
561 NeedLift = llvm::any_of(Calls, [C, this](const CallBase *Call) {
562 return isModOrRefSet(AA->getModRefInfo(C, Call));
563 });
564 }
565
566 if (!NeedLift)
567 continue;
568
569 if (MayAlias) {
570 // Since LI is implicitly moved downwards past the lifted instructions,
571 // none of them may modify its source.
572 if (isModSet(AA->getModRefInfo(C, LoadLoc)))
573 return false;
574 else if (const auto *Call = dyn_cast<CallBase>(C)) {
575 // If we can't lift this before P, it's game over.
576 if (isModOrRefSet(AA->getModRefInfo(P, Call)))
577 return false;
578
579 Calls.push_back(Call);
580 } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
581 // If we can't lift this before P, it's game over.
582 auto ML = MemoryLocation::get(C);
583 if (isModOrRefSet(AA->getModRefInfo(P, ML)))
584 return false;
585
586 MemLocs.push_back(ML);
587 } else
588 // We don't know how to lift this instruction.
589 return false;
590 }
591
592 ToLift.push_back(C);
593 for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
594 if (auto *A = dyn_cast<Instruction>(C->getOperand(k))) {
595 if (A->getParent() == SI->getParent()) {
596 // Cannot hoist user of P above P
597 if(A == P) return false;
598 Args.insert(A);
599 }
600 }
601 }
602
603 // Find MSSA insertion point. Normally P will always have a corresponding
604 // memory access before which we can insert. However, with non-standard AA
605 // pipelines, there may be a mismatch between AA and MSSA, in which case we
606 // will scan for a memory access before P. In either case, we know for sure
607 // that at least the load will have a memory access.
608 // TODO: Simplify this once P will be determined by MSSA, in which case the
609 // discrepancy can no longer occur.
610 MemoryUseOrDef *MemInsertPoint = nullptr;
611 if (MSSAU) {
612 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(P)) {
613 MemInsertPoint = cast<MemoryUseOrDef>(--MA->getIterator());
614 } else {
615 const Instruction *ConstP = P;
616 for (const Instruction &I : make_range(++ConstP->getReverseIterator(),
617 ++LI->getReverseIterator())) {
618 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
619 MemInsertPoint = MA;
620 break;
621 }
622 }
623 }
624 }
625
626 // We made it, we need to lift.
627 for (auto *I : llvm::reverse(ToLift)) {
628 LLVM_DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Lifting " << *I <<
" before " << *P << "\n"; } } while (false)
;
629 I->moveBefore(P);
630 if (MSSAU) {
631 assert(MemInsertPoint && "Must have found insert point")((MemInsertPoint && "Must have found insert point") ?
static_cast<void> (0) : __assert_fail ("MemInsertPoint && \"Must have found insert point\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 631, __PRETTY_FUNCTION__))
;
632 if (MemoryUseOrDef *MA = MSSAU->getMemorySSA()->getMemoryAccess(I)) {
633 MSSAU->moveAfter(MA, MemInsertPoint);
634 MemInsertPoint = MA;
635 }
636 }
637 }
638
639 return true;
640}
641
642bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
643 if (!SI->isSimple()) return false;
644
645 // Avoid merging nontemporal stores since the resulting
646 // memcpy/memset would not be able to preserve the nontemporal hint.
647 // In theory we could teach how to propagate the !nontemporal metadata to
648 // memset calls. However, that change would force the backend to
649 // conservatively expand !nontemporal memset calls back to sequences of
650 // store instructions (effectively undoing the merging).
651 if (SI->getMetadata(LLVMContext::MD_nontemporal))
652 return false;
653
654 const DataLayout &DL = SI->getModule()->getDataLayout();
655
656 Value *StoredVal = SI->getValueOperand();
657
658 // Not all the transforms below are correct for non-integral pointers, bail
659 // until we've audited the individual pieces.
660 if (DL.isNonIntegralPointerType(StoredVal->getType()->getScalarType()))
661 return false;
662
663 // Load to store forwarding can be interpreted as memcpy.
664 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
665 if (LI->isSimple() && LI->hasOneUse() &&
666 LI->getParent() == SI->getParent()) {
667
668 auto *T = LI->getType();
669 if (T->isAggregateType()) {
670 MemoryLocation LoadLoc = MemoryLocation::get(LI);
671
672 // We use alias analysis to check if an instruction may store to
673 // the memory we load from in between the load and the store. If
674 // such an instruction is found, we try to promote there instead
675 // of at the store position.
676 // TODO: Can use MSSA for this.
677 Instruction *P = SI;
678 for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
679 if (isModSet(AA->getModRefInfo(&I, LoadLoc))) {
680 P = &I;
681 break;
682 }
683 }
684
685 // We found an instruction that may write to the loaded memory.
686 // We can try to promote at this position instead of the store
687 // position if nothing alias the store memory after this and the store
688 // destination is not in the range.
689 if (P && P != SI) {
690 if (!moveUp(SI, P, LI))
691 P = nullptr;
692 }
693
694 // If a valid insertion position is found, then we can promote
695 // the load/store pair to a memcpy.
696 if (P) {
697 // If we load from memory that may alias the memory we store to,
698 // memmove must be used to preserve semantic. If not, memcpy can
699 // be used.
700 bool UseMemMove = false;
701 if (!AA->isNoAlias(MemoryLocation::get(SI), LoadLoc))
702 UseMemMove = true;
703
704 uint64_t Size = DL.getTypeStoreSize(T);
705
706 IRBuilder<> Builder(P);
707 Instruction *M;
708 if (UseMemMove)
709 M = Builder.CreateMemMove(
710 SI->getPointerOperand(), SI->getAlign(),
711 LI->getPointerOperand(), LI->getAlign(), Size);
712 else
713 M = Builder.CreateMemCpy(
714 SI->getPointerOperand(), SI->getAlign(),
715 LI->getPointerOperand(), LI->getAlign(), Size);
716
717 LLVM_DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI << " => "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *LI <<
" to " << *SI << " => " << *M << "\n"
; } } while (false)
718 << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *LI <<
" to " << *SI << " => " << *M << "\n"
; } } while (false)
;
719
720 if (MSSAU) {
721 auto *LastDef =
722 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
723 auto *NewAccess =
724 MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
725 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
726 }
727
728 eraseInstruction(SI);
729 eraseInstruction(LI);
730 ++NumMemCpyInstr;
731
732 // Make sure we do not invalidate the iterator.
733 BBI = M->getIterator();
734 return true;
735 }
736 }
737
738 // Detect cases where we're performing call slot forwarding, but
739 // happen to be using a load-store pair to implement it, rather than
740 // a memcpy.
741 CallInst *C = nullptr;
742 if (EnableMemorySSA) {
743 if (auto *LoadClobber = dyn_cast<MemoryUseOrDef>(
744 MSSA->getWalker()->getClobberingMemoryAccess(LI))) {
745 // The load most post-dom the call. Limit to the same block for now.
746 // TODO: Support non-local call-slot optimization?
747 if (LoadClobber->getBlock() == SI->getParent())
748 C = dyn_cast_or_null<CallInst>(LoadClobber->getMemoryInst());
749 }
750 } else {
751 MemDepResult ldep = MD->getDependency(LI);
752 if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
753 C = dyn_cast<CallInst>(ldep.getInst());
754 }
755
756 if (C) {
757 // Check that nothing touches the dest of the "copy" between
758 // the call and the store.
759 MemoryLocation StoreLoc = MemoryLocation::get(SI);
760 if (EnableMemorySSA) {
761 if (accessedBetween(*AA, StoreLoc, MSSA->getMemoryAccess(C),
762 MSSA->getMemoryAccess(SI)))
763 C = nullptr;
764 } else {
765 for (BasicBlock::iterator I = --SI->getIterator(),
766 E = C->getIterator();
767 I != E; --I) {
768 if (isModOrRefSet(AA->getModRefInfo(&*I, StoreLoc))) {
769 C = nullptr;
770 break;
771 }
772 }
773 }
774 }
775
776 if (C) {
777 bool changed = performCallSlotOptzn(
778 LI, SI, SI->getPointerOperand()->stripPointerCasts(),
779 LI->getPointerOperand()->stripPointerCasts(),
780 DL.getTypeStoreSize(SI->getOperand(0)->getType()),
781 commonAlignment(SI->getAlign(), LI->getAlign()), C);
782 if (changed) {
783 eraseInstruction(SI);
784 eraseInstruction(LI);
785 ++NumMemCpyInstr;
786 return true;
787 }
788 }
789 }
790 }
791
792 // There are two cases that are interesting for this code to handle: memcpy
793 // and memset. Right now we only handle memset.
794
795 // Ensure that the value being stored is something that can be memset'able a
796 // byte at a time like "0" or "-1" or any width, as well as things like
797 // 0xA0A0A0A0 and 0.0.
798 auto *V = SI->getOperand(0);
799 if (Value *ByteVal = isBytewiseValue(V, DL)) {
800 if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
801 ByteVal)) {
802 BBI = I->getIterator(); // Don't invalidate iterator.
803 return true;
804 }
805
806 // If we have an aggregate, we try to promote it to memset regardless
807 // of opportunity for merging as it can expose optimization opportunities
808 // in subsequent passes.
809 auto *T = V->getType();
810 if (T->isAggregateType()) {
811 uint64_t Size = DL.getTypeStoreSize(T);
812 IRBuilder<> Builder(SI);
813 auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal, Size,
814 SI->getAlign());
815
816 LLVM_DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Promoting " << *SI <<
" to " << *M << "\n"; } } while (false)
;
817
818 if (MSSAU) {
819 assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI)))((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(SI))) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI))"
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 819, __PRETTY_FUNCTION__))
;
820 auto *LastDef =
821 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(SI));
822 auto *NewAccess = MSSAU->createMemoryAccessAfter(M, LastDef, LastDef);
823 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
824 }
825
826 eraseInstruction(SI);
827 NumMemSetInfer++;
828
829 // Make sure we do not invalidate the iterator.
830 BBI = M->getIterator();
831 return true;
832 }
833 }
834
835 return false;
836}
837
838bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
839 // See if there is another memset or store neighboring this memset which
840 // allows us to widen out the memset to do a single larger store.
841 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
842 if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
843 MSI->getValue())) {
844 BBI = I->getIterator(); // Don't invalidate iterator.
845 return true;
846 }
847 return false;
848}
849
850/// Takes a memcpy and a call that it depends on,
851/// and checks for the possibility of a call slot optimization by having
852/// the call write its result directly into the destination of the memcpy.
853bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
854 Instruction *cpyStore, Value *cpyDest,
855 Value *cpySrc, uint64_t cpyLen,
856 Align cpyAlign, CallInst *C) {
857 // The general transformation to keep in mind is
858 //
859 // call @func(..., src, ...)
860 // memcpy(dest, src, ...)
861 //
862 // ->
863 //
864 // memcpy(dest, src, ...)
865 // call @func(..., dest, ...)
866 //
867 // Since moving the memcpy is technically awkward, we additionally check that
868 // src only holds uninitialized values at the moment of the call, meaning that
869 // the memcpy can be discarded rather than moved.
870
871 // Lifetime marks shouldn't be operated on.
872 if (Function *F = C->getCalledFunction())
873 if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
874 return false;
875
876 // Require that src be an alloca. This simplifies the reasoning considerably.
877 AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
878 if (!srcAlloca)
879 return false;
880
881 ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
882 if (!srcArraySize)
883 return false;
884
885 const DataLayout &DL = cpyLoad->getModule()->getDataLayout();
886 uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) *
887 srcArraySize->getZExtValue();
888
889 if (cpyLen < srcSize)
890 return false;
891
892 // Check that accessing the first srcSize bytes of dest will not cause a
893 // trap. Otherwise the transform is invalid since it might cause a trap
894 // to occur earlier than it otherwise would.
895 if (!isDereferenceableAndAlignedPointer(cpyDest, Align(1), APInt(64, cpyLen),
896 DL, C, DT))
897 return false;
898
899 // Make sure that nothing can observe cpyDest being written early. There are
900 // a number of cases to consider:
901 // 1. cpyDest cannot be accessed between C and cpyStore as a precondition of
902 // the transform.
903 // 2. C itself may not access cpyDest (prior to the transform). This is
904 // checked further below.
905 // 3. If cpyDest is accessible to the caller of this function (potentially
906 // captured and not based on an alloca), we need to ensure that we cannot
907 // unwind between C and cpyStore. This is checked here.
908 // 4. If cpyDest is potentially captured, there may be accesses to it from
909 // another thread. In this case, we need to check that cpyStore is
910 // guaranteed to be executed if C is. As it is a non-atomic access, it
911 // renders accesses from other threads undefined.
912 // TODO: This is currently not checked.
913 if (mayBeVisibleThroughUnwinding(cpyDest, C, cpyStore))
914 return false;
915
916 // Check that dest points to memory that is at least as aligned as src.
917 Align srcAlign = srcAlloca->getAlign();
918 bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
919 // If dest is not aligned enough and we can't increase its alignment then
920 // bail out.
921 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
922 return false;
923
924 // Check that src is not accessed except via the call and the memcpy. This
925 // guarantees that it holds only undefined values when passed in (so the final
926 // memcpy can be dropped), that it is not read or written between the call and
927 // the memcpy, and that writing beyond the end of it is undefined.
928 SmallVector<User *, 8> srcUseList(srcAlloca->users());
929 while (!srcUseList.empty()) {
930 User *U = srcUseList.pop_back_val();
931
932 if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
933 append_range(srcUseList, U->users());
934 continue;
935 }
936 if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) {
937 if (!G->hasAllZeroIndices())
938 return false;
939
940 append_range(srcUseList, U->users());
941 continue;
942 }
943 if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U))
944 if (IT->isLifetimeStartOrEnd())
945 continue;
946
947 if (U != C && U != cpyLoad)
948 return false;
949 }
950
951 // Check that src isn't captured by the called function since the
952 // transformation can cause aliasing issues in that case.
953 for (unsigned ArgI = 0, E = C->arg_size(); ArgI != E; ++ArgI)
954 if (C->getArgOperand(ArgI) == cpySrc && !C->doesNotCapture(ArgI))
955 return false;
956
957 // Since we're changing the parameter to the callsite, we need to make sure
958 // that what would be the new parameter dominates the callsite.
959 if (!DT->dominates(cpyDest, C)) {
960 // Support moving a constant index GEP before the call.
961 auto *GEP = dyn_cast<GetElementPtrInst>(cpyDest);
962 if (GEP && GEP->hasAllConstantIndices() &&
963 DT->dominates(GEP->getPointerOperand(), C))
964 GEP->moveBefore(C);
965 else
966 return false;
967 }
968
969 // In addition to knowing that the call does not access src in some
970 // unexpected manner, for example via a global, which we deduce from
971 // the use analysis, we also need to know that it does not sneakily
972 // access dest. We rely on AA to figure this out for us.
973 ModRefInfo MR = AA->getModRefInfo(C, cpyDest, LocationSize::precise(srcSize));
974 // If necessary, perform additional analysis.
975 if (isModOrRefSet(MR))
976 MR = AA->callCapturesBefore(C, cpyDest, LocationSize::precise(srcSize), DT);
977 if (isModOrRefSet(MR))
978 return false;
979
980 // We can't create address space casts here because we don't know if they're
981 // safe for the target.
982 if (cpySrc->getType()->getPointerAddressSpace() !=
983 cpyDest->getType()->getPointerAddressSpace())
984 return false;
985 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
986 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
987 cpySrc->getType()->getPointerAddressSpace() !=
988 C->getArgOperand(ArgI)->getType()->getPointerAddressSpace())
989 return false;
990
991 // All the checks have passed, so do the transformation.
992 bool changedArgument = false;
993 for (unsigned ArgI = 0; ArgI < C->arg_size(); ++ArgI)
994 if (C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {
995 Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest
996 : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(),
997 cpyDest->getName(), C);
998 changedArgument = true;
999 if (C->getArgOperand(ArgI)->getType() == Dest->getType())
1000 C->setArgOperand(ArgI, Dest);
1001 else
1002 C->setArgOperand(ArgI, CastInst::CreatePointerCast(
1003 Dest, C->getArgOperand(ArgI)->getType(),
1004 Dest->getName(), C));
1005 }
1006
1007 if (!changedArgument)
1008 return false;
1009
1010 // If the destination wasn't sufficiently aligned then increase its alignment.
1011 if (!isDestSufficientlyAligned) {
1012 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!")((isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!"
) ? static_cast<void> (0) : __assert_fail ("isa<AllocaInst>(cpyDest) && \"Can only increase alloca alignment!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1012, __PRETTY_FUNCTION__))
;
1013 cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);
1014 }
1015
1016 // Drop any cached information about the call, because we may have changed
1017 // its dependence information by changing its parameter.
1018 if (MD)
1019 MD->removeInstruction(C);
1020
1021 // Update AA metadata
1022 // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
1023 // handled here, but combineMetadata doesn't support them yet
1024 unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
1025 LLVMContext::MD_noalias,
1026 LLVMContext::MD_invariant_group,
1027 LLVMContext::MD_access_group};
1028 combineMetadata(C, cpyLoad, KnownIDs, true);
1029
1030 ++NumCallSlot;
1031 return true;
1032}
1033
1034/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
1035/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
1036bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
1037 MemCpyInst *MDep) {
1038 // We can only transforms memcpy's where the dest of one is the source of the
1039 // other.
1040 if (M->getSource() != MDep->getDest() || MDep->isVolatile())
1041 return false;
1042
1043 // If dep instruction is reading from our current input, then it is a noop
1044 // transfer and substituting the input won't change this instruction. Just
1045 // ignore the input and let someone else zap MDep. This handles cases like:
1046 // memcpy(a <- a)
1047 // memcpy(b <- a)
1048 if (M->getSource() == MDep->getSource())
1049 return false;
1050
1051 // Second, the length of the memcpy's must be the same, or the preceding one
1052 // must be larger than the following one.
1053 ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
1054 ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength());
1055 if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue())
1056 return false;
1057
1058 // Verify that the copied-from memory doesn't change in between the two
1059 // transfers. For example, in:
1060 // memcpy(a <- b)
1061 // *b = 42;
1062 // memcpy(c <- a)
1063 // It would be invalid to transform the second memcpy into memcpy(c <- b).
1064 //
1065 // TODO: If the code between M and MDep is transparent to the destination "c",
1066 // then we could still perform the xform by moving M up to the first memcpy.
1067 if (EnableMemorySSA) {
1068 // TODO: It would be sufficient to check the MDep source up to the memcpy
1069 // size of M, rather than MDep.
1070 if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
1071 MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(M)))
1072 return false;
1073 } else {
1074 // NOTE: This is conservative, it will stop on any read from the source loc,
1075 // not just the defining memcpy.
1076 MemDepResult SourceDep =
1077 MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false,
1078 M->getIterator(), M->getParent());
1079 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
1080 return false;
1081 }
1082
1083 // If the dest of the second might alias the source of the first, then the
1084 // source and dest might overlap. We still want to eliminate the intermediate
1085 // value, but we have to generate a memmove instead of memcpy.
1086 bool UseMemMove = false;
1087 if (!AA->isNoAlias(MemoryLocation::getForDest(M),
1088 MemoryLocation::getForSource(MDep)))
1089 UseMemMove = true;
1090
1091 // If all checks passed, then we can transform M.
1092 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
<< *MDep << '\n' << *M << '\n'; } } while
(false)
1093 << *MDep << '\n' << *M << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
<< *MDep << '\n' << *M << '\n'; } } while
(false)
;
1094
1095 // TODO: Is this worth it if we're creating a less aligned memcpy? For
1096 // example we could be moving from movaps -> movq on x86.
1097 IRBuilder<> Builder(M);
1098 Instruction *NewM;
1099 if (UseMemMove)
1100 NewM = Builder.CreateMemMove(M->getRawDest(), M->getDestAlign(),
1101 MDep->getRawSource(), MDep->getSourceAlign(),
1102 M->getLength(), M->isVolatile());
1103 else
1104 NewM = Builder.CreateMemCpy(M->getRawDest(), M->getDestAlign(),
1105 MDep->getRawSource(), MDep->getSourceAlign(),
1106 M->getLength(), M->isVolatile());
1107
1108 if (MSSAU) {
1109 assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M)))((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(M))) ? static_cast<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M))"
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1109, __PRETTY_FUNCTION__))
;
1110 auto *LastDef = cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
1111 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
1112 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1113 }
1114
1115 // Remove the instruction we're replacing.
1116 eraseInstruction(M);
1117 ++NumMemCpyInstr;
1118 return true;
1119}
1120
1121/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1122/// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that
1123/// weren't copied over by \p MemCpy.
1124///
1125/// In other words, transform:
1126/// \code
1127/// memset(dst, c, dst_size);
1128/// memcpy(dst, src, src_size);
1129/// \endcode
1130/// into:
1131/// \code
1132/// memcpy(dst, src, src_size);
1133/// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1134/// \endcode
1135bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1136 MemSetInst *MemSet) {
1137 // We can only transform memset/memcpy with the same destination.
1138 if (!AA->isMustAlias(MemSet->getDest(), MemCpy->getDest()))
1139 return false;
1140
1141 // Check that src and dst of the memcpy aren't the same. While memcpy
1142 // operands cannot partially overlap, exact equality is allowed.
1143 if (!AA->isNoAlias(MemoryLocation(MemCpy->getSource(),
1144 LocationSize::precise(1)),
1145 MemoryLocation(MemCpy->getDest(),
1146 LocationSize::precise(1))))
1147 return false;
1148
1149 if (EnableMemorySSA) {
1150 // We know that dst up to src_size is not written. We now need to make sure
1151 // that dst up to dst_size is not accessed. (If we did not move the memset,
1152 // checking for reads would be sufficient.)
1153 if (accessedBetween(*AA, MemoryLocation::getForDest(MemSet),
1154 MSSA->getMemoryAccess(MemSet),
1155 MSSA->getMemoryAccess(MemCpy))) {
1156 return false;
1157 }
1158 } else {
1159 // We have already checked that dst up to src_size is not accessed. We
1160 // need to make sure that there are no accesses up to dst_size either.
1161 MemDepResult DstDepInfo = MD->getPointerDependencyFrom(
1162 MemoryLocation::getForDest(MemSet), false, MemCpy->getIterator(),
1163 MemCpy->getParent());
1164 if (DstDepInfo.getInst() != MemSet)
1165 return false;
1166 }
1167
1168 // Use the same i8* dest as the memcpy, killing the memset dest if different.
1169 Value *Dest = MemCpy->getRawDest();
1170 Value *DestSize = MemSet->getLength();
1171 Value *SrcSize = MemCpy->getLength();
1172
1173 if (mayBeVisibleThroughUnwinding(Dest, MemSet, MemCpy))
1174 return false;
1175
1176 // If the sizes are the same, simply drop the memset instead of generating
1177 // a replacement with zero size.
1178 if (DestSize == SrcSize) {
1179 eraseInstruction(MemSet);
1180 return true;
1181 }
1182
1183 // By default, create an unaligned memset.
1184 unsigned Align = 1;
1185 // If Dest is aligned, and SrcSize is constant, use the minimum alignment
1186 // of the sum.
1187 const unsigned DestAlign =
1188 std::max(MemSet->getDestAlignment(), MemCpy->getDestAlignment());
1189 if (DestAlign > 1)
1190 if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
1191 Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign);
1192
1193 IRBuilder<> Builder(MemCpy);
1194
1195 // If the sizes have different types, zext the smaller one.
1196 if (DestSize->getType() != SrcSize->getType()) {
1197 if (DestSize->getType()->getIntegerBitWidth() >
1198 SrcSize->getType()->getIntegerBitWidth())
1199 SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());
1200 else
1201 DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
1202 }
1203
1204 Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
1205 Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
1206 Value *MemsetLen = Builder.CreateSelect(
1207 Ule, ConstantInt::getNullValue(DestSize->getType()), SizeDiff);
1208 Instruction *NewMemSet = Builder.CreateMemSet(
1209 Builder.CreateGEP(Dest->getType()->getPointerElementType(), Dest,
1210 SrcSize),
1211 MemSet->getOperand(1), MemsetLen, MaybeAlign(Align));
1212
1213 if (MSSAU) {
1214 assert(isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) &&((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(MemCpy)) && "MemCpy must be a MemoryDef") ? static_cast
<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1215, __PRETTY_FUNCTION__))
1215 "MemCpy must be a MemoryDef")((isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess
(MemCpy)) && "MemCpy must be a MemoryDef") ? static_cast
<void> (0) : __assert_fail ("isa<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy)) && \"MemCpy must be a MemoryDef\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp"
, 1215, __PRETTY_FUNCTION__))
;
1216 // The new memset is inserted after the memcpy, but it is known that its
1217 // defining access is the memset about to be removed which immediately
1218 // precedes the memcpy.
1219 auto *LastDef =
1220 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
1221 auto *NewAccess = MSSAU->createMemoryAccessBefore(
1222 NewMemSet, LastDef->getDefiningAccess(), LastDef);
1223 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1224 }
1225
1226 eraseInstruction(MemSet);
1227 return true;
1228}
1229
1230/// Determine whether the instruction has undefined content for the given Size,
1231/// either because it was freshly alloca'd or started its lifetime.
1232static bool hasUndefContents(Instruction *I, ConstantInt *Size) {
1233 if (isa<AllocaInst>(I))
1234 return true;
1235
1236 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
1237 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1238 if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0)))
1239 if (LTSize->getZExtValue() >= Size->getZExtValue())
1240 return true;
1241
1242 return false;
1243}
1244
1245static bool hasUndefContentsMSSA(MemorySSA *MSSA, AliasAnalysis *AA, Value *V,
1246 MemoryDef *Def, ConstantInt *Size) {
1247 if (MSSA->isLiveOnEntryDef(Def))
11
Calling 'MemorySSA::isLiveOnEntryDef'
14
Returning from 'MemorySSA::isLiveOnEntryDef'
15
Taking false branch
1248 return isa<AllocaInst>(getUnderlyingObject(V));
1249
1250 if (IntrinsicInst *II
16.1
'II' is non-null
16.1
'II' is non-null
16.1
'II' is non-null
=
17
Taking true branch
1251 dyn_cast_or_null<IntrinsicInst>(Def->getMemoryInst())) {
16
Assuming the object is a 'IntrinsicInst'
1252 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
18
Assuming the condition is true
19
Taking true branch
1253 ConstantInt *LTSize = cast<ConstantInt>(II->getArgOperand(0));
1254 if (AA->isMustAlias(V, II->getArgOperand(1)) &&
20
Calling 'AAResults::isMustAlias'
23
Returning from 'AAResults::isMustAlias'
1255 LTSize->getZExtValue() >= Size->getZExtValue())
1256 return true;
1257
1258 // If the lifetime.start covers a whole alloca (as it almost always does)
1259 // and we're querying a pointer based on that alloca, then we know the
1260 // memory is definitely undef, regardless of how exactly we alias. The
1261 // size also doesn't matter, as an out-of-bounds access would be UB.
1262 AllocaInst *Alloca = dyn_cast<AllocaInst>(getUnderlyingObject(V));
24
Assuming the object is not a 'AllocaInst'
25
'Alloca' initialized to a null pointer value
1263 if (getUnderlyingObject(II->getArgOperand(1)) == Alloca) {
26
Assuming the condition is true
27
Taking true branch
1264 DataLayout DL = Alloca->getModule()->getDataLayout();
28
Called C++ object pointer is null
1265 if (Optional<TypeSize> AllocaSize = Alloca->getAllocationSizeInBits(DL))
1266 if (*AllocaSize == LTSize->getValue() * 8)
1267 return true;
1268 }
1269 }
1270 }
1271
1272 return false;
1273}
1274
1275/// Transform memcpy to memset when its source was just memset.
1276/// In other words, turn:
1277/// \code
1278/// memset(dst1, c, dst1_size);
1279/// memcpy(dst2, dst1, dst2_size);
1280/// \endcode
1281/// into:
1282/// \code
1283/// memset(dst1, c, dst1_size);
1284/// memset(dst2, c, dst2_size);
1285/// \endcode
1286/// When dst2_size <= dst1_size.
1287///
1288/// The \p MemCpy must have a Constant length.
1289bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1290 MemSetInst *MemSet) {
1291 // Make sure that memcpy(..., memset(...), ...), that is we are memsetting and
1292 // memcpying from the same address. Otherwise it is hard to reason about.
1293 if (!AA->isMustAlias(MemSet->getRawDest(), MemCpy->getRawSource()))
1
Taking false branch
1294 return false;
1295
1296 // A known memset size is required.
1297 ConstantInt *MemSetSize = dyn_cast<ConstantInt>(MemSet->getLength());
1298 if (!MemSetSize)
2
Assuming 'MemSetSize' is non-null
3
Taking false branch
1299 return false;
1300
1301 // Make sure the memcpy doesn't read any more than what the memset wrote.
1302 // Don't worry about sizes larger than i64.
1303 ConstantInt *CopySize = cast<ConstantInt>(MemCpy->getLength());
1304 if (CopySize->getZExtValue() > MemSetSize->getZExtValue()) {
4
Assuming the condition is true
5
Taking true branch
1305 // If the memcpy is larger than the memset, but the memory was undef prior
1306 // to the memset, we can just ignore the tail. Technically we're only
1307 // interested in the bytes from MemSetSize..CopySize here, but as we can't
1308 // easily represent this location, we use the full 0..CopySize range.
1309 MemoryLocation MemCpyLoc = MemoryLocation::getForSource(MemCpy);
1310 bool CanReduceSize = false;
1311 if (EnableMemorySSA) {
6
Assuming the condition is true
7
Taking true branch
1312 MemoryUseOrDef *MemSetAccess = MSSA->getMemoryAccess(MemSet);
1313 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
1314 MemSetAccess->getDefiningAccess(), MemCpyLoc);
1315 if (auto *MD
8.1
'MD' is non-null
8.1
'MD' is non-null
8.1
'MD' is non-null
= dyn_cast<MemoryDef>(Clobber))
8
Assuming 'Clobber' is a 'MemoryDef'
9
Taking true branch
1316 if (hasUndefContentsMSSA(MSSA, AA, MemCpy->getSource(), MD, CopySize))
10
Calling 'hasUndefContentsMSSA'
1317 CanReduceSize = true;
1318 } else {
1319 MemDepResult DepInfo = MD->getPointerDependencyFrom(
1320 MemCpyLoc, true, MemSet->getIterator(), MemSet->getParent());
1321 if (DepInfo.isDef() && hasUndefContents(DepInfo.getInst(), CopySize))
1322 CanReduceSize = true;
1323 }
1324
1325 if (!CanReduceSize)
1326 return false;
1327 CopySize = MemSetSize;
1328 }
1329
1330 IRBuilder<> Builder(MemCpy);
1331 Instruction *NewM =
1332 Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
1333 CopySize, MaybeAlign(MemCpy->getDestAlignment()));
1334 if (MSSAU) {
1335 auto *LastDef =
1336 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(MemCpy));
1337 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
1338 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1339 }
1340
1341 return true;
1342}
1343
1344/// Perform simplification of memcpy's. If we have memcpy A
1345/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1346/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1347/// circumstances). This allows later passes to remove the first memcpy
1348/// altogether.
1349bool MemCpyOptPass::processMemCpy(MemCpyInst *M, BasicBlock::iterator &BBI) {
1350 // We can only optimize non-volatile memcpy's.
1351 if (M->isVolatile()) return false;
1352
1353 // If the source and destination of the memcpy are the same, then zap it.
1354 if (M->getSource() == M->getDest()) {
1355 ++BBI;
1356 eraseInstruction(M);
1357 return true;
1358 }
1359
1360 // If copying from a constant, try to turn the memcpy into a memset.
1361 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
1362 if (GV->isConstant() && GV->hasDefinitiveInitializer())
1363 if (Value *ByteVal = isBytewiseValue(GV->getInitializer(),
1364 M->getModule()->getDataLayout())) {
1365 IRBuilder<> Builder(M);
1366 Instruction *NewM =
1367 Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
1368 MaybeAlign(M->getDestAlignment()), false);
1369 if (MSSAU) {
1370 auto *LastDef =
1371 cast<MemoryDef>(MSSAU->getMemorySSA()->getMemoryAccess(M));
1372 auto *NewAccess =
1373 MSSAU->createMemoryAccessAfter(NewM, LastDef, LastDef);
1374 MSSAU->insertDef(cast<MemoryDef>(NewAccess), /*RenameUses=*/true);
1375 }
1376
1377 eraseInstruction(M);
1378 ++NumCpyToSet;
1379 return true;
1380 }
1381
1382 if (EnableMemorySSA) {
1383 MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);
1384 MemoryAccess *AnyClobber = MSSA->getWalker()->getClobberingMemoryAccess(MA);
1385 MemoryLocation DestLoc = MemoryLocation::getForDest(M);
1386 const MemoryAccess *DestClobber =
1387 MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc);
1388
1389 // Try to turn a partially redundant memset + memcpy into
1390 // memcpy + smaller memset. We don't need the memcpy size for this.
1391 // The memcpy most post-dom the memset, so limit this to the same basic
1392 // block. A non-local generalization is likely not worthwhile.
1393 if (auto *MD = dyn_cast<MemoryDef>(DestClobber))
1394 if (auto *MDep = dyn_cast_or_null<MemSetInst>(MD->getMemoryInst()))
1395 if (DestClobber->getBlock() == M->getParent())
1396 if (processMemSetMemCpyDependence(M, MDep))
1397 return true;
1398
1399 // The optimizations after this point require the memcpy size.
1400 ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
1401 if (!CopySize) return false;
1402
1403 MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(
1404 AnyClobber, MemoryLocation::getForSource(M));
1405
1406 // There are four possible optimizations we can do for memcpy:
1407 // a) memcpy-memcpy xform which exposes redundance for DSE.
1408 // b) call-memcpy xform for return slot optimization.
1409 // c) memcpy from freshly alloca'd space or space that has just started
1410 // its lifetime copies undefined data, and we can therefore eliminate
1411 // the memcpy in favor of the data that was already at the destination.
1412 // d) memcpy from a just-memset'd source can be turned into memset.
1413 if (auto *MD = dyn_cast<MemoryDef>(SrcClobber)) {
1414 if (Instruction *MI = MD->getMemoryInst()) {
1415 if (auto *C = dyn_cast<CallInst>(MI)) {
1416 // The memcpy must post-dom the call. Limit to the same block for now.
1417 // Additionally, we need to ensure that there are no accesses to dest
1418 // between the call and the memcpy. Accesses to src will be checked
1419 // by performCallSlotOptzn().
1420 // TODO: Support non-local call-slot optimization?
1421 if (C->getParent() == M->getParent() &&
1422 !accessedBetween(*AA, DestLoc, MD, MA)) {
1423 // FIXME: Can we pass in either of dest/src alignment here instead
1424 // of conservatively taking the minimum?
1425 Align Alignment = std::min(M->getDestAlign().valueOrOne(),
1426 M->getSourceAlign().valueOrOne());
1427 if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
1428 CopySize->getZExtValue(), Alignment, C)) {
1429 LLVM_DEBUG(dbgs() << "Performed call slot optimization:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
<< " call: " << *C << "\n" << " memcpy: "
<< *M << "\n"; } } while (false)
1430 << " call: " << *C << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
<< " call: " << *C << "\n" << " memcpy: "
<< *M << "\n"; } } while (false)
1431 << " memcpy: " << *M << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Performed call slot optimization:\n"
<< " call: " << *C << "\n" << " memcpy: "
<< *M << "\n"; } } while (false)
;
1432 eraseInstruction(M);
1433 ++NumMemCpyInstr;
1434 return true;
1435 }
1436 }
1437 }
1438 if (auto *MDep = dyn_cast<MemCpyInst>(MI))
1439 return processMemCpyMemCpyDependence(M, MDep);
1440 if (auto *MDep = dyn_cast<MemSetInst>(MI)) {
1441 if (performMemCpyToMemSetOptzn(M, MDep)) {
1442 LLVM_DEBUG(dbgs() << "Converted memcpy to memset\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Converted memcpy to memset\n"
; } } while (false)
;
1443 eraseInstruction(M);
1444 ++NumCpyToSet;
1445 return true;
1446 }
1447 }
1448 }
1449
1450 if (hasUndefContentsMSSA(MSSA, AA, M->getSource(), MD, CopySize)) {
1451 LLVM_DEBUG(dbgs() << "Removed memcpy from undef\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "Removed memcpy from undef\n"
; } } while (false)
;
1452 eraseInstruction(M);
1453 ++NumMemCpyInstr;
1454 return true;
1455 }
1456 }
1457 } else {
1458 MemDepResult DepInfo = MD->getDependency(M);
1459
1460 // Try to turn a partially redundant memset + memcpy into
1461 // memcpy + smaller memset. We don't need the memcpy size for this.
1462 if (DepInfo.isClobber())
1463 if (MemSetInst *MDep = dyn_cast<MemSetInst>(DepInfo.getInst()))
1464 if (processMemSetMemCpyDependence(M, MDep))
1465 return true;
1466
1467 // The optimizations after this point require the memcpy size.
1468 ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
1469 if (!CopySize) return false;
1470
1471 // There are four possible optimizations we can do for memcpy:
1472 // a) memcpy-memcpy xform which exposes redundance for DSE.
1473 // b) call-memcpy xform for return slot optimization.
1474 // c) memcpy from freshly alloca'd space or space that has just started
1475 // its lifetime copies undefined data, and we can therefore eliminate
1476 // the memcpy in favor of the data that was already at the destination.
1477 // d) memcpy from a just-memset'd source can be turned into memset.
1478 if (DepInfo.isClobber()) {
1479 if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
1480 // FIXME: Can we pass in either of dest/src alignment here instead
1481 // of conservatively taking the minimum?
1482 Align Alignment = std::min(M->getDestAlign().valueOrOne(),
1483 M->getSourceAlign().valueOrOne());
1484 if (performCallSlotOptzn(M, M, M->getDest(), M->getSource(),
1485 CopySize->getZExtValue(), Alignment, C)) {
1486 eraseInstruction(M);
1487 ++NumMemCpyInstr;
1488 return true;
1489 }
1490 }
1491 }
1492
1493 MemoryLocation SrcLoc = MemoryLocation::getForSource(M);
1494 MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
1495 SrcLoc, true, M->getIterator(), M->getParent());
1496
1497 if (SrcDepInfo.isClobber()) {
1498 if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
1499 return processMemCpyMemCpyDependence(M, MDep);
1500 } else if (SrcDepInfo.isDef()) {
1501 if (hasUndefContents(SrcDepInfo.getInst(), CopySize)) {
1502 eraseInstruction(M);
1503 ++NumMemCpyInstr;
1504 return true;
1505 }
1506 }
1507
1508 if (SrcDepInfo.isClobber())
1509 if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
1510 if (performMemCpyToMemSetOptzn(M, MDep)) {
1511 eraseInstruction(M);
1512 ++NumCpyToSet;
1513 return true;
1514 }
1515 }
1516
1517 return false;
1518}
1519
1520/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1521/// not to alias.
1522bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
1523 if (!TLI->has(LibFunc_memmove))
1524 return false;
1525
1526 // See if the pointers alias.
1527 if (!AA->isNoAlias(MemoryLocation::getForDest(M),
1528 MemoryLocation::getForSource(M)))
1529 return false;
1530
1531 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *Mdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: "
<< *M << "\n"; } } while (false)
1532 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: "
<< *M << "\n"; } } while (false)
;
1533
1534 // If not, then we know we can transform this.
1535 Type *ArgTys[3] = { M->getRawDest()->getType(),
1536 M->getRawSource()->getType(),
1537 M->getLength()->getType() };
1538 M->setCalledFunction(Intrinsic::getDeclaration(M->getModule(),
1539 Intrinsic::memcpy, ArgTys));
1540
1541 // For MemorySSA nothing really changes (except that memcpy may imply stricter
1542 // aliasing guarantees).
1543
1544 // MemDep may have over conservative information about this instruction, just
1545 // conservatively flush it from the cache.
1546 if (MD)
1547 MD->removeInstruction(M);
1548
1549 ++NumMoveToCpy;
1550 return true;
1551}
1552
1553/// This is called on every byval argument in call sites.
1554bool MemCpyOptPass::processByValArgument(CallBase &CB, unsigned ArgNo) {
1555 const DataLayout &DL = CB.getCaller()->getParent()->getDataLayout();
1556 // Find out what feeds this byval argument.
1557 Value *ByValArg = CB.getArgOperand(ArgNo);
1558 Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
1559 uint64_t ByValSize = DL.getTypeAllocSize(ByValTy);
1560 MemoryLocation Loc(ByValArg, LocationSize::precise(ByValSize));
1561 MemCpyInst *MDep = nullptr;
1562 if (EnableMemorySSA) {
1563 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
1564 if (!CallAccess)
1565 return false;
1566 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
1567 CallAccess->getDefiningAccess(), Loc);
1568 if (auto *MD = dyn_cast<MemoryDef>(Clobber))
1569 MDep = dyn_cast_or_null<MemCpyInst>(MD->getMemoryInst());
1570 } else {
1571 MemDepResult DepInfo = MD->getPointerDependencyFrom(
1572 Loc, true, CB.getIterator(), CB.getParent());
1573 if (!DepInfo.isClobber())
1574 return false;
1575 MDep = dyn_cast<MemCpyInst>(DepInfo.getInst());
1576 }
1577
1578 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by
1579 // a memcpy, see if we can byval from the source of the memcpy instead of the
1580 // result.
1581 if (!MDep || MDep->isVolatile() ||
1582 ByValArg->stripPointerCasts() != MDep->getDest())
1583 return false;
1584
1585 // The length of the memcpy must be larger or equal to the size of the byval.
1586 ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength());
1587 if (!C1 || C1->getValue().getZExtValue() < ByValSize)
1588 return false;
1589
1590 // Get the alignment of the byval. If the call doesn't specify the alignment,
1591 // then it is some target specific value that we can't know.
1592 MaybeAlign ByValAlign = CB.getParamAlign(ArgNo);
1593 if (!ByValAlign) return false;
1594
1595 // If it is greater than the memcpy, then we check to see if we can force the
1596 // source of the memcpy to the alignment we need. If we fail, we bail out.
1597 MaybeAlign MemDepAlign = MDep->getSourceAlign();
1598 if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&
1599 getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL, &CB, AC,
1600 DT) < *ByValAlign)
1601 return false;
1602
1603 // The address space of the memcpy source must match the byval argument
1604 if (MDep->getSource()->getType()->getPointerAddressSpace() !=
1605 ByValArg->getType()->getPointerAddressSpace())
1606 return false;
1607
1608 // Verify that the copied-from memory doesn't change in between the memcpy and
1609 // the byval call.
1610 // memcpy(a <- b)
1611 // *b = 42;
1612 // foo(*a)
1613 // It would be invalid to transform the second memcpy into foo(*b).
1614 if (EnableMemorySSA) {
1615 if (writtenBetween(MSSA, MemoryLocation::getForSource(MDep),
1616 MSSA->getMemoryAccess(MDep), MSSA->getMemoryAccess(&CB)))
1617 return false;
1618 } else {
1619 // NOTE: This is conservative, it will stop on any read from the source loc,
1620 // not just the defining memcpy.
1621 MemDepResult SourceDep = MD->getPointerDependencyFrom(
1622 MemoryLocation::getForSource(MDep), false,
1623 CB.getIterator(), MDep->getParent());
1624 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
1625 return false;
1626 }
1627
1628 Value *TmpCast = MDep->getSource();
1629 if (MDep->getSource()->getType() != ByValArg->getType()) {
1630 BitCastInst *TmpBitCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
1631 "tmpcast", &CB);
1632 // Set the tmpcast's DebugLoc to MDep's
1633 TmpBitCast->setDebugLoc(MDep->getDebugLoc());
1634 TmpCast = TmpBitCast;
1635 }
1636
1637 LLVM_DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
<< " " << *MDep << "\n" << " " <<
CB << "\n"; } } while (false)
1638 << " " << *MDep << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
<< " " << *MDep << "\n" << " " <<
CB << "\n"; } } while (false)
1639 << " " << CB << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("memcpyopt")) { dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
<< " " << *MDep << "\n" << " " <<
CB << "\n"; } } while (false)
;
1640
1641 // Otherwise we're good! Update the byval argument.
1642 CB.setArgOperand(ArgNo, TmpCast);
1643 ++NumMemCpyInstr;
1644 return true;
1645}
1646
1647/// Executes one iteration of MemCpyOptPass.
1648bool MemCpyOptPass::iterateOnFunction(Function &F) {
1649 bool MadeChange = false;
1650
1651 // Walk all instruction in the function.
1652 for (BasicBlock &BB : F) {
1653 // Skip unreachable blocks. For example processStore assumes that an
1654 // instruction in a BB can't be dominated by a later instruction in the
1655 // same BB (which is a scenario that can happen for an unreachable BB that
1656 // has itself as a predecessor).
1657 if (!DT->isReachableFromEntry(&BB))
1658 continue;
1659
1660 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
1661 // Avoid invalidating the iterator.
1662 Instruction *I = &*BI++;
1663
1664 bool RepeatInstruction = false;
1665
1666 if (StoreInst *SI = dyn_cast<StoreInst>(I))
1667 MadeChange |= processStore(SI, BI);
1668 else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
1669 RepeatInstruction = processMemSet(M, BI);
1670 else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
1671 RepeatInstruction = processMemCpy(M, BI);
1672 else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
1673 RepeatInstruction = processMemMove(M);
1674 else if (auto *CB = dyn_cast<CallBase>(I)) {
1675 for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
1676 if (CB->isByValArgument(i))
1677 MadeChange |= processByValArgument(*CB, i);
1678 }
1679
1680 // Reprocess the instruction if desired.
1681 if (RepeatInstruction) {
1682 if (BI != BB.begin())
1683 --BI;
1684 MadeChange = true;
1685 }
1686 }
1687 }
1688
1689 return MadeChange;
1690}
1691
1692PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
1693 auto *MD = !EnableMemorySSA ? &AM.getResult<MemoryDependenceAnalysis>(F)
1694 : AM.getCachedResult<MemoryDependenceAnalysis>(F);
1695 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1696 auto *AA = &AM.getResult<AAManager>(F);
1697 auto *AC = &AM.getResult<AssumptionAnalysis>(F);
1698 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
1699 auto *MSSA = EnableMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F)
1700 : AM.getCachedResult<MemorySSAAnalysis>(F);
1701
1702 bool MadeChange =
1703 runImpl(F, MD, &TLI, AA, AC, DT, MSSA ? &MSSA->getMSSA() : nullptr);
1704 if (!MadeChange)
1705 return PreservedAnalyses::all();
1706
1707 PreservedAnalyses PA;
1708 PA.preserveSet<CFGAnalyses>();
1709 PA.preserve<GlobalsAA>();
1710 if (MD)
1711 PA.preserve<MemoryDependenceAnalysis>();
1712 if (MSSA)
1713 PA.preserve<MemorySSAAnalysis>();
1714 return PA;
1715}
1716
1717bool MemCpyOptPass::runImpl(Function &F, MemoryDependenceResults *MD_,
1718 TargetLibraryInfo *TLI_, AliasAnalysis *AA_,
1719 AssumptionCache *AC_, DominatorTree *DT_,
1720 MemorySSA *MSSA_) {
1721 bool MadeChange = false;
1722 MD = MD_;
1723 TLI = TLI_;
1724 AA = AA_;
1725 AC = AC_;
1726 DT = DT_;
1727 MSSA = MSSA_;
1728 MemorySSAUpdater MSSAU_(MSSA_);
1729 MSSAU = MSSA_ ? &MSSAU_ : nullptr;
1730 // If we don't have at least memset and memcpy, there is little point of doing
1731 // anything here. These are required by a freestanding implementation, so if
1732 // even they are disabled, there is no point in trying hard.
1733 if (!TLI->has(LibFunc_memset) || !TLI->has(LibFunc_memcpy))
1734 return false;
1735
1736 while (true) {
1737 if (!iterateOnFunction(F))
1738 break;
1739 MadeChange = true;
1740 }
1741
1742 if (MSSA_ && VerifyMemorySSA)
1743 MSSA_->verifyMemorySSA();
1744
1745 MD = nullptr;
1746 return MadeChange;
1747}
1748
1749/// This is the main transformation entry point for a function.
1750bool MemCpyOptLegacyPass::runOnFunction(Function &F) {
1751 if (skipFunction(F))
1752 return false;
1753
1754 auto *MDWP = !EnableMemorySSA
1755 ? &getAnalysis<MemoryDependenceWrapperPass>()
1756 : getAnalysisIfAvailable<MemoryDependenceWrapperPass>();
1757 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1758 auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
1759 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1760 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1761 auto *MSSAWP = EnableMemorySSA
1762 ? &getAnalysis<MemorySSAWrapperPass>()
1763 : getAnalysisIfAvailable<MemorySSAWrapperPass>();
1764
1765 return Impl.runImpl(F, MDWP ? & MDWP->getMemDep() : nullptr, TLI, AA, AC, DT,
1766 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
1767}

/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();
12
Assuming the condition is false
13
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/Analysis/AliasAnalysis.h

1//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- 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 generic AliasAnalysis interface, which is used as the
10// common interface used by all clients of alias analysis information, and
11// implemented by all alias analysis implementations. Mod/Ref information is
12// also captured by this interface.
13//
14// Implementations of this interface must implement the various virtual methods,
15// which automatically provides functionality for the entire suite of client
16// APIs.
17//
18// This API identifies memory regions with the MemoryLocation class. The pointer
19// component specifies the base memory address of the region. The Size specifies
20// the maximum size (in address units) of the memory region, or
21// MemoryLocation::UnknownSize if the size is not known. The TBAA tag
22// identifies the "type" of the memory reference; see the
23// TypeBasedAliasAnalysis class for details.
24//
25// Some non-obvious details include:
26// - Pointers that point to two completely different objects in memory never
27// alias, regardless of the value of the Size component.
28// - NoAlias doesn't imply inequal pointers. The most obvious example of this
29// is two pointers to constant memory. Even if they are equal, constant
30// memory is never stored to, so there will never be any dependencies.
31// In this and other situations, the pointers may be both NoAlias and
32// MustAlias at the same time. The current API can only return one result,
33// though this is rarely a problem in practice.
34//
35//===----------------------------------------------------------------------===//
36
37#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H
38#define LLVM_ANALYSIS_ALIASANALYSIS_H
39
40#include "llvm/ADT/DenseMap.h"
41#include "llvm/ADT/None.h"
42#include "llvm/ADT/Optional.h"
43#include "llvm/ADT/SmallVector.h"
44#include "llvm/Analysis/MemoryLocation.h"
45#include "llvm/IR/PassManager.h"
46#include "llvm/Pass.h"
47#include <cstdint>
48#include <functional>
49#include <memory>
50#include <vector>
51
52namespace llvm {
53
54class AnalysisUsage;
55class AtomicCmpXchgInst;
56class BasicAAResult;
57class BasicBlock;
58class CatchPadInst;
59class CatchReturnInst;
60class DominatorTree;
61class FenceInst;
62class Function;
63class InvokeInst;
64class PreservedAnalyses;
65class TargetLibraryInfo;
66class Value;
67
68/// The possible results of an alias query.
69///
70/// These results are always computed between two MemoryLocation objects as
71/// a query to some alias analysis.
72///
73/// Note that these are unscoped enumerations because we would like to support
74/// implicitly testing a result for the existence of any possible aliasing with
75/// a conversion to bool, but an "enum class" doesn't support this. The
76/// canonical names from the literature are suffixed and unique anyways, and so
77/// they serve as global constants in LLVM for these results.
78///
79/// See docs/AliasAnalysis.html for more information on the specific meanings
80/// of these values.
81enum AliasResult : uint8_t {
82 /// The two locations do not alias at all.
83 ///
84 /// This value is arranged to convert to false, while all other values
85 /// convert to true. This allows a boolean context to convert the result to
86 /// a binary flag indicating whether there is the possibility of aliasing.
87 NoAlias = 0,
88 /// The two locations may or may not alias. This is the least precise result.
89 MayAlias,
90 /// The two locations alias, but only due to a partial overlap.
91 PartialAlias,
92 /// The two locations precisely alias each other.
93 MustAlias,
94};
95
96/// << operator for AliasResult.
97raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);
98
99/// Flags indicating whether a memory access modifies or references memory.
100///
101/// This is no access at all, a modification, a reference, or both
102/// a modification and a reference. These are specifically structured such that
103/// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must'
104/// work with any of the possible values.
105enum class ModRefInfo : uint8_t {
106 /// Must is provided for completeness, but no routines will return only
107 /// Must today. See definition of Must below.
108 Must = 0,
109 /// The access may reference the value stored in memory,
110 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
111 MustRef = 1,
112 /// The access may modify the value stored in memory,
113 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
114 MustMod = 2,
115 /// The access may reference, modify or both the value stored in memory,
116 /// a mustAlias relation was found, and no mayAlias or partialAlias found.
117 MustModRef = MustRef | MustMod,
118 /// The access neither references nor modifies the value stored in memory.
119 NoModRef = 4,
120 /// The access may reference the value stored in memory.
121 Ref = NoModRef | MustRef,
122 /// The access may modify the value stored in memory.
123 Mod = NoModRef | MustMod,
124 /// The access may reference and may modify the value stored in memory.
125 ModRef = Ref | Mod,
126
127 /// About Must:
128 /// Must is set in a best effort manner.
129 /// We usually do not try our best to infer Must, instead it is merely
130 /// another piece of "free" information that is presented when available.
131 /// Must set means there was certainly a MustAlias found. For calls,
132 /// where multiple arguments are checked (argmemonly), this translates to
133 /// only MustAlias or NoAlias was found.
134 /// Must is not set for RAR accesses, even if the two locations must
135 /// alias. The reason is that two read accesses translate to an early return
136 /// of NoModRef. An additional alias check to set Must may be
137 /// expensive. Other cases may also not set Must(e.g. callCapturesBefore).
138 /// We refer to Must being *set* when the most significant bit is *cleared*.
139 /// Conversely we *clear* Must information by *setting* the Must bit to 1.
140};
141
142LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isNoModRef(const ModRefInfo MRI) {
143 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
144 static_cast<int>(ModRefInfo::Must);
145}
146LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModOrRefSet(const ModRefInfo MRI) {
147 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
148}
149LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModAndRefSet(const ModRefInfo MRI) {
150 return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) ==
151 static_cast<int>(ModRefInfo::MustModRef);
152}
153LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isModSet(const ModRefInfo MRI) {
154 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
155}
156LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isRefSet(const ModRefInfo MRI) {
157 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
158}
159LLVM_NODISCARD[[clang::warn_unused_result]] inline bool isMustSet(const ModRefInfo MRI) {
160 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
161}
162
163LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMod(const ModRefInfo MRI) {
164 return ModRefInfo(static_cast<int>(MRI) |
165 static_cast<int>(ModRefInfo::MustMod));
166}
167LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setRef(const ModRefInfo MRI) {
168 return ModRefInfo(static_cast<int>(MRI) |
169 static_cast<int>(ModRefInfo::MustRef));
170}
171LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setMust(const ModRefInfo MRI) {
172 return ModRefInfo(static_cast<int>(MRI) &
173 static_cast<int>(ModRefInfo::MustModRef));
174}
175LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
176 return ModRefInfo(static_cast<int>(MRI) |
177 static_cast<int>(ModRefInfo::MustModRef));
178}
179LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMod(const ModRefInfo MRI) {
180 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
181}
182LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearRef(const ModRefInfo MRI) {
183 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
184}
185LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo clearMust(const ModRefInfo MRI) {
186 return ModRefInfo(static_cast<int>(MRI) |
187 static_cast<int>(ModRefInfo::NoModRef));
188}
189LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo unionModRef(const ModRefInfo MRI1,
190 const ModRefInfo MRI2) {
191 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
192}
193LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo intersectModRef(const ModRefInfo MRI1,
194 const ModRefInfo MRI2) {
195 return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2));
196}
197
198/// The locations at which a function might access memory.
199///
200/// These are primarily used in conjunction with the \c AccessKind bits to
201/// describe both the nature of access and the locations of access for a
202/// function call.
203enum FunctionModRefLocation {
204 /// Base case is no access to memory.
205 FMRL_Nowhere = 0,
206 /// Access to memory via argument pointers.
207 FMRL_ArgumentPointees = 8,
208 /// Memory that is inaccessible via LLVM IR.
209 FMRL_InaccessibleMem = 16,
210 /// Access to any memory.
211 FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees
212};
213
214/// Summary of how a function affects memory in the program.
215///
216/// Loads from constant globals are not considered memory accesses for this
217/// interface. Also, functions may freely modify stack space local to their
218/// invocation without having to report it through these interfaces.
219enum FunctionModRefBehavior {
220 /// This function does not perform any non-local loads or stores to memory.
221 ///
222 /// This property corresponds to the GCC 'const' attribute.
223 /// This property corresponds to the LLVM IR 'readnone' attribute.
224 /// This property corresponds to the IntrNoMem LLVM intrinsic flag.
225 FMRB_DoesNotAccessMemory =
226 FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef),
227
228 /// The only memory references in this function (if it has any) are
229 /// non-volatile loads from objects pointed to by its pointer-typed
230 /// arguments, with arbitrary offsets.
231 ///
232 /// This property corresponds to the combination of the IntrReadMem
233 /// and IntrArgMemOnly LLVM intrinsic flags.
234 FMRB_OnlyReadsArgumentPointees =
235 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref),
236
237 /// The only memory references in this function (if it has any) are
238 /// non-volatile stores from objects pointed to by its pointer-typed
239 /// arguments, with arbitrary offsets.
240 ///
241 /// This property corresponds to the combination of the IntrWriteMem
242 /// and IntrArgMemOnly LLVM intrinsic flags.
243 FMRB_OnlyWritesArgumentPointees =
244 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod),
245
246 /// The only memory references in this function (if it has any) are
247 /// non-volatile loads and stores from objects pointed to by its
248 /// pointer-typed arguments, with arbitrary offsets.
249 ///
250 /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag.
251 FMRB_OnlyAccessesArgumentPointees =
252 FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef),
253
254 /// The only memory references in this function (if it has any) are
255 /// reads of memory that is otherwise inaccessible via LLVM IR.
256 ///
257 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
258 FMRB_OnlyReadsInaccessibleMem =
259 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref),
260
261 /// The only memory references in this function (if it has any) are
262 /// writes to memory that is otherwise inaccessible via LLVM IR.
263 ///
264 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
265 FMRB_OnlyWritesInaccessibleMem =
266 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod),
267
268 /// The only memory references in this function (if it has any) are
269 /// references of memory that is otherwise inaccessible via LLVM IR.
270 ///
271 /// This property corresponds to the LLVM IR inaccessiblememonly attribute.
272 FMRB_OnlyAccessesInaccessibleMem =
273 FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef),
274
275 /// The function may perform non-volatile loads from objects pointed
276 /// to by its pointer-typed arguments, with arbitrary offsets, and
277 /// it may also perform loads of memory that is otherwise
278 /// inaccessible via LLVM IR.
279 ///
280 /// This property corresponds to the LLVM IR
281 /// inaccessiblemem_or_argmemonly attribute.
282 FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem |
283 FMRL_ArgumentPointees |
284 static_cast<int>(ModRefInfo::Ref),
285
286 /// The function may perform non-volatile stores to objects pointed
287 /// to by its pointer-typed arguments, with arbitrary offsets, and
288 /// it may also perform stores of memory that is otherwise
289 /// inaccessible via LLVM IR.
290 ///
291 /// This property corresponds to the LLVM IR
292 /// inaccessiblemem_or_argmemonly attribute.
293 FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem |
294 FMRL_ArgumentPointees |
295 static_cast<int>(ModRefInfo::Mod),
296
297 /// The function may perform non-volatile loads and stores of objects
298 /// pointed to by its pointer-typed arguments, with arbitrary offsets, and
299 /// it may also perform loads and stores of memory that is otherwise
300 /// inaccessible via LLVM IR.
301 ///
302 /// This property corresponds to the LLVM IR
303 /// inaccessiblemem_or_argmemonly attribute.
304 FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem |
305 FMRL_ArgumentPointees |
306 static_cast<int>(ModRefInfo::ModRef),
307
308 /// This function does not perform any non-local stores or volatile loads,
309 /// but may read from any memory location.
310 ///
311 /// This property corresponds to the GCC 'pure' attribute.
312 /// This property corresponds to the LLVM IR 'readonly' attribute.
313 /// This property corresponds to the IntrReadMem LLVM intrinsic flag.
314 FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref),
315
316 // This function does not read from memory anywhere, but may write to any
317 // memory location.
318 //
319 // This property corresponds to the LLVM IR 'writeonly' attribute.
320 // This property corresponds to the IntrWriteMem LLVM intrinsic flag.
321 FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod),
322
323 /// This indicates that the function could not be classified into one of the
324 /// behaviors above.
325 FMRB_UnknownModRefBehavior =
326 FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef)
327};
328
329// Wrapper method strips bits significant only in FunctionModRefBehavior,
330// to obtain a valid ModRefInfo. The benefit of using the wrapper is that if
331// ModRefInfo enum changes, the wrapper can be updated to & with the new enum
332// entry with all bits set to 1.
333LLVM_NODISCARD[[clang::warn_unused_result]] inline ModRefInfo
334createModRefInfo(const FunctionModRefBehavior FMRB) {
335 return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef));
336}
337
338/// Reduced version of MemoryLocation that only stores a pointer and size.
339/// Used for caching AATags independent BasicAA results.
340struct AACacheLoc {
341 const Value *Ptr;
342 LocationSize Size;
343};
344
345template <> struct DenseMapInfo<AACacheLoc> {
346 static inline AACacheLoc getEmptyKey() {
347 return {DenseMapInfo<const Value *>::getEmptyKey(),
348 DenseMapInfo<LocationSize>::getEmptyKey()};
349 }
350 static inline AACacheLoc getTombstoneKey() {
351 return {DenseMapInfo<const Value *>::getTombstoneKey(),
352 DenseMapInfo<LocationSize>::getTombstoneKey()};
353 }
354 static unsigned getHashValue(const AACacheLoc &Val) {
355 return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
356 DenseMapInfo<LocationSize>::getHashValue(Val.Size);
357 }
358 static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) {
359 return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size;
360 }
361};
362
363/// This class stores info we want to provide to or retain within an alias
364/// query. By default, the root query is stateless and starts with a freshly
365/// constructed info object. Specific alias analyses can use this query info to
366/// store per-query state that is important for recursive or nested queries to
367/// avoid recomputing. To enable preserving this state across multiple queries
368/// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
369/// The information stored in an `AAQueryInfo` is currently limitted to the
370/// caches used by BasicAA, but can further be extended to fit other AA needs.
371class AAQueryInfo {
372 /// Storage for estimated relative offsets between two partially aliased
373 /// values. Used to optimize out redundant parts of loads/stores (in GVN/DSE).
374 /// These users cannot process quite complicated addresses (e.g. GEPs with
375 /// non-constant offsets). Used by BatchAAResults only.
376 bool CacheOffsets = false;
377 SmallDenseMap<std::pair<std::pair<const Value *, const Value *>,
378 std::pair<uint64_t, uint64_t>>,
379 int64_t, 4>
380 ClobberOffsets;
381
382public:
383 using LocPair = std::pair<AACacheLoc, AACacheLoc>;
384 struct CacheEntry {
385 AliasResult Result;
386 /// Number of times a NoAlias assumption has been used.
387 /// 0 for assumptions that have not been used, -1 for definitive results.
388 int NumAssumptionUses;
389 /// Whether this is a definitive (non-assumption) result.
390 bool isDefinitive() const { return NumAssumptionUses < 0; }
391 };
392 using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>;
393 AliasCacheT AliasCache;
394
395 using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
396 IsCapturedCacheT IsCapturedCache;
397
398 /// Query depth used to distinguish recursive queries.
399 unsigned Depth = 0;
400
401 /// How many active NoAlias assumption uses there are.
402 int NumAssumptionUses = 0;
403
404 /// Location pairs for which an assumption based result is currently stored.
405 /// Used to remove all potentially incorrect results from the cache if an
406 /// assumption is disproven.
407 SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;
408
409 AAQueryInfo(bool CacheOffsets = false)
410 : CacheOffsets(CacheOffsets), ClobberOffsets(), AliasCache(),
411 IsCapturedCache() {}
412
413 /// Create a new AAQueryInfo based on this one, but with the cache cleared.
414 /// This is used for recursive queries across phis, where cache results may
415 /// not be valid.
416 AAQueryInfo withEmptyCache() {
417 AAQueryInfo NewAAQI;
418 NewAAQI.Depth = Depth;
419 return NewAAQI;
420 }
421
422 Optional<int64_t> getClobberOffset(const Value *Ptr1, const Value *Ptr2,
423 uint64_t Size1, uint64_t Size2) const {
424 assert(CacheOffsets && "Clobber offset cached in batch mode only!")((CacheOffsets && "Clobber offset cached in batch mode only!"
) ? static_cast<void> (0) : __assert_fail ("CacheOffsets && \"Clobber offset cached in batch mode only!\""
, "/build/llvm-toolchain-snapshot-13~++20210405022414+5f57793c4fe4/llvm/include/llvm/Analysis/AliasAnalysis.h"
, 424, __PRETTY_FUNCTION__))
;
425 const bool Swapped = Ptr1 > Ptr2;
426 if (Swapped) {
427 std::swap(Ptr1, Ptr2);
428 std::swap(Size1, Size2);
429 }
430 const auto IOff = ClobberOffsets.find({{Ptr1, Ptr2}, {Size1, Size2}});
431 if (IOff != ClobberOffsets.end())
432 return Swapped ? -IOff->second : IOff->second;
433 return None;
434 }
435
436 void setClobberOffset(const Value *Ptr1, const Value *Ptr2, uint64_t Size1,
437 uint64_t Size2, int64_t Offset) {
438 // Cache offset for batch mode only.
439 if (!CacheOffsets)
440 return;
441 if (Ptr1 > Ptr2) {
442 std::swap(Ptr1, Ptr2);
443 std::swap(Size1, Size2);
444 Offset = -Offset;
445 }
446 ClobberOffsets[{{Ptr1, Ptr2}, {Size1, Size2}}] = Offset;
447 }
448};
449
450class BatchAAResults;
451
452class AAResults {
453public:
454 // Make these results default constructable and movable. We have to spell
455 // these out because MSVC won't synthesize them.
456 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
457 AAResults(AAResults &&Arg);
458 ~AAResults();
459
460 /// Register a specific AA result.
461 template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
462 // FIXME: We should use a much lighter weight system than the usual
463 // polymorphic pattern because we don't own AAResult. It should
464 // ideally involve two pointers and no separate allocation.
465 AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
466 }
467
468 /// Register a function analysis ID that the results aggregation depends on.
469 ///
470 /// This is used in the new pass manager to implement the invalidation logic
471 /// where we must invalidate the results aggregation if any of our component
472 /// analyses become invalid.
473 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); }
474
475 /// Handle invalidation events in the new pass manager.
476 ///
477 /// The aggregation is invalidated if any of the underlying analyses is
478 /// invalidated.
479 bool invalidate(Function &F, const PreservedAnalyses &PA,
480 FunctionAnalysisManager::Invalidator &Inv);
481
482 //===--------------------------------------------------------------------===//
483 /// \name Alias Queries
484 /// @{
485
486 /// The main low level interface to the alias analysis implementation.
487 /// Returns an AliasResult indicating whether the two pointers are aliased to
488 /// each other. This is the interface that must be implemented by specific
489 /// alias analysis implementations.
490 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
491
492 /// A convenience wrapper around the primary \c alias interface.
493 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
494 LocationSize V2Size) {
495 return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
496 }
497
498 /// A convenience wrapper around the primary \c alias interface.
499 AliasResult alias(const Value *V1, const Value *V2) {
500 return alias(MemoryLocation::getBeforeOrAfter(V1),
501 MemoryLocation::getBeforeOrAfter(V2));
502 }
503
504 /// A trivial helper function to check to see if the specified pointers are
505 /// no-alias.
506 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
507 return alias(LocA, LocB) == NoAlias;
508 }
509
510 /// A convenience wrapper around the \c isNoAlias helper interface.
511 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
512 LocationSize V2Size) {
513 return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size));
514 }
515
516 /// A convenience wrapper around the \c isNoAlias helper interface.
517 bool isNoAlias(const Value *V1, const Value *V2) {
518 return isNoAlias(MemoryLocation::getBeforeOrAfter(V1),
519 MemoryLocation::getBeforeOrAfter(V2));
520 }
521
522 /// A trivial helper function to check to see if the specified pointers are
523 /// must-alias.
524 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
525 return alias(LocA, LocB) == MustAlias;
526 }
527
528 /// A convenience wrapper around the \c isMustAlias helper interface.
529 bool isMustAlias(const Value *V1, const Value *V2) {
530 return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) ==
21
Assuming the condition is false
22
Returning zero, which participates in a condition later
531 MustAlias;
532 }
533
534 /// Checks whether the given location points to constant memory, or if
535 /// \p OrLocal is true whether it points to a local alloca.
536 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false);
537
538 /// A convenience wrapper around the primary \c pointsToConstantMemory
539 /// interface.
540 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
541 return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal);
542 }
543
544 /// @}
545 //===--------------------------------------------------------------------===//
546 /// \name Simple mod/ref information
547 /// @{
548
549 /// Get the ModRef info associated with a pointer argument of a call. The
550 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
551 /// that these bits do not necessarily account for the overall behavior of
552 /// the function, but rather only provide additional per-argument
553 /// information. This never sets ModRefInfo::Must.
554 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
555
556 /// Return the behavior of the given call site.
557 FunctionModRefBehavior getModRefBehavior(const CallBase *Call);
558
559 /// Return the behavior when calling the given function.
560 FunctionModRefBehavior getModRefBehavior(const Function *F);
561
562 /// Checks if the specified call is known to never read or write memory.
563 ///
564 /// Note that if the call only reads from known-constant memory, it is also
565 /// legal to return true. Also, calls that unwind the stack are legal for
566 /// this predicate.
567 ///
568 /// Many optimizations (such as CSE and LICM) can be performed on such calls
569 /// without worrying about aliasing properties, and many calls have this
570 /// property (e.g. calls to 'sin' and 'cos').
571 ///
572 /// This property corresponds to the GCC 'const' attribute.
573 bool doesNotAccessMemory(const CallBase *Call) {
574 return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory;
575 }
576
577 /// Checks if the specified function is known to never read or write memory.
578 ///
579 /// Note that if the function only reads from known-constant memory, it is
580 /// also legal to return true. Also, function that unwind the stack are legal
581 /// for this predicate.
582 ///
583 /// Many optimizations (such as CSE and LICM) can be performed on such calls
584 /// to such functions without worrying about aliasing properties, and many
585 /// functions have this property (e.g. 'sin' and 'cos').
586 ///
587 /// This property corresponds to the GCC 'const' attribute.
588 bool doesNotAccessMemory(const Function *F) {
589 return getModRefBehavior(F) == FMRB_DoesNotAccessMemory;
590 }
591
592 /// Checks if the specified call is known to only read from non-volatile
593 /// memory (or not access memory at all).
594 ///
595 /// Calls that unwind the stack are legal for this predicate.
596 ///
597 /// This property allows many common optimizations to be performed in the
598 /// absence of interfering store instructions, such as CSE of strlen calls.
599 ///
600 /// This property corresponds to the GCC 'pure' attribute.
601 bool onlyReadsMemory(const CallBase *Call) {
602 return onlyReadsMemory(getModRefBehavior(Call));
603 }
604
605 /// Checks if the specified function is known to only read from non-volatile
606 /// memory (or not access memory at all).
607 ///
608 /// Functions that unwind the stack are legal for this predicate.
609 ///
610 /// This property allows many common optimizations to be performed in the
611 /// absence of interfering store instructions, such as CSE of strlen calls.
612 ///
613 /// This property corresponds to the GCC 'pure' attribute.
614 bool onlyReadsMemory(const Function *F) {
615 return onlyReadsMemory(getModRefBehavior(F));
616 }
617
618 /// Checks if functions with the specified behavior are known to only read
619 /// from non-volatile memory (or not access memory at all).
620 static bool onlyReadsMemory(FunctionModRefBehavior MRB) {
621 return !isModSet(createModRefInfo(MRB));
622 }
623
624 /// Checks if functions with the specified behavior are known to only write
625 /// memory (or not access memory at all).
626 static bool doesNotReadMemory(FunctionModRefBehavior MRB) {
627 return !isRefSet(createModRefInfo(MRB));
628 }
629
630 /// Checks if functions with the specified behavior are known to read and
631 /// write at most from objects pointed to by their pointer-typed arguments
632 /// (with arbitrary offsets).
633 static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) {
634 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees);
635 }
636
637 /// Checks if functions with the specified behavior are known to potentially
638 /// read or write from objects pointed to be their pointer-typed arguments
639 /// (with arbitrary offsets).
640 static bool doesAccessArgPointees(FunctionModRefBehavior MRB) {
641 return isModOrRefSet(createModRefInfo(MRB)) &&
642 ((unsigned)MRB & FMRL_ArgumentPointees);
643 }
644
645 /// Checks if functions with the specified behavior are known to read and
646 /// write at most from memory that is inaccessible from LLVM IR.
647 static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) {
648 return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem);
649 }
650
651 /// Checks if functions with the specified behavior are known to potentially
652 /// read or write from memory that is inaccessible from LLVM IR.
653 static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) {
654 return isModOrRefSet(createModRefInfo(MRB)) &&
655 ((unsigned)MRB & FMRL_InaccessibleMem);
656 }
657
658 /// Checks if functions with the specified behavior are known to read and
659 /// write at most from memory that is inaccessible from LLVM IR or objects
660 /// pointed to by their pointer-typed arguments (with arbitrary offsets).
661 static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) {
662 return !((unsigned)MRB & FMRL_Anywhere &
663 ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees));
664 }
665
666 /// getModRefInfo (for call sites) - Return information about whether
667 /// a particular call site modifies or reads the specified memory location.
668 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc);
669
670 /// getModRefInfo (for call sites) - A convenience wrapper.
671 ModRefInfo getModRefInfo(const CallBase *Call, const Value *P,
672 LocationSize Size) {
673 return getModRefInfo(Call, MemoryLocation(P, Size));
674 }
675
676 /// getModRefInfo (for loads) - Return information about whether
677 /// a particular load modifies or reads the specified memory location.
678 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc);
679
680 /// getModRefInfo (for loads) - A convenience wrapper.
681 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P,
682 LocationSize Size) {
683 return getModRefInfo(L, MemoryLocation(P, Size));
684 }
685
686 /// getModRefInfo (for stores) - Return information about whether
687 /// a particular store modifies or reads the specified memory location.
688 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc);
689
690 /// getModRefInfo (for stores) - A convenience wrapper.
691 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P,
692 LocationSize Size) {
693 return getModRefInfo(S, MemoryLocation(P, Size));
694 }
695
696 /// getModRefInfo (for fences) - Return information about whether
697 /// a particular store modifies or reads the specified memory location.
698 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc);
699
700 /// getModRefInfo (for fences) - A convenience wrapper.
701 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P,
702 LocationSize Size) {
703 return getModRefInfo(S, MemoryLocation(P, Size));
704 }
705
706 /// getModRefInfo (for cmpxchges) - Return information about whether
707 /// a particular cmpxchg modifies or reads the specified memory location.
708 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
709 const MemoryLocation &Loc);
710
711 /// getModRefInfo (for cmpxchges) - A convenience wrapper.
712 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P,
713 LocationSize Size) {
714 return getModRefInfo(CX, MemoryLocation(P, Size));
715 }
716
717 /// getModRefInfo (for atomicrmws) - Return information about whether
718 /// a particular atomicrmw modifies or reads the specified memory location.
719 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc);
720
721 /// getModRefInfo (for atomicrmws) - A convenience wrapper.
722 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P,
723 LocationSize Size) {
724 return getModRefInfo(RMW, MemoryLocation(P, Size));
725 }
726
727 /// getModRefInfo (for va_args) - Return information about whether
728 /// a particular va_arg modifies or reads the specified memory location.
729 ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc);
730
731 /// getModRefInfo (for va_args) - A convenience wrapper.
732 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P,
733 LocationSize Size) {
734 return getModRefInfo(I, MemoryLocation(P, Size));
735 }
736
737 /// getModRefInfo (for catchpads) - Return information about whether
738 /// a particular catchpad modifies or reads the specified memory location.
739 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc);
740
741 /// getModRefInfo (for catchpads) - A convenience wrapper.
742 ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P,
743 LocationSize Size) {
744 return getModRefInfo(I, MemoryLocation(P, Size));
745 }
746
747 /// getModRefInfo (for catchrets) - Return information about whether
748 /// a particular catchret modifies or reads the specified memory location.
749 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc);
750
751 /// getModRefInfo (for catchrets) - A convenience wrapper.
752 ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P,
753 LocationSize Size) {
754 return getModRefInfo(I, MemoryLocation(P, Size));
755 }
756
757 /// Check whether or not an instruction may read or write the optionally
758 /// specified memory location.
759 ///
760 ///
761 /// An instruction that doesn't read or write memory may be trivially LICM'd
762 /// for example.
763 ///
764 /// For function calls, this delegates to the alias-analysis specific
765 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
766 /// helpers above.
767 ModRefInfo getModRefInfo(const Instruction *I,
768 const Optional<MemoryLocation> &OptLoc) {
769 AAQueryInfo AAQIP;
770 return getModRefInfo(I, OptLoc, AAQIP);
771 }
772
773 /// A convenience wrapper for constructing the memory location.
774 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
775 LocationSize Size) {
776 return getModRefInfo(I, MemoryLocation(P, Size));
777 }
778
779 /// Return information about whether a call and an instruction may refer to
780 /// the same memory locations.
781 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call);
782
783 /// Return information about whether two call sites may refer to the same set
784 /// of memory locations. See the AA documentation for details:
785 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
786 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2);
787
788 /// Return information about whether a particular call site modifies
789 /// or reads the specified memory location \p MemLoc before instruction \p I
790 /// in a BasicBlock.
791 /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being
792 /// set.
793 ModRefInfo callCapturesBefore(const Instruction *I,
794 const MemoryLocation &MemLoc, DominatorTree *DT);
795
796 /// A convenience wrapper to synthesize a memory location.
797 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
798 LocationSize Size, DominatorTree *DT) {
799 return callCapturesBefore(I, MemoryLocation(P, Size), DT);
800 }
801
802 /// @}
803 //===--------------------------------------------------------------------===//
804 /// \name Higher level methods for querying mod/ref information.
805 /// @{
806
807 /// Check if it is possible for execution of the specified basic block to
808 /// modify the location Loc.
809 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
810
811 /// A convenience wrapper synthesizing a memory location.
812 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
813 LocationSize Size) {
814 return canBasicBlockModify(BB, MemoryLocation(P, Size));
815 }
816
817 /// Check if it is possible for the execution of the specified instructions
818 /// to mod\ref (according to the mode) the location Loc.
819 ///
820 /// The instructions to consider are all of the instructions in the range of
821 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
822 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
823 const MemoryLocation &Loc,
824 const ModRefInfo Mode);
825
826 /// A convenience wrapper synthesizing a memory location.
827 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
828 const Value *Ptr, LocationSize Size,
829 const ModRefInfo Mode) {
830 return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode);
831 }
832
833private:
834 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
835 AAQueryInfo &AAQI);
836 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
837 bool OrLocal = false);
838 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2,
839 AAQueryInfo &AAQIP);
840 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
841 AAQueryInfo &AAQI);
842 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
843 AAQueryInfo &AAQI);
844 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
845 AAQueryInfo &AAQI);
846 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
847 AAQueryInfo &AAQI);
848 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
849 AAQueryInfo &AAQI);
850 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
851 AAQueryInfo &AAQI);
852 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
853 const MemoryLocation &Loc, AAQueryInfo &AAQI);
854 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
855 AAQueryInfo &AAQI);
856 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
857 AAQueryInfo &AAQI);
858 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
859 AAQueryInfo &AAQI);
860 ModRefInfo getModRefInfo(const Instruction *I,
861 const Optional<MemoryLocation> &OptLoc,
862 AAQueryInfo &AAQIP);
863
864 class Concept;
865
866 template <typename T> class Model;
867
868 template <typename T> friend class AAResultBase;
869
870 const TargetLibraryInfo &TLI;
871
872 std::vector<std::unique_ptr<Concept>> AAs;
873
874 std::vector<AnalysisKey *> AADeps;
875
876 friend class BatchAAResults;
877};
878
879/// This class is a wrapper over an AAResults, and it is intended to be used
880/// only when there are no IR changes inbetween queries. BatchAAResults is
881/// reusing the same `AAQueryInfo` to preserve the state across queries,
882/// esentially making AA work in "batch mode". The internal state cannot be
883/// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
884/// or create a new BatchAAResults.
885class BatchAAResults {
886 AAResults &AA;
887 AAQueryInfo AAQI;
888
889public:
890 BatchAAResults(AAResults &AAR, bool CacheOffsets = false)
891 : AA(AAR), AAQI(CacheOffsets) {}
892 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
893 return AA.alias(LocA, LocB, AAQI);
894 }
895 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
896 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
897 }
898 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
899 return AA.getModRefInfo(Call, Loc, AAQI);
900 }
901 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) {
902 return AA.getModRefInfo(Call1, Call2, AAQI);
903 }
904 ModRefInfo getModRefInfo(const Instruction *I,
905 const Optional<MemoryLocation> &OptLoc) {
906 return AA.getModRefInfo(I, OptLoc, AAQI);
907 }
908 ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) {
909 return AA.getModRefInfo(I, Call2, AAQI);
910 }
911 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
912 return AA.getArgModRefInfo(Call, ArgIdx);
913 }
914 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
915 return AA.getModRefBehavior(Call);
916 }
917 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
918 return alias(LocA, LocB) == MustAlias;
919 }
920 bool isMustAlias(const Value *V1, const Value *V2) {
921 return alias(MemoryLocation(V1, LocationSize::precise(1)),
922 MemoryLocation(V2, LocationSize::precise(1))) == MustAlias;
923 }
924 Optional<int64_t> getClobberOffset(const MemoryLocation &LocA,
925 const MemoryLocation &LocB) const;
926};
927
928/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
929/// pointer or reference.
930using AliasAnalysis = AAResults;
931
932/// A private abstract base class describing the concept of an individual alias
933/// analysis implementation.
934///
935/// This interface is implemented by any \c Model instantiation. It is also the
936/// interface which a type used to instantiate the model must provide.
937///
938/// All of these methods model methods by the same name in the \c
939/// AAResults class. Only differences and specifics to how the
940/// implementations are called are documented here.
941class AAResults::Concept {
942public:
943 virtual ~Concept() = 0;
944
945 /// An update API used internally by the AAResults to provide
946 /// a handle back to the top level aggregation.
947 virtual void setAAResults(AAResults *NewAAR) = 0;
948
949 //===--------------------------------------------------------------------===//
950 /// \name Alias Queries
951 /// @{
952
953 /// The main low level interface to the alias analysis implementation.
954 /// Returns an AliasResult indicating whether the two pointers are aliased to
955 /// each other. This is the interface that must be implemented by specific
956 /// alias analysis implementations.
957 virtual AliasResult alias(const MemoryLocation &LocA,
958 const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0;
959
960 /// Checks whether the given location points to constant memory, or if
961 /// \p OrLocal is true whether it points to a local alloca.
962 virtual bool pointsToConstantMemory(const MemoryLocation &Loc,
963 AAQueryInfo &AAQI, bool OrLocal) = 0;
964
965 /// @}
966 //===--------------------------------------------------------------------===//
967 /// \name Simple mod/ref information
968 /// @{
969
970 /// Get the ModRef info associated with a pointer argument of a callsite. The
971 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
972 /// that these bits do not necessarily account for the overall behavior of
973 /// the function, but rather only provide additional per-argument
974 /// information.
975 virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
976 unsigned ArgIdx) = 0;
977
978 /// Return the behavior of the given call site.
979 virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0;
980
981 /// Return the behavior when calling the given function.
982 virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0;
983
984 /// getModRefInfo (for call sites) - Return information about whether
985 /// a particular call site modifies or reads the specified memory location.
986 virtual ModRefInfo getModRefInfo(const CallBase *Call,
987 const MemoryLocation &Loc,
988 AAQueryInfo &AAQI) = 0;
989
990 /// Return information about whether two call sites may refer to the same set
991 /// of memory locations. See the AA documentation for details:
992 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
993 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
994 AAQueryInfo &AAQI) = 0;
995
996 /// @}
997};
998
999/// A private class template which derives from \c Concept and wraps some other
1000/// type.
1001///
1002/// This models the concept by directly forwarding each interface point to the
1003/// wrapped type which must implement a compatible interface. This provides
1004/// a type erased binding.
1005template <typename AAResultT> class AAResults::Model final : public Concept {
1006 AAResultT &Result;
1007
1008public:
1009 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {
1010 Result.setAAResults(&AAR);
1011 }
1012 ~Model() override = default;
1013
1014 void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); }
1015
1016 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
1017 AAQueryInfo &AAQI) override {
1018 return Result.alias(LocA, LocB, AAQI);
1019 }
1020
1021 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
1022 bool OrLocal) override {
1023 return Result.pointsToConstantMemory(Loc, AAQI, OrLocal);
1024 }
1025
1026 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
1027 return Result.getArgModRefInfo(Call, ArgIdx);
1028 }
1029
1030 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override {
1031 return Result.getModRefBehavior(Call);
1032 }
1033
1034 FunctionModRefBehavior getModRefBehavior(const Function *F) override {
1035 return Result.getModRefBehavior(F);
1036 }
1037
1038 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
1039 AAQueryInfo &AAQI) override {
1040 return Result.getModRefInfo(Call, Loc, AAQI);
1041 }
1042
1043 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1044 AAQueryInfo &AAQI) override {
1045 return Result.getModRefInfo(Call1, Call2, AAQI);
1046 }
1047};
1048
1049/// A CRTP-driven "mixin" base class to help implement the function alias
1050/// analysis results concept.
1051///
1052/// Because of the nature of many alias analysis implementations, they often
1053/// only implement a subset of the interface. This base class will attempt to
1054/// implement the remaining portions of the interface in terms of simpler forms
1055/// of the interface where possible, and otherwise provide conservatively
1056/// correct fallback implementations.
1057///
1058/// Implementors of an alias analysis should derive from this CRTP, and then
1059/// override specific methods that they wish to customize. There is no need to
1060/// use virtual anywhere, the CRTP base class does static dispatch to the
1061/// derived type passed into it.
1062template <typename DerivedT> class AAResultBase {
1063 // Expose some parts of the interface only to the AAResults::Model
1064 // for wrapping. Specifically, this allows the model to call our
1065 // setAAResults method without exposing it as a fully public API.
1066 friend class AAResults::Model<DerivedT>;
1067
1068 /// A pointer to the AAResults object that this AAResult is
1069 /// aggregated within. May be null if not aggregated.
1070 AAResults *AAR = nullptr;
1071
1072 /// Helper to dispatch calls back through the derived type.
1073 DerivedT &derived() { return static_cast<DerivedT &>(*this); }
1074
1075 /// A setter for the AAResults pointer, which is used to satisfy the
1076 /// AAResults::Model contract.
1077 void setAAResults(AAResults *NewAAR) { AAR = NewAAR; }
1078
1079protected:
1080 /// This proxy class models a common pattern where we delegate to either the
1081 /// top-level \c AAResults aggregation if one is registered, or to the
1082 /// current result if none are registered.
1083 class AAResultsProxy {
1084 AAResults *AAR;
1085 DerivedT &CurrentResult;
1086
1087 public:
1088 AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult)
1089 : AAR(AAR), CurrentResult(CurrentResult) {}
1090
1091 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
1092 AAQueryInfo &AAQI) {
1093 return AAR ? AAR->alias(LocA, LocB, AAQI)
1094 : CurrentResult.alias(LocA, LocB, AAQI);
1095 }
1096
1097 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
1098 bool OrLocal) {
1099 return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal)
1100 : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal);
1101 }
1102
1103 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
1104 return AAR ? AAR->getArgModRefInfo(Call, ArgIdx)
1105 : CurrentResult.getArgModRefInfo(Call, ArgIdx);
1106 }
1107
1108 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
1109 return AAR ? AAR->getModRefBehavior(Call)
1110 : CurrentResult.getModRefBehavior(Call);
1111 }
1112
1113 FunctionModRefBehavior getModRefBehavior(const Function *F) {
1114 return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F);
1115 }
1116
1117 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
1118 AAQueryInfo &AAQI) {
1119 return AAR ? AAR->getModRefInfo(Call, Loc, AAQI)
1120 : CurrentResult.getModRefInfo(Call, Loc, AAQI);
1121 }
1122
1123 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1124 AAQueryInfo &AAQI) {
1125 return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI)
1126 : CurrentResult.getModRefInfo(Call1, Call2, AAQI);
1127 }
1128 };
1129
1130 explicit AAResultBase() = default;
1131
1132 // Provide all the copy and move constructors so that derived types aren't
1133 // constrained.
1134 AAResultBase(const AAResultBase &Arg) {}
1135 AAResultBase(AAResultBase &&Arg) {}
1136
1137 /// Get a proxy for the best AA result set to query at this time.
1138 ///
1139 /// When this result is part of a larger aggregation, this will proxy to that
1140 /// aggregation. When this result is used in isolation, it will just delegate
1141 /// back to the derived class's implementation.
1142 ///
1143 /// Note that callers of this need to take considerable care to not cause
1144 /// performance problems when they use this routine, in the case of a large
1145 /// number of alias analyses being aggregated, it can be expensive to walk
1146 /// back across the chain.
1147 AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); }
1148
1149public:
1150 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
1151 AAQueryInfo &AAQI) {
1152 return MayAlias;
1153 }
1154
1155 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
1156 bool OrLocal) {
1157 return false;
1158 }
1159
1160 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
1161 return ModRefInfo::ModRef;
1162 }
1163
1164 FunctionModRefBehavior getModRefBehavior(const CallBase *Call) {
1165 return FMRB_UnknownModRefBehavior;
1166 }
1167
1168 FunctionModRefBehavior getModRefBehavior(const Function *F) {
1169 return FMRB_UnknownModRefBehavior;
1170 }
1171
1172 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
1173 AAQueryInfo &AAQI) {
1174 return ModRefInfo::ModRef;
1175 }
1176
1177 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
1178 AAQueryInfo &AAQI) {
1179 return ModRefInfo::ModRef;
1180 }
1181};
1182
1183/// Return true if this pointer is returned by a noalias function.
1184bool isNoAliasCall(const Value *V);
1185
1186/// Return true if this pointer refers to a distinct and identifiable object.
1187/// This returns true for:
1188/// Global Variables and Functions (but not Global Aliases)
1189/// Allocas
1190/// ByVal and NoAlias Arguments
1191/// NoAlias returns (e.g. calls to malloc)
1192///
1193bool isIdentifiedObject(const Value *V);
1194
1195/// Return true if V is umabigously identified at the function-level.
1196/// Different IdentifiedFunctionLocals can't alias.
1197/// Further, an IdentifiedFunctionLocal can not alias with any function
1198/// arguments other than itself, which is not necessarily true for
1199/// IdentifiedObjects.
1200bool isIdentifiedFunctionLocal(const Value *V);
1201
1202/// A manager for alias analyses.
1203///
1204/// This class can have analyses registered with it and when run, it will run
1205/// all of them and aggregate their results into single AA results interface
1206/// that dispatches across all of the alias analysis results available.
1207///
1208/// Note that the order in which analyses are registered is very significant.
1209/// That is the order in which the results will be aggregated and queried.
1210///
1211/// This manager effectively wraps the AnalysisManager for registering alias
1212/// analyses. When you register your alias analysis with this manager, it will
1213/// ensure the analysis itself is registered with its AnalysisManager.
1214///
1215/// The result of this analysis is only invalidated if one of the particular
1216/// aggregated AA results end up being invalidated. This removes the need to
1217/// explicitly preserve the results of `AAManager`. Note that analyses should no
1218/// longer be registered once the `AAManager` is run.
1219class AAManager : public AnalysisInfoMixin<AAManager> {
1220public:
1221 using Result = AAResults;
1222
1223 /// Register a specific AA result.
1224 template <typename AnalysisT> void registerFunctionAnalysis() {
1225 ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>);
1226 }
1227
1228 /// Register a specific AA result.
1229 template <typename AnalysisT> void registerModuleAnalysis() {
1230 ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>);
1231 }
1232
1233 Result run(Function &F, FunctionAnalysisManager &AM);
1234
1235private:
1236 friend AnalysisInfoMixin<AAManager>;
1237
1238 static AnalysisKey Key;
1239
1240 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
1241 AAResults &AAResults),
1242 4> ResultGetters;
1243
1244 template <typename AnalysisT>
1245 static void getFunctionAAResultImpl(Function &F,
1246 FunctionAnalysisManager &AM,
1247 AAResults &AAResults) {
1248 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
1249 AAResults.addAADependencyID(AnalysisT::ID());
1250 }
1251
1252 template <typename AnalysisT>
1253 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
1254 AAResults &AAResults) {
1255 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
1256 if (auto *R =
1257 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) {
1258 AAResults.addAAResult(*R);
1259 MAMProxy
1260 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
1261 }
1262 }
1263};
1264
1265/// A wrapper pass to provide the legacy pass manager access to a suitably
1266/// prepared AAResults object.
1267class AAResultsWrapperPass : public FunctionPass {
1268 std::unique_ptr<AAResults> AAR;
1269
1270public:
1271 static char ID;
1272
1273 AAResultsWrapperPass();
1274
1275 AAResults &getAAResults() { return *AAR; }
1276 const AAResults &getAAResults() const { return *AAR; }
1277
1278 bool runOnFunction(Function &F) override;
1279
1280 void getAnalysisUsage(AnalysisUsage &AU) const override;
1281};
1282
1283/// A wrapper pass for external alias analyses. This just squirrels away the
1284/// callback used to run any analyses and register their results.
1285struct ExternalAAWrapperPass : ImmutablePass {
1286 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
1287
1288 CallbackT CB;
1289
1290 static char ID;
1291
1292 ExternalAAWrapperPass();
1293
1294 explicit ExternalAAWrapperPass(CallbackT CB);
1295
1296 void getAnalysisUsage(AnalysisUsage &AU) const override {
1297 AU.setPreservesAll();
1298 }
1299};
1300
1301FunctionPass *createAAResultsWrapperPass();
1302
1303/// A wrapper pass around a callback which can be used to populate the
1304/// AAResults in the AAResultsWrapperPass from an external AA.
1305///
1306/// The callback provided here will be used each time we prepare an AAResults
1307/// object, and will receive a reference to the function wrapper pass, the
1308/// function, and the AAResults object to populate. This should be used when
1309/// setting up a custom pass pipeline to inject a hook into the AA results.
1310ImmutablePass *createExternalAAWrapperPass(
1311 std::function<void(Pass &, Function &, AAResults &)> Callback);
1312
1313/// A helper for the legacy pass manager to create a \c AAResults
1314/// object populated to the best of our ability for a particular function when
1315/// inside of a \c ModulePass or a \c CallGraphSCCPass.
1316///
1317/// If a \c ModulePass or a \c CallGraphSCCPass calls \p
1318/// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p
1319/// getAnalysisUsage.
1320AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR);
1321
1322/// A helper for the legacy pass manager to populate \p AU to add uses to make
1323/// sure the analyses required by \p createLegacyPMAAResults are available.
1324void getAAResultsAnalysisUsage(AnalysisUsage &AU);
1325
1326} // end namespace llvm
1327
1328#endif // LLVM_ANALYSIS_ALIASANALYSIS_H