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