llvm/llvm/lib/Analysis/MemorySSA.cpp

//===- MemorySSA.cpp - Memory SSA Builder ---------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements the MemorySSA class.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/MemorySSA.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFGPrinter.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Use.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<std::string>
    DotCFGMSSA("dot-cfg-mssa",
               cl::value_desc("file name for generated dot file"),
               cl::desc("file name for generated dot file"), cl::init(""));

INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
                      true)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
                    true)

static cl::opt<unsigned> MaxCheckLimit(
    "memssa-check-limit", cl::Hidden, cl::init(100),
    cl::desc("The maximum number of stores/phis MemorySSA"
             "will consider trying to walk past (default = 100)"));

// Always verify MemorySSA if expensive checking is enabled.
#ifdef EXPENSIVE_CHECKS
bool llvm::VerifyMemorySSA = true;
#else
bool llvm::VerifyMemorySSA = …;
#endif

static cl::opt<bool, true>
    VerifyMemorySSAX("verify-memoryssa", cl::location(VerifyMemorySSA),
                     cl::Hidden, cl::desc("Enable verification of MemorySSA."));

const static char LiveOnEntryStr[] = …;

namespace {

/// An assembly annotator class to print Memory SSA information in
/// comments.
class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter { … };

/// An assembly annotator class to print Memory SSA information in
/// comments.
class MemorySSAWalkerAnnotatedWriter : public AssemblyAnnotationWriter { … };

} // namespace

namespace {

/// Our current alias analysis API differentiates heavily between calls and
/// non-calls, and functions called on one usually assert on the other.
/// This class encapsulates the distinction to simplify other code that wants
/// "Memory affecting instructions and related data" to use as a key.
/// For example, this class is used as a densemap key in the use optimizer.
class MemoryLocOrCall { … };

} // end anonymous namespace

namespace llvm {

template <> struct DenseMapInfo<MemoryLocOrCall> { … };

} // end namespace llvm

/// This does one-way checks to see if Use could theoretically be hoisted above
/// MayClobber. This will not check the other way around.
///
/// This assumes that, for the purposes of MemorySSA, Use comes directly after
/// MayClobber, with no potentially clobbering operations in between them.
/// (Where potentially clobbering ops are memory barriers, aliased stores, etc.)
static bool areLoadsReorderable(const LoadInst *Use,
                                const LoadInst *MayClobber) { … }

template <typename AliasAnalysisType>
static bool
instructionClobbersQuery(const MemoryDef *MD, const MemoryLocation &UseLoc,
                         const Instruction *UseInst, AliasAnalysisType &AA) { … }

template <typename AliasAnalysisType>
static bool instructionClobbersQuery(MemoryDef *MD, const MemoryUseOrDef *MU,
                                     const MemoryLocOrCall &UseMLOC,
                                     AliasAnalysisType &AA) { … }

// Return true when MD may alias MU, return false otherwise.
bool MemorySSAUtil::defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
                                        AliasAnalysis &AA) { … }

namespace {

struct UpwardsMemoryQuery { … };

} // end anonymous namespace

template <typename AliasAnalysisType>
static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
                                                   const Instruction *I) { … }

/// Verifies that `Start` is clobbered by `ClobberAt`, and that nothing
/// inbetween `Start` and `ClobberAt` can clobbers `Start`.
///
/// This is meant to be as simple and self-contained as possible. Because it
/// uses no cache, etc., it can be relatively expensive.
///
/// \param Start     The MemoryAccess that we want to walk from.
/// \param ClobberAt A clobber for Start.
/// \param StartLoc  The MemoryLocation for Start.
/// \param MSSA      The MemorySSA instance that Start and ClobberAt belong to.
/// \param Query     The UpwardsMemoryQuery we used for our search.
/// \param AA        The AliasAnalysis we used for our search.
/// \param AllowImpreciseClobber Always false, unless we do relaxed verify.

LLVM_ATTRIBUTE_UNUSED static void
checkClobberSanity(const MemoryAccess *Start, MemoryAccess *ClobberAt,
                   const MemoryLocation &StartLoc, const MemorySSA &MSSA,
                   const UpwardsMemoryQuery &Query, BatchAAResults &AA,
                   bool AllowImpreciseClobber = false) { … }

namespace {

/// Our algorithm for walking (and trying to optimize) clobbers, all wrapped up
/// in one class.
class ClobberWalker { … };

struct RenamePassData { … };

} // end anonymous namespace

namespace llvm {

class MemorySSA::ClobberWalkerBase { … };

/// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
/// longer does caching on its own, but the name has been retained for the
/// moment.
class MemorySSA::CachingWalker final : public MemorySSAWalker { … };

class MemorySSA::SkipSelfWalker final : public MemorySSAWalker { … };

} // end namespace llvm

void MemorySSA::renameSuccessorPhis(BasicBlock *BB, MemoryAccess *IncomingVal,
                                    bool RenameAllUses) { … }

/// Rename a single basic block into MemorySSA form.
/// Uses the standard SSA renaming algorithm.
/// \returns The new incoming value.
MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB, MemoryAccess *IncomingVal,
                                     bool RenameAllUses) { … }

/// This is the standard SSA renaming algorithm.
///
/// We walk the dominator tree in preorder, renaming accesses, and then filling
/// in phi nodes in our successors.
void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
                           SmallPtrSetImpl<BasicBlock *> &Visited,
                           bool SkipVisited, bool RenameAllUses) { … }

/// This handles unreachable block accesses by deleting phi nodes in
/// unreachable blocks, and marking all other unreachable MemoryAccess's as
/// being uses of the live on entry definition.
void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) { … }

MemorySSA::MemorySSA(Function &Func, AliasAnalysis *AA, DominatorTree *DT)
    : … { … }

MemorySSA::MemorySSA(Loop &L, AliasAnalysis *AA, DominatorTree *DT)
    : … { … }

MemorySSA::~MemorySSA() { … }

MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) { … }

MemorySSA::DefsList *MemorySSA::getOrCreateDefsList(const BasicBlock *BB) { … }

namespace llvm {

/// This class is a batch walker of all MemoryUse's in the program, and points
/// their defining access at the thing that actually clobbers them.  Because it
/// is a batch walker that touches everything, it does not operate like the
/// other walkers.  This walker is basically performing a top-down SSA renaming
/// pass, where the version stack is used as the cache.  This enables it to be
/// significantly more time and memory efficient than using the regular walker,
/// which is walking bottom-up.
class MemorySSA::OptimizeUses { … };

} // end namespace llvm

/// Optimize the uses in a given block This is basically the SSA renaming
/// algorithm, with one caveat: We are able to use a single stack for all
/// MemoryUses.  This is because the set of *possible* reaching MemoryDefs is
/// the same for every MemoryUse.  The *actual* clobbering MemoryDef is just
/// going to be some position in that stack of possible ones.
///
/// We track the stack positions that each MemoryLocation needs
/// to check, and last ended at.  This is because we only want to check the
/// things that changed since last time.  The same MemoryLocation should
/// get clobbered by the same store (getModRefInfo does not use invariantness or
/// things like this, and if they start, we can modify MemoryLocOrCall to
/// include relevant data)
void MemorySSA::OptimizeUses::optimizeUsesInBlock(
    const BasicBlock *BB, unsigned long &StackEpoch, unsigned long &PopEpoch,
    SmallVectorImpl<MemoryAccess *> &VersionStack,
    DenseMap<MemoryLocOrCall, MemlocStackInfo> &LocStackInfo) { … }

/// Optimize uses to point to their actual clobbering definitions.
void MemorySSA::OptimizeUses::optimizeUses() { … }

void MemorySSA::placePHINodes(
    const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) { … }

template <typename IterT>
void MemorySSA::buildMemorySSA(BatchAAResults &BAA, IterT Blocks) { … }

MemorySSAWalker *MemorySSA::getWalker() { … }

MemorySSA::CachingWalker *MemorySSA::getWalkerImpl() { … }

MemorySSAWalker *MemorySSA::getSkipSelfWalker() { … }


// This is a helper function used by the creation routines. It places NewAccess
// into the access and defs lists for a given basic block, at the given
// insertion point.
void MemorySSA::insertIntoListsForBlock(MemoryAccess *NewAccess,
                                        const BasicBlock *BB,
                                        InsertionPlace Point) { … }

void MemorySSA::insertIntoListsBefore(MemoryAccess *What, const BasicBlock *BB,
                                      AccessList::iterator InsertPt) { … }

void MemorySSA::prepareForMoveTo(MemoryAccess *What, BasicBlock *BB) { … }

// Move What before Where in the IR.  The end result is that What will belong to
// the right lists and have the right Block set, but will not otherwise be
// correct. It will not have the right defining access, and if it is a def,
// things below it will not properly be updated.
void MemorySSA::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                       AccessList::iterator Where) { … }

void MemorySSA::moveTo(MemoryAccess *What, BasicBlock *BB,
                       InsertionPlace Point) { … }

MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) { … }

MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
                                               MemoryAccess *Definition,
                                               const MemoryUseOrDef *Template,
                                               bool CreationMustSucceed) { … }

// Return true if the instruction has ordering constraints.
// Note specifically that this only considers stores and loads
// because others are still considered ModRef by getModRefInfo.
static inline bool isOrdered(const Instruction *I) { … }

/// Helper function to create new memory accesses
template <typename AliasAnalysisType>
MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
                                           AliasAnalysisType *AAP,
                                           const MemoryUseOrDef *Template) { … }

/// Properly remove \p MA from all of MemorySSA's lookup tables.
void MemorySSA::removeFromLookups(MemoryAccess *MA) { … }

/// Properly remove \p MA from all of MemorySSA's lists.
///
/// Because of the way the intrusive list and use lists work, it is important to
/// do removal in the right order.
/// ShouldDelete defaults to true, and will cause the memory access to also be
/// deleted, not just removed.
void MemorySSA::removeFromLists(MemoryAccess *MA, bool ShouldDelete) { … }

void MemorySSA::print(raw_ostream &OS) const { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void MemorySSA::dump() const { print(dbgs()); }
#endif

void MemorySSA::verifyMemorySSA(VerificationLevel VL) const { … }

template <typename IterT>
void MemorySSA::verifyPrevDefInPhis(IterT Blocks) const { … }

/// Verify that all of the blocks we believe to have valid domination numbers
/// actually have valid domination numbers.
template <typename IterT>
void MemorySSA::verifyDominationNumbers(IterT Blocks) const { … }

/// Verify ordering: the order and existence of MemoryAccesses matches the
/// order and existence of memory affecting instructions.
/// Verify domination: each definition dominates all of its uses.
/// Verify def-uses: the immediate use information - walk all the memory
/// accesses and verifying that, for each use, it appears in the appropriate
/// def's use list
template <typename IterT>
void MemorySSA::verifyOrderingDominationAndDefUses(IterT Blocks,
                                                   VerificationLevel VL) const { … }

/// Verify the def-use lists in MemorySSA, by verifying that \p Use
/// appears in the use list of \p Def.
void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) const { … }

/// Perform a local numbering on blocks so that instruction ordering can be
/// determined in constant time.
/// TODO: We currently just number in order.  If we numbered by N, we could
/// allow at least N-1 sequences of insertBefore or insertAfter (and at least
/// log2(N) sequences of mixed before and after) without needing to invalidate
/// the numbering.
void MemorySSA::renumberBlock(const BasicBlock *B) const { … }

/// Determine, for two memory accesses in the same block,
/// whether \p Dominator dominates \p Dominatee.
/// \returns True if \p Dominator dominates \p Dominatee.
bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
                                 const MemoryAccess *Dominatee) const { … }

bool MemorySSA::dominates(const MemoryAccess *Dominator,
                          const MemoryAccess *Dominatee) const { … }

bool MemorySSA::dominates(const MemoryAccess *Dominator,
                          const Use &Dominatee) const { … }

void MemorySSA::ensureOptimizedUses() { … }

void MemoryAccess::print(raw_ostream &OS) const { … }

void MemoryDef::print(raw_ostream &OS) const { … }

void MemoryPhi::print(raw_ostream &OS) const { … }

void MemoryUse::print(raw_ostream &OS) const { … }

void MemoryAccess::dump() const { … }

class DOTFuncMSSAInfo { … };

namespace llvm {

template <>
struct GraphTraits<DOTFuncMSSAInfo *> : public GraphTraits<const BasicBlock *> { … };

template <>
struct DOTGraphTraits<DOTFuncMSSAInfo *> : public DefaultDOTGraphTraits { … };

} // namespace llvm

AnalysisKey MemorySSAAnalysis::Key;

MemorySSAAnalysis::Result MemorySSAAnalysis::run(Function &F,
                                                 FunctionAnalysisManager &AM) { … }

bool MemorySSAAnalysis::Result::invalidate(
    Function &F, const PreservedAnalyses &PA,
    FunctionAnalysisManager::Invalidator &Inv) { … }

PreservedAnalyses MemorySSAPrinterPass::run(Function &F,
                                            FunctionAnalysisManager &AM) { … }

PreservedAnalyses MemorySSAWalkerPrinterPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) { … }

PreservedAnalyses MemorySSAVerifierPass::run(Function &F,
                                             FunctionAnalysisManager &AM) { … }

char MemorySSAWrapperPass::ID = …;

MemorySSAWrapperPass::MemorySSAWrapperPass() : … { … }

void MemorySSAWrapperPass::releaseMemory() { … }

void MemorySSAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

bool MemorySSAWrapperPass::runOnFunction(Function &F) { … }

void MemorySSAWrapperPass::verifyAnalysis() const { … }

void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const { … }

MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : … { … }

/// Walk the use-def chains starting at \p StartingAccess and find
/// the MemoryAccess that actually clobbers Loc.
///
/// \returns our clobbering memory access
MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
    MemoryAccess *StartingAccess, const MemoryLocation &Loc,
    BatchAAResults &BAA, unsigned &UpwardWalkLimit) { … }

static const Instruction *
getInvariantGroupClobberingInstruction(Instruction &I, DominatorTree &DT) { … }

MemoryAccess *MemorySSA::ClobberWalkerBase::getClobberingMemoryAccessBase(
    MemoryAccess *MA, BatchAAResults &BAA, unsigned &UpwardWalkLimit,
    bool SkipSelf, bool UseInvariantGroup) { … }

MemoryAccess *
DoNothingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *MA,
                                                    BatchAAResults &) { … }

MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
    MemoryAccess *StartingAccess, const MemoryLocation &, BatchAAResults &) { … }

void MemoryPhi::deleteMe(DerivedUser *Self) { … }

void MemoryDef::deleteMe(DerivedUser *Self) { … }

void MemoryUse::deleteMe(DerivedUser *Self) { … }

bool upward_defs_iterator::IsGuaranteedLoopInvariant(const Value *Ptr) const { … }