SCCPSolver.cpp | Explore in Territory

//===- SCCPSolver.cpp - SCCP Utility --------------------------- *- 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 implements the Sparse Conditional Constant Propagation (SCCP)
// utility.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/SCCPSolver.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueLatticeUtils.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

// The maximum number of range extensions allowed for operations requiring
// widening.
static const unsigned MaxNumRangeExtensions = …;

/// Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts() { … }

namespace llvm {

bool SCCPSolver::isConstant(const ValueLatticeElement &LV) { … }

bool SCCPSolver::isOverdefined(const ValueLatticeElement &LV) { … }

bool SCCPSolver::tryToReplaceWithConstant(Value *V) { … }

/// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
static bool refineInstruction(SCCPSolver &Solver,
                              const SmallPtrSetImpl<Value *> &InsertedValues,
                              Instruction &Inst) { … }

/// Try to replace signed instructions with their unsigned equivalent.
static bool replaceSignedInst(SCCPSolver &Solver,
                              SmallPtrSetImpl<Value *> &InsertedValues,
                              Instruction &Inst) { … }

bool SCCPSolver::simplifyInstsInBlock(BasicBlock &BB,
                                      SmallPtrSetImpl<Value *> &InsertedValues,
                                      Statistic &InstRemovedStat,
                                      Statistic &InstReplacedStat) { … }

bool SCCPSolver::removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
                                        BasicBlock *&NewUnreachableBB) const { … }

static void inferAttribute(Function *F, unsigned AttrIndex,
                           const ValueLatticeElement &Val) { … }

void SCCPSolver::inferReturnAttributes() const { … }

void SCCPSolver::inferArgAttributes() const { … }

/// Helper class for SCCPSolver. This implements the instruction visitor and
/// holds all the state.
class SCCPInstVisitor : public InstVisitor<SCCPInstVisitor> { … };

} // namespace llvm

bool SCCPInstVisitor::markBlockExecutable(BasicBlock *BB) { … }

void SCCPInstVisitor::pushToWorkList(ValueLatticeElement &IV, Value *V) { … }

void SCCPInstVisitor::pushToWorkListMsg(ValueLatticeElement &IV, Value *V) { … }

bool SCCPInstVisitor::markConstant(ValueLatticeElement &IV, Value *V,
                                   Constant *C, bool MayIncludeUndef) { … }

bool SCCPInstVisitor::markNotConstant(ValueLatticeElement &IV, Value *V,
                                      Constant *C) { … }

bool SCCPInstVisitor::markConstantRange(ValueLatticeElement &IV, Value *V,
                                        const ConstantRange &CR) { … }

bool SCCPInstVisitor::markOverdefined(ValueLatticeElement &IV, Value *V) { … }

bool SCCPInstVisitor::isStructLatticeConstant(Function *F, StructType *STy) { … }

Constant *SCCPInstVisitor::getConstant(const ValueLatticeElement &LV,
                                       Type *Ty) const { … }

Constant *SCCPInstVisitor::getConstantOrNull(Value *V) const { … }

void SCCPInstVisitor::setLatticeValueForSpecializationArguments(Function *F,
                                        const SmallVectorImpl<ArgInfo> &Args) { … }

void SCCPInstVisitor::visitInstruction(Instruction &I) { … }

bool SCCPInstVisitor::mergeInValue(ValueLatticeElement &IV, Value *V,
                                   ValueLatticeElement MergeWithV,
                                   ValueLatticeElement::MergeOptions Opts) { … }

bool SCCPInstVisitor::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { … }

// getFeasibleSuccessors - Return a vector of booleans to indicate which
// successors are reachable from a given terminator instruction.
void SCCPInstVisitor::getFeasibleSuccessors(Instruction &TI,
                                            SmallVectorImpl<bool> &Succs) { … }

// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
// block to the 'To' basic block is currently feasible.
bool SCCPInstVisitor::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const { … }

// visit Implementations - Something changed in this instruction, either an
// operand made a transition, or the instruction is newly executable.  Change
// the value type of I to reflect these changes if appropriate.  This method
// makes sure to do the following actions:
//
// 1. If a phi node merges two constants in, and has conflicting value coming
//    from different branches, or if the PHI node merges in an overdefined
//    value, then the PHI node becomes overdefined.
// 2. If a phi node merges only constants in, and they all agree on value, the
//    PHI node becomes a constant value equal to that.
// 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
// 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
// 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
// 6. If a conditional branch has a value that is constant, make the selected
//    destination executable
// 7. If a conditional branch has a value that is overdefined, make all
//    successors executable.
void SCCPInstVisitor::visitPHINode(PHINode &PN) { … }

void SCCPInstVisitor::visitReturnInst(ReturnInst &I) { … }

void SCCPInstVisitor::visitTerminator(Instruction &TI) { … }

void SCCPInstVisitor::visitCastInst(CastInst &I) { … }

void SCCPInstVisitor::handleExtractOfWithOverflow(ExtractValueInst &EVI,
                                                  const WithOverflowInst *WO,
                                                  unsigned Idx) { … }

void SCCPInstVisitor::visitExtractValueInst(ExtractValueInst &EVI) { … }

void SCCPInstVisitor::visitInsertValueInst(InsertValueInst &IVI) { … }

void SCCPInstVisitor::visitSelectInst(SelectInst &I) { … }

// Handle Unary Operators.
void SCCPInstVisitor::visitUnaryOperator(Instruction &I) { … }

void SCCPInstVisitor::visitFreezeInst(FreezeInst &I) { … }

// Handle Binary Operators.
void SCCPInstVisitor::visitBinaryOperator(Instruction &I) { … }

// Handle ICmpInst instruction.
void SCCPInstVisitor::visitCmpInst(CmpInst &I) { … }

// Handle getelementptr instructions.  If all operands are constants then we
// can turn this into a getelementptr ConstantExpr.
void SCCPInstVisitor::visitGetElementPtrInst(GetElementPtrInst &I) { … }

void SCCPInstVisitor::visitAllocaInst(AllocaInst &I) { … }

void SCCPInstVisitor::visitStoreInst(StoreInst &SI) { … }

static ValueLatticeElement getValueFromMetadata(const Instruction *I) { … }

// Handle load instructions.  If the operand is a constant pointer to a constant
// global, we can replace the load with the loaded constant value!
void SCCPInstVisitor::visitLoadInst(LoadInst &I) { … }

void SCCPInstVisitor::visitCallBase(CallBase &CB) { … }

void SCCPInstVisitor::handleCallOverdefined(CallBase &CB) { … }

void SCCPInstVisitor::handleCallArguments(CallBase &CB) { … }

void SCCPInstVisitor::handleCallResult(CallBase &CB) { … }

void SCCPInstVisitor::solve() { … }

bool SCCPInstVisitor::resolvedUndef(Instruction &I) { … }

/// While solving the dataflow for a function, we don't compute a result for
/// operations with an undef operand, to allow undef to be lowered to a
/// constant later. For example, constant folding of "zext i8 undef to i16"
/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
/// zext result would become "i16 1" and would result into an overdefined
/// lattice value once merged with the previous result. Not computing the
/// result of the zext (treating undef the same as unknown) allows us to handle
/// a later undef->constant lowering more optimally.
///
/// However, if the operand remains undef when the solver returns, we do need
/// to assign some result to the instruction (otherwise we would treat it as
/// unreachable). For simplicity, we mark any instructions that are still
/// unknown as overdefined.
bool SCCPInstVisitor::resolvedUndefsIn(Function &F) { … }

//===----------------------------------------------------------------------===//
//
// SCCPSolver implementations
//
SCCPSolver::SCCPSolver(
    const DataLayout &DL,
    std::function<const TargetLibraryInfo &(Function &)> GetTLI,
    LLVMContext &Ctx)
    : … { … }

SCCPSolver::~SCCPSolver() = default;

void SCCPSolver::addPredicateInfo(Function &F, DominatorTree &DT,
                                  AssumptionCache &AC) { … }

bool SCCPSolver::markBlockExecutable(BasicBlock *BB) { … }

const PredicateBase *SCCPSolver::getPredicateInfoFor(Instruction *I) { … }

void SCCPSolver::trackValueOfGlobalVariable(GlobalVariable *GV) { … }

void SCCPSolver::addTrackedFunction(Function *F) { … }

void SCCPSolver::addToMustPreserveReturnsInFunctions(Function *F) { … }

bool SCCPSolver::mustPreserveReturn(Function *F) { … }

void SCCPSolver::addArgumentTrackedFunction(Function *F) { … }

bool SCCPSolver::isArgumentTrackedFunction(Function *F) { … }

const SmallPtrSetImpl<Function *> &
SCCPSolver::getArgumentTrackedFunctions() const { … }

void SCCPSolver::solve() { … }

bool SCCPSolver::resolvedUndefsIn(Function &F) { … }

void SCCPSolver::solveWhileResolvedUndefsIn(Module &M) { … }

void
SCCPSolver::solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList) { … }

void SCCPSolver::solveWhileResolvedUndefs() { … }

bool SCCPSolver::isBlockExecutable(BasicBlock *BB) const { … }

bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const { … }

std::vector<ValueLatticeElement>
SCCPSolver::getStructLatticeValueFor(Value *V) const { … }

void SCCPSolver::removeLatticeValueFor(Value *V) { … }

void SCCPSolver::resetLatticeValueFor(CallBase *Call) { … }

const ValueLatticeElement &SCCPSolver::getLatticeValueFor(Value *V) const { … }

const MapVector<Function *, ValueLatticeElement> &
SCCPSolver::getTrackedRetVals() const { … }

const DenseMap<GlobalVariable *, ValueLatticeElement> &
SCCPSolver::getTrackedGlobals() { … }

const SmallPtrSet<Function *, 16> SCCPSolver::getMRVFunctionsTracked() { … }

void SCCPSolver::markOverdefined(Value *V) { … }

void SCCPSolver::trackValueOfArgument(Argument *V) { … }

bool SCCPSolver::isStructLatticeConstant(Function *F, StructType *STy) { … }

Constant *SCCPSolver::getConstant(const ValueLatticeElement &LV,
                                  Type *Ty) const { … }

Constant *SCCPSolver::getConstantOrNull(Value *V) const { … }

void SCCPSolver::setLatticeValueForSpecializationArguments(Function *F,
                                   const SmallVectorImpl<ArgInfo> &Args) { … }

void SCCPSolver::markFunctionUnreachable(Function *F) { … }

void SCCPSolver::visit(Instruction *I) { … }

void SCCPSolver::visitCall(CallInst &I) { … }
llvm/llvm/lib/Transforms/Utils/SCCPSolver.cpp
