You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
435 lines
18 KiB
435 lines
18 KiB
//===- CalledValuePropagation.cpp - Propagate called values -----*- 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 implements a transformation that attaches !callees metadata to
|
|
// indirect call sites. For a given call site, the metadata, if present,
|
|
// indicates the set of functions the call site could possibly target at
|
|
// run-time. This metadata is added to indirect call sites when the set of
|
|
// possible targets can be determined by analysis and is known to be small. The
|
|
// analysis driving the transformation is similar to constant propagation and
|
|
// makes uses of the generic sparse propagation solver.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "llvm/Transforms/IPO/CalledValuePropagation.h"
|
|
#include "llvm/Analysis/SparsePropagation.h"
|
|
#include "llvm/Analysis/ValueLatticeUtils.h"
|
|
#include "llvm/IR/MDBuilder.h"
|
|
#include "llvm/InitializePasses.h"
|
|
#include "llvm/Support/CommandLine.h"
|
|
#include "llvm/Transforms/IPO.h"
|
|
using namespace llvm;
|
|
|
|
#define DEBUG_TYPE "called-value-propagation"
|
|
|
|
/// The maximum number of functions to track per lattice value. Once the number
|
|
/// of functions a call site can possibly target exceeds this threshold, it's
|
|
/// lattice value becomes overdefined. The number of possible lattice values is
|
|
/// bounded by Ch(F, M), where F is the number of functions in the module and M
|
|
/// is MaxFunctionsPerValue. As such, this value should be kept very small. We
|
|
/// likely can't do anything useful for call sites with a large number of
|
|
/// possible targets, anyway.
|
|
static cl::opt<unsigned> MaxFunctionsPerValue(
|
|
"cvp-max-functions-per-value", cl::Hidden, cl::init(4),
|
|
cl::desc("The maximum number of functions to track per lattice value"));
|
|
|
|
namespace {
|
|
/// To enable interprocedural analysis, we assign LLVM values to the following
|
|
/// groups. The register group represents SSA registers, the return group
|
|
/// represents the return values of functions, and the memory group represents
|
|
/// in-memory values. An LLVM Value can technically be in more than one group.
|
|
/// It's necessary to distinguish these groups so we can, for example, track a
|
|
/// global variable separately from the value stored at its location.
|
|
enum class IPOGrouping { Register, Return, Memory };
|
|
|
|
/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
|
|
using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
|
|
|
|
/// The lattice value type used by our custom lattice function. It holds the
|
|
/// lattice state, and a set of functions.
|
|
class CVPLatticeVal {
|
|
public:
|
|
/// The states of the lattice values. Only the FunctionSet state is
|
|
/// interesting. It indicates the set of functions to which an LLVM value may
|
|
/// refer.
|
|
enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
|
|
|
|
/// Comparator for sorting the functions set. We want to keep the order
|
|
/// deterministic for testing, etc.
|
|
struct Compare {
|
|
bool operator()(const Function *LHS, const Function *RHS) const {
|
|
return LHS->getName() < RHS->getName();
|
|
}
|
|
};
|
|
|
|
CVPLatticeVal() : LatticeState(Undefined) {}
|
|
CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
|
|
CVPLatticeVal(std::vector<Function *> &&Functions)
|
|
: LatticeState(FunctionSet), Functions(std::move(Functions)) {
|
|
assert(llvm::is_sorted(this->Functions, Compare()));
|
|
}
|
|
|
|
/// Get a reference to the functions held by this lattice value. The number
|
|
/// of functions will be zero for states other than FunctionSet.
|
|
const std::vector<Function *> &getFunctions() const {
|
|
return Functions;
|
|
}
|
|
|
|
/// Returns true if the lattice value is in the FunctionSet state.
|
|
bool isFunctionSet() const { return LatticeState == FunctionSet; }
|
|
|
|
bool operator==(const CVPLatticeVal &RHS) const {
|
|
return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
|
|
}
|
|
|
|
bool operator!=(const CVPLatticeVal &RHS) const {
|
|
return LatticeState != RHS.LatticeState || Functions != RHS.Functions;
|
|
}
|
|
|
|
private:
|
|
/// Holds the state this lattice value is in.
|
|
CVPLatticeStateTy LatticeState;
|
|
|
|
/// Holds functions indicating the possible targets of call sites. This set
|
|
/// is empty for lattice values in the undefined, overdefined, and untracked
|
|
/// states. The maximum size of the set is controlled by
|
|
/// MaxFunctionsPerValue. Since most LLVM values are expected to be in
|
|
/// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
|
|
/// small and efficiently copyable.
|
|
// FIXME: This could be a TinyPtrVector and/or merge with LatticeState.
|
|
std::vector<Function *> Functions;
|
|
};
|
|
|
|
/// The custom lattice function used by the generic sparse propagation solver.
|
|
/// It handles merging lattice values and computing new lattice values for
|
|
/// constants, arguments, values returned from trackable functions, and values
|
|
/// located in trackable global variables. It also computes the lattice values
|
|
/// that change as a result of executing instructions.
|
|
class CVPLatticeFunc
|
|
: public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
|
|
public:
|
|
CVPLatticeFunc()
|
|
: AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),
|
|
CVPLatticeVal(CVPLatticeVal::Overdefined),
|
|
CVPLatticeVal(CVPLatticeVal::Untracked)) {}
|
|
|
|
/// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
|
|
CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
|
|
switch (Key.getInt()) {
|
|
case IPOGrouping::Register:
|
|
if (isa<Instruction>(Key.getPointer())) {
|
|
return getUndefVal();
|
|
} else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
|
|
if (canTrackArgumentsInterprocedurally(A->getParent()))
|
|
return getUndefVal();
|
|
} else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
|
|
return computeConstant(C);
|
|
}
|
|
return getOverdefinedVal();
|
|
case IPOGrouping::Memory:
|
|
case IPOGrouping::Return:
|
|
if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
|
|
if (canTrackGlobalVariableInterprocedurally(GV))
|
|
return computeConstant(GV->getInitializer());
|
|
} else if (auto *F = cast<Function>(Key.getPointer()))
|
|
if (canTrackReturnsInterprocedurally(F))
|
|
return getUndefVal();
|
|
}
|
|
return getOverdefinedVal();
|
|
}
|
|
|
|
/// Merge the two given lattice values. The interesting cases are merging two
|
|
/// FunctionSet values and a FunctionSet value with an Undefined value. For
|
|
/// these cases, we simply union the function sets. If the size of the union
|
|
/// is greater than the maximum functions we track, the merged value is
|
|
/// overdefined.
|
|
CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
|
|
if (X == getOverdefinedVal() || Y == getOverdefinedVal())
|
|
return getOverdefinedVal();
|
|
if (X == getUndefVal() && Y == getUndefVal())
|
|
return getUndefVal();
|
|
std::vector<Function *> Union;
|
|
std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
|
|
Y.getFunctions().begin(), Y.getFunctions().end(),
|
|
std::back_inserter(Union), CVPLatticeVal::Compare{});
|
|
if (Union.size() > MaxFunctionsPerValue)
|
|
return getOverdefinedVal();
|
|
return CVPLatticeVal(std::move(Union));
|
|
}
|
|
|
|
/// Compute the lattice values that change as a result of executing the given
|
|
/// instruction. The changed values are stored in \p ChangedValues. We handle
|
|
/// just a few kinds of instructions since we're only propagating values that
|
|
/// can be called.
|
|
void ComputeInstructionState(
|
|
Instruction &I, DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {
|
|
switch (I.getOpcode()) {
|
|
case Instruction::Call:
|
|
case Instruction::Invoke:
|
|
return visitCallBase(cast<CallBase>(I), ChangedValues, SS);
|
|
case Instruction::Load:
|
|
return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
|
|
case Instruction::Ret:
|
|
return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
|
|
case Instruction::Select:
|
|
return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
|
|
case Instruction::Store:
|
|
return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
|
|
default:
|
|
return visitInst(I, ChangedValues, SS);
|
|
}
|
|
}
|
|
|
|
/// Print the given CVPLatticeVal to the specified stream.
|
|
void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {
|
|
if (LV == getUndefVal())
|
|
OS << "Undefined ";
|
|
else if (LV == getOverdefinedVal())
|
|
OS << "Overdefined";
|
|
else if (LV == getUntrackedVal())
|
|
OS << "Untracked ";
|
|
else
|
|
OS << "FunctionSet";
|
|
}
|
|
|
|
/// Print the given CVPLatticeKey to the specified stream.
|
|
void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {
|
|
if (Key.getInt() == IPOGrouping::Register)
|
|
OS << "<reg> ";
|
|
else if (Key.getInt() == IPOGrouping::Memory)
|
|
OS << "<mem> ";
|
|
else if (Key.getInt() == IPOGrouping::Return)
|
|
OS << "<ret> ";
|
|
if (isa<Function>(Key.getPointer()))
|
|
OS << Key.getPointer()->getName();
|
|
else
|
|
OS << *Key.getPointer();
|
|
}
|
|
|
|
/// We collect a set of indirect calls when visiting call sites. This method
|
|
/// returns a reference to that set.
|
|
SmallPtrSetImpl<CallBase *> &getIndirectCalls() { return IndirectCalls; }
|
|
|
|
private:
|
|
/// Holds the indirect calls we encounter during the analysis. We will attach
|
|
/// metadata to these calls after the analysis indicating the functions the
|
|
/// calls can possibly target.
|
|
SmallPtrSet<CallBase *, 32> IndirectCalls;
|
|
|
|
/// Compute a new lattice value for the given constant. The constant, after
|
|
/// stripping any pointer casts, should be a Function. We ignore null
|
|
/// pointers as an optimization, since calling these values is undefined
|
|
/// behavior.
|
|
CVPLatticeVal computeConstant(Constant *C) {
|
|
if (isa<ConstantPointerNull>(C))
|
|
return CVPLatticeVal(CVPLatticeVal::FunctionSet);
|
|
if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))
|
|
return CVPLatticeVal({F});
|
|
return getOverdefinedVal();
|
|
}
|
|
|
|
/// Handle return instructions. The function's return state is the merge of
|
|
/// the returned value state and the function's return state.
|
|
void visitReturn(ReturnInst &I,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
Function *F = I.getParent()->getParent();
|
|
if (F->getReturnType()->isVoidTy())
|
|
return;
|
|
auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
|
|
auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
|
|
ChangedValues[RetF] =
|
|
MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
|
|
}
|
|
|
|
/// Handle call sites. The state of a called function's formal arguments is
|
|
/// the merge of the argument state with the call sites corresponding actual
|
|
/// argument state. The call site state is the merge of the call site state
|
|
/// with the returned value state of the called function.
|
|
void visitCallBase(CallBase &CB,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
Function *F = CB.getCalledFunction();
|
|
auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);
|
|
|
|
// If this is an indirect call, save it so we can quickly revisit it when
|
|
// attaching metadata.
|
|
if (!F)
|
|
IndirectCalls.insert(&CB);
|
|
|
|
// If we can't track the function's return values, there's nothing to do.
|
|
if (!F || !canTrackReturnsInterprocedurally(F)) {
|
|
// Void return, No need to create and update CVPLattice state as no one
|
|
// can use it.
|
|
if (CB.getType()->isVoidTy())
|
|
return;
|
|
ChangedValues[RegI] = getOverdefinedVal();
|
|
return;
|
|
}
|
|
|
|
// Inform the solver that the called function is executable, and perform
|
|
// the merges for the arguments and return value.
|
|
SS.MarkBlockExecutable(&F->front());
|
|
auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
|
|
for (Argument &A : F->args()) {
|
|
auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
|
|
auto RegActual =
|
|
CVPLatticeKey(CB.getArgOperand(A.getArgNo()), IPOGrouping::Register);
|
|
ChangedValues[RegFormal] =
|
|
MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
|
|
}
|
|
|
|
// Void return, No need to create and update CVPLattice state as no one can
|
|
// use it.
|
|
if (CB.getType()->isVoidTy())
|
|
return;
|
|
|
|
ChangedValues[RegI] =
|
|
MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
|
|
}
|
|
|
|
/// Handle select instructions. The select instruction state is the merge the
|
|
/// true and false value states.
|
|
void visitSelect(SelectInst &I,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
|
|
auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
|
|
auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
|
|
ChangedValues[RegI] =
|
|
MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
|
|
}
|
|
|
|
/// Handle load instructions. If the pointer operand of the load is a global
|
|
/// variable, we attempt to track the value. The loaded value state is the
|
|
/// merge of the loaded value state with the global variable state.
|
|
void visitLoad(LoadInst &I,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
|
|
if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
|
|
auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
|
|
ChangedValues[RegI] =
|
|
MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
|
|
} else {
|
|
ChangedValues[RegI] = getOverdefinedVal();
|
|
}
|
|
}
|
|
|
|
/// Handle store instructions. If the pointer operand of the store is a
|
|
/// global variable, we attempt to track the value. The global variable state
|
|
/// is the merge of the stored value state with the global variable state.
|
|
void visitStore(StoreInst &I,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
|
|
if (!GV)
|
|
return;
|
|
auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
|
|
auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
|
|
ChangedValues[MemGV] =
|
|
MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
|
|
}
|
|
|
|
/// Handle all other instructions. All other instructions are marked
|
|
/// overdefined.
|
|
void visitInst(Instruction &I,
|
|
DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
|
|
// Simply bail if this instruction has no user.
|
|
if (I.use_empty())
|
|
return;
|
|
auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
|
|
ChangedValues[RegI] = getOverdefinedVal();
|
|
}
|
|
};
|
|
} // namespace
|
|
|
|
namespace llvm {
|
|
/// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
|
|
/// must translate between LatticeKeys and LLVM Values when adding Values to
|
|
/// its work list and inspecting the state of control-flow related values.
|
|
template <> struct LatticeKeyInfo<CVPLatticeKey> {
|
|
static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
|
|
return Key.getPointer();
|
|
}
|
|
static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
|
|
return CVPLatticeKey(V, IPOGrouping::Register);
|
|
}
|
|
};
|
|
} // namespace llvm
|
|
|
|
static bool runCVP(Module &M) {
|
|
// Our custom lattice function and generic sparse propagation solver.
|
|
CVPLatticeFunc Lattice;
|
|
SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);
|
|
|
|
// For each function in the module, if we can't track its arguments, let the
|
|
// generic solver assume it is executable.
|
|
for (Function &F : M)
|
|
if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
|
|
Solver.MarkBlockExecutable(&F.front());
|
|
|
|
// Solver our custom lattice. In doing so, we will also build a set of
|
|
// indirect call sites.
|
|
Solver.Solve();
|
|
|
|
// Attach metadata to the indirect call sites that were collected indicating
|
|
// the set of functions they can possibly target.
|
|
bool Changed = false;
|
|
MDBuilder MDB(M.getContext());
|
|
for (CallBase *C : Lattice.getIndirectCalls()) {
|
|
auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register);
|
|
CVPLatticeVal LV = Solver.getExistingValueState(RegI);
|
|
if (!LV.isFunctionSet() || LV.getFunctions().empty())
|
|
continue;
|
|
MDNode *Callees = MDB.createCallees(LV.getFunctions());
|
|
C->setMetadata(LLVMContext::MD_callees, Callees);
|
|
Changed = true;
|
|
}
|
|
|
|
return Changed;
|
|
}
|
|
|
|
PreservedAnalyses CalledValuePropagationPass::run(Module &M,
|
|
ModuleAnalysisManager &) {
|
|
runCVP(M);
|
|
return PreservedAnalyses::all();
|
|
}
|
|
|
|
namespace {
|
|
class CalledValuePropagationLegacyPass : public ModulePass {
|
|
public:
|
|
static char ID;
|
|
|
|
void getAnalysisUsage(AnalysisUsage &AU) const override {
|
|
AU.setPreservesAll();
|
|
}
|
|
|
|
CalledValuePropagationLegacyPass() : ModulePass(ID) {
|
|
initializeCalledValuePropagationLegacyPassPass(
|
|
*PassRegistry::getPassRegistry());
|
|
}
|
|
|
|
bool runOnModule(Module &M) override {
|
|
if (skipModule(M))
|
|
return false;
|
|
return runCVP(M);
|
|
}
|
|
};
|
|
} // namespace
|
|
|
|
char CalledValuePropagationLegacyPass::ID = 0;
|
|
INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
|
|
"Called Value Propagation", false, false)
|
|
|
|
ModulePass *llvm::createCalledValuePropagationPass() {
|
|
return new CalledValuePropagationLegacyPass();
|
|
}
|