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
27using 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.
38static 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
42namespace {
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.
49enum class IPOGrouping { Register, Return, Memory };
50
51/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
52using 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.
56class CVPLatticeVal {
57public:
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
95private:
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.
114class CVPLatticeFunc
115 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
116public:
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
220private:
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
355namespace 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.
359template <> 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
369static 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
401PreservedAnalyses CalledValuePropagationPass::run(Module &M,
402 ModuleAnalysisManager &) {
403 runCVP(M);
404 return PreservedAnalyses::all();
405}
406

source code of llvm/lib/Transforms/IPO/CalledValuePropagation.cpp