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