Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp
Line
Count
Source (jump to first uncovered line)
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/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.
36
static cl::opt<unsigned> MaxFunctionsPerValue(
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
3.08k
    bool operator()(const Function *LHS, const Function *RHS) const {
65
3.08k
      return LHS->getName() < RHS->getName();
66
3.08k
    }
67
  };
68
69
28.2M
  CVPLatticeVal() : LatticeState(Undefined) {}
70
48.2k
  CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
71
  CVPLatticeVal(std::vector<Function *> &&Functions)
72
29.5k
      : LatticeState(FunctionSet), Functions(std::move(Functions)) {
73
29.5k
    assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
74
29.5k
                          Compare()));
75
29.5k
  }
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
116k
  const std::vector<Function *> &getFunctions() const {
80
116k
    return Functions;
81
116k
  }
82
83
  /// Returns true if the lattice value is in the FunctionSet state.
84
66.8k
  bool isFunctionSet() const { return LatticeState == FunctionSet; }
85
86
22.5M
  bool operator==(const CVPLatticeVal &RHS) const {
87
22.5M
    return LatticeState == RHS.LatticeState && 
Functions == RHS.Functions17.3M
;
88
22.5M
  }
89
90
17.7M
  bool operator!=(const CVPLatticeVal &RHS) const {
91
17.7M
    return LatticeState != RHS.LatticeState || 
Functions != RHS.Functions131k
;
92
17.7M
  }
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
13.5k
                                CVPLatticeVal(CVPLatticeVal::Untracked)) {}
120
121
  /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
122
1.76M
  CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
123
1.76M
    switch (Key.getInt()) {
124
1.76M
    case IPOGrouping::Register:
125
1.29M
      if (isa<Instruction>(Key.getPointer())) {
126
924k
        return getUndefVal();
127
924k
      } else 
if (auto *374k
A374k
= dyn_cast<Argument>(Key.getPointer())) {
128
246k
        if (canTrackArgumentsInterprocedurally(A->getParent()))
129
49.9k
          return getUndefVal();
130
128k
      } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
131
128k
        return computeConstant(C);
132
128k
      }
133
196k
      return getOverdefinedVal();
134
469k
    case IPOGrouping::Memory:
135
469k
    case IPOGrouping::Return:
136
469k
      if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
137
43.3k
        if (canTrackGlobalVariableInterprocedurally(GV))
138
4.42k
          return computeConstant(GV->getInitializer());
139
426k
      } else if (auto *F = cast<Function>(Key.getPointer()))
140
426k
        if (canTrackReturnsInterprocedurally(F))
141
61.5k
          return getUndefVal();
142
403k
    }
143
403k
    return getOverdefinedVal();
144
403k
  }
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
3.40M
  CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
152
3.40M
    if (X == getOverdefinedVal() || 
Y == getOverdefinedVal()898k
)
153
3.29M
      return getOverdefinedVal();
154
101k
    if (X == getUndefVal() && 
Y == getUndefVal()90.7k
)
155
72.0k
      return getUndefVal();
156
28.9k
    std::vector<Function *> Union;
157
28.9k
    std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
158
28.9k
                   Y.getFunctions().begin(), Y.getFunctions().end(),
159
28.9k
                   std::back_inserter(Union), CVPLatticeVal::Compare{});
160
28.9k
    if (Union.size() > MaxFunctionsPerValue)
161
7
      return getOverdefinedVal();
162
28.9k
    return CVPLatticeVal(std::move(Union));
163
28.9k
  }
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(
170
      Instruction &I, DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
171
23.0M
      SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {
172
23.0M
    switch (I.getOpcode()) {
173
23.0M
    case Instruction::Call:
174
4.48M
      return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
175
23.0M
    case Instruction::Invoke:
176
71.7k
      return visitCallSite(cast<InvokeInst>(&I), ChangedValues, SS);
177
23.0M
    case Instruction::Load:
178
2.40M
      return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
179
23.0M
    case Instruction::Ret:
180
915k
      return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
181
23.0M
    case Instruction::Select:
182
176k
      return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
183
23.0M
    case Instruction::Store:
184
1.86M
      return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
185
23.0M
    default:
186
13.1M
      return visitInst(I, ChangedValues, SS);
187
23.0M
    }
188
23.0M
  }
189
190
  /// Print the given CVPLatticeVal to the specified stream.
191
0
  void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {
192
0
    if (LV == getUndefVal())
193
0
      OS << "Undefined  ";
194
0
    else if (LV == getOverdefinedVal())
195
0
      OS << "Overdefined";
196
0
    else if (LV == getUntrackedVal())
197
0
      OS << "Untracked  ";
198
0
    else
199
0
      OS << "FunctionSet";
200
0
  }
201
202
  /// Print the given CVPLatticeKey to the specified stream.
203
0
  void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {
204
0
    if (Key.getInt() == IPOGrouping::Register)
205
0
      OS << "<reg> ";
206
0
    else if (Key.getInt() == IPOGrouping::Memory)
207
0
      OS << "<mem> ";
208
0
    else if (Key.getInt() == IPOGrouping::Return)
209
0
      OS << "<ret> ";
210
0
    if (isa<Function>(Key.getPointer()))
211
0
      OS << Key.getPointer()->getName();
212
0
    else
213
0
      OS << *Key.getPointer();
214
0
  }
215
216
  /// We collect a set of indirect calls when visiting call sites. This method
217
  /// returns a reference to that set.
218
13.5k
  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
132k
  CVPLatticeVal computeConstant(Constant *C) {
231
132k
    if (isa<ConstantPointerNull>(C))
232
7.57k
      return CVPLatticeVal(CVPLatticeVal::FunctionSet);
233
125k
    if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))
234
619
      return CVPLatticeVal({F});
235
124k
    return getOverdefinedVal();
236
124k
  }
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
915k
                   SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
243
915k
    Function *F = I.getParent()->getParent();
244
915k
    if (F->getReturnType()->isVoidTy())
245
161k
      return;
246
754k
    auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
247
754k
    auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
248
754k
    ChangedValues[RetF] =
249
754k
        MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
250
754k
  }
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,
257
                     DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
258
4.55M
                     SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
259
4.55M
    Function *F = CS.getCalledFunction();
260
4.55M
    Instruction *I = CS.getInstruction();
261
4.55M
    auto RegI = CVPLatticeKey(I, IPOGrouping::Register);
262
4.55M
263
4.55M
    // If this is an indirect call, save it so we can quickly revisit it when
264
4.55M
    // attaching metadata.
265
4.55M
    if (!F)
266
147k
      IndirectCalls.insert(I);
267
4.55M
268
4.55M
    // If we can't track the function's return values, there's nothing to do.
269
4.55M
    if (!F || 
!canTrackReturnsInterprocedurally(F)4.40M
) {
270
4.10M
      // Void return, No need to create and update CVPLattice state as no one
271
4.10M
      // can use it.
272
4.10M
      if (I->getType()->isVoidTy())
273
1.41M
        return;
274
2.69M
      ChangedValues[RegI] = getOverdefinedVal();
275
2.69M
      return;
276
2.69M
    }
277
447k
278
447k
    // Inform the solver that the called function is executable, and perform
279
447k
    // the merges for the arguments and return value.
280
447k
    SS.MarkBlockExecutable(&F->front());
281
447k
    auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
282
1.35M
    for (Argument &A : F->args()) {
283
1.35M
      auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
284
1.35M
      auto RegActual =
285
1.35M
          CVPLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
286
1.35M
      ChangedValues[RegFormal] =
287
1.35M
          MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
288
1.35M
    }
289
447k
290
447k
    // Void return, No need to create and update CVPLattice state as no one can
291
447k
    // use it.
292
447k
    if (I->getType()->isVoidTy())
293
99.7k
      return;
294
347k
295
347k
    ChangedValues[RegI] =
296
347k
        MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
297
347k
  }
298
299
  /// Handle select instructions. The select instruction state is the merge the
300
  /// true and false value states.
301
  void visitSelect(SelectInst &I,
302
                   DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
303
176k
                   SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
304
176k
    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
305
176k
    auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
306
176k
    auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
307
176k
    ChangedValues[RegI] =
308
176k
        MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
309
176k
  }
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,
315
                 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
316
2.40M
                 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
317
2.40M
    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
318
2.40M
    if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
319
148k
      auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
320
148k
      ChangedValues[RegI] =
321
148k
          MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
322
2.25M
    } else {
323
2.25M
      ChangedValues[RegI] = getOverdefinedVal();
324
2.25M
    }
325
2.40M
  }
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,
331
                  DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
332
1.86M
                  SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
333
1.86M
    auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
334
1.86M
    if (!GV)
335
1.75M
      return;
336
111k
    auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
337
111k
    auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
338
111k
    ChangedValues[MemGV] =
339
111k
        MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
340
111k
  }
341
342
  /// Handle all other instructions. All other instructions are marked
343
  /// overdefined.
344
  void visitInst(Instruction &I,
345
                 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
346
13.1M
                 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
347
13.1M
    // Simply bail if this instruction has no user.
348
13.1M
    if (I.use_empty())
349
3.90M
      return;
350
9.23M
    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
351
9.23M
    ChangedValues[RegI] = getOverdefinedVal();
352
9.23M
  }
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
8.16M
  static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
362
8.16M
    return Key.getPointer();
363
8.16M
  }
364
5.07M
  static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
365
5.07M
    return CVPLatticeKey(V, IPOGrouping::Register);
366
5.07M
  }
367
};
368
} // namespace llvm
369
370
13.5k
static bool runCVP(Module &M) {
371
13.5k
  // Our custom lattice function and generic sparse propagation solver.
372
13.5k
  CVPLatticeFunc Lattice;
373
13.5k
  SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);
374
13.5k
375
13.5k
  // For each function in the module, if we can't track its arguments, let the
376
13.5k
  // generic solver assume it is executable.
377
13.5k
  for (Function &F : M)
378
1.47M
    if (!F.isDeclaration() && 
!canTrackArgumentsInterprocedurally(&F)590k
)
379
565k
      Solver.MarkBlockExecutable(&F.front());
380
13.5k
381
13.5k
  // Solver our custom lattice. In doing so, we will also build a set of
382
13.5k
  // indirect call sites.
383
13.5k
  Solver.Solve();
384
13.5k
385
13.5k
  // Attach metadata to the indirect call sites that were collected indicating
386
13.5k
  // the set of functions they can possibly target.
387
13.5k
  bool Changed = false;
388
13.5k
  MDBuilder MDB(M.getContext());
389
66.8k
  for (Instruction *C : Lattice.getIndirectCalls()) {
390
66.8k
    CallSite CS(C);
391
66.8k
    auto RegI = CVPLatticeKey(CS.getCalledValue(), IPOGrouping::Register);
392
66.8k
    CVPLatticeVal LV = Solver.getExistingValueState(RegI);
393
66.8k
    if (!LV.isFunctionSet() || 
LV.getFunctions().empty()100
)
394
66.7k
      continue;
395
100
    MDNode *Callees = MDB.createCallees(LV.getFunctions());
396
100
    C->setMetadata(LLVMContext::MD_callees, Callees);
397
100
    Changed = true;
398
100
  }
399
13.5k
400
13.5k
  return Changed;
401
13.5k
}
402
403
PreservedAnalyses CalledValuePropagationPass::run(Module &M,
404
181
                                                  ModuleAnalysisManager &) {
405
181
  runCVP(M);
406
181
  return PreservedAnalyses::all();
407
181
}
408
409
namespace {
410
class CalledValuePropagationLegacyPass : public ModulePass {
411
public:
412
  static char ID;
413
414
13.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
415
13.4k
    AU.setPreservesAll();
416
13.4k
  }
417
418
13.4k
  CalledValuePropagationLegacyPass() : ModulePass(ID) {
419
13.4k
    initializeCalledValuePropagationLegacyPassPass(
420
13.4k
        *PassRegistry::getPassRegistry());
421
13.4k
  }
422
423
13.3k
  bool runOnModule(Module &M) override {
424
13.3k
    if (skipModule(M))
425
2
      return false;
426
13.3k
    return runCVP(M);
427
13.3k
  }
428
};
429
} // namespace
430
431
char CalledValuePropagationLegacyPass::ID = 0;
432
INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
433
                "Called Value Propagation", false, false)
434
435
13.4k
ModulePass *llvm::createCalledValuePropagationPass() {
436
13.4k
  return new CalledValuePropagationLegacyPass();
437
13.4k
}