412 lines · cpp
1//===- CalledValuePropagation.cpp - Propagate called values -----*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a transformation that attaches !callees metadata to10// indirect call sites. For a given call site, the metadata, if present,11// indicates the set of functions the call site could possibly target at12// run-time. This metadata is added to indirect call sites when the set of13// possible targets can be determined by analysis and is known to be small. The14// analysis driving the transformation is similar to constant propagation and15// makes uses of the generic sparse propagation solver.16//17//===----------------------------------------------------------------------===//18 19#include "llvm/Transforms/IPO/CalledValuePropagation.h"20#include "llvm/Analysis/SparsePropagation.h"21#include "llvm/Analysis/ValueLatticeUtils.h"22#include "llvm/IR/Constants.h"23#include "llvm/IR/MDBuilder.h"24#include "llvm/IR/Module.h"25#include "llvm/Support/CommandLine.h"26#include "llvm/Transforms/IPO.h"27 28using namespace llvm;29 30#define DEBUG_TYPE "called-value-propagation"31 32/// The maximum number of functions to track per lattice value. Once the number33/// of functions a call site can possibly target exceeds this threshold, it's34/// lattice value becomes overdefined. The number of possible lattice values is35/// bounded by Ch(F, M), where F is the number of functions in the module and M36/// is MaxFunctionsPerValue. As such, this value should be kept very small. We37/// likely can't do anything useful for call sites with a large number of38/// possible targets, anyway.39static cl::opt<unsigned> MaxFunctionsPerValue(40 "cvp-max-functions-per-value", cl::Hidden, cl::init(4),41 cl::desc("The maximum number of functions to track per lattice value"));42 43namespace {44/// To enable interprocedural analysis, we assign LLVM values to the following45/// groups. The register group represents SSA registers, the return group46/// represents the return values of functions, and the memory group represents47/// in-memory values. An LLVM Value can technically be in more than one group.48/// It's necessary to distinguish these groups so we can, for example, track a49/// global variable separately from the value stored at its location.50enum class IPOGrouping { Register, Return, Memory };51 52/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.53using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;54 55/// The lattice value type used by our custom lattice function. It holds the56/// lattice state, and a set of functions.57class CVPLatticeVal {58public:59 /// The states of the lattice values. Only the FunctionSet state is60 /// interesting. It indicates the set of functions to which an LLVM value may61 /// refer.62 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };63 64 /// Comparator for sorting the functions set. We want to keep the order65 /// deterministic for testing, etc.66 struct Compare {67 bool operator()(const Function *LHS, const Function *RHS) const {68 return LHS->getName() < RHS->getName();69 }70 };71 72 CVPLatticeVal() = default;73 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}74 CVPLatticeVal(std::vector<Function *> &&Functions)75 : LatticeState(FunctionSet), Functions(std::move(Functions)) {76 assert(llvm::is_sorted(this->Functions, Compare()));77 }78 79 /// Get a reference to the functions held by this lattice value. The number80 /// of functions will be zero for states other than FunctionSet.81 const std::vector<Function *> &getFunctions() const {82 return Functions;83 }84 85 /// Returns true if the lattice value is in the FunctionSet state.86 bool isFunctionSet() const { return LatticeState == FunctionSet; }87 88 bool operator==(const CVPLatticeVal &RHS) const {89 return LatticeState == RHS.LatticeState && Functions == RHS.Functions;90 }91 92 bool operator!=(const CVPLatticeVal &RHS) const {93 return LatticeState != RHS.LatticeState || Functions != RHS.Functions;94 }95 96private:97 /// Holds the state this lattice value is in.98 CVPLatticeStateTy LatticeState = Undefined;99 100 /// Holds functions indicating the possible targets of call sites. This set101 /// is empty for lattice values in the undefined, overdefined, and untracked102 /// states. The maximum size of the set is controlled by103 /// MaxFunctionsPerValue. Since most LLVM values are expected to be in104 /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be105 /// small and efficiently copyable.106 // FIXME: This could be a TinyPtrVector and/or merge with LatticeState.107 std::vector<Function *> Functions;108};109 110/// The custom lattice function used by the generic sparse propagation solver.111/// It handles merging lattice values and computing new lattice values for112/// constants, arguments, values returned from trackable functions, and values113/// located in trackable global variables. It also computes the lattice values114/// that change as a result of executing instructions.115class CVPLatticeFunc116 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {117public:118 CVPLatticeFunc()119 : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),120 CVPLatticeVal(CVPLatticeVal::Overdefined),121 CVPLatticeVal(CVPLatticeVal::Untracked)) {}122 123 /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.124 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {125 switch (Key.getInt()) {126 case IPOGrouping::Register:127 if (isa<Instruction>(Key.getPointer())) {128 return getUndefVal();129 } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {130 if (canTrackArgumentsInterprocedurally(A->getParent()))131 return getUndefVal();132 } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {133 return computeConstant(C);134 }135 return getOverdefinedVal();136 case IPOGrouping::Memory:137 case IPOGrouping::Return:138 if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {139 if (canTrackGlobalVariableInterprocedurally(GV))140 return computeConstant(GV->getInitializer());141 } else if (auto *F = cast<Function>(Key.getPointer()))142 if (canTrackReturnsInterprocedurally(F))143 return getUndefVal();144 }145 return getOverdefinedVal();146 }147 148 /// Merge the two given lattice values. The interesting cases are merging two149 /// FunctionSet values and a FunctionSet value with an Undefined value. For150 /// these cases, we simply union the function sets. If the size of the union151 /// is greater than the maximum functions we track, the merged value is152 /// overdefined.153 CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {154 if (X == getOverdefinedVal() || Y == getOverdefinedVal())155 return getOverdefinedVal();156 if (X == getUndefVal() && Y == getUndefVal())157 return getUndefVal();158 std::vector<Function *> Union;159 std::set_union(X.getFunctions().begin(), X.getFunctions().end(),160 Y.getFunctions().begin(), Y.getFunctions().end(),161 std::back_inserter(Union), CVPLatticeVal::Compare{});162 if (Union.size() > MaxFunctionsPerValue)163 return getOverdefinedVal();164 return CVPLatticeVal(std::move(Union));165 }166 167 /// Compute the lattice values that change as a result of executing the given168 /// instruction. The changed values are stored in \p ChangedValues. We handle169 /// just a few kinds of instructions since we're only propagating values that170 /// can be called.171 void ComputeInstructionState(172 Instruction &I,173 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,174 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {175 switch (I.getOpcode()) {176 case Instruction::Call:177 case Instruction::Invoke:178 return visitCallBase(cast<CallBase>(I), ChangedValues, SS);179 case Instruction::Load:180 return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);181 case Instruction::Ret:182 return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);183 case Instruction::Select:184 return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);185 case Instruction::Store:186 return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);187 default:188 return visitInst(I, ChangedValues, SS);189 }190 }191 192 /// Print the given CVPLatticeVal to the specified stream.193 void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {194 if (LV == getUndefVal())195 OS << "Undefined ";196 else if (LV == getOverdefinedVal())197 OS << "Overdefined";198 else if (LV == getUntrackedVal())199 OS << "Untracked ";200 else201 OS << "FunctionSet";202 }203 204 /// Print the given CVPLatticeKey to the specified stream.205 void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {206 if (Key.getInt() == IPOGrouping::Register)207 OS << "<reg> ";208 else if (Key.getInt() == IPOGrouping::Memory)209 OS << "<mem> ";210 else if (Key.getInt() == IPOGrouping::Return)211 OS << "<ret> ";212 if (isa<Function>(Key.getPointer()))213 OS << Key.getPointer()->getName();214 else215 OS << *Key.getPointer();216 }217 218 /// We collect a set of indirect calls when visiting call sites. This method219 /// returns a reference to that set.220 SmallPtrSetImpl<CallBase *> &getIndirectCalls() { return IndirectCalls; }221 222private:223 /// Holds the indirect calls we encounter during the analysis. We will attach224 /// metadata to these calls after the analysis indicating the functions the225 /// calls can possibly target.226 SmallPtrSet<CallBase *, 32> IndirectCalls;227 228 /// Compute a new lattice value for the given constant. The constant, after229 /// stripping any pointer casts, should be a Function. We ignore null230 /// pointers as an optimization, since calling these values is undefined231 /// behavior.232 CVPLatticeVal computeConstant(Constant *C) {233 if (isa<ConstantPointerNull>(C))234 return CVPLatticeVal(CVPLatticeVal::FunctionSet);235 if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))236 return CVPLatticeVal({F});237 return getOverdefinedVal();238 }239 240 /// Handle return instructions. The function's return state is the merge of241 /// the returned value state and the function's return state.242 void243 visitReturn(ReturnInst &I,244 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,245 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {246 Function *F = I.getParent()->getParent();247 if (F->getReturnType()->isVoidTy())248 return;249 auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);250 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);251 ChangedValues[RetF] =252 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));253 }254 255 /// Handle call sites. The state of a called function's formal arguments is256 /// the merge of the argument state with the call sites corresponding actual257 /// argument state. The call site state is the merge of the call site state258 /// with the returned value state of the called function.259 void260 visitCallBase(CallBase &CB,261 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,262 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {263 Function *F = CB.getCalledFunction();264 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);265 266 // If this is an indirect call, save it so we can quickly revisit it when267 // attaching metadata.268 if (!F)269 IndirectCalls.insert(&CB);270 271 // If we can't track the function's return values, there's nothing to do.272 if (!F || !canTrackReturnsInterprocedurally(F)) {273 // Void return, No need to create and update CVPLattice state as no one274 // can use it.275 if (CB.getType()->isVoidTy())276 return;277 ChangedValues[RegI] = getOverdefinedVal();278 return;279 }280 281 // Inform the solver that the called function is executable, and perform282 // the merges for the arguments and return value.283 SS.MarkBlockExecutable(&F->front());284 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);285 for (Argument &A : F->args()) {286 auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);287 auto RegActual =288 CVPLatticeKey(CB.getArgOperand(A.getArgNo()), IPOGrouping::Register);289 ChangedValues[RegFormal] =290 MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));291 }292 293 // Void return, No need to create and update CVPLattice state as no one can294 // use it.295 if (CB.getType()->isVoidTy())296 return;297 298 ChangedValues[RegI] =299 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));300 }301 302 /// Handle select instructions. The select instruction state is the merge the303 /// true and false value states.304 void305 visitSelect(SelectInst &I,306 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,307 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {308 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);309 auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);310 auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);311 ChangedValues[RegI] =312 MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));313 }314 315 /// Handle load instructions. If the pointer operand of the load is a global316 /// variable, we attempt to track the value. The loaded value state is the317 /// merge of the loaded value state with the global variable state.318 void visitLoad(LoadInst &I,319 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,320 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {321 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);322 if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {323 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);324 ChangedValues[RegI] =325 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));326 } else {327 ChangedValues[RegI] = getOverdefinedVal();328 }329 }330 331 /// Handle store instructions. If the pointer operand of the store is a332 /// global variable, we attempt to track the value. The global variable state333 /// is the merge of the stored value state with the global variable state.334 void335 visitStore(StoreInst &I,336 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,337 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {338 auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());339 if (!GV)340 return;341 auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);342 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);343 ChangedValues[MemGV] =344 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));345 }346 347 /// Handle all other instructions. All other instructions are marked348 /// overdefined.349 void visitInst(Instruction &I,350 SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues,351 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {352 // Simply bail if this instruction has no user.353 if (I.use_empty())354 return;355 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);356 ChangedValues[RegI] = getOverdefinedVal();357 }358};359} // namespace360 361namespace llvm {362/// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver363/// must translate between LatticeKeys and LLVM Values when adding Values to364/// its work list and inspecting the state of control-flow related values.365template <> struct LatticeKeyInfo<CVPLatticeKey> {366 static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {367 return Key.getPointer();368 }369 static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {370 return CVPLatticeKey(V, IPOGrouping::Register);371 }372};373} // namespace llvm374 375static bool runCVP(Module &M) {376 // Our custom lattice function and generic sparse propagation solver.377 CVPLatticeFunc Lattice;378 SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);379 380 // For each function in the module, if we can't track its arguments, let the381 // generic solver assume it is executable.382 for (Function &F : M)383 if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))384 Solver.MarkBlockExecutable(&F.front());385 386 // Solver our custom lattice. In doing so, we will also build a set of387 // indirect call sites.388 Solver.Solve();389 390 // Attach metadata to the indirect call sites that were collected indicating391 // the set of functions they can possibly target.392 bool Changed = false;393 MDBuilder MDB(M.getContext());394 for (CallBase *C : Lattice.getIndirectCalls()) {395 auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register);396 CVPLatticeVal LV = Solver.getExistingValueState(RegI);397 if (!LV.isFunctionSet() || LV.getFunctions().empty())398 continue;399 MDNode *Callees = MDB.createCallees(LV.getFunctions());400 C->setMetadata(LLVMContext::MD_callees, Callees);401 Changed = true;402 }403 404 return Changed;405}406 407PreservedAnalyses CalledValuePropagationPass::run(Module &M,408 ModuleAnalysisManager &) {409 runCVP(M);410 return PreservedAnalyses::all();411}412