EarlyCSE.cpp | Explore in Territory

//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
//
// 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 pass performs a simple dominator tree walk that eliminates trivially
// redundant instructions.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/EarlyCSE.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/AtomicOrdering.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/RecyclingAllocator.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <deque>
#include <memory>
#include <utility>

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
STATISTIC(NumCSE,      "Number of instructions CSE'd");
STATISTIC(NumCSECVP,   "Number of compare instructions CVP'd");
STATISTIC(NumCSELoad,  "Number of load instructions CSE'd");
STATISTIC(NumCSECall,  "Number of call instructions CSE'd");
STATISTIC(NumCSEGEP, "Number of GEP instructions CSE'd");
STATISTIC(NumDSE,      "Number of trivial dead stores removed");

DEBUG_COUNTER(CSECounter, "early-cse",
              "Controls which instructions are removed");

static cl::opt<unsigned> EarlyCSEMssaOptCap(
    "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
    cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "
             "for faster compile. Caps the MemorySSA clobbering calls."));

static cl::opt<bool> EarlyCSEDebugHash(
    "earlycse-debug-hash", cl::init(false), cl::Hidden,
    cl::desc("Perform extra assertion checking to verify that SimpleValue's hash "
             "function is well-behaved w.r.t. its isEqual predicate"));

//===----------------------------------------------------------------------===//
// SimpleValue
//===----------------------------------------------------------------------===//

namespace {

/// Struct representing the available values in the scoped hash table.
struct SimpleValue { … };

} // end anonymous namespace

namespace llvm {

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

} // end namespace llvm

/// Match a 'select' including an optional 'not's of the condition.
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A,
                                           Value *&B,
                                           SelectPatternFlavor &Flavor) { … }

static unsigned hashCallInst(CallInst *CI) { … }

static unsigned getHashValueImpl(SimpleValue Val) { … }

unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) { … }

static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) { … }

bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) { … }

//===----------------------------------------------------------------------===//
// CallValue
//===----------------------------------------------------------------------===//

namespace {

/// Struct representing the available call values in the scoped hash
/// table.
struct CallValue { … };

} // end anonymous namespace

namespace llvm {

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

} // end namespace llvm

unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) { … }

bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) { … }

//===----------------------------------------------------------------------===//
// GEPValue
//===----------------------------------------------------------------------===//

namespace {

struct GEPValue { … };

} // namespace

namespace llvm {

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

} // end namespace llvm

unsigned DenseMapInfo<GEPValue>::getHashValue(const GEPValue &Val) { … }

bool DenseMapInfo<GEPValue>::isEqual(const GEPValue &LHS, const GEPValue &RHS) { … }

//===----------------------------------------------------------------------===//
// EarlyCSE implementation
//===----------------------------------------------------------------------===//

namespace {

/// A simple and fast domtree-based CSE pass.
///
/// This pass does a simple depth-first walk over the dominator tree,
/// eliminating trivially redundant instructions and using instsimplify to
/// canonicalize things as it goes. It is intended to be fast and catch obvious
/// cases so that instcombine and other passes are more effective. It is
/// expected that a later pass of GVN will catch the interesting/hard cases.
class EarlyCSE { … };

} // end anonymous namespace

/// Determine if the memory referenced by LaterInst is from the same heap
/// version as EarlierInst.
/// This is currently called in two scenarios:
///
///   load p
///   ...
///   load p
///
/// and
///
///   x = load p
///   ...
///   store x, p
///
/// in both cases we want to verify that there are no possible writes to the
/// memory referenced by p between the earlier and later instruction.
bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
                                   unsigned LaterGeneration,
                                   Instruction *EarlierInst,
                                   Instruction *LaterInst) { … }

bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) { … }

bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
                                     const BranchInst *BI, const BasicBlock *BB,
                                     const BasicBlock *Pred) { … }

Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
                                  unsigned CurrentGeneration) { … }

static void combineIRFlags(Instruction &From, Value *To) { … }

bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,
                                const ParseMemoryInst &Later) { … }

bool EarlyCSE::processNode(DomTreeNode *Node) { … }

bool EarlyCSE::run() { … }

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

void EarlyCSEPass::printPipeline(
    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … }

namespace {

/// A simple and fast domtree-based CSE pass.
///
/// This pass does a simple depth-first walk over the dominator tree,
/// eliminating trivially redundant instructions and using instsimplify to
/// canonicalize things as it goes. It is intended to be fast and catch obvious
/// cases so that instcombine and other passes are more effective. It is
/// expected that a later pass of GVN will catch the interesting/hard cases.
template<bool UseMemorySSA>
class EarlyCSELegacyCommonPass : public FunctionPass { … };

} // end anonymous namespace

EarlyCSELegacyPass;

template<>
char EarlyCSELegacyPass::ID = …;

INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
                      false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)

EarlyCSEMemSSALegacyPass;

template<>
char EarlyCSEMemSSALegacyPass::ID = …;

FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) { … }

INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
                      "Early CSE w/ MemorySSA", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
                    "Early CSE w/ MemorySSA", false, false)
llvm/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
