LLVM 17.0.0git
CalledValuePropagation.cpp
Go to the documentation of this file.
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
22#include "llvm/IR/Constants.h"
23#include "llvm/IR/MDBuilder.h"
25#include "llvm/Pass.h"
27#include "llvm/Transforms/IPO.h"
28
29using namespace llvm;
30
31#define DEBUG_TYPE "called-value-propagation"
32
33/// The maximum number of functions to track per lattice value. Once the number
34/// of functions a call site can possibly target exceeds this threshold, it's
35/// lattice value becomes overdefined. The number of possible lattice values is
36/// bounded by Ch(F, M), where F is the number of functions in the module and M
37/// is MaxFunctionsPerValue. As such, this value should be kept very small. We
38/// likely can't do anything useful for call sites with a large number of
39/// possible targets, anyway.
41 "cvp-max-functions-per-value", cl::Hidden, cl::init(4),
42 cl::desc("The maximum number of functions to track per lattice value"));
43
44namespace {
45/// To enable interprocedural analysis, we assign LLVM values to the following
46/// groups. The register group represents SSA registers, the return group
47/// represents the return values of functions, and the memory group represents
48/// in-memory values. An LLVM Value can technically be in more than one group.
49/// It's necessary to distinguish these groups so we can, for example, track a
50/// global variable separately from the value stored at its location.
51enum class IPOGrouping { Register, Return, Memory };
52
53/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
54using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
55
56/// The lattice value type used by our custom lattice function. It holds the
57/// lattice state, and a set of functions.
58class CVPLatticeVal {
59public:
60 /// The states of the lattice values. Only the FunctionSet state is
61 /// interesting. It indicates the set of functions to which an LLVM value may
62 /// refer.
63 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
64
65 /// Comparator for sorting the functions set. We want to keep the order
66 /// deterministic for testing, etc.
67 struct Compare {
68 bool operator()(const Function *LHS, const Function *RHS) const {
69 return LHS->getName() < RHS->getName();
70 }
71 };
72
73 CVPLatticeVal() = default;
74 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
75 CVPLatticeVal(std::vector<Function *> &&Functions)
76 : LatticeState(FunctionSet), Functions(std::move(Functions)) {
77 assert(llvm::is_sorted(this->Functions, Compare()));
78 }
79
80 /// Get a reference to the functions held by this lattice value. The number
81 /// of functions will be zero for states other than FunctionSet.
82 const std::vector<Function *> &getFunctions() const {
83 return Functions;
84 }
85
86 /// Returns true if the lattice value is in the FunctionSet state.
87 bool isFunctionSet() const { return LatticeState == FunctionSet; }
88
89 bool operator==(const CVPLatticeVal &RHS) const {
90 return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
91 }
92
93 bool operator!=(const CVPLatticeVal &RHS) const {
94 return LatticeState != RHS.LatticeState || Functions != RHS.Functions;
95 }
96
97private:
98 /// Holds the state this lattice value is in.
99 CVPLatticeStateTy LatticeState = Undefined;
100
101 /// Holds functions indicating the possible targets of call sites. This set
102 /// is empty for lattice values in the undefined, overdefined, and untracked
103 /// states. The maximum size of the set is controlled by
104 /// MaxFunctionsPerValue. Since most LLVM values are expected to be in
105 /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
106 /// small and efficiently copyable.
107 // FIXME: This could be a TinyPtrVector and/or merge with LatticeState.
108 std::vector<Function *> Functions;
109};
110
111/// The custom lattice function used by the generic sparse propagation solver.
112/// It handles merging lattice values and computing new lattice values for
113/// constants, arguments, values returned from trackable functions, and values
114/// located in trackable global variables. It also computes the lattice values
115/// that change as a result of executing instructions.
116class CVPLatticeFunc
117 : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
118public:
119 CVPLatticeFunc()
120 : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),
121 CVPLatticeVal(CVPLatticeVal::Overdefined),
122 CVPLatticeVal(CVPLatticeVal::Untracked)) {}
123
124 /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
125 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
126 switch (Key.getInt()) {
127 case IPOGrouping::Register:
128 if (isa<Instruction>(Key.getPointer())) {
129 return getUndefVal();
130 } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
131 if (canTrackArgumentsInterprocedurally(A->getParent()))
132 return getUndefVal();
133 } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
134 return computeConstant(C);
135 }
136 return getOverdefinedVal();
137 case IPOGrouping::Memory:
138 case IPOGrouping::Return:
139 if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
141 return computeConstant(GV->getInitializer());
142 } else if (auto *F = cast<Function>(Key.getPointer()))
144 return getUndefVal();
145 }
146 return getOverdefinedVal();
147 }
148
149 /// Merge the two given lattice values. The interesting cases are merging two
150 /// FunctionSet values and a FunctionSet value with an Undefined value. For
151 /// these cases, we simply union the function sets. If the size of the union
152 /// is greater than the maximum functions we track, the merged value is
153 /// overdefined.
154 CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
155 if (X == getOverdefinedVal() || Y == getOverdefinedVal())
156 return getOverdefinedVal();
157 if (X == getUndefVal() && Y == getUndefVal())
158 return getUndefVal();
159 std::vector<Function *> Union;
160 std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
161 Y.getFunctions().begin(), Y.getFunctions().end(),
162 std::back_inserter(Union), CVPLatticeVal::Compare{});
163 if (Union.size() > MaxFunctionsPerValue)
164 return getOverdefinedVal();
165 return CVPLatticeVal(std::move(Union));
166 }
167
168 /// Compute the lattice values that change as a result of executing the given
169 /// instruction. The changed values are stored in \p ChangedValues. We handle
170 /// just a few kinds of instructions since we're only propagating values that
171 /// can be called.
175 switch (I.getOpcode()) {
176 case Instruction::Call:
177 case Instruction::Invoke:
178 return visitCallBase(cast<CallBase>(I), ChangedValues, SS);
179 case Instruction::Load:
180 return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
181 case Instruction::Ret:
182 return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
183 case Instruction::Select:
184 return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
185 case Instruction::Store:
186 return visitStore(*cast<StoreInst>(&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>(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>(C))
234 return CVPLatticeVal(CVPLatticeVal::FunctionSet);
235 if (auto *F = dyn_cast<Function>(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 visitReturn(ReturnInst &I,
245 Function *F = I.getParent()->getParent();
246 if (F->getReturnType()->isVoidTy())
247 return;
248 auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
249 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
250 ChangedValues[RetF] =
251 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
252 }
253
254 /// Handle call sites. The state of a called function's formal arguments is
255 /// the merge of the argument state with the call sites corresponding actual
256 /// argument state. The call site state is the merge of the call site state
257 /// with the returned value state of the called function.
258 void visitCallBase(CallBase &CB,
262 auto RegI = CVPLatticeKey(&CB, IPOGrouping::Register);
263
264 // If this is an indirect call, save it so we can quickly revisit it when
265 // attaching metadata.
266 if (!F)
267 IndirectCalls.insert(&CB);
268
269 // If we can't track the function's return values, there's nothing to do.
271 // Void return, No need to create and update CVPLattice state as no one
272 // can use it.
273 if (CB.getType()->isVoidTy())
274 return;
275 ChangedValues[RegI] = getOverdefinedVal();
276 return;
277 }
278
279 // Inform the solver that the called function is executable, and perform
280 // the merges for the arguments and return value.
281 SS.MarkBlockExecutable(&F->front());
282 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
283 for (Argument &A : F->args()) {
284 auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
285 auto RegActual =
286 CVPLatticeKey(CB.getArgOperand(A.getArgNo()), IPOGrouping::Register);
287 ChangedValues[RegFormal] =
288 MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
289 }
290
291 // Void return, No need to create and update CVPLattice state as no one can
292 // use it.
293 if (CB.getType()->isVoidTy())
294 return;
295
296 ChangedValues[RegI] =
297 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
298 }
299
300 /// Handle select instructions. The select instruction state is the merge the
301 /// true and false value states.
302 void visitSelect(SelectInst &I,
305 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
306 auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
307 auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
308 ChangedValues[RegI] =
309 MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
310 }
311
312 /// Handle load instructions. If the pointer operand of the load is a global
313 /// variable, we attempt to track the value. The loaded value state is the
314 /// merge of the loaded value state with the global variable state.
315 void visitLoad(LoadInst &I,
318 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
319 if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
320 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
321 ChangedValues[RegI] =
322 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
323 } else {
324 ChangedValues[RegI] = getOverdefinedVal();
325 }
326 }
327
328 /// Handle store instructions. If the pointer operand of the store is a
329 /// global variable, we attempt to track the value. The global variable state
330 /// is the merge of the stored value state with the global variable state.
331 void visitStore(StoreInst &I,
334 auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
335 if (!GV)
336 return;
337 auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
338 auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
339 ChangedValues[MemGV] =
340 MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
341 }
342
343 /// Handle all other instructions. All other instructions are marked
344 /// overdefined.
345 void visitInst(Instruction &I,
348 // Simply bail if this instruction has no user.
349 if (I.use_empty())
350 return;
351 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
352 ChangedValues[RegI] = getOverdefinedVal();
353 }
354};
355} // namespace
356
357namespace llvm {
358/// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
359/// must translate between LatticeKeys and LLVM Values when adding Values to
360/// its work list and inspecting the state of control-flow related values.
361template <> struct LatticeKeyInfo<CVPLatticeKey> {
362 static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
363 return Key.getPointer();
364 }
365 static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
366 return CVPLatticeKey(V, IPOGrouping::Register);
367 }
368};
369} // namespace llvm
370
371static bool runCVP(Module &M) {
372 // Our custom lattice function and generic sparse propagation solver.
373 CVPLatticeFunc Lattice;
375
376 // For each function in the module, if we can't track its arguments, let the
377 // generic solver assume it is executable.
378 for (Function &F : M)
379 if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
380 Solver.MarkBlockExecutable(&F.front());
381
382 // Solver our custom lattice. In doing so, we will also build a set of
383 // indirect call sites.
384 Solver.Solve();
385
386 // Attach metadata to the indirect call sites that were collected indicating
387 // the set of functions they can possibly target.
388 bool Changed = false;
389 MDBuilder MDB(M.getContext());
390 for (CallBase *C : Lattice.getIndirectCalls()) {
391 auto RegI = CVPLatticeKey(C->getCalledOperand(), IPOGrouping::Register);
392 CVPLatticeVal LV = Solver.getExistingValueState(RegI);
393 if (!LV.isFunctionSet() || LV.getFunctions().empty())
394 continue;
395 MDNode *Callees = MDB.createCallees(LV.getFunctions());
396 C->setMetadata(LLVMContext::MD_callees, Callees);
397 Changed = true;
398 }
399
400 return Changed;
401}
402
405 runCVP(M);
406 return PreservedAnalyses::all();
407}
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static cl::opt< unsigned > MaxFunctionsPerValue("cvp-max-functions-per-value", cl::Hidden, cl::init(4), cl::desc("The maximum number of functions to track per lattice value"))
The maximum number of functions to track per lattice value.
static bool runCVP(Module &M)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
LatticeVal getOverdefinedVal() const
virtual void ComputeInstructionState(Instruction &I, DenseMap< LatticeKey, LatticeVal > &ChangedValues, SparseSolver< LatticeKey, LatticeVal > &SS)=0
ComputeInstructionState - Compute the LatticeKeys that change as a result of executing instruction I.
virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS)
PrintLatticeKey - Render the given LatticeKey to the specified stream.
virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS)
PrintLatticeVal - Render the given LatticeVal to the specified stream.
LatticeVal getUntrackedVal() const
virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y)
MergeValues - Compute and return the merge of the two specified lattice values.
virtual LatticeVal ComputeLatticeVal(LatticeKey Key)
ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1408
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1353
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
This is an important base class in LLVM.
Definition: Constant.h:41
An instruction for reading from memory.
Definition: Instructions.h:177
MDNode * createCallees(ArrayRef< Function * > Callees)
Return metadata indicating the possible callees of indirect calls.
Definition: MDBuilder.cpp:100
Metadata node.
Definition: Metadata.h:943
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
PointerIntPair - This class implements a pair of a pointer and small integer.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
Return a value (possibly void), from a function.
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void Solve()
Solve - Solve for constants and executable blocks.
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
An instruction for storing to memory.
Definition: Instructions.h:301
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This class provides various memory handling functions that manipulate MemoryBlock instances.
Definition: Memory.h:52
Key
PAL metadata keys.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
@ SS
Definition: X86.h:209
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2047
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)
Determine if the value maintained in the given global variable can be tracked interprocedurally.
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1962
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1909
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function's arguments can be tracked interprocedurally.
Definition: BitVector.h:851
static CVPLatticeKey getLatticeKeyFromValue(Value *V)
static Value * getValueFromLatticeKey(CVPLatticeKey Key)
A template for translating between LLVM Values and LatticeKeys.