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