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
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 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.
39static cl::opt<unsigned> MaxFunctionsPerValue(
40 "cvp-max-functions-per-value", cl::Hidden, cl::init(Val: 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 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.
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 the
56/// lattice state, and a set of functions.
57class CVPLatticeVal {
58public:
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
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 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.
115class CVPLatticeFunc
116 : 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>(Val: Key.getPointer())) {
128 return getUndefVal();
129 } else if (auto *A = dyn_cast<Argument>(Val: Key.getPointer())) {
130 if (canTrackArgumentsInterprocedurally(F: A->getParent()))
131 return getUndefVal();
132 } else if (auto *C = dyn_cast<Constant>(Val: 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>(Val: Key.getPointer())) {
139 if (canTrackGlobalVariableInterprocedurally(GV))
140 return computeConstant(C: GV->getInitializer());
141 } else if (auto *F = cast<Function>(Val: 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(first1: X.getFunctions().begin(), last1: X.getFunctions().end(),
160 first2: Y.getFunctions().begin(), last2: Y.getFunctions().end(),
161 result: std::back_inserter(x&: Union), comp: 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(CB&: cast<CallBase>(Val&: I), ChangedValues, SS);
179 case Instruction::Load:
180 return visitLoad(I&: *cast<LoadInst>(Val: &I), ChangedValues, SS);
181 case Instruction::Ret:
182 return visitReturn(I&: *cast<ReturnInst>(Val: &I), ChangedValues, SS);
183 case Instruction::Select:
184 return visitSelect(I&: *cast<SelectInst>(Val: &I), ChangedValues, SS);
185 case Instruction::Store:
186 return visitStore(I&: *cast<StoreInst>(Val: &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>(Val: 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
222private:
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>(Val: C))
234 return CVPLatticeVal(CVPLatticeVal::FunctionSet);
235 if (auto *F = dyn_cast<Function>(Val: 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(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: 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(Ptr: &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(BB: &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(i: A.getArgNo()), IPOGrouping::Register);
289 ChangedValues[RegFormal] =
290 MergeValues(X: SS.getValueState(Key: RegFormal), Y: SS.getValueState(Key: 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(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: 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(X: SS.getValueState(Key: RegT), Y: SS.getValueState(Key: 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>(Val: I.getPointerOperand())) {
323 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
324 ChangedValues[RegI] =
325 MergeValues(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: 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>(Val: 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(X: SS.getValueState(Key: RegI), Y: SS.getValueState(Key: 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
361namespace 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.
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 llvm
374
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 the
381 // generic solver assume it is executable.
382 for (Function &F : M)
383 if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(F: &F))
384 Solver.MarkBlockExecutable(BB: &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(Key: RegI);
397 if (!LV.isFunctionSet() || LV.getFunctions().empty())
398 continue;
399 MDNode *Callees = MDB.createCallees(Callees: LV.getFunctions());
400 C->setMetadata(KindID: LLVMContext::MD_callees, Node: 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