Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

/// \file

/// This file exposes an interface to building/using memory SSA to

/// walk memory instructions using a use/def graph.

///

/// Memory SSA class builds an SSA form that links together memory access

/// instructions such as loads, stores, atomics, and calls. Additionally, it

/// does a trivial form of "heap versioning" Every time the memory state changes

/// in the program, we generate a new heap version. It generates

/// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.

///

/// As a trivial example,

/// define i32 @main() #0 {

/// entry:

///   %call = call noalias i8* @_Znwm(i64 4) #2

///   %0 = bitcast i8* %call to i32*

///   %call1 = call noalias i8* @_Znwm(i64 4) #2

///   %1 = bitcast i8* %call1 to i32*

///   store i32 5, i32* %0, align 4

///   store i32 7, i32* %1, align 4

///   %2 = load i32* %0, align 4

///   %3 = load i32* %1, align 4

///   %add = add nsw i32 %2, %3

///   ret i32 %add

/// }

///

/// Will become

/// define i32 @main() #0 {

/// entry:

///   ; 1 = MemoryDef(0)

///   %call = call noalias i8* @_Znwm(i64 4) #3

///   %2 = bitcast i8* %call to i32*

///   ; 2 = MemoryDef(1)

///   %call1 = call noalias i8* @_Znwm(i64 4) #3

///   %4 = bitcast i8* %call1 to i32*

///   ; 3 = MemoryDef(2)

///   store i32 5, i32* %2, align 4

///   ; 4 = MemoryDef(3)

///   store i32 7, i32* %4, align 4

///   ; MemoryUse(3)

///   %7 = load i32* %2, align 4

///   ; MemoryUse(4)

///   %8 = load i32* %4, align 4

///   %add = add nsw i32 %7, %8

///   ret i32 %add

/// }

///

/// Given this form, all the stores that could ever effect the load at %8 can be

/// gotten by using the MemoryUse associated with it, and walking from use to

/// def until you hit the top of the function.

///

/// Each def also has a list of users associated with it, so you can walk from

/// both def to users, and users to defs. Note that we disambiguate MemoryUses,

/// but not the RHS of MemoryDefs. You can see this above at %7, which would

/// otherwise be a MemoryUse(4). Being disambiguated means that for a given

/// store, all the MemoryUses on its use lists are may-aliases of that store

/// (but the MemoryDefs on its use list may not be).

///

/// MemoryDefs are not disambiguated because it would require multiple reaching

/// definitions, which would require multiple phis, and multiple memoryaccesses

/// per instruction.

///

/// In addition to the def/use graph described above, MemoryDefs also contain

/// an "optimized" definition use.  The "optimized" use points to some def

/// reachable through the memory def chain.  The optimized def *may* (but is

/// not required to) alias the original MemoryDef, but no def *closer* to the

/// source def may alias it.  As the name implies, the purpose of the optimized

/// use is to allow caching of clobber searches for memory defs.  The optimized

/// def may be nullptr, in which case clients must walk the defining access

/// chain.

///

/// When iterating the uses of a MemoryDef, both defining uses and optimized

/// uses will be encountered.  If only one type is needed, the client must

/// filter the use walk.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_MEMORYSSA_H

#define LLVM_ANALYSIS_MEMORYSSA_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/ilist_node.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Analysis/AliasAnalysis.h"

#include "llvm/Analysis/MemoryLocation.h"

#include "llvm/Analysis/PHITransAddr.h"

#include "llvm/IR/DerivedUser.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/Type.h"

#include "llvm/IR/User.h"

#include "llvm/Pass.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <iterator>

#include <memory>

#include <utility>

namespace llvm {

template <class GraphType> struct GraphTraits;

class BasicBlock;

class Function;

class Instruction;

class LLVMContext;

class MemoryAccess;

class MemorySSAWalker;

class Module;

class Use;

class Value;

class raw_ostream;

namespace MSSAHelpers {

struct AllAccessTag {};

struct DefsOnlyTag {};

} // end namespace MSSAHelpers

enum : unsigned {

  // Used to signify what the default invalid ID is for MemoryAccess's

  // getID()

  INVALID_MEMORYACCESS_ID = -1U

};

template <class T> class memoryaccess_def_iterator_base;

using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;

using const_memoryaccess_def_iterator =

    memoryaccess_def_iterator_base<const MemoryAccess>;

// The base for all memory accesses. All memory accesses in a block are

// linked together using an intrusive list.

class MemoryAccess

    : public DerivedUser,

      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,

      public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {

public:

  using AllAccessType =

      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;

  using DefsOnlyType =

      ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;

  MemoryAccess(const MemoryAccess &) = delete;

  MemoryAccess &operator=(const MemoryAccess &) = delete;

  void *operator new(size_t) = delete;

  // Methods for support type inquiry through isa, cast, and

  // dyn_cast

  static bool classof(const Value *V) {

    unsigned ID = V->getValueID();

    return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;

  }

  BasicBlock *getBlock() const { return Block; }

  void print(raw_ostream &OS) const;

  void dump() const;

  /// The user iterators for a memory access

  using iterator = user_iterator;

  using const_iterator = const_user_iterator;

  /// This iterator walks over all of the defs in a given

  /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For

  /// MemoryUse/MemoryDef, this walks the defining access.

  memoryaccess_def_iterator defs_begin();

  const_memoryaccess_def_iterator defs_begin() const;

  memoryaccess_def_iterator defs_end();

  const_memoryaccess_def_iterator defs_end() const;

  /// Get the iterators for the all access list and the defs only list

  /// We default to the all access list.

  AllAccessType::self_iterator getIterator() {

    return this->AllAccessType::getIterator();

  }

  AllAccessType::const_self_iterator getIterator() const {

    return this->AllAccessType::getIterator();

  }

  AllAccessType::reverse_self_iterator getReverseIterator() {

    return this->AllAccessType::getReverseIterator();

  }

  AllAccessType::const_reverse_self_iterator getReverseIterator() const {

    return this->AllAccessType::getReverseIterator();

  }

  DefsOnlyType::self_iterator getDefsIterator() {

    return this->DefsOnlyType::getIterator();

  }

  DefsOnlyType::const_self_iterator getDefsIterator() const {

    return this->DefsOnlyType::getIterator();

  }

  DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {

    return this->DefsOnlyType::getReverseIterator();

  }

  DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {

    return this->DefsOnlyType::getReverseIterator();

  }

protected:

  friend class MemoryDef;

  friend class MemoryPhi;

  friend class MemorySSA;

  friend class MemoryUse;

  friend class MemoryUseOrDef;

  /// Used by MemorySSA to change the block of a MemoryAccess when it is

  /// moved.

  void setBlock(BasicBlock *BB) { Block = BB; }

  /// Used for debugging and tracking things about MemoryAccesses.

  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.

  inline unsigned getID() const;

  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,

               BasicBlock *BB, unsigned NumOperands)

      : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),

        Block(BB) {}

  // Use deleteValue() to delete a generic MemoryAccess.

  ~MemoryAccess() = default;

private:

  BasicBlock *Block;

};

template <>

struct ilist_alloc_traits<MemoryAccess> {

  static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }

};

inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {

  MA.print(OS);

  return OS;

}

/// Class that has the common methods + fields of memory uses/defs. It's

/// a little awkward to have, but there are many cases where we want either a

/// use or def, and there are many cases where uses are needed (defs aren't

/// acceptable), and vice-versa.

///

/// This class should never be instantiated directly; make a MemoryUse or

/// MemoryDef instead.

class MemoryUseOrDef : public MemoryAccess {

public:

  void *operator new(size_t) = delete;

  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);

  /// Get the instruction that this MemoryUse represents.

  Instruction *getMemoryInst() const { return MemoryInstruction; }

  /// Get the access that produces the memory state used by this Use.

  MemoryAccess *getDefiningAccess() const { return getOperand(0); }

  static bool classof(const Value *MA) {

    return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;

  }

  /// Do we have an optimized use?

  inline bool isOptimized() const;

  /// Return the MemoryAccess associated with the optimized use, or nullptr.

  inline MemoryAccess *getOptimized() const;

  /// Sets the optimized use for a MemoryDef.

  inline void setOptimized(MemoryAccess *);

  /// Reset the ID of what this MemoryUse was optimized to, causing it to

  /// be rewalked by the walker if necessary.

  /// This really should only be called by tests.

  inline void resetOptimized();

protected:

  friend class MemorySSA;

  friend class MemorySSAUpdater;

  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,

                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,

                 unsigned NumOperands)

      : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),

        MemoryInstruction(MI) {

    setDefiningAccess(DMA);

  }

  // Use deleteValue() to delete a generic MemoryUseOrDef.

  ~MemoryUseOrDef() = default;

  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {

    if (!Optimized) {

      setOperand(0, DMA);

      return;

    }

    setOptimized(DMA);

  }

private:

  Instruction *MemoryInstruction;

};

/// Represents read-only accesses to memory

///

/// In particular, the set of Instructions that will be represented by

/// MemoryUse's is exactly the set of Instructions for which

/// AliasAnalysis::getModRefInfo returns "Ref".

class MemoryUse final : public MemoryUseOrDef {

public:

  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);

  MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)

      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,

                       /*NumOperands=*/1) {}

  // allocate space for exactly one operand

  void *operator new(size_t S) { return User::operator new(S, 1); }

  void operator delete(void *Ptr) { User::operator delete(Ptr); }

  static bool classof(const Value *MA) {

    return MA->getValueID() == MemoryUseVal;

  }

  void print(raw_ostream &OS) const;

  void setOptimized(MemoryAccess *DMA) {

    OptimizedID = DMA->getID();

    setOperand(0, DMA);

  }

  /// Whether the MemoryUse is optimized. If ensureOptimizedUses() was called,

  /// uses will usually be optimized, but this is not guaranteed (e.g. due to

  /// invalidation and optimization limits.)

  bool isOptimized() const {

    return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();

  }

  MemoryAccess *getOptimized() const {

    return getDefiningAccess();

  }

  void resetOptimized() {

    OptimizedID = INVALID_MEMORYACCESS_ID;

  }

protected:

  friend class MemorySSA;

private:

  static void deleteMe(DerivedUser *Self);

  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;

};

template <>

struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};

DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)

/// Represents a read-write access to memory, whether it is a must-alias,

/// or a may-alias.

///

/// In particular, the set of Instructions that will be represented by

/// MemoryDef's is exactly the set of Instructions for which

/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".

/// Note that, in order to provide def-def chains, all defs also have a use

/// associated with them. This use points to the nearest reaching

/// MemoryDef/MemoryPhi.

class MemoryDef final : public MemoryUseOrDef {

public:

  friend class MemorySSA;

  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);

  MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,

            unsigned Ver)

      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,

                       /*NumOperands=*/2),

        ID(Ver) {}

  // allocate space for exactly two operands

  void *operator new(size_t S) { return User::operator new(S, 2); }

  void operator delete(void *Ptr) { User::operator delete(Ptr); }

  static bool classof(const Value *MA) {

    return MA->getValueID() == MemoryDefVal;

  }

  void setOptimized(MemoryAccess *MA) {

    setOperand(1, MA);

    OptimizedID = MA->getID();

  }

  MemoryAccess *getOptimized() const {

    return cast_or_null<MemoryAccess>(getOperand(1));

  }

  bool isOptimized() const {

    return getOptimized() && OptimizedID == getOptimized()->getID();

  }

  void resetOptimized() {

    OptimizedID = INVALID_MEMORYACCESS_ID;

    setOperand(1, nullptr);

  }

  void print(raw_ostream &OS) const;

  unsigned getID() const { return ID; }

private:

  static void deleteMe(DerivedUser *Self);

  const unsigned ID;

  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;

};

template <>

struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};

DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)

template <>

struct OperandTraits<MemoryUseOrDef> {

  static Use *op_begin(MemoryUseOrDef *MUD) {

    if (auto *MU = dyn_cast<MemoryUse>(MUD))

      return OperandTraits<MemoryUse>::op_begin(MU);

    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));

  }

  static Use *op_end(MemoryUseOrDef *MUD) {

    if (auto *MU = dyn_cast<MemoryUse>(MUD))

      return OperandTraits<MemoryUse>::op_end(MU);

    return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));

  }

  static unsigned operands(const MemoryUseOrDef *MUD) {

    if (const auto *MU = dyn_cast<MemoryUse>(MUD))

      return OperandTraits<MemoryUse>::operands(MU);

    return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));

  }

};

DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)

/// Represents phi nodes for memory accesses.

///

/// These have the same semantic as regular phi nodes, with the exception that

/// only one phi will ever exist in a given basic block.

/// Guaranteeing one phi per block means guaranteeing there is only ever one

/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.

/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or

/// a MemoryPhi's operands.

/// That is, given

/// if (a) {

///   store %a

///   store %b

/// }

/// it *must* be transformed into

/// if (a) {

///    1 = MemoryDef(liveOnEntry)

///    store %a

///    2 = MemoryDef(1)

///    store %b

/// }

/// and *not*

/// if (a) {

///    1 = MemoryDef(liveOnEntry)

///    store %a

///    2 = MemoryDef(liveOnEntry)

///    store %b

/// }

/// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the

/// end of the branch, and if there are not two phi nodes, one will be

/// disconnected completely from the SSA graph below that point.

/// Because MemoryUse's do not generate new definitions, they do not have this

/// issue.

class MemoryPhi final : public MemoryAccess {

  // allocate space for exactly zero operands

  void *operator new(size_t S) { return User::operator new(S); }

public:

  void operator delete(void *Ptr) { User::operator delete(Ptr); }

  /// Provide fast operand accessors

  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);

  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)

      : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),

        ReservedSpace(NumPreds) {

    allocHungoffUses(ReservedSpace);

  }

  // Block iterator interface. This provides access to the list of incoming

  // basic blocks, which parallels the list of incoming values.

  using block_iterator = BasicBlock **;

  using const_block_iterator = BasicBlock *const *;

  block_iterator block_begin() {

    return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);

  }

  const_block_iterator block_begin() const {

    return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);

  }

  block_iterator block_end() { return block_begin() + getNumOperands(); }

  const_block_iterator block_end() const {

    return block_begin() + getNumOperands();

  }

  iterator_range<block_iterator> blocks() {

    return make_range(block_begin(), block_end());

  }

  iterator_range<const_block_iterator> blocks() const {

    return make_range(block_begin(), block_end());

  }

  op_range incoming_values() { return operands(); }

  const_op_range incoming_values() const { return operands(); }

  /// Return the number of incoming edges

  unsigned getNumIncomingValues() const { return getNumOperands(); }

  /// Return incoming value number x

  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }

  void setIncomingValue(unsigned I, MemoryAccess *V) {

    assert(V && "PHI node got a null value!");

    setOperand(I, V);

  }

  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }

  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }

  /// Return incoming basic block number @p i.

  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }

  /// Return incoming basic block corresponding

  /// to an operand of the PHI.

  BasicBlock *getIncomingBlock(const Use &U) const {

    assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");

    return getIncomingBlock(unsigned(&U - op_begin()));

  }

  /// Return incoming basic block corresponding

  /// to value use iterator.

  BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {

    return getIncomingBlock(I.getUse());

  }

  void setIncomingBlock(unsigned I, BasicBlock *BB) {

    assert(BB && "PHI node got a null basic block!");

    block_begin()[I] = BB;

  }

  /// Add an incoming value to the end of the PHI list

  void addIncoming(MemoryAccess *V, BasicBlock *BB) {

    if (getNumOperands() == ReservedSpace)

      growOperands(); // Get more space!

    // Initialize some new operands.

    setNumHungOffUseOperands(getNumOperands() + 1);

    setIncomingValue(getNumOperands() - 1, V);

    setIncomingBlock(getNumOperands() - 1, BB);

  }

  /// Return the first index of the specified basic

  /// block in the value list for this PHI.  Returns -1 if no instance.

  int getBasicBlockIndex(const BasicBlock *BB) const {

    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)

      if (block_begin()[I] == BB)

        return I;

    return -1;

  }

  MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {

    int Idx = getBasicBlockIndex(BB);

    assert(Idx >= 0 && "Invalid basic block argument!");

    return getIncomingValue(Idx);

  }

  // After deleting incoming position I, the order of incoming may be changed.

  void unorderedDeleteIncoming(unsigned I) {

    unsigned E = getNumOperands();

    assert(I < E && "Cannot remove out of bounds Phi entry.");

    // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi

    // itself should be deleted.

    assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "

                     "at least 2 values.");

    setIncomingValue(I, getIncomingValue(E - 1));

    setIncomingBlock(I, block_begin()[E - 1]);

    setOperand(E - 1, nullptr);

    block_begin()[E - 1] = nullptr;

    setNumHungOffUseOperands(getNumOperands() - 1);

  }

  // After deleting entries that satisfy Pred, remaining entries may have

  // changed order.

  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {

    for (unsigned I = 0, E = getNumOperands(); I != E; ++I)

      if (Pred(getIncomingValue(I), getIncomingBlock(I))) {

        unorderedDeleteIncoming(I);

        E = getNumOperands();

        --I;

      }

    assert(getNumOperands() >= 1 &&

           "Cannot remove all incoming blocks in a MemoryPhi.");

  }

  // After deleting incoming block BB, the incoming blocks order may be changed.

  void unorderedDeleteIncomingBlock(const BasicBlock *BB) {

    unorderedDeleteIncomingIf(

        [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });

  }

  // After deleting incoming memory access MA, the incoming accesses order may

  // be changed.

  void unorderedDeleteIncomingValue(const MemoryAccess *MA) {

    unorderedDeleteIncomingIf(

        [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });

  }

  static bool classof(const Value *V) {

    return V->getValueID() == MemoryPhiVal;

  }

  void print(raw_ostream &OS) const;

  unsigned getID() const { return ID; }

protected:

  friend class MemorySSA;

  /// this is more complicated than the generic

  /// User::allocHungoffUses, because we have to allocate Uses for the incoming

  /// values and pointers to the incoming blocks, all in one allocation.

  void allocHungoffUses(unsigned N) {

    User::allocHungoffUses(N, /* IsPhi */ true);

  }

private:

  // For debugging only

  const unsigned ID;

  unsigned ReservedSpace;

  /// This grows the operand list in response to a push_back style of

  /// operation.  This grows the number of ops by 1.5 times.

  void growOperands() {

    unsigned E = getNumOperands();

    // 2 op PHI nodes are VERY common, so reserve at least enough for that.

    ReservedSpace = std::max(E + E / 2, 2u);

    growHungoffUses(ReservedSpace, /* IsPhi */ true);

  }

  static void deleteMe(DerivedUser *Self);

};

inline unsigned MemoryAccess::getID() const {

  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&

         "only memory defs and phis have ids");

  if (const auto *MD = dyn_cast<MemoryDef>(this))

    return MD->getID();

  return cast<MemoryPhi>(this)->getID();

}

inline bool MemoryUseOrDef::isOptimized() const {

  if (const auto *MD = dyn_cast<MemoryDef>(this))

    return MD->isOptimized();

  return cast<MemoryUse>(this)->isOptimized();

}

inline MemoryAccess *MemoryUseOrDef::getOptimized() const {

  if (const auto *MD = dyn_cast<MemoryDef>(this))

    return MD->getOptimized();

  return cast<MemoryUse>(this)->getOptimized();

}

inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {

  if (auto *MD = dyn_cast<MemoryDef>(this))

    MD->setOptimized(MA);

  else

    cast<MemoryUse>(this)->setOptimized(MA);

}

inline void MemoryUseOrDef::resetOptimized() {

  if (auto *MD = dyn_cast<MemoryDef>(this))

    MD->resetOptimized();

  else

    cast<MemoryUse>(this)->resetOptimized();

}

template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};

DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)

/// Encapsulates MemorySSA, including all data associated with memory

/// accesses.

class MemorySSA {

public:

  MemorySSA(Function &, AliasAnalysis *, DominatorTree *);

  // MemorySSA must remain where it's constructed; Walkers it creates store

  // pointers to it.

  MemorySSA(MemorySSA &&) = delete;

  ~MemorySSA();

  MemorySSAWalker *getWalker();

  MemorySSAWalker *getSkipSelfWalker();

  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA

  /// access associated with it. If passed a basic block gets the memory phi

  /// node that exists for that block, if there is one. Otherwise, this will get

  /// a MemoryUseOrDef.

  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {

    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));

  }

  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {

    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));

  }

  DominatorTree &getDomTree() const { return *DT; }

  void dump() const;

  void print(raw_ostream &) const;

  /// Return true if \p MA represents the live on entry value

  ///

  /// Loads and stores from pointer arguments and other global values may be

  /// defined by memory operations that do not occur in the current function, so

  /// they may be live on entry to the function. MemorySSA represents such

  /// memory state by the live on entry definition, which is guaranteed to occur

  /// before any other memory access in the function.

  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {

    return MA == LiveOnEntryDef.get();

  }

  inline MemoryAccess *getLiveOnEntryDef() const {

    return LiveOnEntryDef.get();

  }

  // Sadly, iplists, by default, owns and deletes pointers added to the

  // list. It's not currently possible to have two iplists for the same type,

  // where one owns the pointers, and one does not. This is because the traits

  // are per-type, not per-tag.  If this ever changes, we should make the

  // DefList an iplist.

  using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;

  using DefsList =

      simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;

  /// Return the list of MemoryAccess's for a given basic block.

  ///

  /// This list is not modifiable by the user.

  const AccessList *getBlockAccesses(const BasicBlock *BB) const {

    return getWritableBlockAccesses(BB);

  }

  /// Return the list of MemoryDef's and MemoryPhi's for a given basic

  /// block.

  ///

  /// This list is not modifiable by the user.

  const DefsList *getBlockDefs(const BasicBlock *BB) const {

    return getWritableBlockDefs(BB);

  }

  /// Given two memory accesses in the same basic block, determine

  /// whether MemoryAccess \p A dominates MemoryAccess \p B.

  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;

  /// Given two memory accesses in potentially different blocks,

  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.

  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;

  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A

  /// dominates Use \p B.

  bool dominates(const MemoryAccess *A, const Use &B) const;

  enum class VerificationLevel { Fast, Full };

  /// Verify that MemorySSA is self consistent (IE definitions dominate

  /// all uses, uses appear in the right places).  This is used by unit tests.

  void verifyMemorySSA(VerificationLevel = VerificationLevel::Fast) const;

  /// Used in various insertion functions to specify whether we are talking

  /// about the beginning or end of a block.

  enum InsertionPlace { Beginning, End, BeforeTerminator };

  /// By default, uses are *not* optimized during MemorySSA construction.

  /// Calling this method will attempt to optimize all MemoryUses, if this has

  /// not happened yet for this MemorySSA instance. This should be done if you

  /// plan to query the clobbering access for most uses, or if you walk the

  /// def-use chain of uses.

  void ensureOptimizedUses();

  AliasAnalysis &getAA() { return *AA; }