1 //=-- ProfilesummaryBuilder.cpp - Profile summary computation ---------------=//
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 contains support for computing profile summary data.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/IR/Attributes.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Metadata.h"
16 #include "llvm/IR/Type.h"
17 #include "llvm/ProfileData/InstrProf.h"
18 #include "llvm/ProfileData/ProfileCommon.h"
19 #include "llvm/ProfileData/SampleProf.h"
20 #include "llvm/Support/Casting.h"
21 #include "llvm/Support/CommandLine.h"
22 
23 using namespace llvm;
24 
25 cl::opt<bool> UseContextLessSummary(
26     "profile-summary-contextless", cl::Hidden, cl::init(false), cl::ZeroOrMore,
27     cl::desc("Merge context profiles before calculating thresholds."));
28 
29 // A set of cutoff values. Each value, when divided by ProfileSummary::Scale
30 // (which is 1000000) is a desired percentile of total counts.
31 static const uint32_t DefaultCutoffsData[] = {
32     10000,  /*  1% */
33     100000, /* 10% */
34     200000, 300000, 400000, 500000, 600000, 700000, 800000,
35     900000, 950000, 990000, 999000, 999900, 999990, 999999};
36 const ArrayRef<uint32_t> ProfileSummaryBuilder::DefaultCutoffs =
37     DefaultCutoffsData;
38 
39 const ProfileSummaryEntry &
40 ProfileSummaryBuilder::getEntryForPercentile(SummaryEntryVector &DS,
41                                              uint64_t Percentile) {
42   auto It = partition_point(DS, [=](const ProfileSummaryEntry &Entry) {
43     return Entry.Cutoff < Percentile;
44   });
45   // The required percentile has to be <= one of the percentiles in the
46   // detailed summary.
47   if (It == DS.end())
48     report_fatal_error("Desired percentile exceeds the maximum cutoff");
49   return *It;
50 }
51 
52 void InstrProfSummaryBuilder::addRecord(const InstrProfRecord &R) {
53   // The first counter is not necessarily an entry count for IR
54   // instrumentation profiles.
55   // Eventually MaxFunctionCount will become obsolete and this can be
56   // removed.
57   addEntryCount(R.Counts[0]);
58   for (size_t I = 1, E = R.Counts.size(); I < E; ++I)
59     addInternalCount(R.Counts[I]);
60 }
61 
62 // To compute the detailed summary, we consider each line containing samples as
63 // equivalent to a block with a count in the instrumented profile.
64 void SampleProfileSummaryBuilder::addRecord(
65     const sampleprof::FunctionSamples &FS, bool isCallsiteSample) {
66   if (!isCallsiteSample) {
67     NumFunctions++;
68     if (FS.getHeadSamples() > MaxFunctionCount)
69       MaxFunctionCount = FS.getHeadSamples();
70   }
71   for (const auto &I : FS.getBodySamples()) {
72     uint64_t Count = I.second.getSamples();
73     if (!sampleprof::FunctionSamples::ProfileIsProbeBased ||
74         (Count != sampleprof::FunctionSamples::InvalidProbeCount))
75       addCount(Count);
76   }
77   for (const auto &I : FS.getCallsiteSamples())
78     for (const auto &CS : I.second)
79       addRecord(CS.second, true);
80 }
81 
82 // The argument to this method is a vector of cutoff percentages and the return
83 // value is a vector of (Cutoff, MinCount, NumCounts) triplets.
84 void ProfileSummaryBuilder::computeDetailedSummary() {
85   if (DetailedSummaryCutoffs.empty())
86     return;
87   llvm::sort(DetailedSummaryCutoffs);
88   auto Iter = CountFrequencies.begin();
89   const auto End = CountFrequencies.end();
90 
91   uint32_t CountsSeen = 0;
92   uint64_t CurrSum = 0, Count = 0;
93 
94   for (const uint32_t Cutoff : DetailedSummaryCutoffs) {
95     assert(Cutoff <= 999999);
96     APInt Temp(128, TotalCount);
97     APInt N(128, Cutoff);
98     APInt D(128, ProfileSummary::Scale);
99     Temp *= N;
100     Temp = Temp.sdiv(D);
101     uint64_t DesiredCount = Temp.getZExtValue();
102     assert(DesiredCount <= TotalCount);
103     while (CurrSum < DesiredCount && Iter != End) {
104       Count = Iter->first;
105       uint32_t Freq = Iter->second;
106       CurrSum += (Count * Freq);
107       CountsSeen += Freq;
108       Iter++;
109     }
110     assert(CurrSum >= DesiredCount);
111     ProfileSummaryEntry PSE = {Cutoff, Count, CountsSeen};
112     DetailedSummary.push_back(PSE);
113   }
114 }
115 
116 std::unique_ptr<ProfileSummary> SampleProfileSummaryBuilder::getSummary() {
117   computeDetailedSummary();
118   return std::make_unique<ProfileSummary>(
119       ProfileSummary::PSK_Sample, DetailedSummary, TotalCount, MaxCount, 0,
120       MaxFunctionCount, NumCounts, NumFunctions);
121 }
122 
123 std::unique_ptr<ProfileSummary>
124 SampleProfileSummaryBuilder::computeSummaryForProfiles(
125     const StringMap<sampleprof::FunctionSamples> &Profiles) {
126   assert(NumFunctions == 0 &&
127          "This can only be called on an empty summary builder");
128   StringMap<sampleprof::FunctionSamples> ContextLessProfiles;
129   const StringMap<sampleprof::FunctionSamples> *ProfilesToUse = &Profiles;
130   // For CSSPGO, context-sensitive profile effectively split a function profile
131   // into many copies each representing the CFG profile of a particular calling
132   // context. That makes the count distribution looks more flat as we now have
133   // more function profiles each with lower counts, which in turn leads to lower
134   // hot thresholds. To compensate for that, by defauly we merge context
135   // profiles before coumputing profile summary.
136   if (UseContextLessSummary || (sampleprof::FunctionSamples::ProfileIsCS &&
137                                 !UseContextLessSummary.getNumOccurrences())) {
138     for (const auto &I : Profiles) {
139       ContextLessProfiles[I.second.getName()].merge(I.second);
140     }
141     ProfilesToUse = &ContextLessProfiles;
142   }
143 
144   for (const auto &I : *ProfilesToUse) {
145     const sampleprof::FunctionSamples &Profile = I.second;
146     addRecord(Profile);
147   }
148 
149   return getSummary();
150 }
151 
152 std::unique_ptr<ProfileSummary> InstrProfSummaryBuilder::getSummary() {
153   computeDetailedSummary();
154   return std::make_unique<ProfileSummary>(
155       ProfileSummary::PSK_Instr, DetailedSummary, TotalCount, MaxCount,
156       MaxInternalBlockCount, MaxFunctionCount, NumCounts, NumFunctions);
157 }
158 
159 void InstrProfSummaryBuilder::addEntryCount(uint64_t Count) {
160   NumFunctions++;
161 
162   // Skip invalid count.
163   if (Count == (uint64_t)-1)
164     return;
165 
166   addCount(Count);
167   if (Count > MaxFunctionCount)
168     MaxFunctionCount = Count;
169 }
170 
171 void InstrProfSummaryBuilder::addInternalCount(uint64_t Count) {
172   // Skip invalid count.
173   if (Count == (uint64_t)-1)
174     return;
175 
176   addCount(Count);
177   if (Count > MaxInternalBlockCount)
178     MaxInternalBlockCount = Count;
179 }
180