Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/IPO/SyntheticCountsPropagation.cpp
Line
Count
Source (jump to first uncovered line)
1
//=- SyntheticCountsPropagation.cpp - Propagate function counts --*- 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 synthesizes entry counts for
10
// functions and attaches !prof metadata to functions with the synthesized
11
// counts. The presence of !prof metadata with counter name set to
12
// 'synthesized_function_entry_count' indicate that the value of the counter is
13
// an estimation of the likely execution count of the function. This transform
14
// is applied only in non PGO mode as functions get 'real' profile-based
15
// function entry counts in the PGO mode.
16
//
17
// The transformation works by first assigning some initial values to the entry
18
// counts of all functions and then doing a top-down traversal of the
19
// callgraph-scc to propagate the counts. For each function the set of callsites
20
// and their relative block frequency is gathered. The relative block frequency
21
// multiplied by the entry count of the caller and added to the callee's entry
22
// count. For non-trivial SCCs, the new counts are computed from the previous
23
// counts and updated in one shot.
24
//
25
//===----------------------------------------------------------------------===//
26
27
#include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
28
#include "llvm/ADT/DenseSet.h"
29
#include "llvm/ADT/STLExtras.h"
30
#include "llvm/Analysis/BlockFrequencyInfo.h"
31
#include "llvm/Analysis/CallGraph.h"
32
#include "llvm/Analysis/ProfileSummaryInfo.h"
33
#include "llvm/Analysis/SyntheticCountsUtils.h"
34
#include "llvm/IR/CallSite.h"
35
#include "llvm/IR/Function.h"
36
#include "llvm/IR/Instructions.h"
37
#include "llvm/IR/Module.h"
38
#include "llvm/Support/CommandLine.h"
39
#include "llvm/Support/Debug.h"
40
#include "llvm/Support/raw_ostream.h"
41
42
using namespace llvm;
43
using Scaled64 = ScaledNumber<uint64_t>;
44
using ProfileCount = Function::ProfileCount;
45
46
#define DEBUG_TYPE "synthetic-counts-propagation"
47
48
/// Initial synthetic count assigned to functions.
49
cl::opt<int>
50
    InitialSyntheticCount("initial-synthetic-count", cl::Hidden, cl::init(10),
51
                          cl::ZeroOrMore,
52
                          cl::desc("Initial value of synthetic entry count."));
53
54
/// Initial synthetic count assigned to inline functions.
55
static cl::opt<int> InlineSyntheticCount(
56
    "inline-synthetic-count", cl::Hidden, cl::init(15), cl::ZeroOrMore,
57
    cl::desc("Initial synthetic entry count for inline functions."));
58
59
/// Initial synthetic count assigned to cold functions.
60
static cl::opt<int> ColdSyntheticCount(
61
    "cold-synthetic-count", cl::Hidden, cl::init(5), cl::ZeroOrMore,
62
    cl::desc("Initial synthetic entry count for cold functions."));
63
64
// Assign initial synthetic entry counts to functions.
65
static void
66
3
initializeCounts(Module &M, function_ref<void(Function *, uint64_t)> SetCount) {
67
4
  auto MayHaveIndirectCalls = [](Function &F) {
68
4
    for (auto *U : F.users()) {
69
2
      if (!isa<CallInst>(U) && 
!isa<InvokeInst>(U)0
)
70
0
        return true;
71
2
    }
72
4
    return false;
73
4
  };
74
3
75
18
  for (Function &F : M) {
76
18
    uint64_t InitialCount = InitialSyntheticCount;
77
18
    if (F.isDeclaration())
78
1
      continue;
79
17
    if (F.hasFnAttribute(Attribute::AlwaysInline) ||
80
17
        
F.hasFnAttribute(Attribute::InlineHint)16
) {
81
4
      // Use a higher value for inline functions to account for the fact that
82
4
      // these are usually beneficial to inline.
83
4
      InitialCount = InlineSyntheticCount;
84
13
    } else if (F.hasLocalLinkage() && 
!MayHaveIndirectCalls(F)4
) {
85
4
      // Local functions without inline hints get counts only through
86
4
      // propagation.
87
4
      InitialCount = 0;
88
9
    } else if (F.hasFnAttribute(Attribute::Cold) ||
89
9
               
F.hasFnAttribute(Attribute::NoInline)8
) {
90
2
      // Use a lower value for noinline and cold functions.
91
2
      InitialCount = ColdSyntheticCount;
92
2
    }
93
17
    SetCount(&F, InitialCount);
94
17
  }
95
3
}
96
97
PreservedAnalyses SyntheticCountsPropagation::run(Module &M,
98
3
                                                  ModuleAnalysisManager &MAM) {
99
3
  FunctionAnalysisManager &FAM =
100
3
      MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
101
3
  DenseMap<Function *, Scaled64> Counts;
102
3
  // Set initial entry counts.
103
3
  initializeCounts(
104
17
      M, [&](Function *F, uint64_t Count) { Counts[F] = Scaled64(Count, 0); });
105
3
106
3
  // Edge includes information about the source. Hence ignore the first
107
3
  // parameter.
108
3
  auto GetCallSiteProfCount = [&](const CallGraphNode *,
109
22
                                  const CallGraphNode::CallRecord &Edge) {
110
22
    Optional<Scaled64> Res = None;
111
22
    if (!Edge.first)
112
15
      return Res;
113
7
    assert(isa<Instruction>(Edge.first));
114
7
    CallSite CS(cast<Instruction>(Edge.first));
115
7
    Function *Caller = CS.getCaller();
116
7
    auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(*Caller);
117
7
118
7
    // Now compute the callsite count from relative frequency and
119
7
    // entry count:
120
7
    BasicBlock *CSBB = CS.getInstruction()->getParent();
121
7
    Scaled64 EntryFreq(BFI.getEntryFreq(), 0);
122
7
    Scaled64 BBCount(BFI.getBlockFreq(CSBB).getFrequency(), 0);
123
7
    BBCount /= EntryFreq;
124
7
    BBCount *= Counts[Caller];
125
7
    return Optional<Scaled64>(BBCount);
126
7
  };
127
3
128
3
  CallGraph CG(M);
129
3
  // Propgate the entry counts on the callgraph.
130
3
  SyntheticCountsUtils<const CallGraph *>::propagate(
131
7
      &CG, GetCallSiteProfCount, [&](const CallGraphNode *N, Scaled64 New) {
132
7
        auto F = N->getFunction();
133
7
        if (!F || F->isDeclaration())
134
1
          return;
135
6
136
6
        Counts[F] += New;
137
6
      });
138
3
139
3
  // Set the counts as metadata.
140
17
  for (auto Entry : Counts) {
141
17
    Entry.first->setEntryCount(ProfileCount(
142
17
        Entry.second.template toInt<uint64_t>(), Function::PCT_Synthetic));
143
17
  }
144
3
145
3
  return PreservedAnalyses::all();
146
3
}