| 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 "IPOOptions.h" |
| 21 | #include "llvm/Analysis/SparsePropagation.h" |
| 22 | #include "llvm/Analysis/ValueLatticeUtils.h" |
| 23 | #include "llvm/IR/Constants.h" |
| 24 | #include "llvm/IR/MDBuilder.h" |
| 25 | #include "llvm/IR/Module.h" |
| 26 | #include "llvm/Transforms/IPO.h" |
| 27 | |
| 28 | using namespace llvm; |
| 29 | |
| 30 | #define DEBUG_TYPE "called-value-propagation" |
| 31 | |
| 32 | namespace { |
| 33 | /// To enable interprocedural analysis, we assign LLVM values to the following |
| 34 | /// groups. The register group represents SSA registers, the return group |
| 35 | /// represents the return values of functions, and the memory group represents |
| 36 | /// in-memory values. An LLVM Value can technically be in more than one group. |
| 37 | /// It's necessary to distinguish these groups so we can, for example, track a |
| 38 | /// global variable separately from the value stored at its location. |
| 39 | enum class IPOGrouping { Register, Return, Memory }; |
| 40 | |
| 41 | /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings. |
| 42 | using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>; |
| 43 | |
| 44 | /// The lattice value type used by our custom lattice function. It holds the |
| 45 | /// lattice state, and a set of functions. |
| 46 | class CVPLatticeVal { |
| 47 | public: |
| 48 | /// The states of the lattice values. Only the FunctionSet state is |
| 49 | /// interesting. It indicates the set of functions to which an LLVM value may |
| 50 | /// refer. |
| 51 | enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked }; |
| 52 | |
| 53 | /// Comparator for sorting the functions set. We want to keep the order |
| 54 | /// deterministic for testing, etc. |
| 55 | struct Compare { |
| 56 | bool operator()(const Function *LHS, const Function *RHS) const { |
| 57 | return LHS->getName() < RHS->getName(); |
| 58 | } |
| 59 | }; |
| 60 | |
| 61 | CVPLatticeVal() = default; |
| 62 | CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {} |
| 63 | CVPLatticeVal(std::vector<Function *> &&Functions) |
| 64 | : LatticeState(FunctionSet), Functions(std::move(Functions)) { |
| 65 | assert(llvm::is_sorted(this->Functions, Compare())); |
| 66 | } |
| 67 | |
| 68 | /// Get a reference to the functions held by this lattice value. The number |
| 69 | /// of functions will be zero for states other than FunctionSet. |
| 70 | const std::vector<Function *> &getFunctions() const { |
| 71 | return Functions; |
| 72 | } |
| 73 | |
| 74 | /// Returns true if the lattice value is in the FunctionSet state. |
| 75 | bool isFunctionSet() const { return LatticeState == FunctionSet; } |
| 76 | |
| 77 | bool operator==(const CVPLatticeVal &RHS) const { |
| 78 | return LatticeState == RHS.LatticeState && Functions == RHS.Functions; |
| 79 | } |
| 80 | |
| 81 | bool operator!=(const CVPLatticeVal &RHS) const { |
| 82 | return LatticeState != RHS.LatticeState || Functions != RHS.Functions; |
| 83 | } |
| 84 | |
| 85 | private: |
| 86 | /// Holds the state this lattice value is in. |
| 87 | CVPLatticeStateTy LatticeState = Undefined; |
| 88 | |
| 89 | /// Holds functions indicating the possible targets of call sites. This set |
| 90 | /// is empty for lattice values in the undefined, overdefined, and untracked |
| 91 | /// states. The maximum size of the set is controlled by |
| 92 | /// -cvp-max-functions-per-value. Since most LLVM values are expected to be in |
| 93 | /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be |
| 94 | /// small and efficiently copyable. |
| 95 | // FIXME: This could be a TinyPtrVector and/or merge with LatticeState. |
| 96 | std::vector<Function *> Functions; |
| 97 | }; |
| 98 | |
| 99 | /// The custom lattice function used by the generic sparse propagation solver. |
| 100 | /// It handles merging lattice values and computing new lattice values for |
| 101 | /// constants, arguments, values returned from trackable functions, and values |
| 102 | /// located in trackable global variables. It also computes the lattice values |
| 103 | /// that change as a result of executing instructions. |
| 104 | class CVPLatticeFunc |
| 105 | : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> { |
| 106 | const IPOOptions &Opts; |
| 107 | |
| 108 | public: |
| 109 | explicit CVPLatticeFunc(const IPOOptions &Opts) |
| 110 | : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined), |
| 111 | CVPLatticeVal(CVPLatticeVal::Overdefined), |
| 112 | CVPLatticeVal(CVPLatticeVal::Untracked)), |
| 113 | Opts(Opts) {} |
| 114 | |
| 115 | /// Compute and return a CVPLatticeVal for the given CVPLatticeKey. |
| 116 | CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override { |
| 117 | switch (Key.getInt()) { |
| 118 | case IPOGrouping::Register: |
| 119 | if (isa<Instruction>(Val: Key.getPointer())) { |
| 120 | return getUndefVal(); |
| 121 | } else if (auto *A = dyn_cast<Argument>(Val: Key.getPointer())) { |
| 122 | if (canTrackArgumentsInterprocedurally(F: A->getParent())) |
| 123 | return getUndefVal(); |
| 124 | } else if (auto *C = dyn_cast<Constant>(Val: Key.getPointer())) { |
| 125 | return computeConstant(C); |
| 126 | } |
| 127 | return getOverdefinedVal(); |
| 128 | case IPOGrouping::Memory: |
| 129 | case IPOGrouping::Return: |
| 130 | if (auto *GV = dyn_cast<GlobalVariable>(Val: Key.getPointer())) { |
| 131 | if (canTrackGlobalVariableInterprocedurally(GV)) |
| 132 | return computeConstant(C: GV->getInitializer()); |
| 133 | } else if (auto *F = cast<Function>(Val: Key.getPointer())) |
| 134 | if (canTrackReturnsInterprocedurally(F)) |
| 135 | return getUndefVal(); |
| 136 | } |
| 137 | return getOverdefinedVal(); |
| 138 | } |
| 139 | |
| 140 | /// Merge the two given lattice values. The interesting cases are merging two |
| 141 | /// FunctionSet values and a FunctionSet value with an Undefined value. For |
| 142 | /// these cases, we simply union the function sets. If the size of the union |
| 143 | /// is greater than the maximum functions we track, the merged value is |
| 144 | /// overdefined. |
| 145 | CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override { |
| 146 | if (X == getOverdefinedVal() || Y == getOverdefinedVal()) |
| 147 | return getOverdefinedVal(); |
| 148 | if (X == getUndefVal() && Y == getUndefVal()) |
| 149 | return getUndefVal(); |
| 150 | std::vector<Function *> Union; |
| 151 | std::set_union(first1: X.getFunctions().begin(), last1: X.getFunctions().end(), |
| 152 | first2: Y.getFunctions().begin(), last2: Y.getFunctions().end(), |
| 153 | result: std::back_inserter(x&: Union), comp: CVPLatticeVal::Compare{}); |
| 154 | if (Union.size() > Opts.cvp_max_functions_per_value) |
| 155 | return getOverdefinedVal(); |
| 156 | return CVPLatticeVal(std::move(Union)); |
| 157 | } |
| 158 | |
| 159 | /// Compute the lattice values that change as a result of executing the given |
| 160 | /// instruction. The changed values are stored in \p ChangedValues. We handle |
| 161 | /// just a few kinds of instructions since we're only propagating values that |
| 162 | /// can be called. |
| 163 | void ComputeInstructionState( |
| 164 | Instruction &I, |
| 165 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 166 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override { |
| 167 | switch (I.getOpcode()) { |
| 168 | case Instruction::Call: |
| 169 | case Instruction::Invoke: |
| 170 | return visitCallBase(CB&: cast<CallBase>(Val&: I), ChangedValues, SS); |
| 171 | case Instruction::Load: |
| 172 | return visitLoad(I&: *cast<LoadInst>(Val: &I), ChangedValues, SS); |
| 173 | case Instruction::Ret: |
| 174 | return visitReturn(I&: *cast<ReturnInst>(Val: &I), ChangedValues, SS); |
| 175 | case Instruction::Select: |
| 176 | return visitSelect(I&: *cast<SelectInst>(Val: &I), ChangedValues, SS); |
| 177 | case Instruction::Store: |
| 178 | return visitStore(I&: *cast<StoreInst>(Val: &I), ChangedValues, SS); |
| 179 | default: |
| 180 | return visitInst(I, ChangedValues, SS); |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | /// Print the given CVPLatticeVal to the specified stream. |
| 185 | void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override { |
| 186 | if (LV == getUndefVal()) |
| 187 | OS << "Undefined " ; |
| 188 | else if (LV == getOverdefinedVal()) |
| 189 | OS << "Overdefined" ; |
| 190 | else if (LV == getUntrackedVal()) |
| 191 | OS << "Untracked " ; |
| 192 | else |
| 193 | OS << "FunctionSet" ; |
| 194 | } |
| 195 | |
| 196 | /// Print the given CVPLatticeKey to the specified stream. |
| 197 | void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override { |
| 198 | if (Key.getInt() == IPOGrouping::Register) |
| 199 | OS << "<reg> " ; |
| 200 | else if (Key.getInt() == IPOGrouping::Memory) |
| 201 | OS << "<mem> " ; |
| 202 | else if (Key.getInt() == IPOGrouping::Return) |
| 203 | OS << "<ret> " ; |
| 204 | if (isa<Function>(Val: Key.getPointer())) |
| 205 | OS << Key.getPointer()->getName(); |
| 206 | else |
| 207 | OS << *Key.getPointer(); |
| 208 | } |
| 209 | |
| 210 | /// We collect a set of indirect calls when visiting call sites. This method |
| 211 | /// returns a reference to that set. |
| 212 | SmallPtrSetImpl<CallBase *> &getIndirectCalls() { return IndirectCalls; } |
| 213 | |
| 214 | private: |
| 215 | /// Holds the indirect calls we encounter during the analysis. We will attach |
| 216 | /// metadata to these calls after the analysis indicating the functions the |
| 217 | /// calls can possibly target. |
| 218 | SmallPtrSet<CallBase *, 32> IndirectCalls; |
| 219 | |
| 220 | /// Compute a new lattice value for the given constant. The constant, after |
| 221 | /// stripping any pointer casts, should be a Function. We ignore null |
| 222 | /// pointers as an optimization, since calling these values is undefined |
| 223 | /// behavior. |
| 224 | CVPLatticeVal computeConstant(Constant *C) { |
| 225 | if (isa<ConstantPointerNull>(Val: C)) |
| 226 | return CVPLatticeVal(CVPLatticeVal::FunctionSet); |
| 227 | if (auto *F = dyn_cast<Function>(Val: C->stripPointerCasts())) |
| 228 | return CVPLatticeVal({F}); |
| 229 | return getOverdefinedVal(); |
| 230 | } |
| 231 | |
| 232 | /// Handle return instructions. The function's return state is the merge of |
| 233 | /// the returned value state and the function's return state. |
| 234 | void |
| 235 | visitReturn(ReturnInst &I, |
| 236 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 237 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 238 | Function *F = I.getParent()->getParent(); |
| 239 | if (F->getReturnType()->isVoidTy()) |
| 240 | return; |
| 241 | auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register); |
| 242 | auto RetF = CVPLatticeKey(F, IPOGrouping::Return); |
| 243 | ChangedValues[RetF] = |
| 244 | MergeValues(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: RetF)); |
| 245 | } |
| 246 | |
| 247 | /// Handle call sites. The state of a called function's formal arguments is |
| 248 | /// the merge of the argument state with the call sites corresponding actual |
| 249 | /// argument state. The call site state is the merge of the call site state |
| 250 | /// with the returned value state of the called function. |
| 251 | void |
| 252 | visitCallBase(CallBase &CB, |
| 253 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 254 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 255 | Function *F = CB.getCalledFunction(); |
| 256 | auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register); |
| 257 | |
| 258 | // If this is an indirect call, save it so we can quickly revisit it when |
| 259 | // attaching metadata. |
| 260 | if (!F) |
| 261 | IndirectCalls.insert(Ptr: &CB); |
| 262 | |
| 263 | // If we can't track the function's return values, there's nothing to do. |
| 264 | if (!F || !canTrackReturnsInterprocedurally(F)) { |
| 265 | // Void return, No need to create and update CVPLattice state as no one |
| 266 | // can use it. |
| 267 | if (CB.getType()->isVoidTy()) |
| 268 | return; |
| 269 | ChangedValues[RegI] = getOverdefinedVal(); |
| 270 | return; |
| 271 | } |
| 272 | |
| 273 | // Inform the solver that the called function is executable, and perform |
| 274 | // the merges for the arguments and return value. |
| 275 | SS.MarkBlockExecutable(BB: &F->front()); |
| 276 | auto RetF = CVPLatticeKey(F, IPOGrouping::Return); |
| 277 | for (Argument &A : F->args()) { |
| 278 | auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register); |
| 279 | auto RegActual = |
| 280 | CVPLatticeKey(CB.getArgOperand(i: A.getArgNo()), IPOGrouping::Register); |
| 281 | ChangedValues[RegFormal] = |
| 282 | MergeValues(X: SS.getValueState(Key: RegFormal), Y: SS.getValueState(Key: RegActual)); |
| 283 | } |
| 284 | |
| 285 | // Void return, No need to create and update CVPLattice state as no one can |
| 286 | // use it. |
| 287 | if (CB.getType()->isVoidTy()) |
| 288 | return; |
| 289 | |
| 290 | ChangedValues[RegI] = |
| 291 | MergeValues(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: RetF)); |
| 292 | } |
| 293 | |
| 294 | /// Handle select instructions. The select instruction state is the merge the |
| 295 | /// true and false value states. |
| 296 | void |
| 297 | visitSelect(SelectInst &I, |
| 298 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 299 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 300 | auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); |
| 301 | auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register); |
| 302 | auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register); |
| 303 | ChangedValues[RegI] = |
| 304 | MergeValues(X: SS.getValueState(Key: RegT), Y: SS.getValueState(Key: RegF)); |
| 305 | } |
| 306 | |
| 307 | /// Handle load instructions. If the pointer operand of the load is a global |
| 308 | /// variable, we attempt to track the value. The loaded value state is the |
| 309 | /// merge of the loaded value state with the global variable state. |
| 310 | void visitLoad(LoadInst &I, |
| 311 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 312 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 313 | auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); |
| 314 | if (auto *GV = dyn_cast<GlobalVariable>(Val: I.getPointerOperand())) { |
| 315 | auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory); |
| 316 | ChangedValues[RegI] = |
| 317 | MergeValues(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: MemGV)); |
| 318 | } else { |
| 319 | ChangedValues[RegI] = getOverdefinedVal(); |
| 320 | } |
| 321 | } |
| 322 | |
| 323 | /// Handle store instructions. If the pointer operand of the store is a |
| 324 | /// global variable, we attempt to track the value. The global variable state |
| 325 | /// is the merge of the stored value state with the global variable state. |
| 326 | void |
| 327 | visitStore(StoreInst &I, |
| 328 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 329 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 330 | auto *GV = dyn_cast<GlobalVariable>(Val: I.getPointerOperand()); |
| 331 | if (!GV) |
| 332 | return; |
| 333 | auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register); |
| 334 | auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory); |
| 335 | ChangedValues[MemGV] = |
| 336 | MergeValues(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: MemGV)); |
| 337 | } |
| 338 | |
| 339 | /// Handle all other instructions. All other instructions are marked |
| 340 | /// overdefined. |
| 341 | void visitInst(Instruction &I, |
| 342 | SmallDenseMap<CVPLatticeKey, CVPLatticeVal, 16> &ChangedValues, |
| 343 | SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) { |
| 344 | // Simply bail if this instruction has no user. |
| 345 | if (I.use_empty()) |
| 346 | return; |
| 347 | auto RegI = CVPLatticeKey(&I, IPOGrouping::Register); |
| 348 | ChangedValues[RegI] = getOverdefinedVal(); |
| 349 | } |
| 350 | }; |
| 351 | } // namespace |
| 352 | |
| 353 | namespace llvm { |
| 354 | /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver |
| 355 | /// must translate between LatticeKeys and LLVM Values when adding Values to |
| 356 | /// its work list and inspecting the state of control-flow related values. |
| 357 | template <> struct LatticeKeyInfo<CVPLatticeKey> { |
| 358 | static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) { |
| 359 | return Key.getPointer(); |
| 360 | } |
| 361 | static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) { |
| 362 | return CVPLatticeKey(V, IPOGrouping::Register); |
| 363 | } |
| 364 | }; |
| 365 | } // namespace llvm |
| 366 | |
| 367 | static bool runCVP(Module &M) { |
| 368 | // Our custom lattice function and generic sparse propagation solver. |
| 369 | CVPLatticeFunc Lattice(getIPOOptions(M)); |
| 370 | SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice); |
| 371 | |
| 372 | // For each function in the module, if we can't track its arguments, let the |
| 373 | // generic solver assume it is executable. |
| 374 | for (Function &F : M) |
| 375 | if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(F: &F)) |
| 376 | Solver.MarkBlockExecutable(BB: &F.front()); |
| 377 | |
| 378 | // Solver our custom lattice. In doing so, we will also build a set of |
| 379 | // indirect call sites. |
| 380 | Solver.Solve(); |
| 381 | |
| 382 | // Attach metadata to the indirect call sites that were collected indicating |
| 383 | // the set of functions they can possibly target. |
| 384 | bool Changed = false; |
| 385 | MDBuilder MDB(M.getContext()); |
| 386 | for (CallBase *C : Lattice.getIndirectCalls()) { |
| 387 | auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register); |
| 388 | CVPLatticeVal LV = Solver.getExistingValueState(Key: RegI); |
| 389 | if (!LV.isFunctionSet() || LV.getFunctions().empty()) |
| 390 | continue; |
| 391 | MDNode *Callees = MDB.createCallees(Callees: LV.getFunctions()); |
| 392 | C->setMetadata(KindID: LLVMContext::MD_callees, Node: Callees); |
| 393 | Changed = true; |
| 394 | } |
| 395 | |
| 396 | return Changed; |
| 397 | } |
| 398 | |
| 399 | PreservedAnalyses CalledValuePropagationPass::run(Module &M, |
| 400 | ModuleAnalysisManager &) { |
| 401 | runCVP(M); |
| 402 | return PreservedAnalyses::all(); |
| 403 | } |
| 404 | |