LLVM  9.0.0svn
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/InstVisitor.h"
23 #include "llvm/IR/MDBuilder.h"
24 #include "llvm/Transforms/IPO.h"
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "called-value-propagation"
28 
29 /// The maximum number of functions to track per lattice value. Once the number
30 /// of functions a call site can possibly target exceeds this threshold, it's
31 /// lattice value becomes overdefined. The number of possible lattice values is
32 /// bounded by Ch(F, M), where F is the number of functions in the module and M
33 /// is MaxFunctionsPerValue. As such, this value should be kept very small. We
34 /// likely can't do anything useful for call sites with a large number of
35 /// possible targets, anyway.
37  "cvp-max-functions-per-value", cl::Hidden, cl::init(4),
38  cl::desc("The maximum number of functions to track per lattice value"));
39 
40 namespace {
41 /// To enable interprocedural analysis, we assign LLVM values to the following
42 /// groups. The register group represents SSA registers, the return group
43 /// represents the return values of functions, and the memory group represents
44 /// in-memory values. An LLVM Value can technically be in more than one group.
45 /// It's necessary to distinguish these groups so we can, for example, track a
46 /// global variable separately from the value stored at its location.
47 enum class IPOGrouping { Register, Return, Memory };
48 
49 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
50 using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
51 
52 /// The lattice value type used by our custom lattice function. It holds the
53 /// lattice state, and a set of functions.
54 class CVPLatticeVal {
55 public:
56  /// The states of the lattice values. Only the FunctionSet state is
57  /// interesting. It indicates the set of functions to which an LLVM value may
58  /// refer.
59  enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
60 
61  /// Comparator for sorting the functions set. We want to keep the order
62  /// deterministic for testing, etc.
63  struct Compare {
64  bool operator()(const Function *LHS, const Function *RHS) const {
65  return LHS->getName() < RHS->getName();
66  }
67  };
68 
69  CVPLatticeVal() : LatticeState(Undefined) {}
70  CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
71  CVPLatticeVal(std::vector<Function *> &&Functions)
72  : LatticeState(FunctionSet), Functions(std::move(Functions)) {
73  assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
74  Compare()));
75  }
76 
77  /// Get a reference to the functions held by this lattice value. The number
78  /// of functions will be zero for states other than FunctionSet.
79  const std::vector<Function *> &getFunctions() const {
80  return Functions;
81  }
82 
83  /// Returns true if the lattice value is in the FunctionSet state.
84  bool isFunctionSet() const { return LatticeState == FunctionSet; }
85 
86  bool operator==(const CVPLatticeVal &RHS) const {
87  return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
88  }
89 
90  bool operator!=(const CVPLatticeVal &RHS) const {
91  return LatticeState != RHS.LatticeState || Functions != RHS.Functions;
92  }
93 
94 private:
95  /// Holds the state this lattice value is in.
96  CVPLatticeStateTy LatticeState;
97 
98  /// Holds functions indicating the possible targets of call sites. This set
99  /// is empty for lattice values in the undefined, overdefined, and untracked
100  /// states. The maximum size of the set is controlled by
101  /// MaxFunctionsPerValue. Since most LLVM values are expected to be in
102  /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
103  /// small and efficiently copyable.
104  // FIXME: This could be a TinyPtrVector and/or merge with LatticeState.
105  std::vector<Function *> Functions;
106 };
107 
108 /// The custom lattice function used by the generic sparse propagation solver.
109 /// It handles merging lattice values and computing new lattice values for
110 /// constants, arguments, values returned from trackable functions, and values
111 /// located in trackable global variables. It also computes the lattice values
112 /// that change as a result of executing instructions.
113 class CVPLatticeFunc
114  : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
115 public:
116  CVPLatticeFunc()
117  : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),
118  CVPLatticeVal(CVPLatticeVal::Overdefined),
119  CVPLatticeVal(CVPLatticeVal::Untracked)) {}
120 
121  /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
122  CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
123  switch (Key.getInt()) {
125  if (isa<Instruction>(Key.getPointer())) {
126  return getUndefVal();
127  } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
128  if (canTrackArgumentsInterprocedurally(A->getParent()))
129  return getUndefVal();
130  } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
131  return computeConstant(C);
132  }
133  return getOverdefinedVal();
134  case IPOGrouping::Memory:
135  case IPOGrouping::Return:
136  if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
138  return computeConstant(GV->getInitializer());
139  } else if (auto *F = cast<Function>(Key.getPointer()))
141  return getUndefVal();
142  }
143  return getOverdefinedVal();
144  }
145 
146  /// Merge the two given lattice values. The interesting cases are merging two
147  /// FunctionSet values and a FunctionSet value with an Undefined value. For
148  /// these cases, we simply union the function sets. If the size of the union
149  /// is greater than the maximum functions we track, the merged value is
150  /// overdefined.
151  CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
152  if (X == getOverdefinedVal() || Y == getOverdefinedVal())
153  return getOverdefinedVal();
154  if (X == getUndefVal() && Y == getUndefVal())
155  return getUndefVal();
156  std::vector<Function *> Union;
157  std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
158  Y.getFunctions().begin(), Y.getFunctions().end(),
159  std::back_inserter(Union), CVPLatticeVal::Compare{});
160  if (Union.size() > MaxFunctionsPerValue)
161  return getOverdefinedVal();
162  return CVPLatticeVal(std::move(Union));
163  }
164 
165  /// Compute the lattice values that change as a result of executing the given
166  /// instruction. The changed values are stored in \p ChangedValues. We handle
167  /// just a few kinds of instructions since we're only propagating values that
168  /// can be called.
169  void ComputeInstructionState(
172  switch (I.getOpcode()) {
173  case Instruction::Call:
174  return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
175  case Instruction::Invoke:
176  return visitCallSite(cast<InvokeInst>(&I), ChangedValues, SS);
177  case Instruction::Load:
178  return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
179  case Instruction::Ret:
180  return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
181  case Instruction::Select:
182  return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
183  case Instruction::Store:
184  return visitStore(*cast<StoreInst>(&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>(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<Instruction *> &getIndirectCalls() { return IndirectCalls; }
219 
220 private:
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<Instruction *, 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>(C))
232  return CVPLatticeVal(CVPLatticeVal::FunctionSet);
233  if (auto *F = dyn_cast<Function>(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,
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(SS.getValueState(RegI), SS.getValueState(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 visitCallSite(CallSite CS,
259  Function *F = CS.getCalledFunction();
260  Instruction *I = CS.getInstruction();
261  auto RegI = CVPLatticeKey(I, IPOGrouping::Register);
262 
263  // If this is an indirect call, save it so we can quickly revisit it when
264  // attaching metadata.
265  if (!F)
266  IndirectCalls.insert(I);
267 
268  // If we can't track the function's return values, there's nothing to do.
269  if (!F || !canTrackReturnsInterprocedurally(F)) {
270  // Void return, No need to create and update CVPLattice state as no one
271  // can use it.
272  if (I->getType()->isVoidTy())
273  return;
274  ChangedValues[RegI] = getOverdefinedVal();
275  return;
276  }
277 
278  // Inform the solver that the called function is executable, and perform
279  // the merges for the arguments and return value.
280  SS.MarkBlockExecutable(&F->front());
281  auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
282  for (Argument &A : F->args()) {
283  auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
284  auto RegActual =
285  CVPLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
286  ChangedValues[RegFormal] =
287  MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
288  }
289 
290  // Void return, No need to create and update CVPLattice state as no one can
291  // use it.
292  if (I->getType()->isVoidTy())
293  return;
294 
295  ChangedValues[RegI] =
296  MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
297  }
298 
299  /// Handle select instructions. The select instruction state is the merge the
300  /// true and false value states.
301  void visitSelect(SelectInst &I,
304  auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
305  auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
306  auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
307  ChangedValues[RegI] =
308  MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
309  }
310 
311  /// Handle load instructions. If the pointer operand of the load is a global
312  /// variable, we attempt to track the value. The loaded value state is the
313  /// merge of the loaded value state with the global variable state.
314  void visitLoad(LoadInst &I,
317  auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
318  if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
319  auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
320  ChangedValues[RegI] =
321  MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
322  } else {
323  ChangedValues[RegI] = getOverdefinedVal();
324  }
325  }
326 
327  /// Handle store instructions. If the pointer operand of the store is a
328  /// global variable, we attempt to track the value. The global variable state
329  /// is the merge of the stored value state with the global variable state.
330  void visitStore(StoreInst &I,
333  auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
334  if (!GV)
335  return;
336  auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
337  auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
338  ChangedValues[MemGV] =
339  MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
340  }
341 
342  /// Handle all other instructions. All other instructions are marked
343  /// overdefined.
344  void visitInst(Instruction &I,
347  // Simply bail if this instruction has no user.
348  if (I.use_empty())
349  return;
350  auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
351  ChangedValues[RegI] = getOverdefinedVal();
352  }
353 };
354 } // namespace
355 
356 namespace llvm {
357 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
358 /// must translate between LatticeKeys and LLVM Values when adding Values to
359 /// its work list and inspecting the state of control-flow related values.
360 template <> struct LatticeKeyInfo<CVPLatticeKey> {
361  static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
362  return Key.getPointer();
363  }
364  static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
365  return CVPLatticeKey(V, IPOGrouping::Register);
366  }
367 };
368 } // namespace llvm
369 
370 static bool runCVP(Module &M) {
371  // Our custom lattice function and generic sparse propagation solver.
372  CVPLatticeFunc Lattice;
374 
375  // For each function in the module, if we can't track its arguments, let the
376  // generic solver assume it is executable.
377  for (Function &F : M)
378  if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
379  Solver.MarkBlockExecutable(&F.front());
380 
381  // Solver our custom lattice. In doing so, we will also build a set of
382  // indirect call sites.
383  Solver.Solve();
384 
385  // Attach metadata to the indirect call sites that were collected indicating
386  // the set of functions they can possibly target.
387  bool Changed = false;
388  MDBuilder MDB(M.getContext());
389  for (Instruction *C : Lattice.getIndirectCalls()) {
390  CallSite CS(C);
391  auto RegI = CVPLatticeKey(CS.getCalledValue(), IPOGrouping::Register);
392  CVPLatticeVal LV = Solver.getExistingValueState(RegI);
393  if (!LV.isFunctionSet() || LV.getFunctions().empty())
394  continue;
395  MDNode *Callees = MDB.createCallees(LV.getFunctions());
397  Changed = true;
398  }
399 
400  return Changed;
401 }
402 
405  runCVP(M);
406  return PreservedAnalyses::all();
407 }
408 
409 namespace {
410 class CalledValuePropagationLegacyPass : public ModulePass {
411 public:
412  static char ID;
413 
414  void getAnalysisUsage(AnalysisUsage &AU) const override {
415  AU.setPreservesAll();
416  }
417 
418  CalledValuePropagationLegacyPass() : ModulePass(ID) {
421  }
422 
423  bool runOnModule(Module &M) override {
424  if (skipModule(M))
425  return false;
426  return runCVP(M);
427  }
428 };
429 } // namespace
430 
432 INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
433  "Called Value Propagation", false, false)
434 
436  return new CalledValuePropagationLegacyPass();
437 }
uint64_t CallInst * C
Return a value (possibly void), from a function.
Value * getValueOperand()
Definition: Instructions.h:409
void initializeCalledValuePropagationLegacyPassPass(PassRegistry &)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function&#39;s arguments can be tracked interprocedurally.
This class provides various memory handling functions that manipulate MemoryBlock instances...
Definition: Memory.h:50
const Value * getTrueValue() const
Metadata node.
Definition: Metadata.h:863
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:111
IPOGrouping
To enable interprocedural analysis, we assign LLVM values to the following groups.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
This class represents the LLVM &#39;select&#39; instruction.
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:104
static CVPLatticeKey getLatticeKeyFromValue(Value *V)
InstrTy * getInstruction() const
Definition: CallSite.h:96
Key
PAL metadata keys.
void Solve()
Solve - Solve for constants and executable blocks.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
ModulePass * createCalledValuePropagationPass()
createCalledValuePropagationPass - Attach metadata to indirct call sites indicating the set of functi...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
An instruction for storing to memory.
Definition: Instructions.h:320
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function&#39;s returns can be tracked interprocedurally.
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:140
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:168
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
PointerIntPair - This class implements a pair of a pointer and small integer.
static bool runCVP(Module &M)
This is an important base class in LLVM.
Definition: Constant.h:41
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:193
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:370
Represent the analysis usage information of a pass.
Value * getPointerOperand()
Definition: Instructions.h:284
static Value * getValueFromLatticeKey(CVPLatticeKey Key)
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
const Constant * stripPointerCasts() const
Definition: Constant.h:177
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1225
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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.
bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)
Determine if the value maintained in the given global variable can be tracked interprocedurally.
Promote Memory to Register
Definition: Mem2Reg.cpp:109
LatticeVal getValueState(LatticeKey Key)
getValueState - Return the LatticeVal object corresponding to the given value from the ValueState map...
void setPreservesAll()
Set by analyses that do not transform their input at all.
const Value * getFalseValue() const
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1968
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
Definition: Function.h:665
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation", "Called Value Propagation", false, false) ModulePass *llvm
Value * getPointerOperand()
Definition: Instructions.h:412
bool use_empty() const
Definition: Value.h:322
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
Definition: SetOperations.h:22
iterator_range< arg_iterator > args()
Definition: Function.h:691
const BasicBlock * getParent() const
Definition: Instruction.h:66
A template for translating between LLVM Values and LatticeKeys.