LCOV - code coverage report
Current view: top level - lib/Analysis - MemorySSA.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 580 615 94.3 %
Date: 2018-07-13 00:08:38 Functions: 85 96 88.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13