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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements a transformation that attaches !callees metadata to 10 // indirect call sites. For a given call site, the metadata, if present, 11 // indicates the set of functions the call site could possibly target at 12 // run-time. This metadata is added to indirect call sites when the set of 13 // possible targets can be determined by analysis and is known to be small. The 14 // analysis driving the transformation is similar to constant propagation and 15 // 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 28 using namespace llvm; 29 30 #define DEBUG_TYPE "called-value-propagation" 31 32 /// The maximum number of functions to track per lattice value. Once the number 33 /// of functions a call site can possibly target exceeds this threshold, it's 34 /// lattice value becomes overdefined. The number of possible lattice values is 35 /// bounded by Ch(F, M), where F is the number of functions in the module and M 36 /// is MaxFunctionsPerValue. As such, this value should be kept very small. We 37 /// likely can't do anything useful for call sites with a large number of 38 /// possible targets, anyway. 39 static 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 43 namespace { 44 /// To enable interprocedural analysis, we assign LLVM values to the following 45 /// groups. The register group represents SSA registers, the return group 46 /// represents the return values of functions, and the memory group represents 47 /// 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 a 49 /// global variable separately from the value stored at its location. 50 enum class IPOGrouping { Register, Return, Memory }; 51 52 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings. 53 using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>; 54 55 /// The lattice value type used by our custom lattice function. It holds the 56 /// lattice state, and a set of functions. 57 class CVPLatticeVal { 58 public: 59 /// The states of the lattice values. Only the FunctionSet state is 60 /// interesting. It indicates the set of functions to which an LLVM value may 61 /// refer. 62 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked }; 63 64 /// Comparator for sorting the functions set. We want to keep the order 65 /// 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 number 80 /// 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 96 private: 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 set 101 /// is empty for lattice values in the undefined, overdefined, and untracked 102 /// states. The maximum size of the set is controlled by 103 /// MaxFunctionsPerValue. Since most LLVM values are expected to be in 104 /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be 105 /// 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 for 112 /// constants, arguments, values returned from trackable functions, and values 113 /// located in trackable global variables. It also computes the lattice values 114 /// that change as a result of executing instructions. 115 class CVPLatticeFunc 116 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> { 117 public: 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 two 149 /// FunctionSet values and a FunctionSet value with an Undefined value. For 150 /// these cases, we simply union the function sets. If the size of the union 151 /// is greater than the maximum functions we track, the merged value is 152 /// 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 given 168 /// instruction. The changed values are stored in \p ChangedValues. We handle 169 /// just a few kinds of instructions since we're only propagating values that 170 /// 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 else 201 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 else 215 OS << *Key.getPointer(); 216 } 217 218 /// We collect a set of indirect calls when visiting call sites. This method 219 /// returns a reference to that set. 220 SmallPtrSetImpl<CallBase *> &getIndirectCalls() { return IndirectCalls; } 221 222 private: 223 /// Holds the indirect calls we encounter during the analysis. We will attach 224 /// metadata to these calls after the analysis indicating the functions the 225 /// calls can possibly target. 226 SmallPtrSet<CallBase *, 32> IndirectCalls; 227 228 /// Compute a new lattice value for the given constant. The constant, after 229 /// stripping any pointer casts, should be a Function. We ignore null 230 /// pointers as an optimization, since calling these values is undefined 231 /// 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 of 241 /// the returned value state and the function's return state. 242 void 243 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 is 256 /// the merge of the argument state with the call sites corresponding actual 257 /// argument state. The call site state is the merge of the call site state 258 /// with the returned value state of the called function. 259 void 260 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 when 267 // 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 one 274 // 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 perform 282 // 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 can 294 // 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 the 303 /// true and false value states. 304 void 305 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 global 316 /// variable, we attempt to track the value. The loaded value state is the 317 /// 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 a 332 /// global variable, we attempt to track the value. The global variable state 333 /// is the merge of the stored value state with the global variable state. 334 void 335 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 marked 348 /// 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 } // namespace 360 361 namespace llvm { 362 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver 363 /// must translate between LatticeKeys and LLVM Values when adding Values to 364 /// its work list and inspecting the state of control-flow related values. 365 template <> 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 llvm 374 375 static 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 the 381 // 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 of 387 // indirect call sites. 388 Solver.Solve(); 389 390 // Attach metadata to the indirect call sites that were collected indicating 391 // 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 407 PreservedAnalyses CalledValuePropagationPass::run(Module &M, 408 ModuleAnalysisManager &) { 409 runCVP(M); 410 return PreservedAnalyses::all(); 411 } 412