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