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/InitializePasses.h" 25 #include "llvm/Pass.h" 26 #include "llvm/Support/CommandLine.h" 27 #include "llvm/Transforms/IPO.h" 28 29 using namespace llvm; 30 31 #define DEBUG_TYPE "called-value-propagation" 32 33 /// The maximum number of functions to track per lattice value. Once the number 34 /// of functions a call site can possibly target exceeds this threshold, it's 35 /// lattice value becomes overdefined. The number of possible lattice values is 36 /// bounded by Ch(F, M), where F is the number of functions in the module and M 37 /// is MaxFunctionsPerValue. As such, this value should be kept very small. We 38 /// likely can't do anything useful for call sites with a large number of 39 /// possible targets, anyway. 40 static cl::opt<unsigned> MaxFunctionsPerValue( 41 "cvp-max-functions-per-value", cl::Hidden, cl::init(4), 42 cl::desc("The maximum number of functions to track per lattice value")); 43 44 namespace { 45 /// To enable interprocedural analysis, we assign LLVM values to the following 46 /// groups. The register group represents SSA registers, the return group 47 /// represents the return values of functions, and the memory group represents 48 /// in-memory values. An LLVM Value can technically be in more than one group. 49 /// It's necessary to distinguish these groups so we can, for example, track a 50 /// global variable separately from the value stored at its location. 51 enum class IPOGrouping { Register, Return, Memory }; 52 53 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings. 54 using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>; 55 56 /// The lattice value type used by our custom lattice function. It holds the 57 /// lattice state, and a set of functions. 58 class CVPLatticeVal { 59 public: 60 /// The states of the lattice values. Only the FunctionSet state is 61 /// interesting. It indicates the set of functions to which an LLVM value may 62 /// refer. 63 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked }; 64 65 /// Comparator for sorting the functions set. We want to keep the order 66 /// deterministic for testing, etc. 67 struct Compare { 68 bool operator()(const Function *LHS, const Function *RHS) const { 69 return LHS->getName() < RHS->getName(); 70 } 71 }; 72 73 CVPLatticeVal() = default; 74 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {} 75 CVPLatticeVal(std::vector<Function *> &&Functions) 76 : LatticeState(FunctionSet), Functions(std::move(Functions)) { 77 assert(llvm::is_sorted(this->Functions, Compare())); 78 } 79 80 /// Get a reference to the functions held by this lattice value. The number 81 /// of functions will be zero for states other than FunctionSet. 82 const std::vector<Function *> &getFunctions() const { 83 return Functions; 84 } 85 86 /// Returns true if the lattice value is in the FunctionSet state. 87 bool isFunctionSet() const { return LatticeState == FunctionSet; } 88 89 bool operator==(const CVPLatticeVal &RHS) const { 90 return LatticeState == RHS.LatticeState && Functions == RHS.Functions; 91 } 92 93 bool operator!=(const CVPLatticeVal &RHS) const { 94 return LatticeState != RHS.LatticeState || Functions != RHS.Functions; 95 } 96 97 private: 98 /// Holds the state this lattice value is in. 99 CVPLatticeStateTy LatticeState = Undefined; 100 101 /// Holds functions indicating the possible targets of call sites. This set 102 /// is empty for lattice values in the undefined, overdefined, and untracked 103 /// states. The maximum size of the set is controlled by 104 /// MaxFunctionsPerValue. Since most LLVM values are expected to be in 105 /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be 106 /// small and efficiently copyable. 107 // FIXME: This could be a TinyPtrVector and/or merge with LatticeState. 108 std::vector<Function *> Functions; 109 }; 110 111 /// The custom lattice function used by the generic sparse propagation solver. 112 /// It handles merging lattice values and computing new lattice values for 113 /// constants, arguments, values returned from trackable functions, and values 114 /// located in trackable global variables. It also computes the lattice values 115 /// that change as a result of executing instructions. 116 class CVPLatticeFunc 117 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> { 118 public: 119 CVPLatticeFunc() 120 : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined), 121 CVPLatticeVal(CVPLatticeVal::Overdefined), 122 CVPLatticeVal(CVPLatticeVal::Untracked)) {} 123 124 /// Compute and return a CVPLatticeVal for the given CVPLatticeKey. 125 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override { 126 switch (Key.getInt()) { 127 case IPOGrouping::Register: 128 if (isa<Instruction>(Key.getPointer())) { 129 return getUndefVal(); 130 } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) { 131 if (canTrackArgumentsInterprocedurally(A->getParent())) 132 return getUndefVal(); 133 } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) { 134 return computeConstant(C); 135 } 136 return getOverdefinedVal(); 137 case IPOGrouping::Memory: 138 case IPOGrouping::Return: 139 if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) { 140 if (canTrackGlobalVariableInterprocedurally(GV)) 141 return computeConstant(GV->getInitializer()); 142 } else if (auto *F = cast<Function>(Key.getPointer())) 143 if (canTrackReturnsInterprocedurally(F)) 144 return getUndefVal(); 145 } 146 return getOverdefinedVal(); 147 } 148 149 /// Merge the two given lattice values. The interesting cases are merging two 150 /// FunctionSet values and a FunctionSet value with an Undefined value. For 151 /// these cases, we simply union the function sets. If the size of the union 152 /// is greater than the maximum functions we track, the merged value is 153 /// overdefined. 154 CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override { 155 if (X == getOverdefinedVal() || Y == getOverdefinedVal()) 156 return getOverdefinedVal(); 157 if (X == getUndefVal() && Y == getUndefVal()) 158 return getUndefVal(); 159 std::vector<Function *> Union; 160 std::set_union(X.getFunctions().begin(), X.getFunctions().end(), 161 Y.getFunctions().begin(), Y.getFunctions().end(), 162 std::back_inserter(Union), CVPLatticeVal::Compare{}); 163 if (Union.size() > MaxFunctionsPerValue) 164 return getOverdefinedVal(); 165 return CVPLatticeVal(std::move(Union)); 166 } 167 168 /// Compute the lattice values that change as a result of executing the given 169 /// instruction. The changed values are stored in \p ChangedValues. We handle 170 /// just a few kinds of instructions since we're only propagating values that 171 /// can be called. 172 void ComputeInstructionState( 173 Instruction &I, DenseMap<CVPLatticeKey, CVPLatticeVal> &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 visitReturn(ReturnInst &I, 243 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 244 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 245 Function *F = I.getParent()->getParent(); 246 if (F->getReturnType()->isVoidTy()) 247 return; 248 auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register); 249 auto RetF = CVPLatticeKey(F, IPOGrouping::Return); 250 ChangedValues[RetF] = 251 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF)); 252 } 253 254 /// Handle call sites. The state of a called function's formal arguments is 255 /// the merge of the argument state with the call sites corresponding actual 256 /// argument state. The call site state is the merge of the call site state 257 /// with the returned value state of the called function. 258 void visitCallBase(CallBase &CB, 259 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 260 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 261 Function *F = CB.getCalledFunction(); 262 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register); 263 264 // If this is an indirect call, save it so we can quickly revisit it when 265 // attaching metadata. 266 if (!F) 267 IndirectCalls.insert(&CB); 268 269 // If we can't track the function's return values, there's nothing to do. 270 if (!F || !canTrackReturnsInterprocedurally(F)) { 271 // Void return, No need to create and update CVPLattice state as no one 272 // can use it. 273 if (CB.getType()->isVoidTy()) 274 return; 275 ChangedValues[RegI] = getOverdefinedVal(); 276 return; 277 } 278 279 // Inform the solver that the called function is executable, and perform 280 // the merges for the arguments and return value. 281 SS.MarkBlockExecutable(&F->front()); 282 auto RetF = CVPLatticeKey(F, IPOGrouping::Return); 283 for (Argument &A : F->args()) { 284 auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register); 285 auto RegActual = 286 CVPLatticeKey(CB.getArgOperand(A.getArgNo()), IPOGrouping::Register); 287 ChangedValues[RegFormal] = 288 MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual)); 289 } 290 291 // Void return, No need to create and update CVPLattice state as no one can 292 // use it. 293 if (CB.getType()->isVoidTy()) 294 return; 295 296 ChangedValues[RegI] = 297 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF)); 298 } 299 300 /// Handle select instructions. The select instruction state is the merge the 301 /// true and false value states. 302 void visitSelect(SelectInst &I, 303 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 304 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 305 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); 306 auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register); 307 auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register); 308 ChangedValues[RegI] = 309 MergeValues(SS.getValueState(RegT), SS.getValueState(RegF)); 310 } 311 312 /// Handle load instructions. If the pointer operand of the load is a global 313 /// variable, we attempt to track the value. The loaded value state is the 314 /// merge of the loaded value state with the global variable state. 315 void visitLoad(LoadInst &I, 316 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 317 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 318 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); 319 if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) { 320 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory); 321 ChangedValues[RegI] = 322 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV)); 323 } else { 324 ChangedValues[RegI] = getOverdefinedVal(); 325 } 326 } 327 328 /// Handle store instructions. If the pointer operand of the store is a 329 /// global variable, we attempt to track the value. The global variable state 330 /// is the merge of the stored value state with the global variable state. 331 void visitStore(StoreInst &I, 332 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 333 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 334 auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand()); 335 if (!GV) 336 return; 337 auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register); 338 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory); 339 ChangedValues[MemGV] = 340 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV)); 341 } 342 343 /// Handle all other instructions. All other instructions are marked 344 /// overdefined. 345 void visitInst(Instruction &I, 346 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues, 347 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { 348 // Simply bail if this instruction has no user. 349 if (I.use_empty()) 350 return; 351 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); 352 ChangedValues[RegI] = getOverdefinedVal(); 353 } 354 }; 355 } // namespace 356 357 namespace llvm { 358 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver 359 /// must translate between LatticeKeys and LLVM Values when adding Values to 360 /// its work list and inspecting the state of control-flow related values. 361 template <> struct LatticeKeyInfo<CVPLatticeKey> { 362 static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) { 363 return Key.getPointer(); 364 } 365 static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) { 366 return CVPLatticeKey(V, IPOGrouping::Register); 367 } 368 }; 369 } // namespace llvm 370 371 static bool runCVP(Module &M) { 372 // Our custom lattice function and generic sparse propagation solver. 373 CVPLatticeFunc Lattice; 374 SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice); 375 376 // For each function in the module, if we can't track its arguments, let the 377 // generic solver assume it is executable. 378 for (Function &F : M) 379 if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F)) 380 Solver.MarkBlockExecutable(&F.front()); 381 382 // Solver our custom lattice. In doing so, we will also build a set of 383 // indirect call sites. 384 Solver.Solve(); 385 386 // Attach metadata to the indirect call sites that were collected indicating 387 // the set of functions they can possibly target. 388 bool Changed = false; 389 MDBuilder MDB(M.getContext()); 390 for (CallBase *C : Lattice.getIndirectCalls()) { 391 auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register); 392 CVPLatticeVal LV = Solver.getExistingValueState(RegI); 393 if (!LV.isFunctionSet() || LV.getFunctions().empty()) 394 continue; 395 MDNode *Callees = MDB.createCallees(LV.getFunctions()); 396 C->setMetadata(LLVMContext::MD_callees, Callees); 397 Changed = true; 398 } 399 400 return Changed; 401 } 402 403 PreservedAnalyses CalledValuePropagationPass::run(Module &M, 404 ModuleAnalysisManager &) { 405 runCVP(M); 406 return PreservedAnalyses::all(); 407 } 408 409 namespace { 410 class CalledValuePropagationLegacyPass : public ModulePass { 411 public: 412 static char ID; 413 414 void getAnalysisUsage(AnalysisUsage &AU) const override { 415 AU.setPreservesAll(); 416 } 417 418 CalledValuePropagationLegacyPass() : ModulePass(ID) { 419 initializeCalledValuePropagationLegacyPassPass( 420 *PassRegistry::getPassRegistry()); 421 } 422 423 bool runOnModule(Module &M) override { 424 if (skipModule(M)) 425 return false; 426 return runCVP(M); 427 } 428 }; 429 } // namespace 430 431 char CalledValuePropagationLegacyPass::ID = 0; 432 INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation", 433 "Called Value Propagation", false, false) 434 435 ModulePass *llvm::createCalledValuePropagationPass() { 436 return new CalledValuePropagationLegacyPass(); 437 } 438