//===- SCCPSolver.h - 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 Sparse Conditional Constant Propagation (SCCP) utility.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
#define LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Transforms/Utils/PredicateInfo.h"
#include <vector>
namespace llvm {
class Argument;
class BasicBlock;
class CallInst;
class Constant;
class DataLayout;
class DominatorTree;
class Function;
class GlobalVariable;
class Instruction;
class LLVMContext;
class LoopInfo;
class PostDominatorTree;
class StructType;
class TargetLibraryInfo;
class Value;
class ValueLatticeElement;
/// Helper struct for bundling up the analysis results per function for IPSCCP.
struct AnalysisResultsForFn {
std::unique_ptr<PredicateInfo> PredInfo;
DominatorTree *DT;
PostDominatorTree *PDT;
LoopInfo *LI;
};
/// Helper struct shared between Function Specialization and SCCP Solver.
struct ArgInfo {
Argument *Formal; // The Formal argument being analysed.
Constant *Actual; // A corresponding actual constant argument.
ArgInfo(Argument *F, Constant *A) : Formal(F), Actual(A) {}
bool operator==(const ArgInfo &Other) const {
return Formal == Other.Formal && Actual == Other.Actual;
}
bool operator!=(const ArgInfo &Other) const { return !(*this == Other); }
friend hash_code hash_value(const ArgInfo &A) {
return hash_combine(hash_value(A.Formal), hash_value(A.Actual));
}
};
class SCCPInstVisitor;
//===----------------------------------------------------------------------===//
//
/// SCCPSolver - This interface class is a general purpose solver for Sparse
/// Conditional Constant Propagation (SCCP).
///
class SCCPSolver {
std::unique_ptr<SCCPInstVisitor> Visitor;
public:
SCCPSolver(const DataLayout &DL,
std::function<const TargetLibraryInfo &(Function &)> GetTLI,
LLVMContext &Ctx);
~SCCPSolver();
void addAnalysis(Function &F, AnalysisResultsForFn A);
/// markBlockExecutable - This method can be used by clients to mark all of
/// the blocks that are known to be intrinsically live in the processed unit.
/// This returns true if the block was not considered live before.
bool markBlockExecutable(BasicBlock *BB);
const PredicateBase *getPredicateInfoFor(Instruction *I);
const LoopInfo &getLoopInfo(Function &F);
DomTreeUpdater getDTU(Function &F);
/// trackValueOfGlobalVariable - Clients can use this method to
/// inform the SCCPSolver that it should track loads and stores to the
/// specified global variable if it can. This is only legal to call if
/// performing Interprocedural SCCP.
void trackValueOfGlobalVariable(GlobalVariable *GV);
/// addTrackedFunction - If the SCCP solver is supposed to track calls into
/// and out of the specified function (which cannot have its address taken),
/// this method must be called.
void addTrackedFunction(Function *F);
/// Add function to the list of functions whose return cannot be modified.
void addToMustPreserveReturnsInFunctions(Function *F);
/// Returns true if the return of the given function cannot be modified.
bool mustPreserveReturn(Function *F);
void addArgumentTrackedFunction(Function *F);
/// Returns true if the given function is in the solver's set of
/// argument-tracked functions.
bool isArgumentTrackedFunction(Function *F);
/// Solve - Solve for constants and executable blocks.
void solve();
/// resolvedUndefsIn - While solving the dataflow for a function, we assume
/// that branches on undef values cannot reach any of their successors.
/// However, this is not a safe assumption. After we solve dataflow, this
/// method should be use to handle this. If this returns true, the solver
/// should be rerun.
bool resolvedUndefsIn(Function &F);
void solveWhileResolvedUndefsIn(Module &M);
void solveWhileResolvedUndefsIn(SmallVectorImpl<Function *> &WorkList);
bool isBlockExecutable(BasicBlock *BB) const;
// isEdgeFeasible - Return true if the control flow edge from the 'From' basic
// block to the 'To' basic block is currently feasible.
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const;
void removeLatticeValueFor(Value *V);
const ValueLatticeElement &getLatticeValueFor(Value *V) const;
/// getTrackedRetVals - Get the inferred return value map.
const MapVector<Function *, ValueLatticeElement> &getTrackedRetVals();
/// getTrackedGlobals - Get and return the set of inferred initializers for
/// global variables.
const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals();
/// getMRVFunctionsTracked - Get the set of functions which return multiple
/// values tracked by the pass.
const SmallPtrSet<Function *, 16> getMRVFunctionsTracked();
/// markOverdefined - Mark the specified value overdefined. This
/// works with both scalars and structs.
void markOverdefined(Value *V);
// isStructLatticeConstant - Return true if all the lattice values
// corresponding to elements of the structure are constants,
// false otherwise.
bool isStructLatticeConstant(Function *F, StructType *STy);
/// Helper to return a Constant if \p LV is either a constant or a constant
/// range with a single element.
Constant *getConstant(const ValueLatticeElement &LV) const;
/// Return a reference to the set of argument tracked functions.
SmallPtrSetImpl<Function *> &getArgumentTrackedFunctions();
/// Mark the constant arguments of a new function specialization. \p F points
/// to the cloned function and \p Args contains a list of constant arguments
/// represented as pairs of {formal,actual} values (the formal argument is
/// associated with the original function definition). All other arguments of
/// the specialization inherit the lattice state of their corresponding values
/// in the original function.
void markArgInFuncSpecialization(Function *F,
const SmallVectorImpl<ArgInfo> &Args);
/// Mark all of the blocks in function \p F non-executable. Clients can used
/// this method to erase a function from the module (e.g., if it has been
/// completely specialized and is no longer needed).
void markFunctionUnreachable(Function *F);
void visit(Instruction *I);
void visitCall(CallInst &I);
bool simplifyInstsInBlock(BasicBlock &BB,
SmallPtrSetImpl<Value *> &InsertedValues,
Statistic &InstRemovedStat,
Statistic &InstReplacedStat);
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU,
BasicBlock *&NewUnreachableBB) const;
bool tryToReplaceWithConstant(Value *V);
// Helper to check if \p LV is either a constant or a constant
// range with a single element. This should cover exactly the same cases as
// the old ValueLatticeElement::isConstant() and is intended to be used in the
// transition to ValueLatticeElement.
static bool isConstant(const ValueLatticeElement &LV);
// Helper to check if \p LV is either overdefined or a constant range with
// more than a single element. This should cover exactly the same cases as the
// old ValueLatticeElement::isOverdefined() and is intended to be used in the
// transition to ValueLatticeElement.
static bool isOverdefined(const ValueLatticeElement &LV);
};
} // namespace llvm
#endif // LLVM_TRANSFORMS_UTILS_SCCPSOLVER_H