LLVM  15.0.0git
MemorySSA.cpp
Go to the documentation of this file.
1 //===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the MemorySSA class.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/DenseMapInfo.h"
16 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringExtras.h"
25 #include "llvm/ADT/iterator.h"
31 #include "llvm/Config/llvm-config.h"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/Instruction.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/IntrinsicInst.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/IR/Operator.h"
41 #include "llvm/IR/PassManager.h"
42 #include "llvm/IR/Use.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/Pass.h"
46 #include "llvm/Support/Casting.h"
48 #include "llvm/Support/Compiler.h"
49 #include "llvm/Support/Debug.h"
54 #include <algorithm>
55 #include <cassert>
56 #include <iterator>
57 #include <memory>
58 #include <utility>
59 
60 using namespace llvm;
61 
62 #define DEBUG_TYPE "memoryssa"
63 
65  DotCFGMSSA("dot-cfg-mssa",
66  cl::value_desc("file name for generated dot file"),
67  cl::desc("file name for generated dot file"), cl::init(""));
68 
69 INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
70  true)
74  true)
75 
81 
82 static cl::opt<unsigned> MaxCheckLimit(
83  "memssa-check-limit", cl::Hidden, cl::init(100),
84  cl::desc("The maximum number of stores/phis MemorySSA"
85  "will consider trying to walk past (default = 100)"));
86 
87 // Always verify MemorySSA if expensive checking is enabled.
88 #ifdef EXPENSIVE_CHECKS
89 bool llvm::VerifyMemorySSA = true;
90 #else
91 bool llvm::VerifyMemorySSA = false;
92 #endif
93 
95  VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA),
96  cl::Hidden, cl::desc("Enable verification of MemorySSA."));
97 
98 const static char LiveOnEntryStr[] = "liveOnEntry";
99 
100 namespace {
101 
102 /// An assembly annotator class to print Memory SSA information in
103 /// comments.
104 class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
105  const MemorySSA *MSSA;
106 
107 public:
108  MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
109 
110  void emitBasicBlockStartAnnot(const BasicBlock *BB,
111  formatted_raw_ostream &OS) override {
112  if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
113  OS << "; " << *MA << "\n";
114  }
115 
116  void emitInstructionAnnot(const Instruction *I,
117  formatted_raw_ostream &OS) override {
118  if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
119  OS << "; " << *MA << "\n";
120  }
121 };
122 
123 /// An assembly annotator class to print Memory SSA information in
124 /// comments.
125 class MemorySSAWalkerAnnotatedWriter : public AssemblyAnnotationWriter {
126  MemorySSA *MSSA;
127  MemorySSAWalker *Walker;
128 
129 public:
130  MemorySSAWalkerAnnotatedWriter(MemorySSA *M)
131  : MSSA(M), Walker(M->getWalker()) {}
132 
133  void emitBasicBlockStartAnnot(const BasicBlock *BB,
134  formatted_raw_ostream &OS) override {
135  if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
136  OS << "; " << *MA << "\n";
137  }
138 
139  void emitInstructionAnnot(const Instruction *I,
140  formatted_raw_ostream &OS) override {
141  if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
142  MemoryAccess *Clobber = Walker->getClobberingMemoryAccess(MA);
143  OS << "; " << *MA;
144  if (Clobber) {
145  OS << " - clobbered by ";
146  if (MSSA->isLiveOnEntryDef(Clobber))
147  OS << LiveOnEntryStr;
148  else
149  OS << *Clobber;
150  }
151  OS << "\n";
152  }
153  }
154 };
155 
156 } // namespace
157 
158 namespace {
159 
160 /// Our current alias analysis API differentiates heavily between calls and
161 /// non-calls, and functions called on one usually assert on the other.
162 /// This class encapsulates the distinction to simplify other code that wants
163 /// "Memory affecting instructions and related data" to use as a key.
164 /// For example, this class is used as a densemap key in the use optimizer.
165 class MemoryLocOrCall {
166 public:
167  bool IsCall = false;
168 
169  MemoryLocOrCall(MemoryUseOrDef *MUD)
170  : MemoryLocOrCall(MUD->getMemoryInst()) {}
171  MemoryLocOrCall(const MemoryUseOrDef *MUD)
172  : MemoryLocOrCall(MUD->getMemoryInst()) {}
173 
174  MemoryLocOrCall(Instruction *Inst) {
175  if (auto *C = dyn_cast<CallBase>(Inst)) {
176  IsCall = true;
177  Call = C;
178  } else {
179  IsCall = false;
180  // There is no such thing as a memorylocation for a fence inst, and it is
181  // unique in that regard.
182  if (!isa<FenceInst>(Inst))
183  Loc = MemoryLocation::get(Inst);
184  }
185  }
186 
187  explicit MemoryLocOrCall(const MemoryLocation &Loc) : Loc(Loc) {}
188 
189  const CallBase *getCall() const {
190  assert(IsCall);
191  return Call;
192  }
193 
194  MemoryLocation getLoc() const {
195  assert(!IsCall);
196  return Loc;
197  }
198 
199  bool operator==(const MemoryLocOrCall &Other) const {
200  if (IsCall != Other.IsCall)
201  return false;
202 
203  if (!IsCall)
204  return Loc == Other.Loc;
205 
206  if (Call->getCalledOperand() != Other.Call->getCalledOperand())
207  return false;
208 
209  return Call->arg_size() == Other.Call->arg_size() &&
210  std::equal(Call->arg_begin(), Call->arg_end(),
211  Other.Call->arg_begin());
212  }
213 
214 private:
215  union {
216  const CallBase *Call;
217  MemoryLocation Loc;
218  };
219 };
220 
221 } // end anonymous namespace
222 
223 namespace llvm {
224 
225 template <> struct DenseMapInfo<MemoryLocOrCall> {
226  static inline MemoryLocOrCall getEmptyKey() {
227  return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey());
228  }
229 
230  static inline MemoryLocOrCall getTombstoneKey() {
231  return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getTombstoneKey());
232  }
233 
234  static unsigned getHashValue(const MemoryLocOrCall &MLOC) {
235  if (!MLOC.IsCall)
236  return hash_combine(
237  MLOC.IsCall,
239 
240  hash_code hash =
242  MLOC.getCall()->getCalledOperand()));
243 
244  for (const Value *Arg : MLOC.getCall()->args())
246  return hash;
247  }
248 
249  static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
250  return LHS == RHS;
251  }
252 };
253 
254 } // end namespace llvm
255 
256 /// This does one-way checks to see if Use could theoretically be hoisted above
257 /// MayClobber. This will not check the other way around.
258 ///
259 /// This assumes that, for the purposes of MemorySSA, Use comes directly after
260 /// MayClobber, with no potentially clobbering operations in between them.
261 /// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
262 static bool areLoadsReorderable(const LoadInst *Use,
263  const LoadInst *MayClobber) {
264  bool VolatileUse = Use->isVolatile();
265  bool VolatileClobber = MayClobber->isVolatile();
266  // Volatile operations may never be reordered with other volatile operations.
267  if (VolatileUse && VolatileClobber)
268  return false;
269  // Otherwise, volatile doesn't matter here. From the language reference:
270  // 'optimizers may change the order of volatile operations relative to
271  // non-volatile operations.'"
272 
273  // If a load is seq_cst, it cannot be moved above other loads. If its ordering
274  // is weaker, it can be moved above other loads. We just need to be sure that
275  // MayClobber isn't an acquire load, because loads can't be moved above
276  // acquire loads.
277  //
278  // Note that this explicitly *does* allow the free reordering of monotonic (or
279  // weaker) loads of the same address.
280  bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
281  bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
283  return !(SeqCstUse || MayClobberIsAcquire);
284 }
285 
286 namespace {
287 
288 struct ClobberAlias {
289  bool IsClobber;
291 };
292 
293 } // end anonymous namespace
294 
295 // Return a pair of {IsClobber (bool), AR (AliasResult)}. It relies on AR being
296 // ignored if IsClobber = false.
297 template <typename AliasAnalysisType>
298 static ClobberAlias
300  const Instruction *UseInst, AliasAnalysisType &AA) {
301  Instruction *DefInst = MD->getMemoryInst();
302  assert(DefInst && "Defining instruction not actually an instruction");
304 
305  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
306  // These intrinsics will show up as affecting memory, but they are just
307  // markers, mostly.
308  //
309  // FIXME: We probably don't actually want MemorySSA to model these at all
310  // (including creating MemoryAccesses for them): we just end up inventing
311  // clobbers where they don't really exist at all. Please see D43269 for
312  // context.
313  switch (II->getIntrinsicID()) {
314  case Intrinsic::invariant_start:
315  case Intrinsic::invariant_end:
316  case Intrinsic::assume:
317  case Intrinsic::experimental_noalias_scope_decl:
318  case Intrinsic::pseudoprobe:
319  return {false, AliasResult(AliasResult::NoAlias)};
320  case Intrinsic::dbg_addr:
321  case Intrinsic::dbg_declare:
322  case Intrinsic::dbg_label:
323  case Intrinsic::dbg_value:
324  llvm_unreachable("debuginfo shouldn't have associated defs!");
325  default:
326  break;
327  }
328  }
329 
330  if (auto *CB = dyn_cast_or_null<CallBase>(UseInst)) {
331  ModRefInfo I = AA.getModRefInfo(DefInst, CB);
333  return {isModOrRefSet(I), AR};
334  }
335 
336  if (auto *DefLoad = dyn_cast<LoadInst>(DefInst))
337  if (auto *UseLoad = dyn_cast_or_null<LoadInst>(UseInst))
338  return {!areLoadsReorderable(UseLoad, DefLoad),
340 
341  ModRefInfo I = AA.getModRefInfo(DefInst, UseLoc);
343  return {isModSet(I), AR};
344 }
345 
346 template <typename AliasAnalysisType>
347 static ClobberAlias instructionClobbersQuery(MemoryDef *MD,
348  const MemoryUseOrDef *MU,
349  const MemoryLocOrCall &UseMLOC,
350  AliasAnalysisType &AA) {
351  // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
352  // to exist while MemoryLocOrCall is pushed through places.
353  if (UseMLOC.IsCall)
355  AA);
356  return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
357  AA);
358 }
359 
360 // Return true when MD may alias MU, return false otherwise.
362  AliasAnalysis &AA) {
363  return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA).IsClobber;
364 }
365 
366 namespace {
367 
368 struct UpwardsMemoryQuery {
369  // True if our original query started off as a call
370  bool IsCall = false;
371  // The pointer location we started the query with. This will be empty if
372  // IsCall is true.
373  MemoryLocation StartingLoc;
374  // This is the instruction we were querying about.
375  const Instruction *Inst = nullptr;
376  // The MemoryAccess we actually got called with, used to test local domination
377  const MemoryAccess *OriginalAccess = nullptr;
379  bool SkipSelfAccess = false;
380 
381  UpwardsMemoryQuery() = default;
382 
383  UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
384  : IsCall(isa<CallBase>(Inst)), Inst(Inst), OriginalAccess(Access) {
385  if (!IsCall)
386  StartingLoc = MemoryLocation::get(Inst);
387  }
388 };
389 
390 } // end anonymous namespace
391 
392 template <typename AliasAnalysisType>
393 static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
394  const Instruction *I) {
395  // If the memory can't be changed, then loads of the memory can't be
396  // clobbered.
397  if (auto *LI = dyn_cast<LoadInst>(I))
398  return I->hasMetadata(LLVMContext::MD_invariant_load) ||
399  AA.pointsToConstantMemory(MemoryLocation::get(LI));
400  return false;
401 }
402 
403 /// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
404 /// inbetween `Start` and `ClobberAt` can clobbers `Start`.
405 ///
406 /// This is meant to be as simple and self-contained as possible. Because it
407 /// uses no cache, etc., it can be relatively expensive.
408 ///
409 /// \param Start The MemoryAccess that we want to walk from.
410 /// \param ClobberAt A clobber for Start.
411 /// \param StartLoc The MemoryLocation for Start.
412 /// \param MSSA The MemorySSA instance that Start and ClobberAt belong to.
413 /// \param Query The UpwardsMemoryQuery we used for our search.
414 /// \param AA The AliasAnalysis we used for our search.
415 /// \param AllowImpreciseClobber Always false, unless we do relaxed verify.
416 
417 template <typename AliasAnalysisType>
418 LLVM_ATTRIBUTE_UNUSED static void
420  const MemoryLocation &StartLoc, const MemorySSA &MSSA,
421  const UpwardsMemoryQuery &Query, AliasAnalysisType &AA,
422  bool AllowImpreciseClobber = false) {
423  assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
424 
425  if (MSSA.isLiveOnEntryDef(Start)) {
426  assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
427  "liveOnEntry must clobber itself");
428  return;
429  }
430 
431  bool FoundClobber = false;
434  Worklist.emplace_back(Start, StartLoc);
435  // Walk all paths from Start to ClobberAt, while looking for clobbers. If one
436  // is found, complain.
437  while (!Worklist.empty()) {
438  auto MAP = Worklist.pop_back_val();
439  // All we care about is that nothing from Start to ClobberAt clobbers Start.
440  // We learn nothing from revisiting nodes.
441  if (!VisitedPhis.insert(MAP).second)
442  continue;
443 
444  for (const auto *MA : def_chain(MAP.first)) {
445  if (MA == ClobberAt) {
446  if (const auto *MD = dyn_cast<MemoryDef>(MA)) {
447  // instructionClobbersQuery isn't essentially free, so don't use `|=`,
448  // since it won't let us short-circuit.
449  //
450  // Also, note that this can't be hoisted out of the `Worklist` loop,
451  // since MD may only act as a clobber for 1 of N MemoryLocations.
452  FoundClobber = FoundClobber || MSSA.isLiveOnEntryDef(MD);
453  if (!FoundClobber) {
454  ClobberAlias CA =
455  instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
456  if (CA.IsClobber) {
457  FoundClobber = true;
458  // Not used: CA.AR;
459  }
460  }
461  }
462  break;
463  }
464 
465  // We should never hit liveOnEntry, unless it's the clobber.
466  assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
467 
468  if (const auto *MD = dyn_cast<MemoryDef>(MA)) {
469  // If Start is a Def, skip self.
470  if (MD == Start)
471  continue;
472 
473  assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA)
474  .IsClobber &&
475  "Found clobber before reaching ClobberAt!");
476  continue;
477  }
478 
479  if (const auto *MU = dyn_cast<MemoryUse>(MA)) {
480  (void)MU;
481  assert (MU == Start &&
482  "Can only find use in def chain if Start is a use");
483  continue;
484  }
485 
486  assert(isa<MemoryPhi>(MA));
487 
488  // Add reachable phi predecessors
489  for (auto ItB = upward_defs_begin(
490  {const_cast<MemoryAccess *>(MA), MAP.second},
491  MSSA.getDomTree()),
492  ItE = upward_defs_end();
493  ItB != ItE; ++ItB)
494  if (MSSA.getDomTree().isReachableFromEntry(ItB.getPhiArgBlock()))
495  Worklist.emplace_back(*ItB);
496  }
497  }
498 
499  // If the verify is done following an optimization, it's possible that
500  // ClobberAt was a conservative clobbering, that we can now infer is not a
501  // true clobbering access. Don't fail the verify if that's the case.
502  // We do have accesses that claim they're optimized, but could be optimized
503  // further. Updating all these can be expensive, so allow it for now (FIXME).
504  if (AllowImpreciseClobber)
505  return;
506 
507  // If ClobberAt is a MemoryPhi, we can assume something above it acted as a
508  // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point.
509  assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
510  "ClobberAt never acted as a clobber");
511 }
512 
513 namespace {
514 
515 /// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
516 /// in one class.
517 template <class AliasAnalysisType> class ClobberWalker {
518  /// Save a few bytes by using unsigned instead of size_t.
519  using ListIndex = unsigned;
520 
521  /// Represents a span of contiguous MemoryDefs, potentially ending in a
522  /// MemoryPhi.
523  struct DefPath {
524  MemoryLocation Loc;
525  // Note that, because we always walk in reverse, Last will always dominate
526  // First. Also note that First and Last are inclusive.
529  Optional<ListIndex> Previous;
530 
531  DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
532  Optional<ListIndex> Previous)
533  : Loc(Loc), First(First), Last(Last), Previous(Previous) {}
534 
535  DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
536  Optional<ListIndex> Previous)
537  : DefPath(Loc, Init, Init, Previous) {}
538  };
539 
540  const MemorySSA &MSSA;
541  AliasAnalysisType &AA;
542  DominatorTree &DT;
543  UpwardsMemoryQuery *Query;
544  unsigned *UpwardWalkLimit;
545 
546  // Phi optimization bookkeeping:
547  // List of DefPath to process during the current phi optimization walk.
549  // List of visited <Access, Location> pairs; we can skip paths already
550  // visited with the same memory location.
552  // Record if phi translation has been performed during the current phi
553  // optimization walk, as merging alias results after phi translation can
554  // yield incorrect results. Context in PR46156.
555  bool PerformedPhiTranslation = false;
556 
557  /// Find the nearest def or phi that `From` can legally be optimized to.
558  const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
559  assert(From->getNumOperands() && "Phi with no operands?");
560 
561  BasicBlock *BB = From->getBlock();
563  DomTreeNode *Node = DT.getNode(BB);
564  while ((Node = Node->getIDom())) {
565  auto *Defs = MSSA.getBlockDefs(Node->getBlock());
566  if (Defs)
567  return &*Defs->rbegin();
568  }
569  return Result;
570  }
571 
572  /// Result of calling walkToPhiOrClobber.
573  struct UpwardsWalkResult {
574  /// The "Result" of the walk. Either a clobber, the last thing we walked, or
575  /// both. Include alias info when clobber found.
577  bool IsKnownClobber;
579  };
580 
581  /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
582  /// This will update Desc.Last as it walks. It will (optionally) also stop at
583  /// StopAt.
584  ///
585  /// This does not test for whether StopAt is a clobber
586  UpwardsWalkResult
587  walkToPhiOrClobber(DefPath &Desc, const MemoryAccess *StopAt = nullptr,
588  const MemoryAccess *SkipStopAt = nullptr) const {
589  assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
590  assert(UpwardWalkLimit && "Need a valid walk limit");
591  bool LimitAlreadyReached = false;
592  // (*UpwardWalkLimit) may be 0 here, due to the loop in tryOptimizePhi. Set
593  // it to 1. This will not do any alias() calls. It either returns in the
594  // first iteration in the loop below, or is set back to 0 if all def chains
595  // are free of MemoryDefs.
596  if (!*UpwardWalkLimit) {
597  *UpwardWalkLimit = 1;
598  LimitAlreadyReached = true;
599  }
600 
601  for (MemoryAccess *Current : def_chain(Desc.Last)) {
602  Desc.Last = Current;
603  if (Current == StopAt || Current == SkipStopAt)
604  return {Current, false, AliasResult(AliasResult::MayAlias)};
605 
606  if (auto *MD = dyn_cast<MemoryDef>(Current)) {
607  if (MSSA.isLiveOnEntryDef(MD))
608  return {MD, true, AliasResult(AliasResult::MustAlias)};
609 
610  if (!--*UpwardWalkLimit)
611  return {Current, true, AliasResult(AliasResult::MayAlias)};
612 
613  ClobberAlias CA =
614  instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA);
615  if (CA.IsClobber)
616  return {MD, true, CA.AR};
617  }
618  }
619 
620  if (LimitAlreadyReached)
621  *UpwardWalkLimit = 0;
622 
623  assert(isa<MemoryPhi>(Desc.Last) &&
624  "Ended at a non-clobber that's not a phi?");
625  return {Desc.Last, false, AliasResult(AliasResult::MayAlias)};
626  }
627 
628  void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
629  ListIndex PriorNode) {
630  auto UpwardDefsBegin = upward_defs_begin({Phi, Paths[PriorNode].Loc}, DT,
631  &PerformedPhiTranslation);
632  auto UpwardDefs = make_range(UpwardDefsBegin, upward_defs_end());
633  for (const MemoryAccessPair &P : UpwardDefs) {
634  PausedSearches.push_back(Paths.size());
635  Paths.emplace_back(P.second, P.first, PriorNode);
636  }
637  }
638 
639  /// Represents a search that terminated after finding a clobber. This clobber
640  /// may or may not be present in the path of defs from LastNode..SearchStart,
641  /// since it may have been retrieved from cache.
642  struct TerminatedPath {
643  MemoryAccess *Clobber;
644  ListIndex LastNode;
645  };
646 
647  /// Get an access that keeps us from optimizing to the given phi.
648  ///
649  /// PausedSearches is an array of indices into the Paths array. Its incoming
650  /// value is the indices of searches that stopped at the last phi optimization
651  /// target. It's left in an unspecified state.
652  ///
653  /// If this returns None, NewPaused is a vector of searches that terminated
654  /// at StopWhere. Otherwise, NewPaused is left in an unspecified state.
656  getBlockingAccess(const MemoryAccess *StopWhere,
657  SmallVectorImpl<ListIndex> &PausedSearches,
658  SmallVectorImpl<ListIndex> &NewPaused,
659  SmallVectorImpl<TerminatedPath> &Terminated) {
660  assert(!PausedSearches.empty() && "No searches to continue?");
661 
662  // BFS vs DFS really doesn't make a difference here, so just do a DFS with
663  // PausedSearches as our stack.
664  while (!PausedSearches.empty()) {
665  ListIndex PathIndex = PausedSearches.pop_back_val();
666  DefPath &Node = Paths[PathIndex];
667 
668  // If we've already visited this path with this MemoryLocation, we don't
669  // need to do so again.
670  //
671  // NOTE: That we just drop these paths on the ground makes caching
672  // behavior sporadic. e.g. given a diamond:
673  // A
674  // B C
675  // D
676  //
677  // ...If we walk D, B, A, C, we'll only cache the result of phi
678  // optimization for A, B, and D; C will be skipped because it dies here.
679  // This arguably isn't the worst thing ever, since:
680  // - We generally query things in a top-down order, so if we got below D
681  // without needing cache entries for {C, MemLoc}, then chances are
682  // that those cache entries would end up ultimately unused.
683  // - We still cache things for A, so C only needs to walk up a bit.
684  // If this behavior becomes problematic, we can fix without a ton of extra
685  // work.
686  if (!VisitedPhis.insert({Node.Last, Node.Loc}).second) {
687  if (PerformedPhiTranslation) {
688  // If visiting this path performed Phi translation, don't continue,
689  // since it may not be correct to merge results from two paths if one
690  // relies on the phi translation.
691  TerminatedPath Term{Node.Last, PathIndex};
692  return Term;
693  }
694  continue;
695  }
696 
697  const MemoryAccess *SkipStopWhere = nullptr;
698  if (Query->SkipSelfAccess && Node.Loc == Query->StartingLoc) {
699  assert(isa<MemoryDef>(Query->OriginalAccess));
700  SkipStopWhere = Query->OriginalAccess;
701  }
702 
703  UpwardsWalkResult Res = walkToPhiOrClobber(Node,
704  /*StopAt=*/StopWhere,
705  /*SkipStopAt=*/SkipStopWhere);
706  if (Res.IsKnownClobber) {
707  assert(Res.Result != StopWhere && Res.Result != SkipStopWhere);
708 
709  // If this wasn't a cache hit, we hit a clobber when walking. That's a
710  // failure.
711  TerminatedPath Term{Res.Result, PathIndex};
712  if (!MSSA.dominates(Res.Result, StopWhere))
713  return Term;
714 
715  // Otherwise, it's a valid thing to potentially optimize to.
716  Terminated.push_back(Term);
717  continue;
718  }
719 
720  if (Res.Result == StopWhere || Res.Result == SkipStopWhere) {
721  // We've hit our target. Save this path off for if we want to continue
722  // walking. If we are in the mode of skipping the OriginalAccess, and
723  // we've reached back to the OriginalAccess, do not save path, we've
724  // just looped back to self.
725  if (Res.Result != SkipStopWhere)
726  NewPaused.push_back(PathIndex);
727  continue;
728  }
729 
730  assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber");
731  addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex);
732  }
733 
734  return None;
735  }
736 
737  template <typename T, typename Walker>
738  struct generic_def_path_iterator
739  : public iterator_facade_base<generic_def_path_iterator<T, Walker>,
740  std::forward_iterator_tag, T *> {
741  generic_def_path_iterator() = default;
742  generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {}
743 
744  T &operator*() const { return curNode(); }
745 
746  generic_def_path_iterator &operator++() {
747  N = curNode().Previous;
748  return *this;
749  }
750 
751  bool operator==(const generic_def_path_iterator &O) const {
752  if (N.has_value() != O.N.has_value())
753  return false;
754  return !N || *N == *O.N;
755  }
756 
757  private:
758  T &curNode() const { return W->Paths[*N]; }
759 
760  Walker *W = nullptr;
762  };
763 
764  using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
765  using const_def_path_iterator =
766  generic_def_path_iterator<const DefPath, const ClobberWalker>;
767 
768  iterator_range<def_path_iterator> def_path(ListIndex From) {
769  return make_range(def_path_iterator(this, From), def_path_iterator());
770  }
771 
772  iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const {
773  return make_range(const_def_path_iterator(this, From),
774  const_def_path_iterator());
775  }
776 
777  struct OptznResult {
778  /// The path that contains our result.
779  TerminatedPath PrimaryClobber;
780  /// The paths that we can legally cache back from, but that aren't
781  /// necessarily the result of the Phi optimization.
782  SmallVector<TerminatedPath, 4> OtherClobbers;
783  };
784 
785  ListIndex defPathIndex(const DefPath &N) const {
786  // The assert looks nicer if we don't need to do &N
787  const DefPath *NP = &N;
788  assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&
789  "Out of bounds DefPath!");
790  return NP - &Paths.front();
791  }
792 
793  /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths
794  /// that act as legal clobbers. Note that this won't return *all* clobbers.
795  ///
796  /// Phi optimization algorithm tl;dr:
797  /// - Find the earliest def/phi, A, we can optimize to
798  /// - Find if all paths from the starting memory access ultimately reach A
799  /// - If not, optimization isn't possible.
800  /// - Otherwise, walk from A to another clobber or phi, A'.
801  /// - If A' is a def, we're done.
802  /// - If A' is a phi, try to optimize it.
803  ///
804  /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
805  /// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
806  OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
807  const MemoryLocation &Loc) {
808  assert(Paths.empty() && VisitedPhis.empty() && !PerformedPhiTranslation &&
809  "Reset the optimization state.");
810 
811  Paths.emplace_back(Loc, Start, Phi, None);
812  // Stores how many "valid" optimization nodes we had prior to calling
813  // addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
814  auto PriorPathsSize = Paths.size();
815 
816  SmallVector<ListIndex, 16> PausedSearches;
817  SmallVector<ListIndex, 8> NewPaused;
818  SmallVector<TerminatedPath, 4> TerminatedPaths;
819 
820  addSearches(Phi, PausedSearches, 0);
821 
822  // Moves the TerminatedPath with the "most dominated" Clobber to the end of
823  // Paths.
824  auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) {
825  assert(!Paths.empty() && "Need a path to move");
826  auto Dom = Paths.begin();
827  for (auto I = std::next(Dom), E = Paths.end(); I != E; ++I)
828  if (!MSSA.dominates(I->Clobber, Dom->Clobber))
829  Dom = I;
830  auto Last = Paths.end() - 1;
831  if (Last != Dom)
832  std::iter_swap(Last, Dom);
833  };
834 
835  MemoryPhi *Current = Phi;
836  while (true) {
837  assert(!MSSA.isLiveOnEntryDef(Current) &&
838  "liveOnEntry wasn't treated as a clobber?");
839 
840  const auto *Target = getWalkTarget(Current);
841  // If a TerminatedPath doesn't dominate Target, then it wasn't a legal
842  // optimization for the prior phi.
843  assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {
844  return MSSA.dominates(P.Clobber, Target);
845  }));
846 
847  // FIXME: This is broken, because the Blocker may be reported to be
848  // liveOnEntry, and we'll happily wait for that to disappear (read: never)
849  // For the moment, this is fine, since we do nothing with blocker info.
850  if (Optional<TerminatedPath> Blocker = getBlockingAccess(
851  Target, PausedSearches, NewPaused, TerminatedPaths)) {
852 
853  // Find the node we started at. We can't search based on N->Last, since
854  // we may have gone around a loop with a different MemoryLocation.
855  auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) {
856  return defPathIndex(N) < PriorPathsSize;
857  });
858  assert(Iter != def_path_iterator());
859 
860  DefPath &CurNode = *Iter;
861  assert(CurNode.Last == Current);
862 
863  // Two things:
864  // A. We can't reliably cache all of NewPaused back. Consider a case
865  // where we have two paths in NewPaused; one of which can't optimize
866  // above this phi, whereas the other can. If we cache the second path
867  // back, we'll end up with suboptimal cache entries. We can handle
868  // cases like this a bit better when we either try to find all
869  // clobbers that block phi optimization, or when our cache starts
870  // supporting unfinished searches.
871  // B. We can't reliably cache TerminatedPaths back here without doing
872  // extra checks; consider a case like:
873  // T
874  // / \
875  // D C
876  // \ /
877  // S
878  // Where T is our target, C is a node with a clobber on it, D is a
879  // diamond (with a clobber *only* on the left or right node, N), and
880  // S is our start. Say we walk to D, through the node opposite N
881  // (read: ignoring the clobber), and see a cache entry in the top
882  // node of D. That cache entry gets put into TerminatedPaths. We then
883  // walk up to C (N is later in our worklist), find the clobber, and
884  // quit. If we append TerminatedPaths to OtherClobbers, we'll cache
885  // the bottom part of D to the cached clobber, ignoring the clobber
886  // in N. Again, this problem goes away if we start tracking all
887  // blockers for a given phi optimization.
888  TerminatedPath Result{CurNode.Last, defPathIndex(CurNode)};
889  return {Result, {}};
890  }
891 
892  // If there's nothing left to search, then all paths led to valid clobbers
893  // that we got from our cache; pick the nearest to the start, and allow
894  // the rest to be cached back.
895  if (NewPaused.empty()) {
896  MoveDominatedPathToEnd(TerminatedPaths);
897  TerminatedPath Result = TerminatedPaths.pop_back_val();
898  return {Result, std::move(TerminatedPaths)};
899  }
900 
901  MemoryAccess *DefChainEnd = nullptr;
903  for (ListIndex Paused : NewPaused) {
904  UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
905  if (WR.IsKnownClobber)
906  Clobbers.push_back({WR.Result, Paused});
907  else
908  // Micro-opt: If we hit the end of the chain, save it.
909  DefChainEnd = WR.Result;
910  }
911 
912  if (!TerminatedPaths.empty()) {
913  // If we couldn't find the dominating phi/liveOnEntry in the above loop,
914  // do it now.
915  if (!DefChainEnd)
916  for (auto *MA : def_chain(const_cast<MemoryAccess *>(Target)))
917  DefChainEnd = MA;
918  assert(DefChainEnd && "Failed to find dominating phi/liveOnEntry");
919 
920  // If any of the terminated paths don't dominate the phi we'll try to
921  // optimize, we need to figure out what they are and quit.
922  const BasicBlock *ChainBB = DefChainEnd->getBlock();
923  for (const TerminatedPath &TP : TerminatedPaths) {
924  // Because we know that DefChainEnd is as "high" as we can go, we
925  // don't need local dominance checks; BB dominance is sufficient.
926  if (DT.dominates(ChainBB, TP.Clobber->getBlock()))
927  Clobbers.push_back(TP);
928  }
929  }
930 
931  // If we have clobbers in the def chain, find the one closest to Current
932  // and quit.
933  if (!Clobbers.empty()) {
934  MoveDominatedPathToEnd(Clobbers);
935  TerminatedPath Result = Clobbers.pop_back_val();
936  return {Result, std::move(Clobbers)};
937  }
938 
939  assert(all_of(NewPaused,
940  [&](ListIndex I) { return Paths[I].Last == DefChainEnd; }));
941 
942  // Because liveOnEntry is a clobber, this must be a phi.
943  auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd);
944 
945  PriorPathsSize = Paths.size();
946  PausedSearches.clear();
947  for (ListIndex I : NewPaused)
948  addSearches(DefChainPhi, PausedSearches, I);
949  NewPaused.clear();
950 
951  Current = DefChainPhi;
952  }
953  }
954 
955  void verifyOptResult(const OptznResult &R) const {
956  assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
957  return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
958  }));
959  }
960 
961  void resetPhiOptznState() {
962  Paths.clear();
963  VisitedPhis.clear();
964  PerformedPhiTranslation = false;
965  }
966 
967 public:
968  ClobberWalker(const MemorySSA &MSSA, AliasAnalysisType &AA, DominatorTree &DT)
969  : MSSA(MSSA), AA(AA), DT(DT) {}
970 
971  AliasAnalysisType *getAA() { return &AA; }
972  /// Finds the nearest clobber for the given query, optimizing phis if
973  /// possible.
974  MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q,
975  unsigned &UpWalkLimit) {
976  Query = &Q;
977  UpwardWalkLimit = &UpWalkLimit;
978  // Starting limit must be > 0.
979  if (!UpWalkLimit)
980  UpWalkLimit++;
981 
982  MemoryAccess *Current = Start;
983  // This walker pretends uses don't exist. If we're handed one, silently grab
984  // its def. (This has the nice side-effect of ensuring we never cache uses)
985  if (auto *MU = dyn_cast<MemoryUse>(Start))
986  Current = MU->getDefiningAccess();
987 
988  DefPath FirstDesc(Q.StartingLoc, Current, Current, None);
989  // Fast path for the overly-common case (no crazy phi optimization
990  // necessary)
991  UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
993  if (WalkResult.IsKnownClobber) {
994  Result = WalkResult.Result;
995  Q.AR = WalkResult.AR;
996  } else {
997  OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
998  Current, Q.StartingLoc);
999  verifyOptResult(OptRes);
1000  resetPhiOptznState();
1001  Result = OptRes.PrimaryClobber.Clobber;
1002  }
1003 
1004 #ifdef EXPENSIVE_CHECKS
1005  if (!Q.SkipSelfAccess && *UpwardWalkLimit > 0)
1006  checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
1007 #endif
1008  return Result;
1009  }
1010 };
1011 
1012 struct RenamePassData {
1013  DomTreeNode *DTN;
1015  MemoryAccess *IncomingVal;
1016 
1017  RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
1018  MemoryAccess *M)
1019  : DTN(D), ChildIt(It), IncomingVal(M) {}
1020 
1021  void swap(RenamePassData &RHS) {
1022  std::swap(DTN, RHS.DTN);
1023  std::swap(ChildIt, RHS.ChildIt);
1024  std::swap(IncomingVal, RHS.IncomingVal);
1025  }
1026 };
1027 
1028 } // end anonymous namespace
1029 
1030 namespace llvm {
1031 
1032 template <class AliasAnalysisType> class MemorySSA::ClobberWalkerBase {
1033  ClobberWalker<AliasAnalysisType> Walker;
1034  MemorySSA *MSSA;
1035 
1036 public:
1037  ClobberWalkerBase(MemorySSA *M, AliasAnalysisType *A, DominatorTree *D)
1038  : Walker(*M, *A, *D), MSSA(M) {}
1039 
1040  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
1041  const MemoryLocation &,
1042  unsigned &);
1043  // Third argument (bool), defines whether the clobber search should skip the
1044  // original queried access. If true, there will be a follow-up query searching
1045  // for a clobber access past "self". Note that the Optimized access is not
1046  // updated if a new clobber is found by this SkipSelf search. If this
1047  // additional query becomes heavily used we may decide to cache the result.
1048  // Walker instantiations will decide how to set the SkipSelf bool.
1049  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, unsigned &, bool,
1050  bool UseInvariantGroup = true);
1051 };
1052 
1053 /// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
1054 /// longer does caching on its own, but the name has been retained for the
1055 /// moment.
1056 template <class AliasAnalysisType>
1057 class MemorySSA::CachingWalker final : public MemorySSAWalker {
1058  ClobberWalkerBase<AliasAnalysisType> *Walker;
1059 
1060 public:
1061  CachingWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
1062  : MemorySSAWalker(M), Walker(W) {}
1063  ~CachingWalker() override = default;
1064 
1066 
1067  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
1068  return Walker->getClobberingMemoryAccessBase(MA, UWL, false);
1069  }
1070  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1071  const MemoryLocation &Loc,
1072  unsigned &UWL) {
1073  return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
1074  }
1075  // This method is not accessible outside of this file.
1076  MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(MemoryAccess *MA,
1077  unsigned &UWL) {
1078  return Walker->getClobberingMemoryAccessBase(MA, UWL, false, false);
1079  }
1080 
1081  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
1082  unsigned UpwardWalkLimit = MaxCheckLimit;
1083  return getClobberingMemoryAccess(MA, UpwardWalkLimit);
1084  }
1085  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1086  const MemoryLocation &Loc) override {
1087  unsigned UpwardWalkLimit = MaxCheckLimit;
1088  return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
1089  }
1090 
1091  void invalidateInfo(MemoryAccess *MA) override {
1092  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1093  MUD->resetOptimized();
1094  }
1095 };
1096 
1097 template <class AliasAnalysisType>
1098 class MemorySSA::SkipSelfWalker final : public MemorySSAWalker {
1099  ClobberWalkerBase<AliasAnalysisType> *Walker;
1100 
1101 public:
1102  SkipSelfWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
1103  : MemorySSAWalker(M), Walker(W) {}
1104  ~SkipSelfWalker() override = default;
1105 
1107 
1108  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
1109  return Walker->getClobberingMemoryAccessBase(MA, UWL, true);
1110  }
1111  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1112  const MemoryLocation &Loc,
1113  unsigned &UWL) {
1114  return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
1115  }
1116 
1117  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
1118  unsigned UpwardWalkLimit = MaxCheckLimit;
1119  return getClobberingMemoryAccess(MA, UpwardWalkLimit);
1120  }
1121  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
1122  const MemoryLocation &Loc) override {
1123  unsigned UpwardWalkLimit = MaxCheckLimit;
1124  return getClobberingMemoryAccess(MA, Loc, UpwardWalkLimit);
1125  }
1126 
1127  void invalidateInfo(MemoryAccess *MA) override {
1128  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1129  MUD->resetOptimized();
1130  }
1131 };
1132 
1133 } // end namespace llvm
1134 
1135 void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
1136  bool RenameAllUses) {
1137  // Pass through values to our successors
1138  for (const BasicBlock *S : successors(BB)) {
1139  auto It = PerBlockAccesses.find(S);
1140  // Rename the phi nodes in our successor block
1141  if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
1142  continue;
1143  AccessList *Accesses = It->second.get();
1144  auto *Phi = cast<MemoryPhi>(&Accesses->front());
1145  if (RenameAllUses) {
1146  bool ReplacementDone = false;
1147  for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
1148  if (Phi->getIncomingBlock(I) == BB) {
1149  Phi->setIncomingValue(I, IncomingVal);
1150  ReplacementDone = true;
1151  }
1152  (void) ReplacementDone;
1153  assert(ReplacementDone && "Incomplete phi during partial rename");
1154  } else
1155  Phi->addIncoming(IncomingVal, BB);
1156  }
1157 }
1158 
1159 /// Rename a single basic block into MemorySSA form.
1160 /// Uses the standard SSA renaming algorithm.
1161 /// \returns The new incoming value.
1162 MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal,
1163  bool RenameAllUses) {
1164  auto It = PerBlockAccesses.find(BB);
1165  // Skip most processing if the list is empty.
1166  if (It != PerBlockAccesses.end()) {
1167  AccessList *Accesses = It->second.get();
1168  for (MemoryAccess &L : *Accesses) {
1169  if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&L)) {
1170  if (MUD->getDefiningAccess() == nullptr || RenameAllUses)
1171  MUD->setDefiningAccess(IncomingVal);
1172  if (isa<MemoryDef>(&L))
1173  IncomingVal = &L;
1174  } else {
1175  IncomingVal = &L;
1176  }
1177  }
1178  }
1179  return IncomingVal;
1180 }
1181 
1182 /// This is the standard SSA renaming algorithm.
1183 ///
1184 /// We walk the dominator tree in preorder, renaming accesses, and then filling
1185 /// in phi nodes in our successors.
1186 void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
1188  bool SkipVisited, bool RenameAllUses) {
1189  assert(Root && "Trying to rename accesses in an unreachable block");
1190 
1192  // Skip everything if we already renamed this block and we are skipping.
1193  // Note: You can't sink this into the if, because we need it to occur
1194  // regardless of whether we skip blocks or not.
1195  bool AlreadyVisited = !Visited.insert(Root->getBlock()).second;
1196  if (SkipVisited && AlreadyVisited)
1197  return;
1198 
1199  IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses);
1200  renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses);
1201  WorkStack.push_back({Root, Root->begin(), IncomingVal});
1202 
1203  while (!WorkStack.empty()) {
1204  DomTreeNode *Node = WorkStack.back().DTN;
1205  DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
1206  IncomingVal = WorkStack.back().IncomingVal;
1207 
1208  if (ChildIt == Node->end()) {
1209  WorkStack.pop_back();
1210  } else {
1211  DomTreeNode *Child = *ChildIt;
1212  ++WorkStack.back().ChildIt;
1213  BasicBlock *BB = Child->getBlock();
1214  // Note: You can't sink this into the if, because we need it to occur
1215  // regardless of whether we skip blocks or not.
1216  AlreadyVisited = !Visited.insert(BB).second;
1217  if (SkipVisited && AlreadyVisited) {
1218  // We already visited this during our renaming, which can happen when
1219  // being asked to rename multiple blocks. Figure out the incoming val,
1220  // which is the last def.
1221  // Incoming value can only change if there is a block def, and in that
1222  // case, it's the last block def in the list.
1223  if (auto *BlockDefs = getWritableBlockDefs(BB))
1224  IncomingVal = &*BlockDefs->rbegin();
1225  } else
1226  IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1227  renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1228  WorkStack.push_back({Child, Child->begin(), IncomingVal});
1229  }
1230  }
1231 }
1232 
1233 /// This handles unreachable block accesses by deleting phi nodes in
1234 /// unreachable blocks, and marking all other unreachable MemoryAccess's as
1235 /// being uses of the live on entry definition.
1236 void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
1237  assert(!DT->isReachableFromEntry(BB) &&
1238  "Reachable block found while handling unreachable blocks");
1239 
1240  // Make sure phi nodes in our reachable successors end up with a
1241  // LiveOnEntryDef for our incoming edge, even though our block is forward
1242  // unreachable. We could just disconnect these blocks from the CFG fully,
1243  // but we do not right now.
1244  for (const BasicBlock *S : successors(BB)) {
1245  if (!DT->isReachableFromEntry(S))
1246  continue;
1247  auto It = PerBlockAccesses.find(S);
1248  // Rename the phi nodes in our successor block
1249  if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
1250  continue;
1251  AccessList *Accesses = It->second.get();
1252  auto *Phi = cast<MemoryPhi>(&Accesses->front());
1253  Phi->addIncoming(LiveOnEntryDef.get(), BB);
1254  }
1255 
1256  auto It = PerBlockAccesses.find(BB);
1257  if (It == PerBlockAccesses.end())
1258  return;
1259 
1260  auto &Accesses = It->second;
1261  for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1262  auto Next = std::next(AI);
1263  // If we have a phi, just remove it. We are going to replace all
1264  // users with live on entry.
1265  if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
1266  UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1267  else
1268  Accesses->erase(AI);
1269  AI = Next;
1270  }
1271 }
1272 
1274  : DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1275  SkipWalker(nullptr) {
1276  // Build MemorySSA using a batch alias analysis. This reuses the internal
1277  // state that AA collects during an alias()/getModRefInfo() call. This is
1278  // safe because there are no CFG changes while building MemorySSA and can
1279  // significantly reduce the time spent by the compiler in AA, because we will
1280  // make queries about all the instructions in the Function.
1281  assert(AA && "No alias analysis?");
1282  BatchAAResults BatchAA(*AA);
1283  buildMemorySSA(BatchAA);
1284  // Intentionally leave AA to nullptr while building so we don't accidently
1285  // use non-batch AliasAnalysis.
1286  this->AA = AA;
1287  // Also create the walker here.
1288  getWalker();
1289 }
1290 
1292  // Drop all our references
1293  for (const auto &Pair : PerBlockAccesses)
1294  for (MemoryAccess &MA : *Pair.second)
1295  MA.dropAllReferences();
1296 }
1297 
1298 MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) {
1299  auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr));
1300 
1301  if (Res.second)
1302  Res.first->second = std::make_unique<AccessList>();
1303  return Res.first->second.get();
1304 }
1305 
1306 MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) {
1307  auto Res = PerBlockDefs.insert(std::make_pair(BB, nullptr));
1308 
1309  if (Res.second)
1310  Res.first->second = std::make_unique<DefsList>();
1311  return Res.first->second.get();
1312 }
1313 
1314 namespace llvm {
1315 
1316 /// This class is a batch walker of all MemoryUse's in the program, and points
1317 /// their defining access at the thing that actually clobbers them. Because it
1318 /// is a batch walker that touches everything, it does not operate like the
1319 /// other walkers. This walker is basically performing a top-down SSA renaming
1320 /// pass, where the version stack is used as the cache. This enables it to be
1321 /// significantly more time and memory efficient than using the regular walker,
1322 /// which is walking bottom-up.
1324 public:
1325  OptimizeUses(MemorySSA *MSSA, CachingWalker<BatchAAResults> *Walker,
1326  BatchAAResults *BAA, DominatorTree *DT)
1327  : MSSA(MSSA), Walker(Walker), AA(BAA), DT(DT) {}
1328 
1329  void optimizeUses();
1330 
1331 private:
1332  /// This represents where a given memorylocation is in the stack.
1333  struct MemlocStackInfo {
1334  // This essentially is keeping track of versions of the stack. Whenever
1335  // the stack changes due to pushes or pops, these versions increase.
1336  unsigned long StackEpoch;
1337  unsigned long PopEpoch;
1338  // This is the lower bound of places on the stack to check. It is equal to
1339  // the place the last stack walk ended.
1340  // Note: Correctness depends on this being initialized to 0, which densemap
1341  // does
1342  unsigned long LowerBound;
1343  const BasicBlock *LowerBoundBlock;
1344  // This is where the last walk for this memory location ended.
1345  unsigned long LastKill;
1346  bool LastKillValid;
1348  };
1349 
1350  void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
1353 
1354  MemorySSA *MSSA;
1355  CachingWalker<BatchAAResults> *Walker;
1356  BatchAAResults *AA;
1357  DominatorTree *DT;
1358 };
1359 
1360 } // end namespace llvm
1361 
1362 /// Optimize the uses in a given block This is basically the SSA renaming
1363 /// algorithm, with one caveat: We are able to use a single stack for all
1364 /// MemoryUses. This is because the set of *possible* reaching MemoryDefs is
1365 /// the same for every MemoryUse. The *actual* clobbering MemoryDef is just
1366 /// going to be some position in that stack of possible ones.
1367 ///
1368 /// We track the stack positions that each MemoryLocation needs
1369 /// to check, and last ended at. This is because we only want to check the
1370 /// things that changed since last time. The same MemoryLocation should
1371 /// get clobbered by the same store (getModRefInfo does not use invariantness or
1372 /// things like this, and if they start, we can modify MemoryLocOrCall to
1373 /// include relevant data)
1374 void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1375  const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch,
1376  SmallVectorImpl<MemoryAccess *> &VersionStack,
1378 
1379  /// If no accesses, nothing to do.
1381  if (Accesses == nullptr)
1382  return;
1383 
1384  // Pop everything that doesn't dominate the current block off the stack,
1385  // increment the PopEpoch to account for this.
1386  while (true) {
1387  assert(
1388  !VersionStack.empty() &&
1389  "Version stack should have liveOnEntry sentinel dominating everything");
1390  BasicBlock *BackBlock = VersionStack.back()->getBlock();
1391  if (DT->dominates(BackBlock, BB))
1392  break;
1393  while (VersionStack.back()->getBlock() == BackBlock)
1394  VersionStack.pop_back();
1395  ++PopEpoch;
1396  }
1397 
1398  for (MemoryAccess &MA : *Accesses) {
1399  auto *MU = dyn_cast<MemoryUse>(&MA);
1400  if (!MU) {
1401  VersionStack.push_back(&MA);
1402  ++StackEpoch;
1403  continue;
1404  }
1405 
1406  if (MU->isOptimized())
1407  continue;
1408 
1409  if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) {
1410  MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true, None);
1411  continue;
1412  }
1413 
1414  MemoryLocOrCall UseMLOC(MU);
1415  auto &LocInfo = LocStackInfo[UseMLOC];
1416  // If the pop epoch changed, it means we've removed stuff from top of
1417  // stack due to changing blocks. We may have to reset the lower bound or
1418  // last kill info.
1419  if (LocInfo.PopEpoch != PopEpoch) {
1420  LocInfo.PopEpoch = PopEpoch;
1421  LocInfo.StackEpoch = StackEpoch;
1422  // If the lower bound was in something that no longer dominates us, we
1423  // have to reset it.
1424  // We can't simply track stack size, because the stack may have had
1425  // pushes/pops in the meantime.
1426  // XXX: This is non-optimal, but only is slower cases with heavily
1427  // branching dominator trees. To get the optimal number of queries would
1428  // be to make lowerbound and lastkill a per-loc stack, and pop it until
1429  // the top of that stack dominates us. This does not seem worth it ATM.
1430  // A much cheaper optimization would be to always explore the deepest
1431  // branch of the dominator tree first. This will guarantee this resets on
1432  // the smallest set of blocks.
1433  if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1434  !DT->dominates(LocInfo.LowerBoundBlock, BB)) {
1435  // Reset the lower bound of things to check.
1436  // TODO: Some day we should be able to reset to last kill, rather than
1437  // 0.
1438  LocInfo.LowerBound = 0;
1439  LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1440  LocInfo.LastKillValid = false;
1441  }
1442  } else if (LocInfo.StackEpoch != StackEpoch) {
1443  // If all that has changed is the StackEpoch, we only have to check the
1444  // new things on the stack, because we've checked everything before. In
1445  // this case, the lower bound of things to check remains the same.
1446  LocInfo.PopEpoch = PopEpoch;
1447  LocInfo.StackEpoch = StackEpoch;
1448  }
1449  if (!LocInfo.LastKillValid) {
1450  LocInfo.LastKill = VersionStack.size() - 1;
1451  LocInfo.LastKillValid = true;
1452  LocInfo.AR = AliasResult::MayAlias;
1453  }
1454 
1455  // At this point, we should have corrected last kill and LowerBound to be
1456  // in bounds.
1457  assert(LocInfo.LowerBound < VersionStack.size() &&
1458  "Lower bound out of range");
1459  assert(LocInfo.LastKill < VersionStack.size() &&
1460  "Last kill info out of range");
1461  // In any case, the new upper bound is the top of the stack.
1462  unsigned long UpperBound = VersionStack.size() - 1;
1463 
1464  if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
1465  LLVM_DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " ("
1466  << *(MU->getMemoryInst()) << ")"
1467  << " because there are "
1468  << UpperBound - LocInfo.LowerBound
1469  << " stores to disambiguate\n");
1470  // Because we did not walk, LastKill is no longer valid, as this may
1471  // have been a kill.
1472  LocInfo.LastKillValid = false;
1473  continue;
1474  }
1475  bool FoundClobberResult = false;
1476  unsigned UpwardWalkLimit = MaxCheckLimit;
1477  while (UpperBound > LocInfo.LowerBound) {
1478  if (isa<MemoryPhi>(VersionStack[UpperBound])) {
1479  // For phis, use the walker, see where we ended up, go there.
1480  // The invariant.group handling in MemorySSA is ad-hoc and doesn't
1481  // support updates, so don't use it to optimize uses.
1482  MemoryAccess *Result =
1483  Walker->getClobberingMemoryAccessWithoutInvariantGroup(
1484  MU, UpwardWalkLimit);
1485  // We are guaranteed to find it or something is wrong.
1486  while (VersionStack[UpperBound] != Result) {
1487  assert(UpperBound != 0);
1488  --UpperBound;
1489  }
1490  FoundClobberResult = true;
1491  break;
1492  }
1493 
1494  MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
1495  ClobberAlias CA = instructionClobbersQuery(MD, MU, UseMLOC, *AA);
1496  if (CA.IsClobber) {
1497  FoundClobberResult = true;
1498  LocInfo.AR = CA.AR;
1499  break;
1500  }
1501  --UpperBound;
1502  }
1503 
1504  // Note: Phis always have AliasResult AR set to MayAlias ATM.
1505 
1506  // At the end of this loop, UpperBound is either a clobber, or lower bound
1507  // PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
1508  if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1509  // We were last killed now by where we got to
1510  if (MSSA->isLiveOnEntryDef(VersionStack[UpperBound]))
1511  LocInfo.AR = None;
1512  MU->setDefiningAccess(VersionStack[UpperBound], true, LocInfo.AR);
1513  LocInfo.LastKill = UpperBound;
1514  } else {
1515  // Otherwise, we checked all the new ones, and now we know we can get to
1516  // LastKill.
1517  MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true, LocInfo.AR);
1518  }
1519  LocInfo.LowerBound = VersionStack.size() - 1;
1520  LocInfo.LowerBoundBlock = BB;
1521  }
1522 }
1523 
1524 /// Optimize uses to point to their actual clobbering definitions.
1526  SmallVector<MemoryAccess *, 16> VersionStack;
1528  VersionStack.push_back(MSSA->getLiveOnEntryDef());
1529 
1530  unsigned long StackEpoch = 1;
1531  unsigned long PopEpoch = 1;
1532  // We perform a non-recursive top-down dominator tree walk.
1533  for (const auto *DomNode : depth_first(DT->getRootNode()))
1534  optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1535  LocStackInfo);
1536 }
1537 
1538 void MemorySSA::placePHINodes(
1539  const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
1540  // Determine where our MemoryPhi's should go
1541  ForwardIDFCalculator IDFs(*DT);
1542  IDFs.setDefiningBlocks(DefiningBlocks);
1544  IDFs.calculate(IDFBlocks);
1545 
1546  // Now place MemoryPhi nodes.
1547  for (auto &BB : IDFBlocks)
1548  createMemoryPhi(BB);
1549 }
1550 
1551 void MemorySSA::buildMemorySSA(BatchAAResults &BAA) {
1552  // We create an access to represent "live on entry", for things like
1553  // arguments or users of globals, where the memory they use is defined before
1554  // the beginning of the function. We do not actually insert it into the IR.
1555  // We do not define a live on exit for the immediate uses, and thus our
1556  // semantics do *not* imply that something with no immediate uses can simply
1557  // be removed.
1558  BasicBlock &StartingPoint = F.getEntryBlock();
1559  LiveOnEntryDef.reset(new MemoryDef(F.getContext(), nullptr, nullptr,
1560  &StartingPoint, NextID++));
1561 
1562  // We maintain lists of memory accesses per-block, trading memory for time. We
1563  // could just look up the memory access for every possible instruction in the
1564  // stream.
1565  SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
1566  // Go through each block, figure out where defs occur, and chain together all
1567  // the accesses.
1568  for (BasicBlock &B : F) {
1569  bool InsertIntoDef = false;
1570  AccessList *Accesses = nullptr;
1571  DefsList *Defs = nullptr;
1572  for (Instruction &I : B) {
1573  MemoryUseOrDef *MUD = createNewAccess(&I, &BAA);
1574  if (!MUD)
1575  continue;
1576 
1577  if (!Accesses)
1578  Accesses = getOrCreateAccessList(&B);
1579  Accesses->push_back(MUD);
1580  if (isa<MemoryDef>(MUD)) {
1581  InsertIntoDef = true;
1582  if (!Defs)
1583  Defs = getOrCreateDefsList(&B);
1584  Defs->push_back(*MUD);
1585  }
1586  }
1587  if (InsertIntoDef)
1588  DefiningBlocks.insert(&B);
1589  }
1590  placePHINodes(DefiningBlocks);
1591 
1592  // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
1593  // filled in with all blocks.
1595  renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
1596 
1597  // Mark the uses in unreachable blocks as live on entry, so that they go
1598  // somewhere.
1599  for (auto &BB : F)
1600  if (!Visited.count(&BB))
1601  markUnreachableAsLiveOnEntry(&BB);
1602 }
1603 
1604 MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
1605 
1606 MemorySSA::CachingWalker<AliasAnalysis> *MemorySSA::getWalkerImpl() {
1607  if (Walker)
1608  return Walker.get();
1609 
1610  if (!WalkerBase)
1611  WalkerBase =
1612  std::make_unique<ClobberWalkerBase<AliasAnalysis>>(this, AA, DT);
1613 
1614  Walker =
1615  std::make_unique<CachingWalker<AliasAnalysis>>(this, WalkerBase.get());
1616  return Walker.get();
1617 }
1618 
1620  if (SkipWalker)
1621  return SkipWalker.get();
1622 
1623  if (!WalkerBase)
1624  WalkerBase =
1625  std::make_unique<ClobberWalkerBase<AliasAnalysis>>(this, AA, DT);
1626 
1627  SkipWalker =
1628  std::make_unique<SkipSelfWalker<AliasAnalysis>>(this, WalkerBase.get());
1629  return SkipWalker.get();
1630  }
1631 
1632 
1633 // This is a helper function used by the creation routines. It places NewAccess
1634 // into the access and defs lists for a given basic block, at the given
1635 // insertion point.
1637  const BasicBlock *BB,
1638  InsertionPlace Point) {
1639  auto *Accesses = getOrCreateAccessList(BB);
1640  if (Point == Beginning) {
1641  // If it's a phi node, it goes first, otherwise, it goes after any phi
1642  // nodes.
1643  if (isa<MemoryPhi>(NewAccess)) {
1644  Accesses->push_front(NewAccess);
1645  auto *Defs = getOrCreateDefsList(BB);
1646  Defs->push_front(*NewAccess);
1647  } else {
1648  auto AI = find_if_not(
1649  *Accesses, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); });
1650  Accesses->insert(AI, NewAccess);
1651  if (!isa<MemoryUse>(NewAccess)) {
1652  auto *Defs = getOrCreateDefsList(BB);
1653  auto DI = find_if_not(
1654  *Defs, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); });
1655  Defs->insert(DI, *NewAccess);
1656  }
1657  }
1658  } else {
1659  Accesses->push_back(NewAccess);
1660  if (!isa<MemoryUse>(NewAccess)) {
1661  auto *Defs = getOrCreateDefsList(BB);
1662  Defs->push_back(*NewAccess);
1663  }
1664  }
1665  BlockNumberingValid.erase(BB);
1666 }
1667 
1669  AccessList::iterator InsertPt) {
1670  auto *Accesses = getWritableBlockAccesses(BB);
1671  bool WasEnd = InsertPt == Accesses->end();
1672  Accesses->insert(AccessList::iterator(InsertPt), What);
1673  if (!isa<MemoryUse>(What)) {
1674  auto *Defs = getOrCreateDefsList(BB);
1675  // If we got asked to insert at the end, we have an easy job, just shove it
1676  // at the end. If we got asked to insert before an existing def, we also get
1677  // an iterator. If we got asked to insert before a use, we have to hunt for
1678  // the next def.
1679  if (WasEnd) {
1680  Defs->push_back(*What);
1681  } else if (isa<MemoryDef>(InsertPt)) {
1682  Defs->insert(InsertPt->getDefsIterator(), *What);
1683  } else {
1684  while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt))
1685  ++InsertPt;
1686  // Either we found a def, or we are inserting at the end
1687  if (InsertPt == Accesses->end())
1688  Defs->push_back(*What);
1689  else
1690  Defs->insert(InsertPt->getDefsIterator(), *What);
1691  }
1692  }
1693  BlockNumberingValid.erase(BB);
1694 }
1695 
1696 void MemorySSA::prepareForMoveTo(MemoryAccess *What, BasicBlock *BB) {
1697  // Keep it in the lookup tables, remove from the lists
1698  removeFromLists(What, false);
1699 
1700  // Note that moving should implicitly invalidate the optimized state of a
1701  // MemoryUse (and Phis can't be optimized). However, it doesn't do so for a
1702  // MemoryDef.
1703  if (auto *MD = dyn_cast<MemoryDef>(What))
1704  MD->resetOptimized();
1705  What->setBlock(BB);
1706 }
1707 
1708 // Move What before Where in the IR. The end result is that What will belong to
1709 // the right lists and have the right Block set, but will not otherwise be
1710 // correct. It will not have the right defining access, and if it is a def,
1711 // things below it will not properly be updated.
1713  AccessList::iterator Where) {
1714  prepareForMoveTo(What, BB);
1715  insertIntoListsBefore(What, BB, Where);
1716 }
1717 
1719  InsertionPlace Point) {
1720  if (isa<MemoryPhi>(What)) {
1721  assert(Point == Beginning &&
1722  "Can only move a Phi at the beginning of the block");
1723  // Update lookup table entry
1724  ValueToMemoryAccess.erase(What->getBlock());
1725  bool Inserted = ValueToMemoryAccess.insert({BB, What}).second;
1726  (void)Inserted;
1727  assert(Inserted && "Cannot move a Phi to a block that already has one");
1728  }
1729 
1730  prepareForMoveTo(What, BB);
1731  insertIntoListsForBlock(What, BB, Point);
1732 }
1733 
1734 MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
1735  assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
1736  MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
1737  // Phi's always are placed at the front of the block.
1739  ValueToMemoryAccess[BB] = Phi;
1740  return Phi;
1741 }
1742 
1744  MemoryAccess *Definition,
1745  const MemoryUseOrDef *Template,
1746  bool CreationMustSucceed) {
1747  assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
1748  MemoryUseOrDef *NewAccess = createNewAccess(I, AA, Template);
1749  if (CreationMustSucceed)
1750  assert(NewAccess != nullptr && "Tried to create a memory access for a "
1751  "non-memory touching instruction");
1752  if (NewAccess) {
1753  assert((!Definition || !isa<MemoryUse>(Definition)) &&
1754  "A use cannot be a defining access");
1755  NewAccess->setDefiningAccess(Definition);
1756  }
1757  return NewAccess;
1758 }
1759 
1760 // Return true if the instruction has ordering constraints.
1761 // Note specifically that this only considers stores and loads
1762 // because others are still considered ModRef by getModRefInfo.
1763 static inline bool isOrdered(const Instruction *I) {
1764  if (auto *SI = dyn_cast<StoreInst>(I)) {
1765  if (!SI->isUnordered())
1766  return true;
1767  } else if (auto *LI = dyn_cast<LoadInst>(I)) {
1768  if (!LI->isUnordered())
1769  return true;
1770  }
1771  return false;
1772 }
1773 
1774 /// Helper function to create new memory accesses
1775 template <typename AliasAnalysisType>
1776 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
1777  AliasAnalysisType *AAP,
1778  const MemoryUseOrDef *Template) {
1779  // The assume intrinsic has a control dependency which we model by claiming
1780  // that it writes arbitrarily. Debuginfo intrinsics may be considered
1781  // clobbers when we have a nonstandard AA pipeline. Ignore these fake memory
1782  // dependencies here.
1783  // FIXME: Replace this special casing with a more accurate modelling of
1784  // assume's control dependency.
1785  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1786  switch (II->getIntrinsicID()) {
1787  default:
1788  break;
1789  case Intrinsic::assume:
1790  case Intrinsic::experimental_noalias_scope_decl:
1791  case Intrinsic::pseudoprobe:
1792  return nullptr;
1793  }
1794  }
1795 
1796  // Using a nonstandard AA pipelines might leave us with unexpected modref
1797  // results for I, so add a check to not model instructions that may not read
1798  // from or write to memory. This is necessary for correctness.
1799  if (!I->mayReadFromMemory() && !I->mayWriteToMemory())
1800  return nullptr;
1801 
1802  bool Def, Use;
1803  if (Template) {
1804  Def = isa<MemoryDef>(Template);
1805  Use = isa<MemoryUse>(Template);
1806 #if !defined(NDEBUG)
1807  ModRefInfo ModRef = AAP->getModRefInfo(I, None);
1808  bool DefCheck, UseCheck;
1809  DefCheck = isModSet(ModRef) || isOrdered(I);
1810  UseCheck = isRefSet(ModRef);
1811  assert(Def == DefCheck && (Def || Use == UseCheck) && "Invalid template");
1812 #endif
1813  } else {
1814  // Find out what affect this instruction has on memory.
1815  ModRefInfo ModRef = AAP->getModRefInfo(I, None);
1816  // The isOrdered check is used to ensure that volatiles end up as defs
1817  // (atomics end up as ModRef right now anyway). Until we separate the
1818  // ordering chain from the memory chain, this enables people to see at least
1819  // some relative ordering to volatiles. Note that getClobberingMemoryAccess
1820  // will still give an answer that bypasses other volatile loads. TODO:
1821  // Separate memory aliasing and ordering into two different chains so that
1822  // we can precisely represent both "what memory will this read/write/is
1823  // clobbered by" and "what instructions can I move this past".
1824  Def = isModSet(ModRef) || isOrdered(I);
1825  Use = isRefSet(ModRef);
1826  }
1827 
1828  // It's possible for an instruction to not modify memory at all. During
1829  // construction, we ignore them.
1830  if (!Def && !Use)
1831  return nullptr;
1832 
1833  MemoryUseOrDef *MUD;
1834  if (Def)
1835  MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
1836  else
1837  MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
1838  ValueToMemoryAccess[I] = MUD;
1839  return MUD;
1840 }
1841 
1842 /// Properly remove \p MA from all of MemorySSA's lookup tables.
1844  assert(MA->use_empty() &&
1845  "Trying to remove memory access that still has uses");
1846  BlockNumbering.erase(MA);
1847  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1848  MUD->setDefiningAccess(nullptr);
1849  // Invalidate our walker's cache if necessary
1850  if (!isa<MemoryUse>(MA))
1851  getWalker()->invalidateInfo(MA);
1852 
1853  Value *MemoryInst;
1854  if (const auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1855  MemoryInst = MUD->getMemoryInst();
1856  else
1857  MemoryInst = MA->getBlock();
1858 
1859  auto VMA = ValueToMemoryAccess.find(MemoryInst);
1860  if (VMA->second == MA)
1861  ValueToMemoryAccess.erase(VMA);
1862 }
1863 
1864 /// Properly remove \p MA from all of MemorySSA's lists.
1865 ///
1866 /// Because of the way the intrusive list and use lists work, it is important to
1867 /// do removal in the right order.
1868 /// ShouldDelete defaults to true, and will cause the memory access to also be
1869 /// deleted, not just removed.
1870 void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
1871  BasicBlock *BB = MA->getBlock();
1872  // The access list owns the reference, so we erase it from the non-owning list
1873  // first.
1874  if (!isa<MemoryUse>(MA)) {
1875  auto DefsIt = PerBlockDefs.find(BB);
1876  std::unique_ptr<DefsList> &Defs = DefsIt->second;
1877  Defs->remove(*MA);
1878  if (Defs->empty())
1879  PerBlockDefs.erase(DefsIt);
1880  }
1881 
1882  // The erase call here will delete it. If we don't want it deleted, we call
1883  // remove instead.
1884  auto AccessIt = PerBlockAccesses.find(BB);
1885  std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1886  if (ShouldDelete)
1887  Accesses->erase(MA);
1888  else
1889  Accesses->remove(MA);
1890 
1891  if (Accesses->empty()) {
1892  PerBlockAccesses.erase(AccessIt);
1893  BlockNumberingValid.erase(BB);
1894  }
1895 }
1896 
1898  MemorySSAAnnotatedWriter Writer(this);
1899  F.print(OS, &Writer);
1900 }
1901 
1902 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1904 #endif
1905 
1907 #if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
1909 #endif
1910 
1911 #ifndef NDEBUG
1914  if (VL == VerificationLevel::Full)
1916 #endif
1917  // Previously, the verification used to also verify that the clobberingAccess
1918  // cached by MemorySSA is the same as the clobberingAccess found at a later
1919  // query to AA. This does not hold true in general due to the current fragility
1920  // of BasicAA which has arbitrary caps on the things it analyzes before giving
1921  // up. As a result, transformations that are correct, will lead to BasicAA
1922  // returning different Alias answers before and after that transformation.
1923  // Invalidating MemorySSA is not an option, as the results in BasicAA can be so
1924  // random, in the worst case we'd need to rebuild MemorySSA from scratch after
1925  // every transformation, which defeats the purpose of using it. For such an
1926  // example, see test4 added in D51960.
1927 }
1928 
1930  for (const BasicBlock &BB : F) {
1931  if (MemoryPhi *Phi = getMemoryAccess(&BB)) {
1932  for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1933  auto *Pred = Phi->getIncomingBlock(I);
1934  auto *IncAcc = Phi->getIncomingValue(I);
1935  // If Pred has no unreachable predecessors, get last def looking at
1936  // IDoms. If, while walkings IDoms, any of these has an unreachable
1937  // predecessor, then the incoming def can be any access.
1938  if (auto *DTNode = DT->getNode(Pred)) {
1939  while (DTNode) {
1940  if (auto *DefList = getBlockDefs(DTNode->getBlock())) {
1941  auto *LastAcc = &*(--DefList->end());
1942  assert(LastAcc == IncAcc &&
1943  "Incorrect incoming access into phi.");
1944  (void)IncAcc;
1945  (void)LastAcc;
1946  break;
1947  }
1948  DTNode = DTNode->getIDom();
1949  }
1950  } else {
1951  // If Pred has unreachable predecessors, but has at least a Def, the
1952  // incoming access can be the last Def in Pred, or it could have been
1953  // optimized to LoE. After an update, though, the LoE may have been
1954  // replaced by another access, so IncAcc may be any access.
1955  // If Pred has unreachable predecessors and no Defs, incoming access
1956  // should be LoE; However, after an update, it may be any access.
1957  }
1958  }
1959  }
1960  }
1961 }
1962 
1963 /// Verify that all of the blocks we believe to have valid domination numbers
1964 /// actually have valid domination numbers.
1966  if (BlockNumberingValid.empty())
1967  return;
1968 
1969  SmallPtrSet<const BasicBlock *, 16> ValidBlocks = BlockNumberingValid;
1970  for (const BasicBlock &BB : F) {
1971  if (!ValidBlocks.count(&BB))
1972  continue;
1973 
1974  ValidBlocks.erase(&BB);
1975 
1976  const AccessList *Accesses = getBlockAccesses(&BB);
1977  // It's correct to say an empty block has valid numbering.
1978  if (!Accesses)
1979  continue;
1980 
1981  // Block numbering starts at 1.
1982  unsigned long LastNumber = 0;
1983  for (const MemoryAccess &MA : *Accesses) {
1984  auto ThisNumberIter = BlockNumbering.find(&MA);
1985  assert(ThisNumberIter != BlockNumbering.end() &&
1986  "MemoryAccess has no domination number in a valid block!");
1987 
1988  unsigned long ThisNumber = ThisNumberIter->second;
1989  assert(ThisNumber > LastNumber &&
1990  "Domination numbers should be strictly increasing!");
1991  (void)LastNumber;
1992  LastNumber = ThisNumber;
1993  }
1994  }
1995 
1996  assert(ValidBlocks.empty() &&
1997  "All valid BasicBlocks should exist in F -- dangling pointers?");
1998 }
1999 
2000 /// Verify ordering: the order and existence of MemoryAccesses matches the
2001 /// order and existence of memory affecting instructions.
2002 /// Verify domination: each definition dominates all of its uses.
2003 /// Verify def-uses: the immediate use information - walk all the memory
2004 /// accesses and verifying that, for each use, it appears in the appropriate
2005 /// def's use list
2007  VerificationLevel VL) const {
2008  // Walk all the blocks, comparing what the lookups think and what the access
2009  // lists think, as well as the order in the blocks vs the order in the access
2010  // lists.
2011  SmallVector<MemoryAccess *, 32> ActualAccesses;
2013  for (BasicBlock &B : F) {
2014  const AccessList *AL = getBlockAccesses(&B);
2015  const auto *DL = getBlockDefs(&B);
2016  MemoryPhi *Phi = getMemoryAccess(&B);
2017  if (Phi) {
2018  // Verify ordering.
2019  ActualAccesses.push_back(Phi);
2020  ActualDefs.push_back(Phi);
2021  // Verify domination
2022  for (const Use &U : Phi->uses()) {
2023  assert(dominates(Phi, U) && "Memory PHI does not dominate it's uses");
2024  (void)U;
2025  }
2026  // Verify def-uses for full verify.
2027  if (VL == VerificationLevel::Full) {
2028  assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance(
2029  pred_begin(&B), pred_end(&B))) &&
2030  "Incomplete MemoryPhi Node");
2031  for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
2032  verifyUseInDefs(Phi->getIncomingValue(I), Phi);
2034  "Incoming phi block not a block predecessor");
2035  }
2036  }
2037  }
2038 
2039  for (Instruction &I : B) {
2041  assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) &&
2042  "We have memory affecting instructions "
2043  "in this block but they are not in the "
2044  "access list or defs list");
2045  if (MA) {
2046  // Verify ordering.
2047  ActualAccesses.push_back(MA);
2048  if (MemoryAccess *MD = dyn_cast<MemoryDef>(MA)) {
2049  // Verify ordering.
2050  ActualDefs.push_back(MA);
2051  // Verify domination.
2052  for (const Use &U : MD->uses()) {
2053  assert(dominates(MD, U) &&
2054  "Memory Def does not dominate it's uses");
2055  (void)U;
2056  }
2057  }
2058  // Verify def-uses for full verify.
2059  if (VL == VerificationLevel::Full)
2060  verifyUseInDefs(MA->getDefiningAccess(), MA);
2061  }
2062  }
2063  // Either we hit the assert, really have no accesses, or we have both
2064  // accesses and an access list. Same with defs.
2065  if (!AL && !DL)
2066  continue;
2067  // Verify ordering.
2068  assert(AL->size() == ActualAccesses.size() &&
2069  "We don't have the same number of accesses in the block as on the "
2070  "access list");
2071  assert((DL || ActualDefs.size() == 0) &&
2072  "Either we should have a defs list, or we should have no defs");
2073  assert((!DL || DL->size() == ActualDefs.size()) &&
2074  "We don't have the same number of defs in the block as on the "
2075  "def list");
2076  auto ALI = AL->begin();
2077  auto AAI = ActualAccesses.begin();
2078  while (ALI != AL->end() && AAI != ActualAccesses.end()) {
2079  assert(&*ALI == *AAI && "Not the same accesses in the same order");
2080  ++ALI;
2081  ++AAI;
2082  }
2083  ActualAccesses.clear();
2084  if (DL) {
2085  auto DLI = DL->begin();
2086  auto ADI = ActualDefs.begin();
2087  while (DLI != DL->end() && ADI != ActualDefs.end()) {
2088  assert(&*DLI == *ADI && "Not the same defs in the same order");
2089  ++DLI;
2090  ++ADI;
2091  }
2092  }
2093  ActualDefs.clear();
2094  }
2095 }
2096 
2097 /// Verify the def-use lists in MemorySSA, by verifying that \p Use
2098 /// appears in the use list of \p Def.
2099 void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const {
2100  // The live on entry use may cause us to get a NULL def here
2101  if (!Def)
2103  "Null def but use not point to live on entry def");
2104  else
2105  assert(is_contained(Def->users(), Use) &&
2106  "Did not find use in def's use list");
2107 }
2108 
2109 /// Perform a local numbering on blocks so that instruction ordering can be
2110 /// determined in constant time.
2111 /// TODO: We currently just number in order. If we numbered by N, we could
2112 /// allow at least N-1 sequences of insertBefore or insertAfter (and at least
2113 /// log2(N) sequences of mixed before and after) without needing to invalidate
2114 /// the numbering.
2115 void MemorySSA::renumberBlock(const BasicBlock *B) const {
2116  // The pre-increment ensures the numbers really start at 1.
2117  unsigned long CurrentNumber = 0;
2118  const AccessList *AL = getBlockAccesses(B);
2119  assert(AL != nullptr && "Asking to renumber an empty block");
2120  for (const auto &I : *AL)
2121  BlockNumbering[&I] = ++CurrentNumber;
2122  BlockNumberingValid.insert(B);
2123 }
2124 
2125 /// Determine, for two memory accesses in the same block,
2126 /// whether \p Dominator dominates \p Dominatee.
2127 /// \returns True if \p Dominator dominates \p Dominatee.
2129  const MemoryAccess *Dominatee) const {
2130  const BasicBlock *DominatorBlock = Dominator->getBlock();
2131 
2132  assert((DominatorBlock == Dominatee->getBlock()) &&
2133  "Asking for local domination when accesses are in different blocks!");
2134  // A node dominates itself.
2135  if (Dominatee == Dominator)
2136  return true;
2137 
2138  // When Dominatee is defined on function entry, it is not dominated by another
2139  // memory access.
2140  if (isLiveOnEntryDef(Dominatee))
2141  return false;
2142 
2143  // When Dominator is defined on function entry, it dominates the other memory
2144  // access.
2145  if (isLiveOnEntryDef(Dominator))
2146  return true;
2147 
2148  if (!BlockNumberingValid.count(DominatorBlock))
2149  renumberBlock(DominatorBlock);
2150 
2151  unsigned long DominatorNum = BlockNumbering.lookup(Dominator);
2152  // All numbers start with 1
2153  assert(DominatorNum != 0 && "Block was not numbered properly");
2154  unsigned long DominateeNum = BlockNumbering.lookup(Dominatee);
2155  assert(DominateeNum != 0 && "Block was not numbered properly");
2156  return DominatorNum < DominateeNum;
2157 }
2158 
2159 bool MemorySSA::dominates(const MemoryAccess *Dominator,
2160  const MemoryAccess *Dominatee) const {
2161  if (Dominator == Dominatee)
2162  return true;
2163 
2164  if (isLiveOnEntryDef(Dominatee))
2165  return false;
2166 
2167  if (Dominator->getBlock() != Dominatee->getBlock())
2168  return DT->dominates(Dominator->getBlock(), Dominatee->getBlock());
2169  return locallyDominates(Dominator, Dominatee);
2170 }
2171 
2172 bool MemorySSA::dominates(const MemoryAccess *Dominator,
2173  const Use &Dominatee) const {
2174  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Dominatee.getUser())) {
2175  BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
2176  // The def must dominate the incoming block of the phi.
2177  if (UseBB != Dominator->getBlock())
2178  return DT->dominates(Dominator->getBlock(), UseBB);
2179  // If the UseBB and the DefBB are the same, compare locally.
2180  return locallyDominates(Dominator, cast<MemoryAccess>(Dominatee));
2181  }
2182  // If it's not a PHI node use, the normal dominates can already handle it.
2183  return dominates(Dominator, cast<MemoryAccess>(Dominatee.getUser()));
2184 }
2185 
2187  if (IsOptimized)
2188  return;
2189 
2190  BatchAAResults BatchAA(*AA);
2191  ClobberWalkerBase<BatchAAResults> WalkerBase(this, &BatchAA, DT);
2192  CachingWalker<BatchAAResults> WalkerLocal(this, &WalkerBase);
2193  OptimizeUses(this, &WalkerLocal, &BatchAA, DT).optimizeUses();
2194  IsOptimized = true;
2195 }
2196 
2198  switch (getValueID()) {
2199  case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
2200  case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);
2201  case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS);
2202  }
2203  llvm_unreachable("invalid value id");
2204 }
2205 
2207  MemoryAccess *UO = getDefiningAccess();
2208 
2209  auto printID = [&OS](MemoryAccess *A) {
2210  if (A && A->getID())
2211  OS << A->getID();
2212  else
2213  OS << LiveOnEntryStr;
2214  };
2215 
2216  OS << getID() << " = MemoryDef(";
2217  printID(UO);
2218  OS << ")";
2219 
2220  if (isOptimized()) {
2221  OS << "->";
2222  printID(getOptimized());
2223 
2224  if (Optional<AliasResult> AR = getOptimizedAccessType())
2225  OS << " " << *AR;
2226  }
2227 }
2228 
2230  ListSeparator LS(",");
2231  OS << getID() << " = MemoryPhi(";
2232  for (const auto &Op : operands()) {
2233  BasicBlock *BB = getIncomingBlock(Op);
2234  MemoryAccess *MA = cast<MemoryAccess>(Op);
2235 
2236  OS << LS << '{';
2237  if (BB->hasName())
2238  OS << BB->getName();
2239  else
2240  BB->printAsOperand(OS, false);
2241  OS << ',';
2242  if (unsigned ID = MA->getID())
2243  OS << ID;
2244  else
2245  OS << LiveOnEntryStr;
2246  OS << '}';
2247  }
2248  OS << ')';
2249 }
2250 
2252  MemoryAccess *UO = getDefiningAccess();
2253  OS << "MemoryUse(";
2254  if (UO && UO->getID())
2255  OS << UO->getID();
2256  else
2257  OS << LiveOnEntryStr;
2258  OS << ')';
2259 
2260  if (Optional<AliasResult> AR = getOptimizedAccessType())
2261  OS << " " << *AR;
2262 }
2263 
2264 void MemoryAccess::dump() const {
2265 // Cannot completely remove virtual function even in release mode.
2266 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2267  print(dbgs());
2268  dbgs() << "\n";
2269 #endif
2270 }
2271 
2273 
2276 }
2277 
2279  AU.setPreservesAll();
2281 }
2282 
2284 private:
2285  const Function &F;
2286  MemorySSAAnnotatedWriter MSSAWriter;
2287 
2288 public:
2290  : F(F), MSSAWriter(&MSSA) {}
2291 
2292  const Function *getFunction() { return &F; }
2293  MemorySSAAnnotatedWriter &getWriter() { return MSSAWriter; }
2294 };
2295 
2296 namespace llvm {
2297 
2298 template <>
2301  return &(CFGInfo->getFunction()->getEntryBlock());
2302  }
2303 
2304  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
2306 
2308  return nodes_iterator(CFGInfo->getFunction()->begin());
2309  }
2310 
2312  return nodes_iterator(CFGInfo->getFunction()->end());
2313  }
2314 
2315  static size_t size(DOTFuncMSSAInfo *CFGInfo) {
2316  return CFGInfo->getFunction()->size();
2317  }
2318 };
2319 
2320 template <>
2322 
2323  DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {}
2324 
2325  static std::string getGraphName(DOTFuncMSSAInfo *CFGInfo) {
2326  return "MSSA CFG for '" + CFGInfo->getFunction()->getName().str() +
2327  "' function";
2328  }
2329 
2330  std::string getNodeLabel(const BasicBlock *Node, DOTFuncMSSAInfo *CFGInfo) {
2332  Node, nullptr,
2333  [CFGInfo](raw_string_ostream &OS, const BasicBlock &BB) -> void {
2334  BB.print(OS, &CFGInfo->getWriter(), true, true);
2335  },
2336  [](std::string &S, unsigned &I, unsigned Idx) -> void {
2337  std::string Str = S.substr(I, Idx - I);
2338  StringRef SR = Str;
2339  if (SR.count(" = MemoryDef(") || SR.count(" = MemoryPhi(") ||
2340  SR.count("MemoryUse("))
2341  return;
2343  });
2344  }
2345 
2346  static std::string getEdgeSourceLabel(const BasicBlock *Node,
2349  }
2350 
2351  /// Display the raw branch weights from PGO.
2353  DOTFuncMSSAInfo *CFGInfo) {
2354  return "";
2355  }
2356 
2357  std::string getNodeAttributes(const BasicBlock *Node,
2358  DOTFuncMSSAInfo *CFGInfo) {
2359  return getNodeLabel(Node, CFGInfo).find(';') != std::string::npos
2360  ? "style=filled, fillcolor=lightpink"
2361  : "";
2362  }
2363 };
2364 
2365 } // namespace llvm
2366 
2368  auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2369  MSSA.ensureOptimizedUses();
2370  if (DotCFGMSSA != "") {
2371  DOTFuncMSSAInfo CFGInfo(F, MSSA);
2372  WriteGraph(&CFGInfo, "", false, "MSSA", DotCFGMSSA);
2373  } else
2374  MSSA.print(dbgs());
2375 
2376  if (VerifyMemorySSA)
2377  MSSA.verifyMemorySSA();
2378  return false;
2379 }
2380 
2382 
2385  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
2386  auto &AA = AM.getResult<AAManager>(F);
2387  return MemorySSAAnalysis::Result(std::make_unique<MemorySSA>(F, &AA, &DT));
2388 }
2389 
2391  Function &F, const PreservedAnalyses &PA,
2393  auto PAC = PA.getChecker<MemorySSAAnalysis>();
2394  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
2395  Inv.invalidate<AAManager>(F, PA) ||
2397 }
2398 
2401  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2402  MSSA.ensureOptimizedUses();
2403  if (DotCFGMSSA != "") {
2404  DOTFuncMSSAInfo CFGInfo(F, MSSA);
2405  WriteGraph(&CFGInfo, "", false, "MSSA", DotCFGMSSA);
2406  } else {
2407  OS << "MemorySSA for function: " << F.getName() << "\n";
2408  MSSA.print(OS);
2409  }
2410 
2411  return PreservedAnalyses::all();
2412 }
2413 
2416  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
2417  OS << "MemorySSA (walker) for function: " << F.getName() << "\n";
2418  MemorySSAWalkerAnnotatedWriter Writer(&MSSA);
2419  F.print(OS, &Writer);
2420 
2421  return PreservedAnalyses::all();
2422 }
2423 
2426  AM.getResult<MemorySSAAnalysis>(F).getMSSA().verifyMemorySSA();
2427 
2428  return PreservedAnalyses::all();
2429 }
2430 
2431 char MemorySSAWrapperPass::ID = 0;
2432 
2435 }
2436 
2437 void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); }
2438 
2440  AU.setPreservesAll();
2443 }
2444 
2446  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2447  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2448  MSSA.reset(new MemorySSA(F, &AA, &DT));
2449  return false;
2450 }
2451 
2453  if (VerifyMemorySSA)
2454  MSSA->verifyMemorySSA();
2455 }
2456 
2458  MSSA->print(OS);
2459 }
2460 
2462 
2463 /// Walk the use-def chains starting at \p StartingAccess and find
2464 /// the MemoryAccess that actually clobbers Loc.
2465 ///
2466 /// \returns our clobbering memory access
2467 template <typename AliasAnalysisType>
2468 MemoryAccess *
2469 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
2470  MemoryAccess *StartingAccess, const MemoryLocation &Loc,
2471  unsigned &UpwardWalkLimit) {
2472  assert(!isa<MemoryUse>(StartingAccess) && "Use cannot be defining access");
2473 
2474  Instruction *I = nullptr;
2475  if (auto *StartingUseOrDef = dyn_cast<MemoryUseOrDef>(StartingAccess)) {
2476  if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
2477  return StartingUseOrDef;
2478 
2479  I = StartingUseOrDef->getMemoryInst();
2480 
2481  // Conservatively, fences are always clobbers, so don't perform the walk if
2482  // we hit a fence.
2483  if (!isa<CallBase>(I) && I->isFenceLike())
2484  return StartingUseOrDef;
2485  }
2486 
2487  UpwardsMemoryQuery Q;
2488  Q.OriginalAccess = StartingAccess;
2489  Q.StartingLoc = Loc;
2490  Q.Inst = nullptr;
2491  Q.IsCall = false;
2492 
2493  // Unlike the other function, do not walk to the def of a def, because we are
2494  // handed something we already believe is the clobbering access.
2495  // We never set SkipSelf to true in Q in this method.
2496  MemoryAccess *Clobber =
2497  Walker.findClobber(StartingAccess, Q, UpwardWalkLimit);
2498  LLVM_DEBUG({
2499  dbgs() << "Clobber starting at access " << *StartingAccess << "\n";
2500  if (I)
2501  dbgs() << " for instruction " << *I << "\n";
2502  dbgs() << " is " << *Clobber << "\n";
2503  });
2504  return Clobber;
2505 }
2506 
2507 static const Instruction *
2509  if (!I.hasMetadata(LLVMContext::MD_invariant_group) || I.isVolatile())
2510  return nullptr;
2511 
2512  // We consider bitcasts and zero GEPs to be the same pointer value. Start by
2513  // stripping bitcasts and zero GEPs, then we will recursively look at loads
2514  // and stores through bitcasts and zero GEPs.
2515  Value *PointerOperand = getLoadStorePointerOperand(&I)->stripPointerCasts();
2516 
2517  // It's not safe to walk the use list of a global value because function
2518  // passes aren't allowed to look outside their functions.
2519  // FIXME: this could be fixed by filtering instructions from outside of
2520  // current function.
2521  if (isa<Constant>(PointerOperand))
2522  return nullptr;
2523 
2524  // Queue to process all pointers that are equivalent to load operand.
2525  SmallVector<const Value *, 8> PointerUsesQueue;
2526  PointerUsesQueue.push_back(PointerOperand);
2527 
2528  const Instruction *MostDominatingInstruction = &I;
2529 
2530  // FIXME: This loop is O(n^2) because dominates can be O(n) and in worst case
2531  // we will see all the instructions. It may not matter in practice. If it
2532  // does, we will have to support MemorySSA construction and updates.
2533  while (!PointerUsesQueue.empty()) {
2534  const Value *Ptr = PointerUsesQueue.pop_back_val();
2535  assert(Ptr && !isa<GlobalValue>(Ptr) &&
2536  "Null or GlobalValue should not be inserted");
2537 
2538  for (const User *Us : Ptr->users()) {
2539  auto *U = dyn_cast<Instruction>(Us);
2540  if (!U || U == &I || !DT.dominates(U, MostDominatingInstruction))
2541  continue;
2542 
2543  // Add bitcasts and zero GEPs to queue.
2544  if (isa<BitCastInst>(U)) {
2545  PointerUsesQueue.push_back(U);
2546  continue;
2547  }
2548  if (auto *GEP = dyn_cast<GetElementPtrInst>(U)) {
2549  if (GEP->hasAllZeroIndices())
2550  PointerUsesQueue.push_back(U);
2551  continue;
2552  }
2553 
2554  // If we hit a load/store with an invariant.group metadata and the same
2555  // pointer operand, we can assume that value pointed to by the pointer
2556  // operand didn't change.
2557  if (U->hasMetadata(LLVMContext::MD_invariant_group) &&
2558  getLoadStorePointerOperand(U) == Ptr && !U->isVolatile()) {
2559  MostDominatingInstruction = U;
2560  }
2561  }
2562  }
2563  return MostDominatingInstruction == &I ? nullptr : MostDominatingInstruction;
2564 }
2565 
2566 template <typename AliasAnalysisType>
2567 MemoryAccess *
2568 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
2569  MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf,
2570  bool UseInvariantGroup) {
2571  auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
2572  // If this is a MemoryPhi, we can't do anything.
2573  if (!StartingAccess)
2574  return MA;
2575 
2576  if (UseInvariantGroup) {
2578  *StartingAccess->getMemoryInst(), MSSA->getDomTree())) {
2579  assert(isa<LoadInst>(I) || isa<StoreInst>(I));
2580 
2581  auto *ClobberMA = MSSA->getMemoryAccess(I);
2582  assert(ClobberMA);
2583  if (isa<MemoryUse>(ClobberMA))
2584  return ClobberMA->getDefiningAccess();
2585  return ClobberMA;
2586  }
2587  }
2588 
2589  bool IsOptimized = false;
2590 
2591  // If this is an already optimized use or def, return the optimized result.
2592  // Note: Currently, we store the optimized def result in a separate field,
2593  // since we can't use the defining access.
2594  if (StartingAccess->isOptimized()) {
2595  if (!SkipSelf || !isa<MemoryDef>(StartingAccess))
2596  return StartingAccess->getOptimized();
2597  IsOptimized = true;
2598  }
2599 
2600  const Instruction *I = StartingAccess->getMemoryInst();
2601  // We can't sanely do anything with a fence, since they conservatively clobber
2602  // all memory, and have no locations to get pointers from to try to
2603  // disambiguate.
2604  if (!isa<CallBase>(I) && I->isFenceLike())
2605  return StartingAccess;
2606 
2607  UpwardsMemoryQuery Q(I, StartingAccess);
2608 
2609  if (isUseTriviallyOptimizableToLiveOnEntry(*Walker.getAA(), I)) {
2610  MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
2611  StartingAccess->setOptimized(LiveOnEntry);
2612  StartingAccess->setOptimizedAccessType(None);
2613  return LiveOnEntry;
2614  }
2615 
2616  MemoryAccess *OptimizedAccess;
2617  if (!IsOptimized) {
2618  // Start with the thing we already think clobbers this location
2619  MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2620 
2621  // At this point, DefiningAccess may be the live on entry def.
2622  // If it is, we will not get a better result.
2623  if (MSSA->isLiveOnEntryDef(DefiningAccess)) {
2624  StartingAccess->setOptimized(DefiningAccess);
2625  StartingAccess->setOptimizedAccessType(None);
2626  return DefiningAccess;
2627  }
2628 
2629  OptimizedAccess = Walker.findClobber(DefiningAccess, Q, UpwardWalkLimit);
2630  StartingAccess->setOptimized(OptimizedAccess);
2631  if (MSSA->isLiveOnEntryDef(OptimizedAccess))
2632  StartingAccess->setOptimizedAccessType(None);
2633  else if (Q.AR && *Q.AR == AliasResult::MustAlias)
2634  StartingAccess->setOptimizedAccessType(
2636  } else
2637  OptimizedAccess = StartingAccess->getOptimized();
2638 
2639  LLVM_DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
2640  LLVM_DEBUG(dbgs() << *StartingAccess << "\n");
2641  LLVM_DEBUG(dbgs() << "Optimized Memory SSA clobber for " << *I << " is ");
2642  LLVM_DEBUG(dbgs() << *OptimizedAccess << "\n");
2643 
2645  if (SkipSelf && isa<MemoryPhi>(OptimizedAccess) &&
2646  isa<MemoryDef>(StartingAccess) && UpwardWalkLimit) {
2647  assert(isa<MemoryDef>(Q.OriginalAccess));
2648  Q.SkipSelfAccess = true;
2649  Result = Walker.findClobber(OptimizedAccess, Q, UpwardWalkLimit);
2650  } else
2651  Result = OptimizedAccess;
2652 
2653  LLVM_DEBUG(dbgs() << "Result Memory SSA clobber [SkipSelf = " << SkipSelf);
2654  LLVM_DEBUG(dbgs() << "] for " << *I << " is " << *Result << "\n");
2655 
2656  return Result;
2657 }
2658 
2659 MemoryAccess *
2661  if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
2662  return Use->getDefiningAccess();
2663  return MA;
2664 }
2665 
2667  MemoryAccess *StartingAccess, const MemoryLocation &) {
2668  if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
2669  return Use->getDefiningAccess();
2670  return StartingAccess;
2671 }
2672 
2673 void MemoryPhi::deleteMe(DerivedUser *Self) {
2674  delete static_cast<MemoryPhi *>(Self);
2675 }
2676 
2677 void MemoryDef::deleteMe(DerivedUser *Self) {
2678  delete static_cast<MemoryDef *>(Self);
2679 }
2680 
2681 void MemoryUse::deleteMe(DerivedUser *Self) {
2682  delete static_cast<MemoryUse *>(Self);
2683 }
2684 
2685 bool upward_defs_iterator::IsGuaranteedLoopInvariant(Value *Ptr) const {
2686  auto IsGuaranteedLoopInvariantBase = [](Value *Ptr) {
2687  Ptr = Ptr->stripPointerCasts();
2688  if (!isa<Instruction>(Ptr))
2689  return true;
2690  return isa<AllocaInst>(Ptr);
2691  };
2692 
2693  Ptr = Ptr->stripPointerCasts();
2694  if (auto *I = dyn_cast<Instruction>(Ptr)) {
2695  if (I->getParent()->isEntryBlock())
2696  return true;
2697  }
2698  if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
2699  return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
2700  GEP->hasAllConstantIndices();
2701  }
2702  return IsGuaranteedLoopInvariantBase(Ptr);
2703 }
isOrdered
static bool isOrdered(const Instruction *I)
Definition: MemorySSA.cpp:1763
llvm::SuccIterator
Definition: CFG.h:138
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::BatchAAResults
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
Definition: AliasAnalysis.h:951
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm::GraphTraits< DOTFuncMSSAInfo * >::getEntryNode
static NodeRef getEntryNode(DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2300
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::MemorySSA::verifyMemorySSA
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1906
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::MemorySSA::getWritableBlockDefs
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:828
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::SmallPtrSetImpl::erase
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
Optional.h
llvm::StringRef::count
LLVM_NODISCARD size_t count(char C) const
Return the number of occurrences of C in the string.
Definition: StringRef.h:493
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::Function::end
iterator end()
Definition: Function.h:728
llvm::isModOrRefSet
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:189
IntrinsicInst.h
AtomicOrdering.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
VerifyMemorySSAX
static cl::opt< bool, true > VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA), cl::Hidden, cl::desc("Enable verification of MemorySSA."))
T
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
llvm::AnalysisManager::Invalidator::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:685
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::MemoryDef::resetOptimized
void resetOptimized()
Definition: MemorySSA.h:419
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:632
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:145
llvm::MemorySSA::DefsList
simple_ilist< MemoryAccess, ilist_tag< MSSAHelpers::DefsOnlyTag > > DefsList
Definition: MemorySSA.h:766
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::MemorySSA::OptimizeUses::OptimizeUses
OptimizeUses(MemorySSA *MSSA, CachingWalker< BatchAAResults > *Walker, BatchAAResults *BAA, DominatorTree *DT)
Definition: MemorySSA.cpp:1325
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:242
llvm::User::dropAllReferences
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
TemplateParamKind::Template
@ Template
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::getGraphName
static std::string getGraphName(DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2325
ErrorHandling.h
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:710
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::MemorySSA::dominates
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:2159
llvm::MemoryAccess::getID
unsigned getID() const
Used for debugging and tracking things about MemoryAccesses.
Definition: MemorySSA.h:675
llvm::MemorySSA::renamePass
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
Definition: MemorySSA.h:841
llvm::AtomicOrdering::SequentiallyConsistent
@ SequentiallyConsistent
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
stores
hexagon widen stores
Definition: HexagonStoreWidening.cpp:118
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::MemorySSAWalker::MemorySSAWalker
MemorySSAWalker(MemorySSA *)
Definition: MemorySSA.cpp:2461
to
Should compile to
Definition: README.txt:449
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:320
llvm::MemorySSAWrapperPass::ID
static char ID
Definition: MemorySSA.h:1002
llvm::MemorySSA::insertIntoListsBefore
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator)
Definition: MemorySSA.cpp:1668
DenseMap.h
llvm::MemorySSA::getLiveOnEntryDef
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:755
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::isa
LLVM_NODISCARD bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition: Casting.h:548
llvm::MemorySSA::VerificationLevel
VerificationLevel
Definition: MemorySSA.h:795
llvm::Optional
Definition: APInt.h:33
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
llvm::MemorySSA::VerificationLevel::Full
@ Full
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
DOTFuncMSSAInfo
Definition: MemorySSA.cpp:2283
Operator.h
Hashing.h
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::MemoryPhi
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:493
llvm::MemoryUse::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2251
STLExtras.h
llvm::MemorySSA::~MemorySSA
~MemorySSA()
Definition: MemorySSA.cpp:1291
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::MemoryUse
Represents read-only accesses to memory.
Definition: MemorySSA.h:326
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:182
llvm::DoNothingMemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(MemoryAccess *) override
Does the same thing as getClobberingMemoryAccess(const Instruction *I), but takes a MemoryAccess inst...
Definition: MemorySSA.cpp:2660
memssa
early cse memssa
Definition: EarlyCSE.cpp:1774
llvm::MemorySSA::verifyPrevDefInPhis
void verifyPrevDefInPhis(Function &F) const
Definition: MemorySSA.cpp:1929
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
Use.h
llvm::MemorySSA::print
void print(raw_ostream &) const
Definition: MemorySSA.cpp:1897
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:391
llvm::MemoryPhi::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:554
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::MemorySSAPrinterLegacyPass::ID
static char ID
Definition: MemorySSA.h:943
llvm::MemorySSA::insertIntoListsForBlock
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, InsertionPlace)
Definition: MemorySSA.cpp:1636
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::lltok::equal
@ equal
Definition: LLToken.h:25
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
llvm::isAtLeastOrStrongerThan
bool isAtLeastOrStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Definition: AtomicOrdering.h:105
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
Instruction.h
CommandLine.h
FormattedStream.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
llvm::MemorySSAWrapperPass::MemorySSAWrapperPass
MemorySSAWrapperPass()
Definition: MemorySSA.cpp:2433
memoryssa
memoryssa
Definition: MemorySSA.cpp:73
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::getNodeAttributes
std::string getNodeAttributes(const BasicBlock *Node, DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2357
llvm::MemorySSAPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2399
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:998
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::maximum
LLVM_READONLY APFloat maximum(const APFloat &A, const APFloat &B)
Implements IEEE 754-2018 maximum semantics.
Definition: APFloat.h:1331
llvm::AAResults
Definition: AliasAnalysis.h:511
llvm::MemorySSA::isLiveOnEntryDef
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:751
llvm::MemorySSA::moveTo
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where)
Definition: MemorySSA.cpp:1712
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MemorySSAWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MemorySSA.cpp:2437
llvm::MemorySSAAnalysis::Result
Definition: MemorySSA.h:957
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::DenseMapInfo< MemoryLocOrCall >::isEqual
static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS)
Definition: MemorySSA.cpp:249
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::MemorySSA::Beginning
@ Beginning
Definition: MemorySSA.h:802
llvm::MemorySSAPrinterLegacyPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: MemorySSA.cpp:2367
llvm::MemorySSAWrapperPass::print
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: MemorySSA.cpp:2457
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::MemorySSAWalker::invalidateInfo
virtual void invalidateInfo(MemoryAccess *)
Given a memory access, invalidate anything this walker knows about that access.
Definition: MemorySSA.h:1087
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
DenseSet.h
false
Definition: StackSlotColoring.cpp:141
check
#define check(cond)
llvm::MemorySSAPrinterLegacyPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: MemorySSA.cpp:2278
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
opt
arm prera ldst opt
Definition: ARMLoadStoreOptimizer.cpp:2191
llvm::Instruction
Definition: Instruction.h:42
llvm::MemorySSAAnalysis::run
Result run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2383
llvm::MemoryPhi::addIncoming
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:575
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::AtomicOrdering::Acquire
@ Acquire
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::MemorySSA::getBlockAccesses
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:771
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
llvm::MemorySSA::removeFromLookups
void removeFromLookups(MemoryAccess *)
Properly remove MA from all of MemorySSA's lookup tables.
Definition: MemorySSA.cpp:1843
SmallPtrSet.h
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::MemoryPhi::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: MemorySSA.h:541
llvm::MemoryUseOrDef::getMemoryInst
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition: MemorySSA.h:259
llvm::initializeMemorySSAPrinterLegacyPassPass
void initializeMemorySSAPrinterLegacyPassPass(PassRegistry &)
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:249
llvm::None
const NoneType None
Definition: None.h:24
llvm::MemoryAccess::getBlock
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
llvm::MemorySSAPrinterLegacyPass
Definition: MemorySSA.h:936
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MemorySSAVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2424
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
will
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj obj **nth_el If the i64 division is lowered to a then a safe point will(must) appear for the call site. If a collection occurs
llvm::MemorySSA::locallyDominates
bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
Definition: MemorySSA.cpp:2128
llvm::DOTGraphTraits
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
Definition: DOTGraphTraits.h:166
AssemblyAnnotationWriter.h
llvm::MemoryDef::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2206
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::getNodeLabel
std::string getNodeLabel(const BasicBlock *Node, DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2330
llvm::DenseSet< ConstMemoryAccessPair >
llvm::MemorySSAWalker::getClobberingMemoryAccess
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:1058
llvm::pointer_iterator
Definition: iterator.h:344
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::MemorySSAWrapperPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: MemorySSA.cpp:2445
SSA
Memory SSA
Definition: MemorySSA.cpp:73
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:240
llvm::MemorySSA::dump
void dump() const
Definition: MemorySSA.cpp:1903
CFGPrinter.h
llvm::MemorySSA::verifyOrderingDominationAndDefUses
void verifyOrderingDominationAndDefUses(Function &F, VerificationLevel=VerificationLevel::Fast) const
Verify ordering: the order and existence of MemoryAccesses matches the order and existence of memory ...
Definition: MemorySSA.cpp:2006
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::GraphTraits< DOTFuncMSSAInfo * >::nodes_end
static nodes_iterator nodes_end(DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2311
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::MemoryAccess::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2197
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::iplist_impl< simple_ilist< T, Options... >, ilist_traits< T > >::iterator
base_list_type::iterator iterator
Definition: ilist.h:178
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::def_chain
iterator_range< def_chain_iterator< T > > def_chain(T MA, MemoryAccess *UpTo=nullptr)
Definition: MemorySSA.h:1362
llvm::MemorySSA::OptimizeUses::optimizeUses
void optimizeUses()
Optimize uses to point to their actual clobbering definitions.
Definition: MemorySSA.cpp:1525
MemoryLocation.h
llvm::DenseMap
Definition: DenseMap.h:716
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::getEdgeAttributes
std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I, DOTFuncMSSAInfo *CFGInfo)
Display the raw branch weights from PGO.
Definition: MemorySSA.cpp:2352
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:714
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MemorySSA::getMemoryAccess
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:731
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
StringExtras.h
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::detail::DenseSetImpl::empty
bool empty() const
Definition: DenseSet.h:80
DOTFuncMSSAInfo::getWriter
MemorySSAAnnotatedWriter & getWriter()
Definition: MemorySSA.cpp:2293
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1682
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::getEdgeSourceLabel
static std::string getEdgeSourceLabel(const BasicBlock *Node, const_succ_iterator I)
Definition: MemorySSA.cpp:2346
llvm::MemoryDef
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:386
llvm::MemorySSA::getDomTree
DominatorTree & getDomTree() const
Definition: MemorySSA.h:739
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
llvm::MemorySSA::InsertionPlace
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:802
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
llvm::formatted_raw_ostream
formatted_raw_ostream - A raw_ostream that wraps another one and keeps track of line and column posit...
Definition: FormattedStream.h:30
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:248
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::upward_defs_begin
upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT, bool *PerformedPhiTranslation=nullptr)
Definition: MemorySSA.h:1306
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::IndexedInstrProf::HashT::Last
@ Last
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:335
llvm::IDFCalculator
Definition: IteratedDominanceFrontier.h:39
llvm::WriteGraph
raw_ostream & WriteGraph(raw_ostream &O, const GraphType &G, bool ShortNames=false, const Twine &Title="")
Definition: GraphWriter.h:359
iterator_range.h
llvm::GraphTraits< const BasicBlock * >
Definition: CFG.h:309
llvm::GraphTraits< DOTFuncMSSAInfo * >::size
static size_t size(DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2315
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::MemorySSA::getWalker
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1604
llvm::MemoryPhi::getIncomingValue
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
Definition: MemorySSA.h:544
llvm::MemorySSAWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: MemorySSA.cpp:2439
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::MemorySSA::createDefinedAccess
MemoryUseOrDef * createDefinedAccess(Instruction *, MemoryAccess *, const MemoryUseOrDef *Template=nullptr, bool CreationMustSucceed=true)
Definition: MemorySSA.cpp:1743
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2114
llvm::MemoryAccessPair
std::pair< MemoryAccess *, MemoryLocation > MemoryAccessPair
Definition: MemorySSA.h:1108
MAP
#define MAP(n)
None.h
getInvariantGroupClobberingInstruction
static const Instruction * getInvariantGroupClobberingInstruction(Instruction &I, DominatorTree &DT)
Definition: MemorySSA.cpp:2508
llvm::sys::Memory
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
llvm::DenseMapInfo< MemoryLocOrCall >::getHashValue
static unsigned getHashValue(const MemoryLocOrCall &MLOC)
Definition: MemorySSA.cpp:234
llvm::MemorySSA::getSkipSelfWalker
MemorySSAWalker * getSkipSelfWalker()
Definition: MemorySSA.cpp:1619
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
Printer
Memory true print Memory SSA Printer
Definition: MemorySSA.cpp:80
llvm::simple_ilist::rbegin
reverse_iterator rbegin()
Definition: simple_ilist.h:121
cl
http eax xorl edx cl sete al setne dl sall cl
Definition: README.txt:25
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::MemorySSA::getBlockDefs
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:779
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::DefaultDOTGraphTraits::getEdgeSourceLabel
static std::string getEdgeSourceLabel(const void *, EdgeIter)
getEdgeSourceLabel - If you want to label the edge source itself, implement this method.
Definition: DOTGraphTraits.h:112
Compiler.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::MemoryPhi::setIncomingValue
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:545
llvm::DomTreeNodeBase::begin
iterator begin()
Definition: GenericDomTree.h:75
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::LoadInst::getOrdering
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:225
llvm::MemoryAccess
Definition: MemorySSA.h:142
llvm::DomTreeNodeBase< BasicBlock >
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
consider
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from where P can be anything The alignment inference code cannot handle loads from globals in static non mode because it doesn t look through the extra dyld stub load If you try vec_align ll without relocation you ll see what I mean We should lower which eliminates a constant pool load For consider
Definition: README-SSE.txt:421
llvm::Init
Definition: Record.h:281
llvm::Function::begin
iterator begin()
Definition: Function.h:726
llvm::DenseMapInfo< MemoryLocOrCall >::getEmptyKey
static MemoryLocOrCall getEmptyKey()
Definition: MemorySSA.cpp:226
MaxCheckLimit
Memory true print Memory SSA static false cl::opt< unsigned > MaxCheckLimit("memssa-check-limit", cl::Hidden, cl::init(100), cl::desc("The maximum number of stores/phis MemorySSA" "will consider trying to walk past (default = 100)"))
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:682
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1644
llvm::MemoryAccess::setBlock
void setBlock(BasicBlock *BB)
Used by MemorySSA to change the block of a MemoryAccess when it is moved.
Definition: MemorySSA.h:217
llvm::MemorySSA::OptimizeUses
This class is a batch walker of all MemoryUse's in the program, and points their defining access at t...
Definition: MemorySSA.cpp:1323
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
llvm::MemorySSA::ensureOptimizedUses
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
Definition: MemorySSA.cpp:2186
isUseTriviallyOptimizableToLiveOnEntry
static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA, const Instruction *I)
Definition: MemorySSA.cpp:393
DOTFuncMSSAInfo::getFunction
const Function * getFunction()
Definition: MemorySSA.cpp:2292
GraphWriter.h
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::GraphTraits< DOTFuncMSSAInfo * >::nodes_begin
static nodes_iterator nodes_begin(DOTFuncMSSAInfo *CFGInfo)
Definition: MemorySSA.cpp:2307
llvm::MemoryUseOrDef::getDefiningAccess
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:262
llvm::MemoryPhi::print
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:2229
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::isMustSet
LLVM_NODISCARD bool isMustSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:202
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
areLoadsReorderable
static bool areLoadsReorderable(const LoadInst *Use, const LoadInst *MayClobber)
This does one-way checks to see if Use could theoretically be hoisted above MayClobber.
Definition: MemorySSA.cpp:262
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::AssemblyAnnotationWriter
Definition: AssemblyAnnotationWriter.h:27
checkClobberSanity
static LLVM_ATTRIBUTE_UNUSED void checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt, const MemoryLocation &StartLoc, const MemorySSA &MSSA, const UpwardsMemoryQuery &Query, AliasAnalysisType &AA, bool AllowImpreciseClobber=false)
Verifies that Start is clobbered by ClobberAt, and that nothing inbetween Start and ClobberAt can clo...
Definition: MemorySSA.cpp:419
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
Casting.h
LiveOnEntryStr
const static char LiveOnEntryStr[]
Definition: MemorySSA.cpp:98
Function.h
llvm::MemorySSAWrapperPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: MemorySSA.cpp:2452
PassManager.h
instructionClobbersQuery
static ClobberAlias instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc, const Instruction *UseInst, AliasAnalysisType &AA)
Definition: MemorySSA.cpp:299
llvm::MemorySSA::removeFromLists
void removeFromLists(MemoryAccess *, bool ShouldDelete=true)
Properly remove MA from all of MemorySSA's lists.
Definition: MemorySSA.cpp:1870
llvm::MemoryUseOrDef
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
llvm::cl::value_desc
Definition: CommandLine.h:414
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::MemoryAccess::dump
void dump() const
Definition: MemorySSA.cpp:2264
llvm::MemorySSA::getWritableBlockAccesses
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:822
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
IteratedDominanceFrontier.h
AA
llvm::pred_begin
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
MemorySSA.h
llvm::DomTreeNodeBase< BasicBlock >::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
Instructions.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::LoadInst::isVolatile
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:210
llvm::MemorySSAWalkerPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: MemorySSA.cpp:2414
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:278
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::isRefSet
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:199
Dominators.h
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
N
#define N
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1351
llvm::initializeMemorySSAWrapperPassPass
void initializeMemorySSAWrapperPassPass(PassRegistry &)
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::MemorySSA::MemorySSA
MemorySSA(Function &, AliasAnalysis *, DominatorTree *)
Definition: MemorySSA.cpp:1273
llvm::simple_ilist
A simple intrusive list implementation.
Definition: simple_ilist.h:78
DOTFuncMSSAInfo::DOTFuncMSSAInfo
DOTFuncMSSAInfo(const Function &F, MemorySSA &MSSA)
Definition: MemorySSA.cpp:2289
llvm::MemorySSA::AccessList
iplist< MemoryAccess, ilist_tag< MSSAHelpers::AllAccessTag > > AccessList
Definition: MemorySSA.h:764
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::DefaultDOTGraphTraits
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
Definition: DOTGraphTraits.h:28
DenseMapInfo.h
llvm::MemorySSAAnalysis::Result::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Definition: LoopAnalysisManager.cpp:28
getNodeLabel
static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS)
Definition: ModuleSummaryIndex.cpp:482
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::getLoadStorePointerOperand
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
Definition: Instructions.h:5317
llvm::MemorySSA::verifyDominationNumbers
void verifyDominationNumbers(const Function &F) const
Verify that all of the blocks we believe to have valid domination numbers actually have valid dominat...
Definition: MemorySSA.cpp:1965
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false, true) INITIALIZE_PASS_END(MemorySSAWrapperPass
llvm::upward_defs_end
upward_defs_iterator upward_defs_end()
Definition: MemorySSA.h:1311
llvm::MemorySSAUtil::defClobbersUseOrDef
static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU, AliasAnalysis &AA)
Definition: MemorySSA.cpp:361
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::VerifyMemorySSA
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:91
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::MemorySSAWalker
This is the generic walker interface for walkers of MemorySSA.
Definition: MemorySSA.h:1029
llvm::cl::desc
Definition: CommandLine.h:405
llvm::MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass
MemorySSAPrinterLegacyPass()
Definition: MemorySSA.cpp:2274
raw_ostream.h
llvm::MemoryUseOrDef::setDefiningAccess
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false, Optional< AliasResult > AR=AliasResult(AliasResult::MayAlias))
Definition: MemorySSA.h:305
llvm::DenseMapInfo< MemoryLocOrCall >::getTombstoneKey
static MemoryLocOrCall getTombstoneKey()
Definition: MemorySSA.cpp:230
MemorySSA
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1775
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
DotCFGMSSA
static cl::opt< std::string > DotCFGMSSA("dot-cfg-mssa", cl::value_desc("file name for generated dot file"), cl::desc("file name for generated dot file"), cl::init(""))
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::DerivedUser
Extension point for the Value hierarchy.
Definition: DerivedUser.h:27
llvm::find_if_not
auto find_if_not(R &&Range, UnaryPredicate P)
Definition: STLExtras.h:1649
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:280
llvm::DOTGraphTraits< DOTFuncMSSAInfo * >::DOTGraphTraits
DOTGraphTraits(bool IsSimple=false)
Definition: MemorySSA.cpp:2323
llvm::ModRefInfo::ModRef
@ ModRef
The access may reference and may modify the value stored in memory.
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1237
of
Add support for conditional and other related patterns Instead of
Definition: README.txt:134
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:927
llvm::Function::size
size_t size() const
Definition: Function.h:731
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::hash_code
An opaque object representing a hash code.
Definition: Hashing.h:73