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