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