LazyValueInfo.cpp | Explore in Territory

//===- LazyValueInfo.cpp - Value constraint analysis ------------*- 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
//
//===----------------------------------------------------------------------===//
//
// This file defines the interface for lazy computation of value constraint
// information.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>
usingnamespacellvm;
usingnamespacePatternMatch;

#define DEBUG_TYPE …

// This is the number of worklist items we will process to try to discover an
// answer for a given value.
static const unsigned MaxProcessedPerValue = …;

char LazyValueInfoWrapperPass::ID = …;
LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : … { … }
INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
                "Lazy Value Information Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
                "Lazy Value Information Analysis", false, true)

namespace llvm {
FunctionPass *createLazyValueInfoPass() { … }
} // namespace llvm

AnalysisKey LazyValueAnalysis::Key;

/// Returns true if this lattice value represents at most one possible value.
/// This is as precise as any lattice value can get while still representing
/// reachable code.
static bool hasSingleValue(const ValueLatticeElement &Val) { … }

//===----------------------------------------------------------------------===//
//                          LazyValueInfoCache Decl
//===----------------------------------------------------------------------===//

namespace {
  /// A callback value handle updates the cache when values are erased.
  class LazyValueInfoCache;
  struct LVIValueHandle final : public CallbackVH { … };
} // end anonymous namespace

namespace {
NonNullPointerSet;

/// This is the cache kept by LazyValueInfo which
/// maintains information about queries across the clients' queries.
class LazyValueInfoCache { … };
} // namespace

void LazyValueInfoCache::eraseValue(Value *V) { … }

void LVIValueHandle::deleted() { … }

void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { … }

void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
                                        BasicBlock *NewSucc) { … }

namespace llvm {
namespace {
/// An assembly annotator class to print LazyValueCache information in
/// comments.
class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter { … };
} // namespace
// The actual implementation of the lazy analysis and update.
class LazyValueInfoImpl { … };
} // namespace llvm

void LazyValueInfoImpl::solve() { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB,
                                 Instruction *CxtI) { … }

static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { … }

bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) { … }

static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) { … }

static void AddNonNullPointersByInstruction(
    Instruction *I, NonNullPointerSet &PtrSet) { … }

bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) { … }

// If we can determine a constraint on the value given conditions assumed by
// the program, intersect those constraints with BBLV
void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
    Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) { … }

std::optional<ConstantRange>
LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueCast(CastInst *CI, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
    Instruction *I, BasicBlock *BB,
    std::function<ConstantRange(const ConstantRange &, const ConstantRange &)>
        OpFn) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
                                                    BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueInsertElement(InsertElementInst *IEI,
                                                BasicBlock *BB) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI,
                                               BasicBlock *BB) { … }

static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val,
                             ICmpInst::Predicate Pred) { … }

/// Get value range for a "(Val + Offset) Pred RHS" condition.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getValueFromSimpleICmpCondition(CmpInst::Predicate Pred,
                                                   Value *RHS,
                                                   const APInt &Offset,
                                                   Instruction *CxtI,
                                                   bool UseBlockValue) { … }

static std::optional<ConstantRange>
getRangeViaSLT(CmpInst::Predicate Pred, APInt RHS,
               function_ref<std::optional<ConstantRange>(const APInt &)> Fn) { … }

std::optional<ValueLatticeElement> LazyValueInfoImpl::getValueFromICmpCondition(
    Value *Val, ICmpInst *ICI, bool isTrueDest, bool UseBlockValue) { … }

// Handle conditions of the form
// extractvalue(op.with.overflow(%x, C), 1).
static ValueLatticeElement getValueFromOverflowCondition(
    Value *Val, WithOverflowInst *WO, bool IsTrueDest) { … }

std::optional<ValueLatticeElement>
LazyValueInfoImpl::getValueFromCondition(Value *Val, Value *Cond,
                                         bool IsTrueDest, bool UseBlockValue,
                                         unsigned Depth) { … }

// Return true if Usr has Op as an operand, otherwise false.
static bool usesOperand(User *Usr, Value *Op) { … }

// Return true if the instruction type of Val is supported by
// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
// Call this before calling constantFoldUser() to find out if it's even worth
// attempting to call it.
static bool isOperationFoldable(User *Usr) { … }

// Check if Usr can be simplified to an integer constant when the value of one
// of its operands Op is an integer constant OpConstVal. If so, return it as an
// lattice value range with a single element or otherwise return an overdefined
// lattice value.
static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
                                            const APInt &OpConstVal,
                                            const DataLayout &DL) { … }

/// Compute the value of Val on the edge BBFrom -> BBTo.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                                     BasicBlock *BBTo, bool UseBlockValue) { … }

/// Compute the value of Val on the edge BBFrom -> BBTo or the value at
/// the basic block if the edge does not constrain Val.
std::optional<ValueLatticeElement>
LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
                                BasicBlock *BBTo, Instruction *CxtI) { … }

ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
                                                       Instruction *CxtI) { … }

ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { … }

ValueLatticeElement LazyValueInfoImpl::
getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
               Instruction *CxtI) { … }

ValueLatticeElement LazyValueInfoImpl::getValueAtUse(const Use &U) { … }

void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                                   BasicBlock *NewSucc) { … }

//===----------------------------------------------------------------------===//
//                            LazyValueInfo Impl
//===----------------------------------------------------------------------===//

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

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

LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { … }

/// This lazily constructs the LazyValueInfoImpl.
LazyValueInfoImpl &LazyValueInfo::getOrCreateImpl(const Module *M) { … }

LazyValueInfoImpl *LazyValueInfo::getImpl() { … }

LazyValueInfo::~LazyValueInfo() { … }

void LazyValueInfo::releaseMemory() { … }

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

void LazyValueInfoWrapperPass::releaseMemory() { … }

LazyValueInfo LazyValueAnalysis::run(Function &F,
                                     FunctionAnalysisManager &FAM) { … }

/// Returns true if we can statically tell that this value will never be a
/// "useful" constant.  In practice, this means we've got something like an
/// alloca or a malloc call for which a comparison against a constant can
/// only be guarding dead code.  Note that we are potentially giving up some
/// precision in dead code (a constant result) in favour of avoiding a
/// expensive search for a easily answered common query.
static bool isKnownNonConstant(Value *V) { … }

Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) { … }

ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI,
                                              bool UndefAllowed) { … }

ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U,
                                                   bool UndefAllowed) { … }

/// Determine whether the specified value is known to be a
/// constant on the specified edge. Return null if not.
Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
                                           BasicBlock *ToBB,
                                           Instruction *CxtI) { … }

ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
                                                    BasicBlock *FromBB,
                                                    BasicBlock *ToBB,
                                                    Instruction *CxtI) { … }

static Constant *getPredicateResult(CmpInst::Predicate Pred, Constant *C,
                                    const ValueLatticeElement &Val,
                                    const DataLayout &DL) { … }

/// Determine whether the specified value comparison with a constant is known to
/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
Constant *LazyValueInfo::getPredicateOnEdge(CmpInst::Predicate Pred, Value *V,
                                            Constant *C, BasicBlock *FromBB,
                                            BasicBlock *ToBB,
                                            Instruction *CxtI) { … }

Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *V,
                                        Constant *C, Instruction *CxtI,
                                        bool UseBlockValue) { … }

Constant *LazyValueInfo::getPredicateAt(CmpInst::Predicate Pred, Value *LHS,
                                        Value *RHS, Instruction *CxtI,
                                        bool UseBlockValue) { … }

void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                               BasicBlock *NewSucc) { … }

void LazyValueInfo::forgetValue(Value *V) { … }

void LazyValueInfo::eraseBlock(BasicBlock *BB) { … }

void LazyValueInfo::clear() { … }

void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { … }

// Print the LVI for the function arguments at the start of each basic block.
void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
    const BasicBlock *BB, formatted_raw_ostream &OS) { … }

// This function prints the LVI analysis for the instruction I at the beginning
// of various basic blocks. It relies on calculated values that are stored in
// the LazyValueInfoCache, and in the absence of cached values, recalculate the
// LazyValueInfo for `I`, and print that info.
void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
    const Instruction *I, formatted_raw_ostream &OS) { … }

PreservedAnalyses LazyValueInfoPrinterPass::run(Function &F,
                                                FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Analysis/LazyValueInfo.cpp
