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
28using namespace llvm;
29
30#define DEBUG_TYPE "called-value-propagation"
31
32namespace {
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.
39enum class IPOGrouping { Register, Return, Memory };
40
41/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
42using 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.
46class CVPLatticeVal {
47public:
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
85private:
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.
104class CVPLatticeFunc
105 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
106 const IPOOptions &Opts;
107
108public:
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
214private:
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
353namespace 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.
357template <> 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
367static 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
399PreservedAnalyses CalledValuePropagationPass::run(Module &M,
400 ModuleAnalysisManager &) {
401 runCVP(M);
402 return PreservedAnalyses::all();
403}
404