contrib/llvm/lib/Analysis/MemorySSA.cpp

   1 //===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the MemorySSA class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/MemorySSA.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/DenseMapInfo.h"
  17 #include "llvm/ADT/DenseSet.h"
  18 #include "llvm/ADT/DepthFirstIterator.h"
  19 #include "llvm/ADT/Hashing.h"
  20 #include "llvm/ADT/None.h"
  21 #include "llvm/ADT/Optional.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/ADT/SmallPtrSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/iterator.h"
  26 #include "llvm/ADT/iterator_range.h"
  27 #include "llvm/Analysis/AliasAnalysis.h"
  28 #include "llvm/Analysis/IteratedDominanceFrontier.h"
  29 #include "llvm/Analysis/MemoryLocation.h"
  30 #include "llvm/IR/AssemblyAnnotationWriter.h"
  31 #include "llvm/IR/BasicBlock.h"
  32 #include "llvm/IR/CallSite.h"
  33 #include "llvm/IR/Dominators.h"
  34 #include "llvm/IR/Function.h"
  35 #include "llvm/IR/Instruction.h"
  36 #include "llvm/IR/Instructions.h"
  37 #include "llvm/IR/IntrinsicInst.h"
  38 #include "llvm/IR/Intrinsics.h"
  39 #include "llvm/IR/LLVMContext.h"
  40 #include "llvm/IR/PassManager.h"
  41 #include "llvm/IR/Use.h"
  42 #include "llvm/Pass.h"
  43 #include "llvm/Support/AtomicOrdering.h"
  44 #include "llvm/Support/Casting.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/Compiler.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/ErrorHandling.h"
  49 #include "llvm/Support/FormattedStream.h"
  50 #include "llvm/Support/raw_ostream.h"
  51 #include <algorithm>
  52 #include <cassert>
  53 #include <iterator>
  54 #include <memory>
  55 #include <utility>
  56
  57 using namespace llvm;
  58
  59 #define DEBUG_TYPE "memoryssa"
  60
  61 INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
  62                       true)
  63 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  64 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
  65 INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
  66                     true)
  67
  68 INITIALIZE_PASS_BEGIN(MemorySSAPrinterLegacyPass, "print-memoryssa",
  69                       "Memory SSA Printer", false, false)
  70 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
  71 INITIALIZE_PASS_END(MemorySSAPrinterLegacyPass, "print-memoryssa",
  72                     "Memory SSA Printer", false, false)
  73
  74 static cl::opt<unsigned> MaxCheckLimit(
  75     "memssa-check-limit", cl::Hidden, cl::init(100),
  76     cl::desc("The maximum number of stores/phis MemorySSA"
  77              "will consider trying to walk past (default = 100)"));
  78
  79 static cl::opt<bool>
  80     VerifyMemorySSA("verify-memoryssa", cl::init(false), cl::Hidden,
  81                     cl::desc("Verify MemorySSA in legacy printer pass."));
  82
  83 namespace llvm {
  84
  85 /// \brief An assembly annotator class to print Memory SSA information in
  86 /// comments.
  87 class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
  88   friend class MemorySSA;
  89
  90   const MemorySSA *MSSA;
  91
  92 public:
  93   MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
  94
  95   void emitBasicBlockStartAnnot(const BasicBlock *BB,
  96                                 formatted_raw_ostream &OS) override {
  97     if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
  98       OS << "; " << *MA << "\n";
  99   }
 100
 101   void emitInstructionAnnot(const Instruction *I,
 102                             formatted_raw_ostream &OS) override {
 103     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
 104       OS << "; " << *MA << "\n";
 105   }
 106 };
 107
 108 } // end namespace llvm
 109
 110 namespace {
 111
 112 /// Our current alias analysis API differentiates heavily between calls and
 113 /// non-calls, and functions called on one usually assert on the other.
 114 /// This class encapsulates the distinction to simplify other code that wants
 115 /// "Memory affecting instructions and related data" to use as a key.
 116 /// For example, this class is used as a densemap key in the use optimizer.
 117 class MemoryLocOrCall {
 118 public:
 119   bool IsCall = false;
 120
 121   MemoryLocOrCall() = default;
 122   MemoryLocOrCall(MemoryUseOrDef *MUD)
 123       : MemoryLocOrCall(MUD->getMemoryInst()) {}
 124   MemoryLocOrCall(const MemoryUseOrDef *MUD)
 125       : MemoryLocOrCall(MUD->getMemoryInst()) {}
 126
 127   MemoryLocOrCall(Instruction *Inst) {
 128     if (ImmutableCallSite(Inst)) {
 129       IsCall = true;
 130       CS = ImmutableCallSite(Inst);
 131     } else {
 132       IsCall = false;
 133       // There is no such thing as a memorylocation for a fence inst, and it is
 134       // unique in that regard.
 135       if (!isa<FenceInst>(Inst))
 136         Loc = MemoryLocation::get(Inst);
 137     }
 138   }
 139
 140   explicit MemoryLocOrCall(const MemoryLocation &Loc) : Loc(Loc) {}
 141
 142   ImmutableCallSite getCS() const {
 143     assert(IsCall);
 144     return CS;
 145   }
 146
 147   MemoryLocation getLoc() const {
 148     assert(!IsCall);
 149     return Loc;
 150   }
 151
 152   bool operator==(const MemoryLocOrCall &Other) const {
 153     if (IsCall != Other.IsCall)
 154       return false;
 155
 156     if (IsCall)
 157       return CS.getCalledValue() == Other.CS.getCalledValue();
 158     return Loc == Other.Loc;
 159   }
 160
 161 private:
 162   union {
 163     ImmutableCallSite CS;
 164     MemoryLocation Loc;
 165   };
 166 };
 167
 168 } // end anonymous namespace
 169
 170 namespace llvm {
 171
 172 template <> struct DenseMapInfo<MemoryLocOrCall> {
 173   static inline MemoryLocOrCall getEmptyKey() {
 174     return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getEmptyKey());
 175   }
 176
 177   static inline MemoryLocOrCall getTombstoneKey() {
 178     return MemoryLocOrCall(DenseMapInfo<MemoryLocation>::getTombstoneKey());
 179   }
 180
 181   static unsigned getHashValue(const MemoryLocOrCall &MLOC) {
 182     if (MLOC.IsCall)
 183       return hash_combine(MLOC.IsCall,
 184                           DenseMapInfo<const Value *>::getHashValue(
 185                               MLOC.getCS().getCalledValue()));
 186     return hash_combine(
 187         MLOC.IsCall, DenseMapInfo<MemoryLocation>::getHashValue(MLOC.getLoc()));
 188   }
 189
 190   static bool isEqual(const MemoryLocOrCall &LHS, const MemoryLocOrCall &RHS) {
 191     return LHS == RHS;
 192   }
 193 };
 194
 195 enum class Reorderability { Always, IfNoAlias, Never };
 196
 197 } // end namespace llvm
 198
 199 /// This does one-way checks to see if Use could theoretically be hoisted above
 200 /// MayClobber. This will not check the other way around.
 201 ///
 202 /// This assumes that, for the purposes of MemorySSA, Use comes directly after
 203 /// MayClobber, with no potentially clobbering operations in between them.
 204 /// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
 205 static Reorderability getLoadReorderability(const LoadInst *Use,
 206                                             const LoadInst *MayClobber) {
 207   bool VolatileUse = Use->isVolatile();
 208   bool VolatileClobber = MayClobber->isVolatile();
 209   // Volatile operations may never be reordered with other volatile operations.
 210   if (VolatileUse && VolatileClobber)
 211     return Reorderability::Never;
 212
 213   // The lang ref allows reordering of volatile and non-volatile operations.
 214   // Whether an aliasing nonvolatile load and volatile load can be reordered,
 215   // though, is ambiguous. Because it may not be best to exploit this ambiguity,
 216   // we only allow volatile/non-volatile reordering if the volatile and
 217   // non-volatile operations don't alias.
 218   Reorderability Result = VolatileUse || VolatileClobber
 219                               ? Reorderability::IfNoAlias
 220                               : Reorderability::Always;
 221
 222   // If a load is seq_cst, it cannot be moved above other loads. If its ordering
 223   // is weaker, it can be moved above other loads. We just need to be sure that
 224   // MayClobber isn't an acquire load, because loads can't be moved above
 225   // acquire loads.
 226   //
 227   // Note that this explicitly *does* allow the free reordering of monotonic (or
 228   // weaker) loads of the same address.
 229   bool SeqCstUse = Use->getOrdering() == AtomicOrdering::SequentiallyConsistent;
 230   bool MayClobberIsAcquire = isAtLeastOrStrongerThan(MayClobber->getOrdering(),
 231                                                      AtomicOrdering::Acquire);
 232   if (SeqCstUse || MayClobberIsAcquire)
 233     return Reorderability::Never;
 234   return Result;
 235 }
 236
 237 static bool instructionClobbersQuery(MemoryDef *MD,
 238                                      const MemoryLocation &UseLoc,
 239                                      const Instruction *UseInst,
 240                                      AliasAnalysis &AA) {
 241   Instruction *DefInst = MD->getMemoryInst();
 242   assert(DefInst && "Defining instruction not actually an instruction");
 243   ImmutableCallSite UseCS(UseInst);
 244
 245   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
 246     // These intrinsics will show up as affecting memory, but they are just
 247     // markers.
 248     switch (II->getIntrinsicID()) {
 249     case Intrinsic::lifetime_start:
 250       if (UseCS)
 251         return false;
 252       return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
 253     case Intrinsic::lifetime_end:
 254     case Intrinsic::invariant_start:
 255     case Intrinsic::invariant_end:
 256     case Intrinsic::assume:
 257       return false;
 258     default:
 259       break;
 260     }
 261   }
 262
 263   if (UseCS) {
 264     ModRefInfo I = AA.getModRefInfo(DefInst, UseCS);
 265     return isModOrRefSet(I);
 266   }
 267
 268   if (auto *DefLoad = dyn_cast<LoadInst>(DefInst)) {
 269     if (auto *UseLoad = dyn_cast<LoadInst>(UseInst)) {
 270       switch (getLoadReorderability(UseLoad, DefLoad)) {
 271       case Reorderability::Always:
 272         return false;
 273       case Reorderability::Never:
 274         return true;
 275       case Reorderability::IfNoAlias:
 276         return !AA.isNoAlias(UseLoc, MemoryLocation::get(DefLoad));
 277       }
 278     }
 279   }
 280
 281   return isModSet(AA.getModRefInfo(DefInst, UseLoc));
 282 }
 283
 284 static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
 285                                      const MemoryLocOrCall &UseMLOC,
 286                                      AliasAnalysis &AA) {
 287   // FIXME: This is a temporary hack to allow a single instructionClobbersQuery
 288   // to exist while MemoryLocOrCall is pushed through places.
 289   if (UseMLOC.IsCall)
 290     return instructionClobbersQuery(MD, MemoryLocation(), MU->getMemoryInst(),
 291                                     AA);
 292   return instructionClobbersQuery(MD, UseMLOC.getLoc(), MU->getMemoryInst(),
 293                                   AA);
 294 }
 295
 296 // Return true when MD may alias MU, return false otherwise.
 297 bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
 298                                         AliasAnalysis &AA) {
 299   return instructionClobbersQuery(MD, MU, MemoryLocOrCall(MU), AA);
 300 }
 301
 302 namespace {
 303
 304 struct UpwardsMemoryQuery {
 305   // True if our original query started off as a call
 306   bool IsCall = false;
 307   // The pointer location we started the query with. This will be empty if
 308   // IsCall is true.
 309   MemoryLocation StartingLoc;
 310   // This is the instruction we were querying about.
 311   const Instruction *Inst = nullptr;
 312   // The MemoryAccess we actually got called with, used to test local domination
 313   const MemoryAccess *OriginalAccess = nullptr;
 314
 315   UpwardsMemoryQuery() = default;
 316
 317   UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
 318       : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
 319     if (!IsCall)
 320       StartingLoc = MemoryLocation::get(Inst);
 321   }
 322 };
 323
 324 } // end anonymous namespace
 325
 326 static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc,
 327                            AliasAnalysis &AA) {
 328   Instruction *Inst = MD->getMemoryInst();
 329   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
 330     switch (II->getIntrinsicID()) {
 331     case Intrinsic::lifetime_end:
 332       return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc);
 333     default:
 334       return false;
 335     }
 336   }
 337   return false;
 338 }
 339
 340 static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysis &AA,
 341                                                    const Instruction *I) {
 342   // If the memory can't be changed, then loads of the memory can't be
 343   // clobbered.
 344   //
 345   // FIXME: We should handle invariant groups, as well. It's a bit harder,
 346   // because we need to pay close attention to invariant group barriers.
 347   return isa<LoadInst>(I) && (I->getMetadata(LLVMContext::MD_invariant_load) ||
 348                               AA.pointsToConstantMemory(cast<LoadInst>(I)->
 349                                                           getPointerOperand()));
 350 }
 351
 352 /// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
 353 /// inbetween `Start` and `ClobberAt` can clobbers `Start`.
 354 ///
 355 /// This is meant to be as simple and self-contained as possible. Because it
 356 /// uses no cache, etc., it can be relatively expensive.
 357 ///
 358 /// \param Start     The MemoryAccess that we want to walk from.
 359 /// \param ClobberAt A clobber for Start.
 360 /// \param StartLoc  The MemoryLocation for Start.
 361 /// \param MSSA      The MemorySSA isntance that Start and ClobberAt belong to.
 362 /// \param Query     The UpwardsMemoryQuery we used for our search.
 363 /// \param AA        The AliasAnalysis we used for our search.
 364 static void LLVM_ATTRIBUTE_UNUSED
 365 checkClobberSanity(MemoryAccess *Start, MemoryAccess *ClobberAt,
 366                    const MemoryLocation &StartLoc, const MemorySSA &MSSA,
 367                    const UpwardsMemoryQuery &Query, AliasAnalysis &AA) {
 368   assert(MSSA.dominates(ClobberAt, Start) && "Clobber doesn't dominate start?");
 369
 370   if (MSSA.isLiveOnEntryDef(Start)) {
 371     assert(MSSA.isLiveOnEntryDef(ClobberAt) &&
 372            "liveOnEntry must clobber itself");
 373     return;
 374   }
 375
 376   bool FoundClobber = false;
 377   DenseSet<MemoryAccessPair> VisitedPhis;
 378   SmallVector<MemoryAccessPair, 8> Worklist;
 379   Worklist.emplace_back(Start, StartLoc);
 380   // Walk all paths from Start to ClobberAt, while looking for clobbers. If one
 381   // is found, complain.
 382   while (!Worklist.empty()) {
 383     MemoryAccessPair MAP = Worklist.pop_back_val();
 384     // All we care about is that nothing from Start to ClobberAt clobbers Start.
 385     // We learn nothing from revisiting nodes.
 386     if (!VisitedPhis.insert(MAP).second)
 387       continue;
 388
 389     for (MemoryAccess *MA : def_chain(MAP.first)) {
 390       if (MA == ClobberAt) {
 391         if (auto *MD = dyn_cast<MemoryDef>(MA)) {
 392           // instructionClobbersQuery isn't essentially free, so don't use `|=`,
 393           // since it won't let us short-circuit.
 394           //
 395           // Also, note that this can't be hoisted out of the `Worklist` loop,
 396           // since MD may only act as a clobber for 1 of N MemoryLocations.
 397           FoundClobber =
 398               FoundClobber || MSSA.isLiveOnEntryDef(MD) ||
 399               instructionClobbersQuery(MD, MAP.second, Query.Inst, AA);
 400         }
 401         break;
 402       }
 403
 404       // We should never hit liveOnEntry, unless it's the clobber.
 405       assert(!MSSA.isLiveOnEntryDef(MA) && "Hit liveOnEntry before clobber?");
 406
 407       if (auto *MD = dyn_cast<MemoryDef>(MA)) {
 408         (void)MD;
 409         assert(!instructionClobbersQuery(MD, MAP.second, Query.Inst, AA) &&
 410                "Found clobber before reaching ClobberAt!");
 411         continue;
 412       }
 413
 414       assert(isa<MemoryPhi>(MA));
 415       Worklist.append(upward_defs_begin({MA, MAP.second}), upward_defs_end());
 416     }
 417   }
 418
 419   // If ClobberAt is a MemoryPhi, we can assume something above it acted as a
 420   // clobber. Otherwise, `ClobberAt` should've acted as a clobber at some point.
 421   assert((isa<MemoryPhi>(ClobberAt) || FoundClobber) &&
 422          "ClobberAt never acted as a clobber");
 423 }
 424
 425 namespace {
 426
 427 /// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
 428 /// in one class.
 429 class ClobberWalker {
 430   /// Save a few bytes by using unsigned instead of size_t.
 431   using ListIndex = unsigned;
 432
 433   /// Represents a span of contiguous MemoryDefs, potentially ending in a
 434   /// MemoryPhi.
 435   struct DefPath {
 436     MemoryLocation Loc;
 437     // Note that, because we always walk in reverse, Last will always dominate
 438     // First. Also note that First and Last are inclusive.
 439     MemoryAccess *First;
 440     MemoryAccess *Last;
 441     Optional<ListIndex> Previous;
 442
 443     DefPath(const MemoryLocation &Loc, MemoryAccess *First, MemoryAccess *Last,
 444             Optional<ListIndex> Previous)
 445         : Loc(Loc), First(First), Last(Last), Previous(Previous) {}
 446
 447     DefPath(const MemoryLocation &Loc, MemoryAccess *Init,
 448             Optional<ListIndex> Previous)
 449         : DefPath(Loc, Init, Init, Previous) {}
 450   };
 451
 452   const MemorySSA &MSSA;
 453   AliasAnalysis &AA;
 454   DominatorTree &DT;
 455   UpwardsMemoryQuery *Query;
 456
 457   // Phi optimization bookkeeping
 458   SmallVector<DefPath, 32> Paths;
 459   DenseSet<ConstMemoryAccessPair> VisitedPhis;
 460
 461   /// Find the nearest def or phi that `From` can legally be optimized to.
 462   const MemoryAccess *getWalkTarget(const MemoryPhi *From) const {
 463     assert(From->getNumOperands() && "Phi with no operands?");
 464
 465     BasicBlock *BB = From->getBlock();
 466     MemoryAccess *Result = MSSA.getLiveOnEntryDef();
 467     DomTreeNode *Node = DT.getNode(BB);
 468     while ((Node = Node->getIDom())) {
 469       auto *Defs = MSSA.getBlockDefs(Node->getBlock());
 470       if (Defs)
 471         return &*Defs->rbegin();
 472     }
 473     return Result;
 474   }
 475
 476   /// Result of calling walkToPhiOrClobber.
 477   struct UpwardsWalkResult {
 478     /// The "Result" of the walk. Either a clobber, the last thing we walked, or
 479     /// both.
 480     MemoryAccess *Result;
 481     bool IsKnownClobber;
 482   };
 483
 484   /// Walk to the next Phi or Clobber in the def chain starting at Desc.Last.
 485   /// This will update Desc.Last as it walks. It will (optionally) also stop at
 486   /// StopAt.
 487   ///
 488   /// This does not test for whether StopAt is a clobber
 489   UpwardsWalkResult
 490   walkToPhiOrClobber(DefPath &Desc,
 491                      const MemoryAccess *StopAt = nullptr) const {
 492     assert(!isa<MemoryUse>(Desc.Last) && "Uses don't exist in my world");
 493
 494     for (MemoryAccess *Current : def_chain(Desc.Last)) {
 495       Desc.Last = Current;
 496       if (Current == StopAt)
 497         return {Current, false};
 498
 499       if (auto *MD = dyn_cast<MemoryDef>(Current))
 500         if (MSSA.isLiveOnEntryDef(MD) ||
 501             instructionClobbersQuery(MD, Desc.Loc, Query->Inst, AA))
 502           return {MD, true};
 503     }
 504
 505     assert(isa<MemoryPhi>(Desc.Last) &&
 506            "Ended at a non-clobber that's not a phi?");
 507     return {Desc.Last, false};
 508   }
 509
 510   void addSearches(MemoryPhi *Phi, SmallVectorImpl<ListIndex> &PausedSearches,
 511                    ListIndex PriorNode) {
 512     auto UpwardDefs = make_range(upward_defs_begin({Phi, Paths[PriorNode].Loc}),
 513                                  upward_defs_end());
 514     for (const MemoryAccessPair &P : UpwardDefs) {
 515       PausedSearches.push_back(Paths.size());
 516       Paths.emplace_back(P.second, P.first, PriorNode);
 517     }
 518   }
 519
 520   /// Represents a search that terminated after finding a clobber. This clobber
 521   /// may or may not be present in the path of defs from LastNode..SearchStart,
 522   /// since it may have been retrieved from cache.
 523   struct TerminatedPath {
 524     MemoryAccess *Clobber;
 525     ListIndex LastNode;
 526   };
 527
 528   /// Get an access that keeps us from optimizing to the given phi.
 529   ///
 530   /// PausedSearches is an array of indices into the Paths array. Its incoming
 531   /// value is the indices of searches that stopped at the last phi optimization
 532   /// target. It's left in an unspecified state.
 533   ///
 534   /// If this returns None, NewPaused is a vector of searches that terminated
 535   /// at StopWhere. Otherwise, NewPaused is left in an unspecified state.
 536   Optional<TerminatedPath>
 537   getBlockingAccess(const MemoryAccess *StopWhere,
 538                     SmallVectorImpl<ListIndex> &PausedSearches,
 539                     SmallVectorImpl<ListIndex> &NewPaused,
 540                     SmallVectorImpl<TerminatedPath> &Terminated) {
 541     assert(!PausedSearches.empty() && "No searches to continue?");
 542
 543     // BFS vs DFS really doesn't make a difference here, so just do a DFS with
 544     // PausedSearches as our stack.
 545     while (!PausedSearches.empty()) {
 546       ListIndex PathIndex = PausedSearches.pop_back_val();
 547       DefPath &Node = Paths[PathIndex];
 548
 549       // If we've already visited this path with this MemoryLocation, we don't
 550       // need to do so again.
 551       //
 552       // NOTE: That we just drop these paths on the ground makes caching
 553       // behavior sporadic. e.g. given a diamond:
 554       //  A
 555       // B C
 556       //  D
 557       //
 558       // ...If we walk D, B, A, C, we'll only cache the result of phi
 559       // optimization for A, B, and D; C will be skipped because it dies here.
 560       // This arguably isn't the worst thing ever, since:
 561       //   - We generally query things in a top-down order, so if we got below D
 562       //     without needing cache entries for {C, MemLoc}, then chances are
 563       //     that those cache entries would end up ultimately unused.
 564       //   - We still cache things for A, so C only needs to walk up a bit.
 565       // If this behavior becomes problematic, we can fix without a ton of extra
 566       // work.
 567       if (!VisitedPhis.insert({Node.Last, Node.Loc}).second)
 568         continue;
 569
 570       UpwardsWalkResult Res = walkToPhiOrClobber(Node, /*StopAt=*/StopWhere);
 571       if (Res.IsKnownClobber) {
 572         assert(Res.Result != StopWhere);
 573         // If this wasn't a cache hit, we hit a clobber when walking. That's a
 574         // failure.
 575         TerminatedPath Term{Res.Result, PathIndex};
 576         if (!MSSA.dominates(Res.Result, StopWhere))
 577           return Term;
 578
 579         // Otherwise, it's a valid thing to potentially optimize to.
 580         Terminated.push_back(Term);
 581         continue;
 582       }
 583
 584       if (Res.Result == StopWhere) {
 585         // We've hit our target. Save this path off for if we want to continue
 586         // walking.
 587         NewPaused.push_back(PathIndex);
 588         continue;
 589       }
 590
 591       assert(!MSSA.isLiveOnEntryDef(Res.Result) && "liveOnEntry is a clobber");
 592       addSearches(cast<MemoryPhi>(Res.Result), PausedSearches, PathIndex);
 593     }
 594
 595     return None;
 596   }
 597
 598   template <typename T, typename Walker>
 599   struct generic_def_path_iterator
 600       : public iterator_facade_base<generic_def_path_iterator<T, Walker>,
 601                                     std::forward_iterator_tag, T *> {
 602     generic_def_path_iterator() = default;
 603     generic_def_path_iterator(Walker *W, ListIndex N) : W(W), N(N) {}
 604
 605     T &operator*() const { return curNode(); }
 606
 607     generic_def_path_iterator &operator++() {
 608       N = curNode().Previous;
 609       return *this;
 610     }
 611
 612     bool operator==(const generic_def_path_iterator &O) const {
 613       if (N.hasValue() != O.N.hasValue())
 614         return false;
 615       return !N.hasValue() || *N == *O.N;
 616     }
 617
 618   private:
 619     T &curNode() const { return W->Paths[*N]; }
 620
 621     Walker *W = nullptr;
 622     Optional<ListIndex> N = None;
 623   };
 624
 625   using def_path_iterator = generic_def_path_iterator<DefPath, ClobberWalker>;
 626   using const_def_path_iterator =
 627       generic_def_path_iterator<const DefPath, const ClobberWalker>;
 628
 629   iterator_range<def_path_iterator> def_path(ListIndex From) {
 630     return make_range(def_path_iterator(this, From), def_path_iterator());
 631   }
 632
 633   iterator_range<const_def_path_iterator> const_def_path(ListIndex From) const {
 634     return make_range(const_def_path_iterator(this, From),
 635                       const_def_path_iterator());
 636   }
 637
 638   struct OptznResult {
 639     /// The path that contains our result.
 640     TerminatedPath PrimaryClobber;
 641     /// The paths that we can legally cache back from, but that aren't
 642     /// necessarily the result of the Phi optimization.
 643     SmallVector<TerminatedPath, 4> OtherClobbers;
 644   };
 645
 646   ListIndex defPathIndex(const DefPath &N) const {
 647     // The assert looks nicer if we don't need to do &N
 648     const DefPath *NP = &N;
 649     assert(!Paths.empty() && NP >= &Paths.front() && NP <= &Paths.back() &&
 650            "Out of bounds DefPath!");
 651     return NP - &Paths.front();
 652   }
 653
 654   /// Try to optimize a phi as best as we can. Returns a SmallVector of Paths
 655   /// that act as legal clobbers. Note that this won't return *all* clobbers.
 656   ///
 657   /// Phi optimization algorithm tl;dr:
 658   ///   - Find the earliest def/phi, A, we can optimize to
 659   ///   - Find if all paths from the starting memory access ultimately reach A
 660   ///     - If not, optimization isn't possible.
 661   ///     - Otherwise, walk from A to another clobber or phi, A'.
 662   ///       - If A' is a def, we're done.
 663   ///       - If A' is a phi, try to optimize it.
 664   ///
 665   /// A path is a series of {MemoryAccess, MemoryLocation} pairs. A path
 666   /// terminates when a MemoryAccess that clobbers said MemoryLocation is found.
 667   OptznResult tryOptimizePhi(MemoryPhi *Phi, MemoryAccess *Start,
 668                              const MemoryLocation &Loc) {
 669     assert(Paths.empty() && VisitedPhis.empty() &&
 670            "Reset the optimization state.");
 671
 672     Paths.emplace_back(Loc, Start, Phi, None);
 673     // Stores how many "valid" optimization nodes we had prior to calling
 674     // addSearches/getBlockingAccess. Necessary for caching if we had a blocker.
 675     auto PriorPathsSize = Paths.size();
 676
 677     SmallVector<ListIndex, 16> PausedSearches;
 678     SmallVector<ListIndex, 8> NewPaused;
 679     SmallVector<TerminatedPath, 4> TerminatedPaths;
 680
 681     addSearches(Phi, PausedSearches, 0);
 682
 683     // Moves the TerminatedPath with the "most dominated" Clobber to the end of
 684     // Paths.
 685     auto MoveDominatedPathToEnd = [&](SmallVectorImpl<TerminatedPath> &Paths) {
 686       assert(!Paths.empty() && "Need a path to move");
 687       auto Dom = Paths.begin();
 688       for (auto I = std::next(Dom), E = Paths.end(); I != E; ++I)
 689         if (!MSSA.dominates(I->Clobber, Dom->Clobber))
 690           Dom = I;
 691       auto Last = Paths.end() - 1;
 692       if (Last != Dom)
 693         std::iter_swap(Last, Dom);
 694     };
 695
 696     MemoryPhi *Current = Phi;
 697     while (true) {
 698       assert(!MSSA.isLiveOnEntryDef(Current) &&
 699              "liveOnEntry wasn't treated as a clobber?");
 700
 701       const auto *Target = getWalkTarget(Current);
 702       // If a TerminatedPath doesn't dominate Target, then it wasn't a legal
 703       // optimization for the prior phi.
 704       assert(all_of(TerminatedPaths, [&](const TerminatedPath &P) {
 705         return MSSA.dominates(P.Clobber, Target);
 706       }));
 707
 708       // FIXME: This is broken, because the Blocker may be reported to be
 709       // liveOnEntry, and we'll happily wait for that to disappear (read: never)
 710       // For the moment, this is fine, since we do nothing with blocker info.
 711       if (Optional<TerminatedPath> Blocker = getBlockingAccess(
 712               Target, PausedSearches, NewPaused, TerminatedPaths)) {
 713
 714         // Find the node we started at. We can't search based on N->Last, since
 715         // we may have gone around a loop with a different MemoryLocation.
 716         auto Iter = find_if(def_path(Blocker->LastNode), [&](const DefPath &N) {
 717           return defPathIndex(N) < PriorPathsSize;
 718         });
 719         assert(Iter != def_path_iterator());
 720
 721         DefPath &CurNode = *Iter;
 722         assert(CurNode.Last == Current);
 723
 724         // Two things:
 725         // A. We can't reliably cache all of NewPaused back. Consider a case
 726         //    where we have two paths in NewPaused; one of which can't optimize
 727         //    above this phi, whereas the other can. If we cache the second path
 728         //    back, we'll end up with suboptimal cache entries. We can handle
 729         //    cases like this a bit better when we either try to find all
 730         //    clobbers that block phi optimization, or when our cache starts
 731         //    supporting unfinished searches.
 732         // B. We can't reliably cache TerminatedPaths back here without doing
 733         //    extra checks; consider a case like:
 734         //       T
 735         //      / \
 736         //     D   C
 737         //      \ /
 738         //       S
 739         //    Where T is our target, C is a node with a clobber on it, D is a
 740         //    diamond (with a clobber *only* on the left or right node, N), and
 741         //    S is our start. Say we walk to D, through the node opposite N
 742         //    (read: ignoring the clobber), and see a cache entry in the top
 743         //    node of D. That cache entry gets put into TerminatedPaths. We then
 744         //    walk up to C (N is later in our worklist), find the clobber, and
 745         //    quit. If we append TerminatedPaths to OtherClobbers, we'll cache
 746         //    the bottom part of D to the cached clobber, ignoring the clobber
 747         //    in N. Again, this problem goes away if we start tracking all
 748         //    blockers for a given phi optimization.
 749         TerminatedPath Result{CurNode.Last, defPathIndex(CurNode)};
 750         return {Result, {}};
 751       }
 752
 753       // If there's nothing left to search, then all paths led to valid clobbers
 754       // that we got from our cache; pick the nearest to the start, and allow
 755       // the rest to be cached back.
 756       if (NewPaused.empty()) {
 757         MoveDominatedPathToEnd(TerminatedPaths);
 758         TerminatedPath Result = TerminatedPaths.pop_back_val();
 759         return {Result, std::move(TerminatedPaths)};
 760       }
 761
 762       MemoryAccess *DefChainEnd = nullptr;
 763       SmallVector<TerminatedPath, 4> Clobbers;
 764       for (ListIndex Paused : NewPaused) {
 765         UpwardsWalkResult WR = walkToPhiOrClobber(Paths[Paused]);
 766         if (WR.IsKnownClobber)
 767           Clobbers.push_back({WR.Result, Paused});
 768         else
 769           // Micro-opt: If we hit the end of the chain, save it.
 770           DefChainEnd = WR.Result;
 771       }
 772
 773       if (!TerminatedPaths.empty()) {
 774         // If we couldn't find the dominating phi/liveOnEntry in the above loop,
 775         // do it now.
 776         if (!DefChainEnd)
 777           for (auto *MA : def_chain(const_cast<MemoryAccess *>(Target)))
 778             DefChainEnd = MA;
 779
 780         // If any of the terminated paths don't dominate the phi we'll try to
 781         // optimize, we need to figure out what they are and quit.
 782         const BasicBlock *ChainBB = DefChainEnd->getBlock();
 783         for (const TerminatedPath &TP : TerminatedPaths) {
 784           // Because we know that DefChainEnd is as "high" as we can go, we
 785           // don't need local dominance checks; BB dominance is sufficient.
 786           if (DT.dominates(ChainBB, TP.Clobber->getBlock()))
 787             Clobbers.push_back(TP);
 788         }
 789       }
 790
 791       // If we have clobbers in the def chain, find the one closest to Current
 792       // and quit.
 793       if (!Clobbers.empty()) {
 794         MoveDominatedPathToEnd(Clobbers);
 795         TerminatedPath Result = Clobbers.pop_back_val();
 796         return {Result, std::move(Clobbers)};
 797       }
 798
 799       assert(all_of(NewPaused,
 800                     [&](ListIndex I) { return Paths[I].Last == DefChainEnd; }));
 801
 802       // Because liveOnEntry is a clobber, this must be a phi.
 803       auto *DefChainPhi = cast<MemoryPhi>(DefChainEnd);
 804
 805       PriorPathsSize = Paths.size();
 806       PausedSearches.clear();
 807       for (ListIndex I : NewPaused)
 808         addSearches(DefChainPhi, PausedSearches, I);
 809       NewPaused.clear();
 810
 811       Current = DefChainPhi;
 812     }
 813   }
 814
 815   void verifyOptResult(const OptznResult &R) const {
 816     assert(all_of(R.OtherClobbers, [&](const TerminatedPath &P) {
 817       return MSSA.dominates(P.Clobber, R.PrimaryClobber.Clobber);
 818     }));
 819   }
 820
 821   void resetPhiOptznState() {
 822     Paths.clear();
 823     VisitedPhis.clear();
 824   }
 825
 826 public:
 827   ClobberWalker(const MemorySSA &MSSA, AliasAnalysis &AA, DominatorTree &DT)
 828       : MSSA(MSSA), AA(AA), DT(DT) {}
 829
 830   void reset() {}
 831
 832   /// Finds the nearest clobber for the given query, optimizing phis if
 833   /// possible.
 834   MemoryAccess *findClobber(MemoryAccess *Start, UpwardsMemoryQuery &Q) {
 835     Query = &Q;
 836
 837     MemoryAccess *Current = Start;
 838     // This walker pretends uses don't exist. If we're handed one, silently grab
 839     // its def. (This has the nice side-effect of ensuring we never cache uses)
 840     if (auto *MU = dyn_cast<MemoryUse>(Start))
 841       Current = MU->getDefiningAccess();
 842
 843     DefPath FirstDesc(Q.StartingLoc, Current, Current, None);
 844     // Fast path for the overly-common case (no crazy phi optimization
 845     // necessary)
 846     UpwardsWalkResult WalkResult = walkToPhiOrClobber(FirstDesc);
 847     MemoryAccess *Result;
 848     if (WalkResult.IsKnownClobber) {
 849       Result = WalkResult.Result;
 850     } else {
 851       OptznResult OptRes = tryOptimizePhi(cast<MemoryPhi>(FirstDesc.Last),
 852                                           Current, Q.StartingLoc);
 853       verifyOptResult(OptRes);
 854       resetPhiOptznState();
 855       Result = OptRes.PrimaryClobber.Clobber;
 856     }
 857
 858 #ifdef EXPENSIVE_CHECKS
 859     checkClobberSanity(Current, Result, Q.StartingLoc, MSSA, Q, AA);
 860 #endif
 861     return Result;
 862   }
 863
 864   void verify(const MemorySSA *MSSA) { assert(MSSA == &this->MSSA); }
 865 };
 866
 867 struct RenamePassData {
 868   DomTreeNode *DTN;
 869   DomTreeNode::const_iterator ChildIt;
 870   MemoryAccess *IncomingVal;
 871
 872   RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
 873                  MemoryAccess *M)
 874       : DTN(D), ChildIt(It), IncomingVal(M) {}
 875
 876   void swap(RenamePassData &RHS) {
 877     std::swap(DTN, RHS.DTN);
 878     std::swap(ChildIt, RHS.ChildIt);
 879     std::swap(IncomingVal, RHS.IncomingVal);
 880   }
 881 };
 882
 883 } // end anonymous namespace
 884
 885 namespace llvm {
 886
 887 /// \brief A MemorySSAWalker that does AA walks to disambiguate accesses. It no
 888 /// longer does caching on its own,
 889 /// but the name has been retained for the moment.
 890 class MemorySSA::CachingWalker final : public MemorySSAWalker {
 891   ClobberWalker Walker;
 892   bool AutoResetWalker = true;
 893
 894   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
 895
 896 public:
 897   CachingWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
 898   ~CachingWalker() override = default;
 899
 900   using MemorySSAWalker::getClobberingMemoryAccess;
 901
 902   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
 903   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
 904                                           const MemoryLocation &) override;
 905   void invalidateInfo(MemoryAccess *) override;
 906
 907   /// Whether we call resetClobberWalker() after each time we *actually* walk to
 908   /// answer a clobber query.
 909   void setAutoResetWalker(bool AutoReset) { AutoResetWalker = AutoReset; }
 910
 911   /// Drop the walker's persistent data structures.
 912   void resetClobberWalker() { Walker.reset(); }
 913
 914   void verify(const MemorySSA *MSSA) override {
 915     MemorySSAWalker::verify(MSSA);
 916     Walker.verify(MSSA);
 917   }
 918 };
 919
 920 } // end namespace llvm
 921
 922 void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
 923                                     bool RenameAllUses) {
 924   // Pass through values to our successors
 925   for (const BasicBlock *S : successors(BB)) {
 926     auto It = PerBlockAccesses.find(S);
 927     // Rename the phi nodes in our successor block
 928     if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
 929       continue;
 930     AccessList *Accesses = It->second.get();
 931     auto *Phi = cast<MemoryPhi>(&Accesses->front());
 932     if (RenameAllUses) {
 933       int PhiIndex = Phi->getBasicBlockIndex(BB);
 934       assert(PhiIndex != -1 && "Incomplete phi during partial rename");
 935       Phi->setIncomingValue(PhiIndex, IncomingVal);
 936     } else
 937       Phi->addIncoming(IncomingVal, BB);
 938   }
 939 }
 940
 941 /// \brief Rename a single basic block into MemorySSA form.
 942 /// Uses the standard SSA renaming algorithm.
 943 /// \returns The new incoming value.
 944 MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal,
 945                                      bool RenameAllUses) {
 946   auto It = PerBlockAccesses.find(BB);
 947   // Skip most processing if the list is empty.
 948   if (It != PerBlockAccesses.end()) {
 949     AccessList *Accesses = It->second.get();
 950     for (MemoryAccess &L : *Accesses) {
 951       if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&L)) {
 952         if (MUD->getDefiningAccess() == nullptr || RenameAllUses)
 953           MUD->setDefiningAccess(IncomingVal);
 954         if (isa<MemoryDef>(&L))
 955           IncomingVal = &L;
 956       } else {
 957         IncomingVal = &L;
 958       }
 959     }
 960   }
 961   return IncomingVal;
 962 }
 963
 964 /// \brief This is the standard SSA renaming algorithm.
 965 ///
 966 /// We walk the dominator tree in preorder, renaming accesses, and then filling
 967 /// in phi nodes in our successors.
 968 void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
 969                            SmallPtrSetImpl<BasicBlock *> &Visited,
 970                            bool SkipVisited, bool RenameAllUses) {
 971   SmallVector<RenamePassData, 32> WorkStack;
 972   // Skip everything if we already renamed this block and we are skipping.
 973   // Note: You can't sink this into the if, because we need it to occur
 974   // regardless of whether we skip blocks or not.
 975   bool AlreadyVisited = !Visited.insert(Root->getBlock()).second;
 976   if (SkipVisited && AlreadyVisited)
 977     return;
 978
 979   IncomingVal = renameBlock(Root->getBlock(), IncomingVal, RenameAllUses);
 980   renameSuccessorPhis(Root->getBlock(), IncomingVal, RenameAllUses);
 981   WorkStack.push_back({Root, Root->begin(), IncomingVal});
 982
 983   while (!WorkStack.empty()) {
 984     DomTreeNode *Node = WorkStack.back().DTN;
 985     DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
 986     IncomingVal = WorkStack.back().IncomingVal;
 987
 988     if (ChildIt == Node->end()) {
 989       WorkStack.pop_back();
 990     } else {
 991       DomTreeNode *Child = *ChildIt;
 992       ++WorkStack.back().ChildIt;
 993       BasicBlock *BB = Child->getBlock();
 994       // Note: You can't sink this into the if, because we need it to occur
 995       // regardless of whether we skip blocks or not.
 996       AlreadyVisited = !Visited.insert(BB).second;
 997       if (SkipVisited && AlreadyVisited) {
 998         // We already visited this during our renaming, which can happen when
 999         // being asked to rename multiple blocks. Figure out the incoming val,
1000         // which is the last def.
1001         // Incoming value can only change if there is a block def, and in that
1002         // case, it's the last block def in the list.
1003         if (auto *BlockDefs = getWritableBlockDefs(BB))
1004           IncomingVal = &*BlockDefs->rbegin();
1005       } else
1006         IncomingVal = renameBlock(BB, IncomingVal, RenameAllUses);
1007       renameSuccessorPhis(BB, IncomingVal, RenameAllUses);
1008       WorkStack.push_back({Child, Child->begin(), IncomingVal});
1009     }
1010   }
1011 }
1012
1013 /// \brief This handles unreachable block accesses by deleting phi nodes in
1014 /// unreachable blocks, and marking all other unreachable MemoryAccess's as
1015 /// being uses of the live on entry definition.
1016 void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
1017   assert(!DT->isReachableFromEntry(BB) &&
1018          "Reachable block found while handling unreachable blocks");
1019
1020   // Make sure phi nodes in our reachable successors end up with a
1021   // LiveOnEntryDef for our incoming edge, even though our block is forward
1022   // unreachable.  We could just disconnect these blocks from the CFG fully,
1023   // but we do not right now.
1024   for (const BasicBlock *S : successors(BB)) {
1025     if (!DT->isReachableFromEntry(S))
1026       continue;
1027     auto It = PerBlockAccesses.find(S);
1028     // Rename the phi nodes in our successor block
1029     if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
1030       continue;
1031     AccessList *Accesses = It->second.get();
1032     auto *Phi = cast<MemoryPhi>(&Accesses->front());
1033     Phi->addIncoming(LiveOnEntryDef.get(), BB);
1034   }
1035
1036   auto It = PerBlockAccesses.find(BB);
1037   if (It == PerBlockAccesses.end())
1038     return;
1039
1040   auto &Accesses = It->second;
1041   for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
1042     auto Next = std::next(AI);
1043     // If we have a phi, just remove it. We are going to replace all
1044     // users with live on entry.
1045     if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
1046       UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
1047     else
1048       Accesses->erase(AI);
1049     AI = Next;
1050   }
1051 }
1052
1053 MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
1054     : AA(AA), DT(DT), F(Func), LiveOnEntryDef(nullptr), Walker(nullptr),
1055       NextID(INVALID_MEMORYACCESS_ID) {
1056   buildMemorySSA();
1057 }
1058
1059 MemorySSA::~MemorySSA() {
1060   // Drop all our references
1061   for (const auto &Pair : PerBlockAccesses)
1062     for (MemoryAccess &MA : *Pair.second)
1063       MA.dropAllReferences();
1064 }
1065
1066 MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) {
1067   auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr));
1068
1069   if (Res.second)
1070     Res.first->second = llvm::make_unique<AccessList>();
1071   return Res.first->second.get();
1072 }
1073
1074 MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) {
1075   auto Res = PerBlockDefs.insert(std::make_pair(BB, nullptr));
1076
1077   if (Res.second)
1078     Res.first->second = llvm::make_unique<DefsList>();
1079   return Res.first->second.get();
1080 }
1081
1082 namespace llvm {
1083
1084 /// This class is a batch walker of all MemoryUse's in the program, and points
1085 /// their defining access at the thing that actually clobbers them.  Because it
1086 /// is a batch walker that touches everything, it does not operate like the
1087 /// other walkers.  This walker is basically performing a top-down SSA renaming
1088 /// pass, where the version stack is used as the cache.  This enables it to be
1089 /// significantly more time and memory efficient than using the regular walker,
1090 /// which is walking bottom-up.
1091 class MemorySSA::OptimizeUses {
1092 public:
1093   OptimizeUses(MemorySSA *MSSA, MemorySSAWalker *Walker, AliasAnalysis *AA,
1094                DominatorTree *DT)
1095       : MSSA(MSSA), Walker(Walker), AA(AA), DT(DT) {
1096     Walker = MSSA->getWalker();
1097   }
1098
1099   void optimizeUses();
1100
1101 private:
1102   /// This represents where a given memorylocation is in the stack.
1103   struct MemlocStackInfo {
1104     // This essentially is keeping track of versions of the stack. Whenever
1105     // the stack changes due to pushes or pops, these versions increase.
1106     unsigned long StackEpoch;
1107     unsigned long PopEpoch;
1108     // This is the lower bound of places on the stack to check. It is equal to
1109     // the place the last stack walk ended.
1110     // Note: Correctness depends on this being initialized to 0, which densemap
1111     // does
1112     unsigned long LowerBound;
1113     const BasicBlock *LowerBoundBlock;
1114     // This is where the last walk for this memory location ended.
1115     unsigned long LastKill;
1116     bool LastKillValid;
1117   };
1118
1119   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
1120                            SmallVectorImpl<MemoryAccess *> &,
1121                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
1122
1123   MemorySSA *MSSA;
1124   MemorySSAWalker *Walker;
1125   AliasAnalysis *AA;
1126   DominatorTree *DT;
1127 };
1128
1129 } // end namespace llvm
1130
1131 /// Optimize the uses in a given block This is basically the SSA renaming
1132 /// algorithm, with one caveat: We are able to use a single stack for all
1133 /// MemoryUses.  This is because the set of *possible* reaching MemoryDefs is
1134 /// the same for every MemoryUse.  The *actual* clobbering MemoryDef is just
1135 /// going to be some position in that stack of possible ones.
1136 ///
1137 /// We track the stack positions that each MemoryLocation needs
1138 /// to check, and last ended at.  This is because we only want to check the
1139 /// things that changed since last time.  The same MemoryLocation should
1140 /// get clobbered by the same store (getModRefInfo does not use invariantness or
1141 /// things like this, and if they start, we can modify MemoryLocOrCall to
1142 /// include relevant data)
1143 void MemorySSA::OptimizeUses::optimizeUsesInBlock(
1144     const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch,
1145     SmallVectorImpl<MemoryAccess *> &VersionStack,
1146     DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) {
1147
1148   /// If no accesses, nothing to do.
1149   MemorySSA::AccessList *Accesses = MSSA->getWritableBlockAccesses(BB);
1150   if (Accesses == nullptr)
1151     return;
1152
1153   // Pop everything that doesn't dominate the current block off the stack,
1154   // increment the PopEpoch to account for this.
1155   while (true) {
1156     assert(
1157         !VersionStack.empty() &&
1158         "Version stack should have liveOnEntry sentinel dominating everything");
1159     BasicBlock *BackBlock = VersionStack.back()->getBlock();
1160     if (DT->dominates(BackBlock, BB))
1161       break;
1162     while (VersionStack.back()->getBlock() == BackBlock)
1163       VersionStack.pop_back();
1164     ++PopEpoch;
1165   }
1166
1167   for (MemoryAccess &MA : *Accesses) {
1168     auto *MU = dyn_cast<MemoryUse>(&MA);
1169     if (!MU) {
1170       VersionStack.push_back(&MA);
1171       ++StackEpoch;
1172       continue;
1173     }
1174
1175     if (isUseTriviallyOptimizableToLiveOnEntry(*AA, MU->getMemoryInst())) {
1176       MU->setDefiningAccess(MSSA->getLiveOnEntryDef(), true);
1177       continue;
1178     }
1179
1180     MemoryLocOrCall UseMLOC(MU);
1181     auto &LocInfo = LocStackInfo[UseMLOC];
1182     // If the pop epoch changed, it means we've removed stuff from top of
1183     // stack due to changing blocks. We may have to reset the lower bound or
1184     // last kill info.
1185     if (LocInfo.PopEpoch != PopEpoch) {
1186       LocInfo.PopEpoch = PopEpoch;
1187       LocInfo.StackEpoch = StackEpoch;
1188       // If the lower bound was in something that no longer dominates us, we
1189       // have to reset it.
1190       // We can't simply track stack size, because the stack may have had
1191       // pushes/pops in the meantime.
1192       // XXX: This is non-optimal, but only is slower cases with heavily
1193       // branching dominator trees.  To get the optimal number of queries would
1194       // be to make lowerbound and lastkill a per-loc stack, and pop it until
1195       // the top of that stack dominates us.  This does not seem worth it ATM.
1196       // A much cheaper optimization would be to always explore the deepest
1197       // branch of the dominator tree first. This will guarantee this resets on
1198       // the smallest set of blocks.
1199       if (LocInfo.LowerBoundBlock && LocInfo.LowerBoundBlock != BB &&
1200           !DT->dominates(LocInfo.LowerBoundBlock, BB)) {
1201         // Reset the lower bound of things to check.
1202         // TODO: Some day we should be able to reset to last kill, rather than
1203         // 0.
1204         LocInfo.LowerBound = 0;
1205         LocInfo.LowerBoundBlock = VersionStack[0]->getBlock();
1206         LocInfo.LastKillValid = false;
1207       }
1208     } else if (LocInfo.StackEpoch != StackEpoch) {
1209       // If all that has changed is the StackEpoch, we only have to check the
1210       // new things on the stack, because we've checked everything before.  In
1211       // this case, the lower bound of things to check remains the same.
1212       LocInfo.PopEpoch = PopEpoch;
1213       LocInfo.StackEpoch = StackEpoch;
1214     }
1215     if (!LocInfo.LastKillValid) {
1216       LocInfo.LastKill = VersionStack.size() - 1;
1217       LocInfo.LastKillValid = true;
1218     }
1219
1220     // At this point, we should have corrected last kill and LowerBound to be
1221     // in bounds.
1222     assert(LocInfo.LowerBound < VersionStack.size() &&
1223            "Lower bound out of range");
1224     assert(LocInfo.LastKill < VersionStack.size() &&
1225            "Last kill info out of range");
1226     // In any case, the new upper bound is the top of the stack.
1227     unsigned long UpperBound = VersionStack.size() - 1;
1228
1229     if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
1230       DEBUG(dbgs() << "MemorySSA skipping optimization of " << *MU << " ("
1231                    << *(MU->getMemoryInst()) << ")"
1232                    << " because there are " << UpperBound - LocInfo.LowerBound
1233                    << " stores to disambiguate\n");
1234       // Because we did not walk, LastKill is no longer valid, as this may
1235       // have been a kill.
1236       LocInfo.LastKillValid = false;
1237       continue;
1238     }
1239     bool FoundClobberResult = false;
1240     while (UpperBound > LocInfo.LowerBound) {
1241       if (isa<MemoryPhi>(VersionStack[UpperBound])) {
1242         // For phis, use the walker, see where we ended up, go there
1243         Instruction *UseInst = MU->getMemoryInst();
1244         MemoryAccess *Result = Walker->getClobberingMemoryAccess(UseInst);
1245         // We are guaranteed to find it or something is wrong
1246         while (VersionStack[UpperBound] != Result) {
1247           assert(UpperBound != 0);
1248           --UpperBound;
1249         }
1250         FoundClobberResult = true;
1251         break;
1252       }
1253
1254       MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
1255       // If the lifetime of the pointer ends at this instruction, it's live on
1256       // entry.
1257       if (!UseMLOC.IsCall && lifetimeEndsAt(MD, UseMLOC.getLoc(), *AA)) {
1258         // Reset UpperBound to liveOnEntryDef's place in the stack
1259         UpperBound = 0;
1260         FoundClobberResult = true;
1261         break;
1262       }
1263       if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) {
1264         FoundClobberResult = true;
1265         break;
1266       }
1267       --UpperBound;
1268     }
1269     // At the end of this loop, UpperBound is either a clobber, or lower bound
1270     // PHI walking may cause it to be < LowerBound, and in fact, < LastKill.
1271     if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
1272       MU->setDefiningAccess(VersionStack[UpperBound], true);
1273       // We were last killed now by where we got to
1274       LocInfo.LastKill = UpperBound;
1275     } else {
1276       // Otherwise, we checked all the new ones, and now we know we can get to
1277       // LastKill.
1278       MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true);
1279     }
1280     LocInfo.LowerBound = VersionStack.size() - 1;
1281     LocInfo.LowerBoundBlock = BB;
1282   }
1283 }
1284
1285 /// Optimize uses to point to their actual clobbering definitions.
1286 void MemorySSA::OptimizeUses::optimizeUses() {
1287   SmallVector<MemoryAccess *, 16> VersionStack;
1288   DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo;
1289   VersionStack.push_back(MSSA->getLiveOnEntryDef());
1290
1291   unsigned long StackEpoch = 1;
1292   unsigned long PopEpoch = 1;
1293   // We perform a non-recursive top-down dominator tree walk.
1294   for (const auto *DomNode : depth_first(DT->getRootNode()))
1295     optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
1296                         LocStackInfo);
1297 }
1298
1299 void MemorySSA::placePHINodes(
1300     const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks,
1301     const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) {
1302   // Determine where our MemoryPhi's should go
1303   ForwardIDFCalculator IDFs(*DT);
1304   IDFs.setDefiningBlocks(DefiningBlocks);
1305   SmallVector<BasicBlock *, 32> IDFBlocks;
1306   IDFs.calculate(IDFBlocks);
1307
1308   std::sort(IDFBlocks.begin(), IDFBlocks.end(),
1309             [&BBNumbers](const BasicBlock *A, const BasicBlock *B) {
1310               return BBNumbers.lookup(A) < BBNumbers.lookup(B);
1311             });
1312
1313   // Now place MemoryPhi nodes.
1314   for (auto &BB : IDFBlocks)
1315     createMemoryPhi(BB);
1316 }
1317
1318 void MemorySSA::buildMemorySSA() {
1319   // We create an access to represent "live on entry", for things like
1320   // arguments or users of globals, where the memory they use is defined before
1321   // the beginning of the function. We do not actually insert it into the IR.
1322   // We do not define a live on exit for the immediate uses, and thus our
1323   // semantics do *not* imply that something with no immediate uses can simply
1324   // be removed.
1325   BasicBlock &StartingPoint = F.getEntryBlock();
1326   LiveOnEntryDef =
1327       llvm::make_unique<MemoryDef>(F.getContext(), nullptr, nullptr,
1328                                    &StartingPoint, NextID++);
1329   DenseMap<const BasicBlock *, unsigned int> BBNumbers;
1330   unsigned NextBBNum = 0;
1331
1332   // We maintain lists of memory accesses per-block, trading memory for time. We
1333   // could just look up the memory access for every possible instruction in the
1334   // stream.
1335   SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
1336   // Go through each block, figure out where defs occur, and chain together all
1337   // the accesses.
1338   for (BasicBlock &B : F) {
1339     BBNumbers[&B] = NextBBNum++;
1340     bool InsertIntoDef = false;
1341     AccessList *Accesses = nullptr;
1342     DefsList *Defs = nullptr;
1343     for (Instruction &I : B) {
1344       MemoryUseOrDef *MUD = createNewAccess(&I);
1345       if (!MUD)
1346         continue;
1347
1348       if (!Accesses)
1349         Accesses = getOrCreateAccessList(&B);
1350       Accesses->push_back(MUD);
1351       if (isa<MemoryDef>(MUD)) {
1352         InsertIntoDef = true;
1353         if (!Defs)
1354           Defs = getOrCreateDefsList(&B);
1355         Defs->push_back(*MUD);
1356       }
1357     }
1358     if (InsertIntoDef)
1359       DefiningBlocks.insert(&B);
1360   }
1361   placePHINodes(DefiningBlocks, BBNumbers);
1362
1363   // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
1364   // filled in with all blocks.
1365   SmallPtrSet<BasicBlock *, 16> Visited;
1366   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
1367
1368   CachingWalker *Walker = getWalkerImpl();
1369
1370   // We're doing a batch of updates; don't drop useful caches between them.
1371   Walker->setAutoResetWalker(false);
1372   OptimizeUses(this, Walker, AA, DT).optimizeUses();
1373   Walker->setAutoResetWalker(true);
1374   Walker->resetClobberWalker();
1375
1376   // Mark the uses in unreachable blocks as live on entry, so that they go
1377   // somewhere.
1378   for (auto &BB : F)
1379     if (!Visited.count(&BB))
1380       markUnreachableAsLiveOnEntry(&BB);
1381 }
1382
1383 MemorySSAWalker *MemorySSA::getWalker() { return getWalkerImpl(); }
1384
1385 MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() {
1386   if (Walker)
1387     return Walker.get();
1388
1389   Walker = llvm::make_unique<CachingWalker>(this, AA, DT);
1390   return Walker.get();
1391 }
1392
1393 // This is a helper function used by the creation routines. It places NewAccess
1394 // into the access and defs lists for a given basic block, at the given
1395 // insertion point.
1396 void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess,
1397                                         const BasicBlock *BB,
1398                                         InsertionPlace Point) {
1399   auto *Accesses = getOrCreateAccessList(BB);
1400   if (Point == Beginning) {
1401     // If it's a phi node, it goes first, otherwise, it goes after any phi
1402     // nodes.
1403     if (isa<MemoryPhi>(NewAccess)) {
1404       Accesses->push_front(NewAccess);
1405       auto *Defs = getOrCreateDefsList(BB);
1406       Defs->push_front(*NewAccess);
1407     } else {
1408       auto AI = find_if_not(
1409           *Accesses, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); });
1410       Accesses->insert(AI, NewAccess);
1411       if (!isa<MemoryUse>(NewAccess)) {
1412         auto *Defs = getOrCreateDefsList(BB);
1413         auto DI = find_if_not(
1414             *Defs, [](const MemoryAccess &MA) { return isa<MemoryPhi>(MA); });
1415         Defs->insert(DI, *NewAccess);
1416       }
1417     }
1418   } else {
1419     Accesses->push_back(NewAccess);
1420     if (!isa<MemoryUse>(NewAccess)) {
1421       auto *Defs = getOrCreateDefsList(BB);
1422       Defs->push_back(*NewAccess);
1423     }
1424   }
1425   BlockNumberingValid.erase(BB);
1426 }
1427
1428 void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB,
1429                                       AccessList::iterator InsertPt) {
1430   auto *Accesses = getWritableBlockAccesses(BB);
1431   bool WasEnd = InsertPt == Accesses->end();
1432   Accesses->insert(AccessList::iterator(InsertPt), What);
1433   if (!isa<MemoryUse>(What)) {
1434     auto *Defs = getOrCreateDefsList(BB);
1435     // If we got asked to insert at the end, we have an easy job, just shove it
1436     // at the end. If we got asked to insert before an existing def, we also get
1437     // an terator. If we got asked to insert before a use, we have to hunt for
1438     // the next def.
1439     if (WasEnd) {
1440       Defs->push_back(*What);
1441     } else if (isa<MemoryDef>(InsertPt)) {
1442       Defs->insert(InsertPt->getDefsIterator(), *What);
1443     } else {
1444       while (InsertPt != Accesses->end() && !isa<MemoryDef>(InsertPt))
1445         ++InsertPt;
1446       // Either we found a def, or we are inserting at the end
1447       if (InsertPt == Accesses->end())
1448         Defs->push_back(*What);
1449       else
1450         Defs->insert(InsertPt->getDefsIterator(), *What);
1451     }
1452   }
1453   BlockNumberingValid.erase(BB);
1454 }
1455
1456 // Move What before Where in the IR.  The end result is taht What will belong to
1457 // the right lists and have the right Block set, but will not otherwise be
1458 // correct. It will not have the right defining access, and if it is a def,
1459 // things below it will not properly be updated.
1460 void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1461                        AccessList::iterator Where) {
1462   // Keep it in the lookup tables, remove from the lists
1463   removeFromLists(What, false);
1464   What->setBlock(BB);
1465   insertIntoListsBefore(What, BB, Where);
1466 }
1467
1468 void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1469                        InsertionPlace Point) {
1470   removeFromLists(What, false);
1471   What->setBlock(BB);
1472   insertIntoListsForBlock(What, BB, Point);
1473 }
1474
1475 MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
1476   assert(!getMemoryAccess(BB) && "MemoryPhi already exists for this BB");
1477   MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
1478   // Phi's always are placed at the front of the block.
1479   insertIntoListsForBlock(Phi, BB, Beginning);
1480   ValueToMemoryAccess[BB] = Phi;
1481   return Phi;
1482 }
1483
1484 MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
1485                                                MemoryAccess *Definition) {
1486   assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
1487   MemoryUseOrDef *NewAccess = createNewAccess(I);
1488   assert(
1489       NewAccess != nullptr &&
1490       "Tried to create a memory access for a non-memory touching instruction");
1491   NewAccess->setDefiningAccess(Definition);
1492   return NewAccess;
1493 }
1494
1495 // Return true if the instruction has ordering constraints.
1496 // Note specifically that this only considers stores and loads
1497 // because others are still considered ModRef by getModRefInfo.
1498 static inline bool isOrdered(const Instruction *I) {
1499   if (auto *SI = dyn_cast<StoreInst>(I)) {
1500     if (!SI->isUnordered())
1501       return true;
1502   } else if (auto *LI = dyn_cast<LoadInst>(I)) {
1503     if (!LI->isUnordered())
1504       return true;
1505   }
1506   return false;
1507 }
1508
1509 /// \brief Helper function to create new memory accesses
1510 MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
1511   // The assume intrinsic has a control dependency which we model by claiming
1512   // that it writes arbitrarily. Ignore that fake memory dependency here.
1513   // FIXME: Replace this special casing with a more accurate modelling of
1514   // assume's control dependency.
1515   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
1516     if (II->getIntrinsicID() == Intrinsic::assume)
1517       return nullptr;
1518
1519   // Find out what affect this instruction has on memory.
1520   ModRefInfo ModRef = AA->getModRefInfo(I, None);
1521   // The isOrdered check is used to ensure that volatiles end up as defs
1522   // (atomics end up as ModRef right now anyway).  Until we separate the
1523   // ordering chain from the memory chain, this enables people to see at least
1524   // some relative ordering to volatiles.  Note that getClobberingMemoryAccess
1525   // will still give an answer that bypasses other volatile loads.  TODO:
1526   // Separate memory aliasing and ordering into two different chains so that we
1527   // can precisely represent both "what memory will this read/write/is clobbered
1528   // by" and "what instructions can I move this past".
1529   bool Def = isModSet(ModRef) || isOrdered(I);
1530   bool Use = isRefSet(ModRef);
1531
1532   // It's possible for an instruction to not modify memory at all. During
1533   // construction, we ignore them.
1534   if (!Def && !Use)
1535     return nullptr;
1536
1537   assert((Def || Use) &&
1538          "Trying to create a memory access with a non-memory instruction");
1539
1540   MemoryUseOrDef *MUD;
1541   if (Def)
1542     MUD = new MemoryDef(I->getContext(), nullptr, I, I->getParent(), NextID++);
1543   else
1544     MUD = new MemoryUse(I->getContext(), nullptr, I, I->getParent());
1545   ValueToMemoryAccess[I] = MUD;
1546   return MUD;
1547 }
1548
1549 /// \brief Returns true if \p Replacer dominates \p Replacee .
1550 bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
1551                              const MemoryAccess *Replacee) const {
1552   if (isa<MemoryUseOrDef>(Replacee))
1553     return DT->dominates(Replacer->getBlock(), Replacee->getBlock());
1554   const auto *MP = cast<MemoryPhi>(Replacee);
1555   // For a phi node, the use occurs in the predecessor block of the phi node.
1556   // Since we may occur multiple times in the phi node, we have to check each
1557   // operand to ensure Replacer dominates each operand where Replacee occurs.
1558   for (const Use &Arg : MP->operands()) {
1559     if (Arg.get() != Replacee &&
1560         !DT->dominates(Replacer->getBlock(), MP->getIncomingBlock(Arg)))
1561       return false;
1562   }
1563   return true;
1564 }
1565
1566 /// \brief Properly remove \p MA from all of MemorySSA's lookup tables.
1567 void MemorySSA::removeFromLookups(MemoryAccess *MA) {
1568   assert(MA->use_empty() &&
1569          "Trying to remove memory access that still has uses");
1570   BlockNumbering.erase(MA);
1571   if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA))
1572     MUD->setDefiningAccess(nullptr);
1573   // Invalidate our walker's cache if necessary
1574   if (!isa<MemoryUse>(MA))
1575     Walker->invalidateInfo(MA);
1576   // The call below to erase will destroy MA, so we can't change the order we
1577   // are doing things here
1578   Value *MemoryInst;
1579   if (MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1580     MemoryInst = MUD->getMemoryInst();
1581   } else {
1582     MemoryInst = MA->getBlock();
1583   }
1584   auto VMA = ValueToMemoryAccess.find(MemoryInst);
1585   if (VMA->second == MA)
1586     ValueToMemoryAccess.erase(VMA);
1587 }
1588
1589 /// \brief Properly remove \p MA from all of MemorySSA's lists.
1590 ///
1591 /// Because of the way the intrusive list and use lists work, it is important to
1592 /// do removal in the right order.
1593 /// ShouldDelete defaults to true, and will cause the memory access to also be
1594 /// deleted, not just removed.
1595 void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) {
1596   // The access list owns the reference, so we erase it from the non-owning list
1597   // first.
1598   if (!isa<MemoryUse>(MA)) {
1599     auto DefsIt = PerBlockDefs.find(MA->getBlock());
1600     std::unique_ptr<DefsList> &Defs = DefsIt->second;
1601     Defs->remove(*MA);
1602     if (Defs->empty())
1603       PerBlockDefs.erase(DefsIt);
1604   }
1605
1606   // The erase call here will delete it. If we don't want it deleted, we call
1607   // remove instead.
1608   auto AccessIt = PerBlockAccesses.find(MA->getBlock());
1609   std::unique_ptr<AccessList> &Accesses = AccessIt->second;
1610   if (ShouldDelete)
1611     Accesses->erase(MA);
1612   else
1613     Accesses->remove(MA);
1614
1615   if (Accesses->empty())
1616     PerBlockAccesses.erase(AccessIt);
1617 }
1618
1619 void MemorySSA::print(raw_ostream &OS) const {
1620   MemorySSAAnnotatedWriter Writer(this);
1621   F.print(OS, &Writer);
1622 }
1623
1624 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1625 LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); }
1626 #endif
1627
1628 void MemorySSA::verifyMemorySSA() const {
1629   verifyDefUses(F);
1630   verifyDomination(F);
1631   verifyOrdering(F);
1632   Walker->verify(this);
1633 }
1634
1635 /// \brief Verify that the order and existence of MemoryAccesses matches the
1636 /// order and existence of memory affecting instructions.
1637 void MemorySSA::verifyOrdering(Function &F) const {
1638   // Walk all the blocks, comparing what the lookups think and what the access
1639   // lists think, as well as the order in the blocks vs the order in the access
1640   // lists.
1641   SmallVector<MemoryAccess *, 32> ActualAccesses;
1642   SmallVector<MemoryAccess *, 32> ActualDefs;
1643   for (BasicBlock &B : F) {
1644     const AccessList *AL = getBlockAccesses(&B);
1645     const auto *DL = getBlockDefs(&B);
1646     MemoryAccess *Phi = getMemoryAccess(&B);
1647     if (Phi) {
1648       ActualAccesses.push_back(Phi);
1649       ActualDefs.push_back(Phi);
1650     }
1651
1652     for (Instruction &I : B) {
1653       MemoryAccess *MA = getMemoryAccess(&I);
1654       assert((!MA || (AL && (isa<MemoryUse>(MA) || DL))) &&
1655              "We have memory affecting instructions "
1656              "in this block but they are not in the "
1657              "access list or defs list");
1658       if (MA) {
1659         ActualAccesses.push_back(MA);
1660         if (isa<MemoryDef>(MA))
1661           ActualDefs.push_back(MA);
1662       }
1663     }
1664     // Either we hit the assert, really have no accesses, or we have both
1665     // accesses and an access list.
1666     // Same with defs.
1667     if (!AL && !DL)
1668       continue;
1669     assert(AL->size() == ActualAccesses.size() &&
1670            "We don't have the same number of accesses in the block as on the "
1671            "access list");
1672     assert((DL || ActualDefs.size() == 0) &&
1673            "Either we should have a defs list, or we should have no defs");
1674     assert((!DL || DL->size() == ActualDefs.size()) &&
1675            "We don't have the same number of defs in the block as on the "
1676            "def list");
1677     auto ALI = AL->begin();
1678     auto AAI = ActualAccesses.begin();
1679     while (ALI != AL->end() && AAI != ActualAccesses.end()) {
1680       assert(&*ALI == *AAI && "Not the same accesses in the same order");
1681       ++ALI;
1682       ++AAI;
1683     }
1684     ActualAccesses.clear();
1685     if (DL) {
1686       auto DLI = DL->begin();
1687       auto ADI = ActualDefs.begin();
1688       while (DLI != DL->end() && ADI != ActualDefs.end()) {
1689         assert(&*DLI == *ADI && "Not the same defs in the same order");
1690         ++DLI;
1691         ++ADI;
1692       }
1693     }
1694     ActualDefs.clear();
1695   }
1696 }
1697
1698 /// \brief Verify the domination properties of MemorySSA by checking that each
1699 /// definition dominates all of its uses.
1700 void MemorySSA::verifyDomination(Function &F) const {
1701 #ifndef NDEBUG
1702   for (BasicBlock &B : F) {
1703     // Phi nodes are attached to basic blocks
1704     if (MemoryPhi *MP = getMemoryAccess(&B))
1705       for (const Use &U : MP->uses())
1706         assert(dominates(MP, U) && "Memory PHI does not dominate it's uses");
1707
1708     for (Instruction &I : B) {
1709       MemoryAccess *MD = dyn_cast_or_null<MemoryDef>(getMemoryAccess(&I));
1710       if (!MD)
1711         continue;
1712
1713       for (const Use &U : MD->uses())
1714         assert(dominates(MD, U) && "Memory Def does not dominate it's uses");
1715     }
1716   }
1717 #endif
1718 }
1719
1720 /// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use
1721 /// appears in the use list of \p Def.
1722 void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const {
1723 #ifndef NDEBUG
1724   // The live on entry use may cause us to get a NULL def here
1725   if (!Def)
1726     assert(isLiveOnEntryDef(Use) &&
1727            "Null def but use not point to live on entry def");
1728   else
1729     assert(is_contained(Def->users(), Use) &&
1730            "Did not find use in def's use list");
1731 #endif
1732 }
1733
1734 /// \brief Verify the immediate use information, by walking all the memory
1735 /// accesses and verifying that, for each use, it appears in the
1736 /// appropriate def's use list
1737 void MemorySSA::verifyDefUses(Function &F) const {
1738   for (BasicBlock &B : F) {
1739     // Phi nodes are attached to basic blocks
1740     if (MemoryPhi *Phi = getMemoryAccess(&B)) {
1741       assert(Phi->getNumOperands() == static_cast<unsigned>(std::distance(
1742                                           pred_begin(&B), pred_end(&B))) &&
1743              "Incomplete MemoryPhi Node");
1744       for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I)
1745         verifyUseInDefs(Phi->getIncomingValue(I), Phi);
1746     }
1747
1748     for (Instruction &I : B) {
1749       if (MemoryUseOrDef *MA = getMemoryAccess(&I)) {
1750         verifyUseInDefs(MA->getDefiningAccess(), MA);
1751       }
1752     }
1753   }
1754 }
1755
1756 MemoryUseOrDef *MemorySSA::getMemoryAccess(const Instruction *I) const {
1757   return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
1758 }
1759
1760 MemoryPhi *MemorySSA::getMemoryAccess(const BasicBlock *BB) const {
1761   return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
1762 }
1763
1764 /// Perform a local numbering on blocks so that instruction ordering can be
1765 /// determined in constant time.
1766 /// TODO: We currently just number in order.  If we numbered by N, we could
1767 /// allow at least N-1 sequences of insertBefore or insertAfter (and at least
1768 /// log2(N) sequences of mixed before and after) without needing to invalidate
1769 /// the numbering.
1770 void MemorySSA::renumberBlock(const BasicBlock *B) const {
1771   // The pre-increment ensures the numbers really start at 1.
1772   unsigned long CurrentNumber = 0;
1773   const AccessList *AL = getBlockAccesses(B);
1774   assert(AL != nullptr && "Asking to renumber an empty block");
1775   for (const auto &I : *AL)
1776     BlockNumbering[&I] = ++CurrentNumber;
1777   BlockNumberingValid.insert(B);
1778 }
1779
1780 /// \brief Determine, for two memory accesses in the same block,
1781 /// whether \p Dominator dominates \p Dominatee.
1782 /// \returns True if \p Dominator dominates \p Dominatee.
1783 bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
1784                                  const MemoryAccess *Dominatee) const {
1785   const BasicBlock *DominatorBlock = Dominator->getBlock();
1786
1787   assert((DominatorBlock == Dominatee->getBlock()) &&
1788          "Asking for local domination when accesses are in different blocks!");
1789   // A node dominates itself.
1790   if (Dominatee == Dominator)
1791     return true;
1792
1793   // When Dominatee is defined on function entry, it is not dominated by another
1794   // memory access.
1795   if (isLiveOnEntryDef(Dominatee))
1796     return false;
1797
1798   // When Dominator is defined on function entry, it dominates the other memory
1799   // access.
1800   if (isLiveOnEntryDef(Dominator))
1801     return true;
1802
1803   if (!BlockNumberingValid.count(DominatorBlock))
1804     renumberBlock(DominatorBlock);
1805
1806   unsigned long DominatorNum = BlockNumbering.lookup(Dominator);
1807   // All numbers start with 1
1808   assert(DominatorNum != 0 && "Block was not numbered properly");
1809   unsigned long DominateeNum = BlockNumbering.lookup(Dominatee);
1810   assert(DominateeNum != 0 && "Block was not numbered properly");
1811   return DominatorNum < DominateeNum;
1812 }
1813
1814 bool MemorySSA::dominates(const MemoryAccess *Dominator,
1815                           const MemoryAccess *Dominatee) const {
1816   if (Dominator == Dominatee)
1817     return true;
1818
1819   if (isLiveOnEntryDef(Dominatee))
1820     return false;
1821
1822   if (Dominator->getBlock() != Dominatee->getBlock())
1823     return DT->dominates(Dominator->getBlock(), Dominatee->getBlock());
1824   return locallyDominates(Dominator, Dominatee);
1825 }
1826
1827 bool MemorySSA::dominates(const MemoryAccess *Dominator,
1828                           const Use &Dominatee) const {
1829   if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Dominatee.getUser())) {
1830     BasicBlock *UseBB = MP->getIncomingBlock(Dominatee);
1831     // The def must dominate the incoming block of the phi.
1832     if (UseBB != Dominator->getBlock())
1833       return DT->dominates(Dominator->getBlock(), UseBB);
1834     // If the UseBB and the DefBB are the same, compare locally.
1835     return locallyDominates(Dominator, cast<MemoryAccess>(Dominatee));
1836   }
1837   // If it's not a PHI node use, the normal dominates can already handle it.
1838   return dominates(Dominator, cast<MemoryAccess>(Dominatee.getUser()));
1839 }
1840
1841 const static char LiveOnEntryStr[] = "liveOnEntry";
1842
1843 void MemoryAccess::print(raw_ostream &OS) const {
1844   switch (getValueID()) {
1845   case MemoryPhiVal: return static_cast<const MemoryPhi *>(this)->print(OS);
1846   case MemoryDefVal: return static_cast<const MemoryDef *>(this)->print(OS);
1847   case MemoryUseVal: return static_cast<const MemoryUse *>(this)->print(OS);
1848   }
1849   llvm_unreachable("invalid value id");
1850 }
1851
1852 void MemoryDef::print(raw_ostream &OS) const {
1853   MemoryAccess *UO = getDefiningAccess();
1854
1855   OS << getID() << " = MemoryDef(";
1856   if (UO && UO->getID())
1857     OS << UO->getID();
1858   else
1859     OS << LiveOnEntryStr;
1860   OS << ')';
1861 }
1862
1863 void MemoryPhi::print(raw_ostream &OS) const {
1864   bool First = true;
1865   OS << getID() << " = MemoryPhi(";
1866   for (const auto &Op : operands()) {
1867     BasicBlock *BB = getIncomingBlock(Op);
1868     MemoryAccess *MA = cast<MemoryAccess>(Op);
1869     if (!First)
1870       OS << ',';
1871     else
1872       First = false;
1873
1874     OS << '{';
1875     if (BB->hasName())
1876       OS << BB->getName();
1877     else
1878       BB->printAsOperand(OS, false);
1879     OS << ',';
1880     if (unsigned ID = MA->getID())
1881       OS << ID;
1882     else
1883       OS << LiveOnEntryStr;
1884     OS << '}';
1885   }
1886   OS << ')';
1887 }
1888
1889 void MemoryUse::print(raw_ostream &OS) const {
1890   MemoryAccess *UO = getDefiningAccess();
1891   OS << "MemoryUse(";
1892   if (UO && UO->getID())
1893     OS << UO->getID();
1894   else
1895     OS << LiveOnEntryStr;
1896   OS << ')';
1897 }
1898
1899 void MemoryAccess::dump() const {
1900 // Cannot completely remove virtual function even in release mode.
1901 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1902   print(dbgs());
1903   dbgs() << "\n";
1904 #endif
1905 }
1906
1907 char MemorySSAPrinterLegacyPass::ID = 0;
1908
1909 MemorySSAPrinterLegacyPass::MemorySSAPrinterLegacyPass() : FunctionPass(ID) {
1910   initializeMemorySSAPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
1911 }
1912
1913 void MemorySSAPrinterLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
1914   AU.setPreservesAll();
1915   AU.addRequired<MemorySSAWrapperPass>();
1916 }
1917
1918 bool MemorySSAPrinterLegacyPass::runOnFunction(Function &F) {
1919   auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
1920   MSSA.print(dbgs());
1921   if (VerifyMemorySSA)
1922     MSSA.verifyMemorySSA();
1923   return false;
1924 }
1925
1926 AnalysisKey MemorySSAAnalysis::Key;
1927
1928 MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F,
1929                                                  FunctionAnalysisManager &AM) {
1930   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1931   auto &AA = AM.getResult<AAManager>(F);
1932   return MemorySSAAnalysis::Result(llvm::make_unique<MemorySSA>(F, &AA, &DT));
1933 }
1934
1935 PreservedAnalyses MemorySSAPrinterPass::run(Function &F,
1936                                             FunctionAnalysisManager &AM) {
1937   OS << "MemorySSA for function: " << F.getName() << "\n";
1938   AM.getResult<MemorySSAAnalysis>(F).getMSSA().print(OS);
1939
1940   return PreservedAnalyses::all();
1941 }
1942
1943 PreservedAnalyses MemorySSAVerifierPass::run(Function &F,
1944                                              FunctionAnalysisManager &AM) {
1945   AM.getResult<MemorySSAAnalysis>(F).getMSSA().verifyMemorySSA();
1946
1947   return PreservedAnalyses::all();
1948 }
1949
1950 char MemorySSAWrapperPass::ID = 0;
1951
1952 MemorySSAWrapperPass::MemorySSAWrapperPass() : FunctionPass(ID) {
1953   initializeMemorySSAWrapperPassPass(*PassRegistry::getPassRegistry());
1954 }
1955
1956 void MemorySSAWrapperPass::releaseMemory() { MSSA.reset(); }
1957
1958 void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1959   AU.setPreservesAll();
1960   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1961   AU.addRequiredTransitive<AAResultsWrapperPass>();
1962 }
1963
1964 bool MemorySSAWrapperPass::runOnFunction(Function &F) {
1965   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1966   auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1967   MSSA.reset(new MemorySSA(F, &AA, &DT));
1968   return false;
1969 }
1970
1971 void MemorySSAWrapperPass::verifyAnalysis() const { MSSA->verifyMemorySSA(); }
1972
1973 void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const {
1974   MSSA->print(OS);
1975 }
1976
1977 MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
1978
1979 MemorySSA::CachingWalker::CachingWalker(MemorySSA *M, AliasAnalysis *A,
1980                                         DominatorTree *D)
1981     : MemorySSAWalker(M), Walker(*M, *A, *D) {}
1982
1983 void MemorySSA::CachingWalker::invalidateInfo(MemoryAccess *MA) {
1984   if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA))
1985     MUD->resetOptimized();
1986 }
1987
1988 /// \brief Walk the use-def chains starting at \p MA and find
1989 /// the MemoryAccess that actually clobbers Loc.
1990 ///
1991 /// \returns our clobbering memory access
1992 MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess(
1993     MemoryAccess *StartingAccess, UpwardsMemoryQuery &Q) {
1994   MemoryAccess *New = Walker.findClobber(StartingAccess, Q);
1995 #ifdef EXPENSIVE_CHECKS
1996   MemoryAccess *NewNoCache = Walker.findClobber(StartingAccess, Q);
1997   assert(NewNoCache == New && "Cache made us hand back a different result?");
1998   (void)NewNoCache;
1999 #endif
2000   if (AutoResetWalker)
2001     resetClobberWalker();
2002   return New;
2003 }
2004
2005 MemoryAccess *MemorySSA::CachingWalker::getClobberingMemoryAccess(
2006     MemoryAccess *StartingAccess, const MemoryLocation &Loc) {
2007   if (isa<MemoryPhi>(StartingAccess))
2008     return StartingAccess;
2009
2010   auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess);
2011   if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
2012     return StartingUseOrDef;
2013
2014   Instruction *I = StartingUseOrDef->getMemoryInst();
2015
2016   // Conservatively, fences are always clobbers, so don't perform the walk if we
2017   // hit a fence.
2018   if (!ImmutableCallSite(I) && I->isFenceLike())
2019     return StartingUseOrDef;
2020
2021   UpwardsMemoryQuery Q;
2022   Q.OriginalAccess = StartingUseOrDef;
2023   Q.StartingLoc = Loc;
2024   Q.Inst = I;
2025   Q.IsCall = false;
2026
2027   // Unlike the other function, do not walk to the def of a def, because we are
2028   // handed something we already believe is the clobbering access.
2029   MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
2030                                      ? StartingUseOrDef->getDefiningAccess()
2031                                      : StartingUseOrDef;
2032
2033   MemoryAccess *Clobber = getClobberingMemoryAccess(DefiningAccess, Q);
2034   DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
2035   DEBUG(dbgs() << *StartingUseOrDef << "\n");
2036   DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
2037   DEBUG(dbgs() << *Clobber << "\n");
2038   return Clobber;
2039 }
2040
2041 MemoryAccess *
2042 MemorySSA::CachingWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
2043   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
2044   // If this is a MemoryPhi, we can't do anything.
2045   if (!StartingAccess)
2046     return MA;
2047
2048   // If this is an already optimized use or def, return the optimized result.
2049   // Note: Currently, we do not store the optimized def result because we'd need
2050   // a separate field, since we can't use it as the defining access.
2051   if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
2052     if (MUD->isOptimized())
2053       return MUD->getOptimized();
2054
2055   const Instruction *I = StartingAccess->getMemoryInst();
2056   UpwardsMemoryQuery Q(I, StartingAccess);
2057   // We can't sanely do anything with a fences, they conservatively
2058   // clobber all memory, and have no locations to get pointers from to
2059   // try to disambiguate.
2060   if (!Q.IsCall && I->isFenceLike())
2061     return StartingAccess;
2062
2063   if (isUseTriviallyOptimizableToLiveOnEntry(*MSSA->AA, I)) {
2064     MemoryAccess *LiveOnEntry = MSSA->getLiveOnEntryDef();
2065     if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
2066       MUD->setOptimized(LiveOnEntry);
2067     return LiveOnEntry;
2068   }
2069
2070   // Start with the thing we already think clobbers this location
2071   MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
2072
2073   // At this point, DefiningAccess may be the live on entry def.
2074   // If it is, we will not get a better result.
2075   if (MSSA->isLiveOnEntryDef(DefiningAccess))
2076     return DefiningAccess;
2077
2078   MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
2079   DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
2080   DEBUG(dbgs() << *DefiningAccess << "\n");
2081   DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
2082   DEBUG(dbgs() << *Result << "\n");
2083   if (auto *MUD = dyn_cast<MemoryUseOrDef>(StartingAccess))
2084     MUD->setOptimized(Result);
2085
2086   return Result;
2087 }
2088
2089 MemoryAccess *
2090 DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA) {
2091   if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
2092     return Use->getDefiningAccess();
2093   return MA;
2094 }
2095
2096 MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
2097     MemoryAccess *StartingAccess, const MemoryLocation &) {
2098   if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
2099     return Use->getDefiningAccess();
2100   return StartingAccess;
2101 }
2102
2103 void MemoryPhi::deleteMe(DerivedUser *Self) {
2104   delete static_cast<MemoryPhi *>(Self);
2105 }
2106
2107 void MemoryDef::deleteMe(DerivedUser *Self) {
2108   delete static_cast<MemoryDef *>(Self);
2109 }
2110
2111 void MemoryUse::deleteMe(DerivedUser *Self) {
2112   delete static_cast<MemoryUse *>(Self);
2113 }