1 //===- CalledValuePropagation.cpp - Propagate called values -----*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a transformation that attaches !callees metadata to
11 // indirect call sites. For a given call site, the metadata, if present,
12 // indicates the set of functions the call site could possibly target at
13 // run-time. This metadata is added to indirect call sites when the set of
14 // possible targets can be determined by analysis and is known to be small. The
15 // analysis driving the transformation is similar to constant propagation and
16 // makes uses of the generic sparse propagation solver.
17 //
18 //===----------------------------------------------------------------------===//
19
20 #include "llvm/Transforms/IPO/CalledValuePropagation.h"
21 #include "llvm/Analysis/SparsePropagation.h"
22 #include "llvm/Analysis/ValueLatticeUtils.h"
23 #include "llvm/IR/InstVisitor.h"
24 #include "llvm/IR/MDBuilder.h"
25 #include "llvm/Transforms/IPO.h"
26 using namespace llvm;
27
28 #define DEBUG_TYPE "called-value-propagation"
29
30 /// The maximum number of functions to track per lattice value. Once the number
31 /// of functions a call site can possibly target exceeds this threshold, it's
32 /// lattice value becomes overdefined. The number of possible lattice values is
33 /// bounded by Ch(F, M), where F is the number of functions in the module and M
34 /// is MaxFunctionsPerValue. As such, this value should be kept very small. We
35 /// likely can't do anything useful for call sites with a large number of
36 /// possible targets, anyway.
37 static cl::opt<unsigned> MaxFunctionsPerValue(
38 "cvp-max-functions-per-value", cl::Hidden, cl::init(4),
39 cl::desc("The maximum number of functions to track per lattice value"));
40
41 namespace {
42 /// To enable interprocedural analysis, we assign LLVM values to the following
43 /// groups. The register group represents SSA registers, the return group
44 /// represents the return values of functions, and the memory group represents
45 /// in-memory values. An LLVM Value can technically be in more than one group.
46 /// It's necessary to distinguish these groups so we can, for example, track a
47 /// global variable separately from the value stored at its location.
48 enum class IPOGrouping { Register, Return, Memory };
49
50 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
51 using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
52
53 /// The lattice value type used by our custom lattice function. It holds the
54 /// lattice state, and a set of functions.
55 class CVPLatticeVal {
56 public:
57 /// The states of the lattice values. Only the FunctionSet state is
58 /// interesting. It indicates the set of functions to which an LLVM value may
59 /// refer.
60 enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
61
62 /// Comparator for sorting the functions set. We want to keep the order
63 /// deterministic for testing, etc.
64 struct Compare {
operator ()__anonb1fa75b00111::CVPLatticeVal::Compare65 bool operator()(const Function *LHS, const Function *RHS) const {
66 return LHS->getName() < RHS->getName();
67 }
68 };
69
CVPLatticeVal()70 CVPLatticeVal() : LatticeState(Undefined) {}
CVPLatticeVal(CVPLatticeStateTy LatticeState)71 CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
CVPLatticeVal(std::vector<Function * > && Functions)72 CVPLatticeVal(std::vector<Function *> &&Functions)
73 : LatticeState(FunctionSet), Functions(std::move(Functions)) {
74 assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
75 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.
getFunctions() const80 const std::vector<Function *> &getFunctions() const {
81 return Functions;
82 }
83
84 /// Returns true if the lattice value is in the FunctionSet state.
isFunctionSet() const85 bool isFunctionSet() const { return LatticeState == FunctionSet; }
86
operator ==(const CVPLatticeVal & RHS) const87 bool operator==(const CVPLatticeVal &RHS) const {
88 return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
89 }
90
operator !=(const CVPLatticeVal & RHS) const91 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;
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:
CVPLatticeFunc()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.
ComputeLatticeVal(CVPLatticeKey Key)123 CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
124 switch (Key.getInt()) {
125 case IPOGrouping::Register:
126 if (isa<Instruction>(Key.getPointer())) {
127 return getUndefVal();
128 } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
129 if (canTrackArgumentsInterprocedurally(A->getParent()))
130 return getUndefVal();
131 } else if (auto *C = dyn_cast<Constant>(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>(Key.getPointer())) {
138 if (canTrackGlobalVariableInterprocedurally(GV))
139 return computeConstant(GV->getInitializer());
140 } else if (auto *F = cast<Function>(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.
MergeValues(CVPLatticeVal X,CVPLatticeVal Y)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(X.getFunctions().begin(), X.getFunctions().end(),
159 Y.getFunctions().begin(), Y.getFunctions().end(),
160 std::back_inserter(Union), 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.
ComputeInstructionState(Instruction & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)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 return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
176 case Instruction::Invoke:
177 return visitCallSite(cast<InvokeInst>(&I), ChangedValues, SS);
178 case Instruction::Load:
179 return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
180 case Instruction::Ret:
181 return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
182 case Instruction::Select:
183 return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
184 case Instruction::Store:
185 return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
186 default:
187 return visitInst(I, ChangedValues, SS);
188 }
189 }
190
191 /// Print the given CVPLatticeVal to the specified stream.
PrintLatticeVal(CVPLatticeVal LV,raw_ostream & OS)192 void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {
193 if (LV == getUndefVal())
194 OS << "Undefined ";
195 else if (LV == getOverdefinedVal())
196 OS << "Overdefined";
197 else if (LV == getUntrackedVal())
198 OS << "Untracked ";
199 else
200 OS << "FunctionSet";
201 }
202
203 /// Print the given CVPLatticeKey to the specified stream.
PrintLatticeKey(CVPLatticeKey Key,raw_ostream & OS)204 void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {
205 if (Key.getInt() == IPOGrouping::Register)
206 OS << "<reg> ";
207 else if (Key.getInt() == IPOGrouping::Memory)
208 OS << "<mem> ";
209 else if (Key.getInt() == IPOGrouping::Return)
210 OS << "<ret> ";
211 if (isa<Function>(Key.getPointer()))
212 OS << Key.getPointer()->getName();
213 else
214 OS << *Key.getPointer();
215 }
216
217 /// We collect a set of indirect calls when visiting call sites. This method
218 /// returns a reference to that set.
getIndirectCalls()219 SmallPtrSetImpl<Instruction *> &getIndirectCalls() { return IndirectCalls; }
220
221 private:
222 /// Holds the indirect calls we encounter during the analysis. We will attach
223 /// metadata to these calls after the analysis indicating the functions the
224 /// calls can possibly target.
225 SmallPtrSet<Instruction *, 32> IndirectCalls;
226
227 /// Compute a new lattice value for the given constant. The constant, after
228 /// stripping any pointer casts, should be a Function. We ignore null
229 /// pointers as an optimization, since calling these values is undefined
230 /// behavior.
computeConstant(Constant * C)231 CVPLatticeVal computeConstant(Constant *C) {
232 if (isa<ConstantPointerNull>(C))
233 return CVPLatticeVal(CVPLatticeVal::FunctionSet);
234 if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))
235 return CVPLatticeVal({F});
236 return getOverdefinedVal();
237 }
238
239 /// Handle return instructions. The function's return state is the merge of
240 /// the returned value state and the function's return state.
visitReturn(ReturnInst & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)241 void visitReturn(ReturnInst &I,
242 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
243 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
244 Function *F = I.getParent()->getParent();
245 if (F->getReturnType()->isVoidTy())
246 return;
247 auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
248 auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
249 ChangedValues[RetF] =
250 MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
251 }
252
253 /// Handle call sites. The state of a called function's formal arguments is
254 /// the merge of the argument state with the call sites corresponding actual
255 /// argument state. The call site state is the merge of the call site state
256 /// with the returned value state of the called function.
visitCallSite(CallSite CS,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)257 void visitCallSite(CallSite CS,
258 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
259 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
260 Function *F = CS.getCalledFunction();
261 Instruction *I = CS.getInstruction();
262 auto RegI = CVPLatticeKey(I, 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(I);
268
269 // If we can't track the function's return values, there's nothing to do.
270 if (!F || !canTrackReturnsInterprocedurally(F)) {
271 // Void return, No need to create and update CVPLattice state as no one
272 // can use it.
273 if (I->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(CS.getArgument(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 (I->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.
visitSelect(SelectInst & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)302 void visitSelect(SelectInst &I,
303 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
304 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
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.
visitLoad(LoadInst & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)315 void visitLoad(LoadInst &I,
316 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
317 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
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.
visitStore(StoreInst & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)331 void visitStore(StoreInst &I,
332 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
333 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
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.
visitInst(Instruction & I,DenseMap<CVPLatticeKey,CVPLatticeVal> & ChangedValues,SparseSolver<CVPLatticeKey,CVPLatticeVal> & SS)345 void visitInst(Instruction &I,
346 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
347 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
348 auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
349 ChangedValues[RegI] = getOverdefinedVal();
350 }
351 };
352 } // namespace
353
354 namespace llvm {
355 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
356 /// must translate between LatticeKeys and LLVM Values when adding Values to
357 /// its work list and inspecting the state of control-flow related values.
358 template <> struct LatticeKeyInfo<CVPLatticeKey> {
getValueFromLatticeKeyllvm::LatticeKeyInfo359 static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
360 return Key.getPointer();
361 }
getLatticeKeyFromValuellvm::LatticeKeyInfo362 static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
363 return CVPLatticeKey(V, IPOGrouping::Register);
364 }
365 };
366 } // namespace llvm
367
runCVP(Module & M)368 static bool runCVP(Module &M) {
369 // Our custom lattice function and generic sparse propagation solver.
370 CVPLatticeFunc Lattice;
371 SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);
372
373 // For each function in the module, if we can't track its arguments, let the
374 // generic solver assume it is executable.
375 for (Function &F : M)
376 if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
377 Solver.MarkBlockExecutable(&F.front());
378
379 // Solver our custom lattice. In doing so, we will also build a set of
380 // indirect call sites.
381 Solver.Solve();
382
383 // Attach metadata to the indirect call sites that were collected indicating
384 // the set of functions they can possibly target.
385 bool Changed = false;
386 MDBuilder MDB(M.getContext());
387 for (Instruction *C : Lattice.getIndirectCalls()) {
388 CallSite CS(C);
389 auto RegI = CVPLatticeKey(CS.getCalledValue(), IPOGrouping::Register);
390 CVPLatticeVal LV = Solver.getExistingValueState(RegI);
391 if (!LV.isFunctionSet() || LV.getFunctions().empty())
392 continue;
393 MDNode *Callees = MDB.createCallees(LV.getFunctions());
394 C->setMetadata(LLVMContext::MD_callees, Callees);
395 Changed = true;
396 }
397
398 return Changed;
399 }
400
run(Module & M,ModuleAnalysisManager &)401 PreservedAnalyses CalledValuePropagationPass::run(Module &M,
402 ModuleAnalysisManager &) {
403 runCVP(M);
404 return PreservedAnalyses::all();
405 }
406
407 namespace {
408 class CalledValuePropagationLegacyPass : public ModulePass {
409 public:
410 static char ID;
411
getAnalysisUsage(AnalysisUsage & AU) const412 void getAnalysisUsage(AnalysisUsage &AU) const override {
413 AU.setPreservesAll();
414 }
415
CalledValuePropagationLegacyPass()416 CalledValuePropagationLegacyPass() : ModulePass(ID) {
417 initializeCalledValuePropagationLegacyPassPass(
418 *PassRegistry::getPassRegistry());
419 }
420
runOnModule(Module & M)421 bool runOnModule(Module &M) override {
422 if (skipModule(M))
423 return false;
424 return runCVP(M);
425 }
426 };
427 } // namespace
428
429 char CalledValuePropagationLegacyPass::ID = 0;
430 INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
431 "Called Value Propagation", false, false)
432
createCalledValuePropagationPass()433 ModulePass *llvm::createCalledValuePropagationPass() {
434 return new CalledValuePropagationLegacyPass();
435 }
436