Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- IndirectCallPromotion.cpp - Optimizations based on value profiling -===//
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 the transformation that promotes indirect calls to
10
// conditional direct calls when the indirect-call value profile metadata is
11
// available.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/ADT/ArrayRef.h"
16
#include "llvm/ADT/STLExtras.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/ADT/StringRef.h"
20
#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
21
#include "llvm/Analysis/IndirectCallVisitor.h"
22
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
23
#include "llvm/Analysis/ProfileSummaryInfo.h"
24
#include "llvm/IR/Attributes.h"
25
#include "llvm/IR/BasicBlock.h"
26
#include "llvm/IR/CallSite.h"
27
#include "llvm/IR/DerivedTypes.h"
28
#include "llvm/IR/DiagnosticInfo.h"
29
#include "llvm/IR/Function.h"
30
#include "llvm/IR/IRBuilder.h"
31
#include "llvm/IR/InstrTypes.h"
32
#include "llvm/IR/Instruction.h"
33
#include "llvm/IR/Instructions.h"
34
#include "llvm/IR/LLVMContext.h"
35
#include "llvm/IR/MDBuilder.h"
36
#include "llvm/IR/PassManager.h"
37
#include "llvm/IR/Type.h"
38
#include "llvm/IR/Value.h"
39
#include "llvm/Pass.h"
40
#include "llvm/ProfileData/InstrProf.h"
41
#include "llvm/Support/Casting.h"
42
#include "llvm/Support/CommandLine.h"
43
#include "llvm/Support/Debug.h"
44
#include "llvm/Support/Error.h"
45
#include "llvm/Support/raw_ostream.h"
46
#include "llvm/Transforms/Instrumentation.h"
47
#include "llvm/Transforms/Instrumentation/PGOInstrumentation.h"
48
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
49
#include "llvm/Transforms/Utils/CallPromotionUtils.h"
50
#include <cassert>
51
#include <cstdint>
52
#include <memory>
53
#include <string>
54
#include <utility>
55
#include <vector>
56
57
using namespace llvm;
58
59
18
#define DEBUG_TYPE "pgo-icall-prom"
60
61
STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
62
STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
63
64
// Command line option to disable indirect-call promotion with the default as
65
// false. This is for debug purpose.
66
static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,
67
                                cl::desc("Disable indirect call promotion"));
68
69
// Set the cutoff value for the promotion. If the value is other than 0, we
70
// stop the transformation once the total number of promotions equals the cutoff
71
// value.
72
// For debug use only.
73
static cl::opt<unsigned>
74
    ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore,
75
              cl::desc("Max number of promotions for this compilation"));
76
77
// If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.
78
// For debug use only.
79
static cl::opt<unsigned>
80
    ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore,
81
              cl::desc("Skip Callsite up to this number for this compilation"));
82
83
// Set if the pass is called in LTO optimization. The difference for LTO mode
84
// is the pass won't prefix the source module name to the internal linkage
85
// symbols.
86
static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(false), cl::Hidden,
87
                                cl::desc("Run indirect-call promotion in LTO "
88
                                         "mode"));
89
90
// Set if the pass is called in SamplePGO mode. The difference for SamplePGO
91
// mode is it will add prof metadatato the created direct call.
92
static cl::opt<bool>
93
    ICPSamplePGOMode("icp-samplepgo", cl::init(false), cl::Hidden,
94
                     cl::desc("Run indirect-call promotion in SamplePGO mode"));
95
96
// If the option is set to true, only call instructions will be considered for
97
// transformation -- invoke instructions will be ignored.
98
static cl::opt<bool>
99
    ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden,
100
                cl::desc("Run indirect-call promotion for call instructions "
101
                         "only"));
102
103
// If the option is set to true, only invoke instructions will be considered for
104
// transformation -- call instructions will be ignored.
105
static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false),
106
                                   cl::Hidden,
107
                                   cl::desc("Run indirect-call promotion for "
108
                                            "invoke instruction only"));
109
110
// Dump the function level IR if the transformation happened in this
111
// function. For debug use only.
112
static cl::opt<bool>
113
    ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
114
                 cl::desc("Dump IR after transformation happens"));
115
116
namespace {
117
118
class PGOIndirectCallPromotionLegacyPass : public ModulePass {
119
public:
120
  static char ID;
121
122
  PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false)
123
826
      : ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) {
124
826
    initializePGOIndirectCallPromotionLegacyPassPass(
125
826
        *PassRegistry::getPassRegistry());
126
826
  }
127
128
826
  void getAnalysisUsage(AnalysisUsage &AU) const override {
129
826
    AU.addRequired<ProfileSummaryInfoWrapperPass>();
130
826
  }
131
132
19
  StringRef getPassName() const override { return "PGOIndirectCallPromotion"; }
133
134
private:
135
  bool runOnModule(Module &M) override;
136
137
  // If this pass is called in LTO. We need to special handling the PGOFuncName
138
  // for the static variables due to LTO's internalization.
139
  bool InLTO;
140
141
  // If this pass is called in SamplePGO. We need to add the prof metadata to
142
  // the promoted direct call.
143
  bool SamplePGO;
144
};
145
146
} // end anonymous namespace
147
148
char PGOIndirectCallPromotionLegacyPass::ID = 0;
149
150
11.5k
INITIALIZE_PASS_BEGIN(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
151
11.5k
                      "Use PGO instrumentation profile to promote indirect "
152
11.5k
                      "calls to direct calls.",
153
11.5k
                      false, false)
154
11.5k
INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
155
11.5k
INITIALIZE_PASS_END(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
156
                    "Use PGO instrumentation profile to promote indirect "
157
                    "calls to direct calls.",
158
                    false, false)
159
160
ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,
161
809
                                                           bool SamplePGO) {
162
809
  return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);
163
809
}
164
165
namespace {
166
167
// The class for main data structure to promote indirect calls to conditional
168
// direct calls.
169
class ICallPromotionFunc {
170
private:
171
  Function &F;
172
  Module *M;
173
174
  // Symtab that maps indirect call profile values to function names and
175
  // defines.
176
  InstrProfSymtab *Symtab;
177
178
  bool SamplePGO;
179
180
  OptimizationRemarkEmitter &ORE;
181
182
  // A struct that records the direct target and it's call count.
183
  struct PromotionCandidate {
184
    Function *TargetFunction;
185
    uint64_t Count;
186
187
50
    PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {}
188
  };
189
190
  // Check if the indirect-call call site should be promoted. Return the number
191
  // of promotions. Inst is the candidate indirect call, ValueDataRef
192
  // contains the array of value profile data for profiled targets,
193
  // TotalCount is the total profiled count of call executions, and
194
  // NumCandidates is the number of candidate entries in ValueDataRef.
195
  std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
196
      Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
197
      uint64_t TotalCount, uint32_t NumCandidates);
198
199
  // Promote a list of targets for one indirect-call callsite. Return
200
  // the number of promotions.
201
  uint32_t tryToPromote(Instruction *Inst,
202
                        const std::vector<PromotionCandidate> &Candidates,
203
                        uint64_t &TotalCount);
204
205
public:
206
  ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab,
207
                     bool SamplePGO, OptimizationRemarkEmitter &ORE)
208
1.00k
      : F(Func), M(Modu), Symtab(Symtab), SamplePGO(SamplePGO), ORE(ORE) {}
209
  ICallPromotionFunc(const ICallPromotionFunc &) = delete;
210
  ICallPromotionFunc &operator=(const ICallPromotionFunc &) = delete;
211
212
  bool processFunction(ProfileSummaryInfo *PSI);
213
};
214
215
} // end anonymous namespace
216
217
// Indirect-call promotion heuristic. The direct targets are sorted based on
218
// the count. Stop at the first target that is not promoted.
219
std::vector<ICallPromotionFunc::PromotionCandidate>
220
ICallPromotionFunc::getPromotionCandidatesForCallSite(
221
    Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
222
44
    uint64_t TotalCount, uint32_t NumCandidates) {
223
44
  std::vector<PromotionCandidate> Ret;
224
44
225
44
  LLVM_DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
226
44
                    << " Num_targets: " << ValueDataRef.size()
227
44
                    << " Num_candidates: " << NumCandidates << "\n");
228
44
  NumOfPGOICallsites++;
229
44
  if (ICPCSSkip != 0 && 
NumOfPGOICallsites <= ICPCSSkip0
) {
230
0
    LLVM_DEBUG(dbgs() << " Skip: User options.\n");
231
0
    return Ret;
232
0
  }
233
44
234
94
  
for (uint32_t I = 0; 44
I < NumCandidates;
I++50
) {
235
57
    uint64_t Count = ValueDataRef[I].Count;
236
57
    assert(Count <= TotalCount);
237
57
    uint64_t Target = ValueDataRef[I].Value;
238
57
    LLVM_DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
239
57
                      << "  Target_func: " << Target << "\n");
240
57
241
57
    if (ICPInvokeOnly && 
isa<CallInst>(Inst)0
) {
242
0
      LLVM_DEBUG(dbgs() << " Not promote: User options.\n");
243
0
      ORE.emit([&]() {
244
0
        return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
245
0
               << " Not promote: User options";
246
0
      });
247
0
      break;
248
0
    }
249
57
    if (ICPCallOnly && 
isa<InvokeInst>(Inst)0
) {
250
0
      LLVM_DEBUG(dbgs() << " Not promote: User option.\n");
251
0
      ORE.emit([&]() {
252
0
        return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
253
0
               << " Not promote: User options";
254
0
      });
255
0
      break;
256
0
    }
257
57
    if (ICPCutOff != 0 && 
NumOfPGOICallPromotion >= ICPCutOff0
) {
258
0
      LLVM_DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
259
0
      ORE.emit([&]() {
260
0
        return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", Inst)
261
0
               << " Not promote: Cutoff reached";
262
0
      });
263
0
      break;
264
0
    }
265
57
266
57
    Function *TargetFunction = Symtab->getFunction(Target);
267
57
    if (TargetFunction == nullptr) {
268
3
      LLVM_DEBUG(dbgs() << " Not promote: Cannot find the target\n");
269
3
      ORE.emit([&]() {
270
2
        return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", Inst)
271
2
               << "Cannot promote indirect call: target with md5sum "
272
2
               << ore::NV("target md5sum", Target) << " not found";
273
2
      });
274
3
      break;
275
3
    }
276
54
277
54
    const char *Reason = nullptr;
278
54
    if (!isLegalToPromote(CallSite(Inst), TargetFunction, &Reason)) {
279
4
      using namespace ore;
280
4
281
4
      ORE.emit([&]() {
282
4
        return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", Inst)
283
4
               << "Cannot promote indirect call to "
284
4
               << NV("TargetFunction", TargetFunction) << " with count of "
285
4
               << NV("Count", Count) << ": " << Reason;
286
4
      });
287
4
      break;
288
4
    }
289
50
290
50
    Ret.push_back(PromotionCandidate(TargetFunction, Count));
291
50
    TotalCount -= Count;
292
50
  }
293
44
  return Ret;
294
44
}
295
296
Instruction *llvm::pgo::promoteIndirectCall(Instruction *Inst,
297
                                            Function *DirectCallee,
298
                                            uint64_t Count, uint64_t TotalCount,
299
                                            bool AttachProfToDirectCall,
300
62
                                            OptimizationRemarkEmitter *ORE) {
301
62
302
62
  uint64_t ElseCount = TotalCount - Count;
303
62
  uint64_t MaxCount = (Count >= ElseCount ? 
Count60
:
ElseCount2
);
304
62
  uint64_t Scale = calculateCountScale(MaxCount);
305
62
  MDBuilder MDB(Inst->getContext());
306
62
  MDNode *BranchWeights = MDB.createBranchWeights(
307
62
      scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
308
62
309
62
  Instruction *NewInst =
310
62
      promoteCallWithIfThenElse(CallSite(Inst), DirectCallee, BranchWeights);
311
62
312
62
  if (AttachProfToDirectCall) {
313
6
    MDBuilder MDB(NewInst->getContext());
314
6
    NewInst->setMetadata(
315
6
        LLVMContext::MD_prof,
316
6
        MDB.createBranchWeights({static_cast<uint32_t>(Count)}));
317
6
  }
318
62
319
62
  using namespace ore;
320
62
321
62
  if (ORE)
322
62
    ORE->emit([&]() {
323
12
      return OptimizationRemark(DEBUG_TYPE, "Promoted", Inst)
324
12
             << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
325
12
             << " with count " << NV("Count", Count) << " out of "
326
12
             << NV("TotalCount", TotalCount);
327
12
    });
328
62
  return NewInst;
329
62
}
330
331
// Promote indirect-call to conditional direct-call for one callsite.
332
uint32_t ICallPromotionFunc::tryToPromote(
333
    Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
334
44
    uint64_t &TotalCount) {
335
44
  uint32_t NumPromoted = 0;
336
44
337
50
  for (auto &C : Candidates) {
338
50
    uint64_t Count = C.Count;
339
50
    pgo::promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount,
340
50
                             SamplePGO, &ORE);
341
50
    assert(TotalCount >= Count);
342
50
    TotalCount -= Count;
343
50
    NumOfPGOICallPromotion++;
344
50
    NumPromoted++;
345
50
  }
346
44
  return NumPromoted;
347
44
}
348
349
// Traverse all the indirect-call callsite and get the value profile
350
// annotation to perform indirect-call promotion.
351
1.00k
bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) {
352
1.00k
  bool Changed = false;
353
1.00k
  ICallPromotionAnalysis ICallAnalysis;
354
1.00k
  for (auto &I : findIndirectCalls(F)) {
355
67
    uint32_t NumVals, NumCandidates;
356
67
    uint64_t TotalCount;
357
67
    auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
358
67
        I, NumVals, TotalCount, NumCandidates);
359
67
    if (!NumCandidates ||
360
67
        
(44
PSI44
&&
PSI->hasProfileSummary()44
&&
!PSI->isHotCount(TotalCount)12
))
361
22
      continue;
362
45
    auto PromotionCandidates = getPromotionCandidatesForCallSite(
363
45
        I, ICallProfDataRef, TotalCount, NumCandidates);
364
45
    uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
365
45
    if (NumPromoted == 0)
366
7
      continue;
367
38
368
38
    Changed = true;
369
38
    // Adjust the MD.prof metadata. First delete the old one.
370
38
    I->setMetadata(LLVMContext::MD_prof, nullptr);
371
38
    // If all promoted, we don't need the MD.prof metadata.
372
38
    if (TotalCount == 0 || 
NumPromoted == NumVals7
)
373
33
      continue;
374
5
    // Otherwise we need update with the un-promoted records back.
375
5
    annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
376
5
                      IPVK_IndirectCallTarget, NumCandidates);
377
5
  }
378
1.00k
  return Changed;
379
1.00k
}
380
381
// A wrapper function that does the actual work.
382
static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI,
383
                                 bool InLTO, bool SamplePGO,
384
902
                                 ModuleAnalysisManager *AM = nullptr) {
385
902
  if (DisableICP)
386
0
    return false;
387
902
  InstrProfSymtab Symtab;
388
902
  if (Error E = Symtab.create(M, InLTO)) {
389
0
    std::string SymtabFailure = toString(std::move(E));
390
0
    LLVM_DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
391
0
    (void)SymtabFailure;
392
0
    return false;
393
0
  }
394
902
  bool Changed = false;
395
1.38k
  for (auto &F : M) {
396
1.38k
    if (F.isDeclaration() || 
F.hasOptNone()1.01k
)
397
382
      continue;
398
1.00k
399
1.00k
    std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
400
1.00k
    OptimizationRemarkEmitter *ORE;
401
1.00k
    if (AM) {
402
70
      auto &FAM =
403
70
          AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
404
70
      ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
405
934
    } else {
406
934
      OwnedORE = llvm::make_unique<OptimizationRemarkEmitter>(&F);
407
934
      ORE = OwnedORE.get();
408
934
    }
409
1.00k
410
1.00k
    ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE);
411
1.00k
    bool FuncChanged = ICallPromotion.processFunction(PSI);
412
1.00k
    if (ICPDUMPAFTER && 
FuncChanged0
) {
413
0
      LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
414
0
      LLVM_DEBUG(dbgs() << "\n");
415
0
    }
416
1.00k
    Changed |= FuncChanged;
417
1.00k
    if (ICPCutOff != 0 && 
NumOfPGOICallPromotion >= ICPCutOff0
) {
418
0
      LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n");
419
0
      break;
420
0
    }
421
1.00k
  }
422
902
  return Changed;
423
902
}
424
425
822
bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
426
822
  ProfileSummaryInfo *PSI =
427
822
      &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
428
822
429
822
  // Command-line option has the priority for InLTO.
430
822
  return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
431
822
                              SamplePGO | ICPSamplePGOMode);
432
822
}
433
434
PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
435
80
                                                ModuleAnalysisManager &AM) {
436
80
  ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
437
80
438
80
  if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
439
80
                            SamplePGO | ICPSamplePGOMode, &AM))
440
70
    return PreservedAnalyses::all();
441
10
442
10
  return PreservedAnalyses::none();
443
10
}