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