1 //===-- ProfileGenerator.cpp - Profile Generator ---------------*- 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 #include "ProfileGenerator.h" 10 11 static cl::opt<std::string> OutputFilename("output", cl::value_desc("output"), 12 cl::Required, 13 cl::desc("Output profile file")); 14 15 static cl::opt<SampleProfileFormat> OutputFormat( 16 "format", cl::desc("Format of output profile"), cl::init(SPF_Text), 17 cl::values( 18 clEnumValN(SPF_Binary, "binary", "Binary encoding (default)"), 19 clEnumValN(SPF_Compact_Binary, "compbinary", "Compact binary encoding"), 20 clEnumValN(SPF_Ext_Binary, "extbinary", "Extensible binary encoding"), 21 clEnumValN(SPF_Text, "text", "Text encoding"), 22 clEnumValN(SPF_GCC, "gcc", 23 "GCC encoding (only meaningful for -sample)"))); 24 25 using namespace llvm; 26 using namespace sampleprof; 27 28 namespace llvm { 29 namespace sampleprof { 30 31 std::unique_ptr<ProfileGenerator> 32 ProfileGenerator::create(const BinarySampleCounterMap &BinarySampleCounters, 33 enum PerfScriptType SampleType) { 34 std::unique_ptr<ProfileGenerator> ProfileGenerator; 35 36 if (SampleType == PERF_LBR_STACK) { 37 ProfileGenerator.reset(new CSProfileGenerator(BinarySampleCounters)); 38 } else { 39 // TODO: 40 llvm_unreachable("Unsupported perfscript!"); 41 } 42 43 return ProfileGenerator; 44 } 45 46 void ProfileGenerator::write() { 47 auto WriterOrErr = SampleProfileWriter::create(OutputFilename, OutputFormat); 48 if (std::error_code EC = WriterOrErr.getError()) 49 exitWithError(EC, OutputFilename); 50 auto Writer = std::move(WriterOrErr.get()); 51 Writer->write(ProfileMap); 52 } 53 54 void ProfileGenerator::findDisjointRanges(RangeSample &DisjointRanges, 55 const RangeSample &Ranges) { 56 57 /* 58 Regions may overlap with each other. Using the boundary info, find all 59 disjoint ranges and their sample count. BoundaryPoint contains the count 60 mutiple samples begin/end at this points. 61 62 |<--100-->| Sample1 63 |<------200------>| Sample2 64 A B C 65 66 In the example above, 67 Sample1 begins at A, ends at B, its value is 100. 68 Sample2 beings at A, ends at C, its value is 200. 69 For A, BeginCount is the sum of sample begins at A, which is 300 and no 70 samples ends at A, so EndCount is 0. 71 Then boundary points A, B, and C with begin/end counts are: 72 A: (300, 0) 73 B: (0, 100) 74 C: (0, 200) 75 */ 76 struct BoundaryPoint { 77 // Sum of sample counts beginning at this point 78 uint64_t BeginCount; 79 // Sum of sample counts ending at this point 80 uint64_t EndCount; 81 82 BoundaryPoint() : BeginCount(0), EndCount(0){}; 83 84 void addBeginCount(uint64_t Count) { BeginCount += Count; } 85 86 void addEndCount(uint64_t Count) { EndCount += Count; } 87 }; 88 89 /* 90 For the above example. With boundary points, follwing logic finds two 91 disjoint region of 92 93 [A,B]: 300 94 [B+1,C]: 200 95 96 If there is a boundary point that both begin and end, the point itself 97 becomes a separate disjoint region. For example, if we have original 98 ranges of 99 100 |<--- 100 --->| 101 |<--- 200 --->| 102 A B C 103 104 there are three boundary points with their begin/end counts of 105 106 A: (100, 0) 107 B: (200, 100) 108 C: (0, 200) 109 110 the disjoint ranges would be 111 112 [A, B-1]: 100 113 [B, B]: 300 114 [B+1, C]: 200. 115 */ 116 std::map<uint64_t, BoundaryPoint> Boundaries; 117 118 for (auto Item : Ranges) { 119 uint64_t Begin = Item.first.first; 120 uint64_t End = Item.first.second; 121 uint64_t Count = Item.second; 122 if (Boundaries.find(Begin) == Boundaries.end()) 123 Boundaries[Begin] = BoundaryPoint(); 124 Boundaries[Begin].addBeginCount(Count); 125 126 if (Boundaries.find(End) == Boundaries.end()) 127 Boundaries[End] = BoundaryPoint(); 128 Boundaries[End].addEndCount(Count); 129 } 130 131 uint64_t BeginAddress = 0; 132 int Count = 0; 133 for (auto Item : Boundaries) { 134 uint64_t Address = Item.first; 135 BoundaryPoint &Point = Item.second; 136 if (Point.BeginCount) { 137 if (BeginAddress) 138 DisjointRanges[{BeginAddress, Address - 1}] = Count; 139 Count += Point.BeginCount; 140 BeginAddress = Address; 141 } 142 if (Point.EndCount) { 143 assert(BeginAddress && "First boundary point cannot be 'end' point"); 144 DisjointRanges[{BeginAddress, Address}] = Count; 145 Count -= Point.EndCount; 146 BeginAddress = Address + 1; 147 } 148 } 149 } 150 151 FunctionSamples & 152 CSProfileGenerator::getFunctionProfileForContext(StringRef ContextStr) { 153 auto Ret = ProfileMap.try_emplace(ContextStr, FunctionSamples()); 154 if (Ret.second) { 155 SampleContext FContext(Ret.first->first(), RawContext); 156 FunctionSamples &FProfile = Ret.first->second; 157 FProfile.setName(FContext.getName()); 158 FProfile.setContext(FContext); 159 } 160 return Ret.first->second; 161 } 162 163 void CSProfileGenerator::updateBodySamplesforFunctionProfile( 164 FunctionSamples &FunctionProfile, const FrameLocation &LeafLoc, 165 uint64_t Count) { 166 // Filter out invalid negative(int type) lineOffset 167 if (LeafLoc.second.LineOffset & 0x80000000) 168 return; 169 // Use the maximum count of samples with same line location 170 ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt( 171 LeafLoc.second.LineOffset, LeafLoc.second.Discriminator); 172 uint64_t PreviousCount = R ? R.get() : 0; 173 if (PreviousCount < Count) { 174 FunctionProfile.addBodySamples(LeafLoc.second.LineOffset, 175 LeafLoc.second.Discriminator, 176 Count - PreviousCount); 177 FunctionProfile.addTotalSamples(Count - PreviousCount); 178 } 179 } 180 181 void CSProfileGenerator::populateFunctionBodySamples() { 182 for (const auto &BI : BinarySampleCounters) { 183 ProfiledBinary *Binary = BI.first; 184 for (const auto &CI : BI.second.RangeCounter) { 185 StringRef ContextId(CI.first); 186 // Get or create function profile for the range 187 FunctionSamples &FunctionProfile = 188 getFunctionProfileForContext(ContextId); 189 // Compute disjoint ranges first, so we can use MAX 190 // for calculating count for each location. 191 RangeSample Ranges; 192 findDisjointRanges(Ranges, CI.second); 193 194 for (auto Range : Ranges) { 195 uint64_t RangeBegin = Binary->offsetToVirtualAddr(Range.first.first); 196 uint64_t RangeEnd = Binary->offsetToVirtualAddr(Range.first.second); 197 uint64_t Count = Range.second; 198 // Disjoint ranges have introduce zero-filled gap that 199 // doesn't belong to current context, filter them out. 200 if (Count == 0) 201 continue; 202 203 InstructionPointer IP(Binary, RangeBegin, true); 204 205 // Disjoint ranges may have range in the middle of two instr, 206 // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range 207 // can be Addr1+1 to Addr2-1. We should ignore such range. 208 if (IP.Address > RangeEnd) 209 continue; 210 211 while (IP.Address <= RangeEnd) { 212 uint64_t Offset = Binary->virtualAddrToOffset(IP.Address); 213 const FrameLocation &LeafLoc = Binary->getInlineLeafFrameLoc(Offset); 214 // Recording body sample for this specific context 215 updateBodySamplesforFunctionProfile(FunctionProfile, LeafLoc, Count); 216 // Move to next IP within the range 217 IP.advance(); 218 } 219 } 220 } 221 } 222 } 223 224 void CSProfileGenerator::populateFunctionBoundarySamples() { 225 for (const auto &BI : BinarySampleCounters) { 226 ProfiledBinary *Binary = BI.first; 227 for (const auto &CI : BI.second.BranchCounter) { 228 StringRef ContextId(CI.first); 229 // Get or create function profile for branch Source 230 FunctionSamples &FunctionProfile = 231 getFunctionProfileForContext(ContextId); 232 233 for (auto Entry : CI.second) { 234 uint64_t SourceOffset = Entry.first.first; 235 uint64_t TargetOffset = Entry.first.second; 236 uint64_t Count = Entry.second; 237 // Get the callee name by branch target if it's a call branch 238 StringRef CalleeName = FunctionSamples::getCanonicalFnName( 239 Binary->getFuncFromStartOffset(TargetOffset)); 240 if (CalleeName.size() == 0) 241 continue; 242 243 // Record called target sample and its count 244 const FrameLocation &LeafLoc = 245 Binary->getInlineLeafFrameLoc(SourceOffset); 246 247 FunctionProfile.addCalledTargetSamples(LeafLoc.second.LineOffset, 248 LeafLoc.second.Discriminator, 249 CalleeName, Count); 250 FunctionProfile.addTotalSamples(Count); 251 252 // Record head sample for called target(callee) 253 // TODO: Cleanup ' @ ' 254 std::string CalleeContextId = 255 getCallSite(LeafLoc) + " @ " + CalleeName.str(); 256 if (ContextId.find(" @ ") != StringRef::npos) { 257 CalleeContextId = 258 ContextId.rsplit(" @ ").first.str() + " @ " + CalleeContextId; 259 } 260 261 if (ProfileMap.find(CalleeContextId) != ProfileMap.end()) { 262 FunctionSamples &CalleeProfile = ProfileMap[CalleeContextId]; 263 assert(Count != 0 && "Unexpected zero weight branch"); 264 if (CalleeProfile.getName().size()) { 265 CalleeProfile.addHeadSamples(Count); 266 } 267 } 268 } 269 } 270 } 271 } 272 273 static FrameLocation getCallerContext(StringRef CalleeContext, 274 StringRef &CallerNameWithContext) { 275 StringRef CallerContext = CalleeContext.rsplit(" @ ").first; 276 CallerNameWithContext = CallerContext.rsplit(':').first; 277 auto ContextSplit = CallerContext.rsplit(" @ "); 278 FrameLocation LeafFrameLoc = {"", {0, 0}}; 279 StringRef Funcname; 280 SampleContext::decodeContextString(ContextSplit.second, Funcname, 281 LeafFrameLoc.second); 282 LeafFrameLoc.first = Funcname.str(); 283 return LeafFrameLoc; 284 } 285 286 void CSProfileGenerator::populateInferredFunctionSamples() { 287 for (const auto &Item : ProfileMap) { 288 const StringRef CalleeContext = Item.first(); 289 const FunctionSamples &CalleeProfile = Item.second; 290 291 // If we already have head sample counts, we must have value profile 292 // for call sites added already. Skip to avoid double counting. 293 if (CalleeProfile.getHeadSamples()) 294 continue; 295 // If we don't have context, nothing to do for caller's call site. 296 // This could happen for entry point function. 297 if (CalleeContext.find(" @ ") == StringRef::npos) 298 continue; 299 300 // Infer Caller's frame loc and context ID through string splitting 301 StringRef CallerContextId; 302 FrameLocation &&CallerLeafFrameLoc = 303 getCallerContext(CalleeContext, CallerContextId); 304 305 // It's possible that we haven't seen any sample directly in the caller, 306 // in which case CallerProfile will not exist. But we can't modify 307 // ProfileMap while iterating it. 308 // TODO: created function profile for those callers too 309 if (ProfileMap.find(CallerContextId) == ProfileMap.end()) 310 continue; 311 FunctionSamples &CallerProfile = ProfileMap[CallerContextId]; 312 313 // Since we don't have call count for inlined functions, we 314 // estimate it from inlinee's profile using entry body sample. 315 uint64_t EstimatedCallCount = CalleeProfile.getEntrySamples(); 316 // If we don't have samples with location, use 1 to indicate live. 317 if (!EstimatedCallCount && !CalleeProfile.getBodySamples().size()) 318 EstimatedCallCount = 1; 319 CallerProfile.addCalledTargetSamples( 320 CallerLeafFrameLoc.second.LineOffset, 321 CallerLeafFrameLoc.second.Discriminator, CalleeProfile.getName(), 322 EstimatedCallCount); 323 updateBodySamplesforFunctionProfile(CallerProfile, CallerLeafFrameLoc, 324 EstimatedCallCount); 325 } 326 } 327 328 } // end namespace sampleprof 329 } // end namespace llvm 330