1 //===- SampleProfWriter.cpp - Write LLVM sample profile data --------------===//
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 class that writes LLVM sample profiles. It
10 // supports two file formats: text and binary. The textual representation
11 // is useful for debugging and testing purposes. The binary representation
12 // is more compact, resulting in smaller file sizes. However, they can
13 // both be used interchangeably.
14 //
15 // See lib/ProfileData/SampleProfReader.cpp for documentation on each of the
16 // supported formats.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "llvm/ProfileData/SampleProfWriter.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/ProfileData/ProfileCommon.h"
23 #include "llvm/ProfileData/SampleProf.h"
24 #include "llvm/Support/Compression.h"
25 #include "llvm/Support/Endian.h"
26 #include "llvm/Support/EndianStream.h"
27 #include "llvm/Support/ErrorOr.h"
28 #include "llvm/Support/FileSystem.h"
29 #include "llvm/Support/LEB128.h"
30 #include "llvm/Support/MD5.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include <algorithm>
33 #include <cmath>
34 #include <cstdint>
35 #include <memory>
36 #include <set>
37 #include <system_error>
38 #include <utility>
39 #include <vector>
40 
41 #define DEBUG_TYPE "llvm-profdata"
42 
43 using namespace llvm;
44 using namespace sampleprof;
45 
46 namespace llvm {
47 namespace support {
48 namespace endian {
49 namespace {
50 
51 // Adapter class to llvm::support::endian::Writer for pwrite().
52 struct SeekableWriter {
53   raw_pwrite_stream &OS;
54   endianness Endian;
55   SeekableWriter(raw_pwrite_stream &OS, endianness Endian)
56       : OS(OS), Endian(Endian) {}
57 
58   template <typename ValueType>
59   void pwrite(ValueType Val, size_t Offset) {
60     std::string StringBuf;
61     raw_string_ostream SStream(StringBuf);
62     Writer(SStream, Endian).write(Val);
63     OS.pwrite(StringBuf.data(), StringBuf.size(), Offset);
64   }
65 };
66 
67 } // namespace
68 } // namespace endian
69 } // namespace support
70 } // namespace llvm
71 
72 DefaultFunctionPruningStrategy::DefaultFunctionPruningStrategy(
73     SampleProfileMap &ProfileMap, size_t OutputSizeLimit)
74     : FunctionPruningStrategy(ProfileMap, OutputSizeLimit) {
75   sortFuncProfiles(ProfileMap, SortedFunctions);
76 }
77 
78 void DefaultFunctionPruningStrategy::Erase(size_t CurrentOutputSize) {
79   double D = (double)OutputSizeLimit / CurrentOutputSize;
80   size_t NewSize = (size_t)round(ProfileMap.size() * D * D);
81   size_t NumToRemove = ProfileMap.size() - NewSize;
82   if (NumToRemove < 1)
83     NumToRemove = 1;
84 
85   assert(NumToRemove <= SortedFunctions.size());
86   llvm::for_each(
87       llvm::make_range(SortedFunctions.begin() + SortedFunctions.size() -
88                            NumToRemove,
89                        SortedFunctions.end()),
90       [&](const NameFunctionSamples &E) { ProfileMap.erase(E.first); });
91   SortedFunctions.resize(SortedFunctions.size() - NumToRemove);
92 }
93 
94 std::error_code SampleProfileWriter::writeWithSizeLimitInternal(
95     SampleProfileMap &ProfileMap, size_t OutputSizeLimit,
96     FunctionPruningStrategy *Strategy) {
97   if (OutputSizeLimit == 0)
98     return write(ProfileMap);
99 
100   size_t OriginalFunctionCount = ProfileMap.size();
101 
102   std::unique_ptr<raw_ostream> OriginalOutputStream;
103   OutputStream.swap(OriginalOutputStream);
104 
105   size_t IterationCount = 0;
106   size_t TotalSize;
107 
108   SmallVector<char> StringBuffer;
109   do {
110     StringBuffer.clear();
111     OutputStream.reset(new raw_svector_ostream(StringBuffer));
112     if (std::error_code EC = write(ProfileMap))
113       return EC;
114 
115     TotalSize = StringBuffer.size();
116     // On Windows every "\n" is actually written as "\r\n" to disk but not to
117     // memory buffer, this difference should be added when considering the total
118     // output size.
119 #ifdef _WIN32
120     if (Format == SPF_Text)
121       TotalSize += LineCount;
122 #endif
123     if (TotalSize <= OutputSizeLimit)
124       break;
125 
126     Strategy->Erase(TotalSize);
127     IterationCount++;
128   } while (ProfileMap.size() != 0);
129 
130   if (ProfileMap.size() == 0)
131     return sampleprof_error::too_large;
132 
133   OutputStream.swap(OriginalOutputStream);
134   OutputStream->write(StringBuffer.data(), StringBuffer.size());
135   LLVM_DEBUG(dbgs() << "Profile originally has " << OriginalFunctionCount
136                     << " functions, reduced to " << ProfileMap.size() << " in "
137                     << IterationCount << " iterations\n");
138   // Silence warning on Release build.
139   (void)OriginalFunctionCount;
140   (void)IterationCount;
141   return sampleprof_error::success;
142 }
143 
144 std::error_code
145 SampleProfileWriter::writeFuncProfiles(const SampleProfileMap &ProfileMap) {
146   std::vector<NameFunctionSamples> V;
147   sortFuncProfiles(ProfileMap, V);
148   for (const auto &I : V) {
149     if (std::error_code EC = writeSample(*I.second))
150       return EC;
151   }
152   return sampleprof_error::success;
153 }
154 
155 std::error_code SampleProfileWriter::write(const SampleProfileMap &ProfileMap) {
156   if (std::error_code EC = writeHeader(ProfileMap))
157     return EC;
158 
159   if (std::error_code EC = writeFuncProfiles(ProfileMap))
160     return EC;
161 
162   return sampleprof_error::success;
163 }
164 
165 /// Return the current position and prepare to use it as the start
166 /// position of a section given the section type \p Type and its position
167 /// \p LayoutIdx in SectionHdrLayout.
168 uint64_t
169 SampleProfileWriterExtBinaryBase::markSectionStart(SecType Type,
170                                                    uint32_t LayoutIdx) {
171   uint64_t SectionStart = OutputStream->tell();
172   assert(LayoutIdx < SectionHdrLayout.size() && "LayoutIdx out of range");
173   const auto &Entry = SectionHdrLayout[LayoutIdx];
174   assert(Entry.Type == Type && "Unexpected section type");
175   // Use LocalBuf as a temporary output for writting data.
176   if (hasSecFlag(Entry, SecCommonFlags::SecFlagCompress))
177     LocalBufStream.swap(OutputStream);
178   return SectionStart;
179 }
180 
181 std::error_code SampleProfileWriterExtBinaryBase::compressAndOutput() {
182   if (!llvm::compression::zlib::isAvailable())
183     return sampleprof_error::zlib_unavailable;
184   std::string &UncompressedStrings =
185       static_cast<raw_string_ostream *>(LocalBufStream.get())->str();
186   if (UncompressedStrings.size() == 0)
187     return sampleprof_error::success;
188   auto &OS = *OutputStream;
189   SmallVector<uint8_t, 128> CompressedStrings;
190   compression::zlib::compress(arrayRefFromStringRef(UncompressedStrings),
191                               CompressedStrings,
192                               compression::zlib::BestSizeCompression);
193   encodeULEB128(UncompressedStrings.size(), OS);
194   encodeULEB128(CompressedStrings.size(), OS);
195   OS << toStringRef(CompressedStrings);
196   UncompressedStrings.clear();
197   return sampleprof_error::success;
198 }
199 
200 /// Add a new section into section header table given the section type
201 /// \p Type, its position \p LayoutIdx in SectionHdrLayout and the
202 /// location \p SectionStart where the section should be written to.
203 std::error_code SampleProfileWriterExtBinaryBase::addNewSection(
204     SecType Type, uint32_t LayoutIdx, uint64_t SectionStart) {
205   assert(LayoutIdx < SectionHdrLayout.size() && "LayoutIdx out of range");
206   const auto &Entry = SectionHdrLayout[LayoutIdx];
207   assert(Entry.Type == Type && "Unexpected section type");
208   if (hasSecFlag(Entry, SecCommonFlags::SecFlagCompress)) {
209     LocalBufStream.swap(OutputStream);
210     if (std::error_code EC = compressAndOutput())
211       return EC;
212   }
213   SecHdrTable.push_back({Type, Entry.Flags, SectionStart - FileStart,
214                          OutputStream->tell() - SectionStart, LayoutIdx});
215   return sampleprof_error::success;
216 }
217 
218 std::error_code
219 SampleProfileWriterExtBinaryBase::write(const SampleProfileMap &ProfileMap) {
220   // When calling write on a different profile map, existing states should be
221   // cleared.
222   NameTable.clear();
223   CSNameTable.clear();
224   SecHdrTable.clear();
225 
226   if (std::error_code EC = writeHeader(ProfileMap))
227     return EC;
228 
229   std::string LocalBuf;
230   LocalBufStream = std::make_unique<raw_string_ostream>(LocalBuf);
231   if (std::error_code EC = writeSections(ProfileMap))
232     return EC;
233 
234   if (std::error_code EC = writeSecHdrTable())
235     return EC;
236 
237   return sampleprof_error::success;
238 }
239 
240 std::error_code SampleProfileWriterExtBinaryBase::writeContextIdx(
241     const SampleContext &Context) {
242   if (Context.hasContext())
243     return writeCSNameIdx(Context);
244   else
245     return SampleProfileWriterBinary::writeNameIdx(Context.getName());
246 }
247 
248 std::error_code
249 SampleProfileWriterExtBinaryBase::writeCSNameIdx(const SampleContext &Context) {
250   const auto &Ret = CSNameTable.find(Context);
251   if (Ret == CSNameTable.end())
252     return sampleprof_error::truncated_name_table;
253   encodeULEB128(Ret->second, *OutputStream);
254   return sampleprof_error::success;
255 }
256 
257 std::error_code
258 SampleProfileWriterExtBinaryBase::writeSample(const FunctionSamples &S) {
259   uint64_t Offset = OutputStream->tell();
260   auto &Context = S.getContext();
261   FuncOffsetTable[Context] = Offset - SecLBRProfileStart;
262   encodeULEB128(S.getHeadSamples(), *OutputStream);
263   return writeBody(S);
264 }
265 
266 std::error_code SampleProfileWriterExtBinaryBase::writeFuncOffsetTable() {
267   auto &OS = *OutputStream;
268 
269   // Write out the table size.
270   encodeULEB128(FuncOffsetTable.size(), OS);
271 
272   // Write out FuncOffsetTable.
273   auto WriteItem = [&](const SampleContext &Context, uint64_t Offset) {
274     if (std::error_code EC = writeContextIdx(Context))
275       return EC;
276     encodeULEB128(Offset, OS);
277     return (std::error_code)sampleprof_error::success;
278   };
279 
280   if (FunctionSamples::ProfileIsCS) {
281     // Sort the contexts before writing them out. This is to help fast load all
282     // context profiles for a function as well as their callee contexts which
283     // can help profile-guided importing for ThinLTO.
284     std::map<SampleContext, uint64_t> OrderedFuncOffsetTable(
285         FuncOffsetTable.begin(), FuncOffsetTable.end());
286     for (const auto &Entry : OrderedFuncOffsetTable) {
287       if (std::error_code EC = WriteItem(Entry.first, Entry.second))
288         return EC;
289     }
290     addSectionFlag(SecFuncOffsetTable, SecFuncOffsetFlags::SecFlagOrdered);
291   } else {
292     for (const auto &Entry : FuncOffsetTable) {
293       if (std::error_code EC = WriteItem(Entry.first, Entry.second))
294         return EC;
295     }
296   }
297 
298   FuncOffsetTable.clear();
299   return sampleprof_error::success;
300 }
301 
302 std::error_code SampleProfileWriterExtBinaryBase::writeFuncMetadata(
303     const FunctionSamples &FunctionProfile) {
304   auto &OS = *OutputStream;
305   if (std::error_code EC = writeContextIdx(FunctionProfile.getContext()))
306     return EC;
307 
308   if (FunctionSamples::ProfileIsProbeBased)
309     encodeULEB128(FunctionProfile.getFunctionHash(), OS);
310   if (FunctionSamples::ProfileIsCS || FunctionSamples::ProfileIsPreInlined) {
311     encodeULEB128(FunctionProfile.getContext().getAllAttributes(), OS);
312   }
313 
314   if (!FunctionSamples::ProfileIsCS) {
315     // Recursively emit attributes for all callee samples.
316     uint64_t NumCallsites = 0;
317     for (const auto &J : FunctionProfile.getCallsiteSamples())
318       NumCallsites += J.second.size();
319     encodeULEB128(NumCallsites, OS);
320     for (const auto &J : FunctionProfile.getCallsiteSamples()) {
321       for (const auto &FS : J.second) {
322         LineLocation Loc = J.first;
323         encodeULEB128(Loc.LineOffset, OS);
324         encodeULEB128(Loc.Discriminator, OS);
325         if (std::error_code EC = writeFuncMetadata(FS.second))
326           return EC;
327       }
328     }
329   }
330 
331   return sampleprof_error::success;
332 }
333 
334 std::error_code SampleProfileWriterExtBinaryBase::writeFuncMetadata(
335     const SampleProfileMap &Profiles) {
336   if (!FunctionSamples::ProfileIsProbeBased && !FunctionSamples::ProfileIsCS &&
337       !FunctionSamples::ProfileIsPreInlined)
338     return sampleprof_error::success;
339   for (const auto &Entry : Profiles) {
340     if (std::error_code EC = writeFuncMetadata(Entry.second))
341       return EC;
342   }
343   return sampleprof_error::success;
344 }
345 
346 std::error_code SampleProfileWriterExtBinaryBase::writeNameTable() {
347   if (!UseMD5)
348     return SampleProfileWriterBinary::writeNameTable();
349 
350   auto &OS = *OutputStream;
351   std::set<StringRef> V;
352   stablizeNameTable(NameTable, V);
353 
354   // Write out the MD5 name table. We wrote unencoded MD5 so reader can
355   // retrieve the name using the name index without having to read the
356   // whole name table.
357   encodeULEB128(NameTable.size(), OS);
358   support::endian::Writer Writer(OS, support::little);
359   for (auto N : V)
360     Writer.write(MD5Hash(N));
361   return sampleprof_error::success;
362 }
363 
364 std::error_code SampleProfileWriterExtBinaryBase::writeNameTableSection(
365     const SampleProfileMap &ProfileMap) {
366   for (const auto &I : ProfileMap) {
367     assert(I.first == I.second.getContext() && "Inconsistent profile map");
368     addContext(I.second.getContext());
369     addNames(I.second);
370   }
371 
372   // If NameTable contains ".__uniq." suffix, set SecFlagUniqSuffix flag
373   // so compiler won't strip the suffix during profile matching after
374   // seeing the flag in the profile.
375   for (const auto &I : NameTable) {
376     if (I.first.contains(FunctionSamples::UniqSuffix)) {
377       addSectionFlag(SecNameTable, SecNameTableFlags::SecFlagUniqSuffix);
378       break;
379     }
380   }
381 
382   if (auto EC = writeNameTable())
383     return EC;
384   return sampleprof_error::success;
385 }
386 
387 std::error_code SampleProfileWriterExtBinaryBase::writeCSNameTableSection() {
388   // Sort the names to make CSNameTable deterministic.
389   std::set<SampleContext> OrderedContexts;
390   for (const auto &I : CSNameTable)
391     OrderedContexts.insert(I.first);
392   assert(OrderedContexts.size() == CSNameTable.size() &&
393          "Unmatched ordered and unordered contexts");
394   uint64_t I = 0;
395   for (auto &Context : OrderedContexts)
396     CSNameTable[Context] = I++;
397 
398   auto &OS = *OutputStream;
399   encodeULEB128(OrderedContexts.size(), OS);
400   support::endian::Writer Writer(OS, support::little);
401   for (auto Context : OrderedContexts) {
402     auto Frames = Context.getContextFrames();
403     encodeULEB128(Frames.size(), OS);
404     for (auto &Callsite : Frames) {
405       if (std::error_code EC = writeNameIdx(Callsite.FuncName))
406         return EC;
407       encodeULEB128(Callsite.Location.LineOffset, OS);
408       encodeULEB128(Callsite.Location.Discriminator, OS);
409     }
410   }
411 
412   return sampleprof_error::success;
413 }
414 
415 std::error_code
416 SampleProfileWriterExtBinaryBase::writeProfileSymbolListSection() {
417   if (ProfSymList && ProfSymList->size() > 0)
418     if (std::error_code EC = ProfSymList->write(*OutputStream))
419       return EC;
420 
421   return sampleprof_error::success;
422 }
423 
424 std::error_code SampleProfileWriterExtBinaryBase::writeOneSection(
425     SecType Type, uint32_t LayoutIdx, const SampleProfileMap &ProfileMap) {
426   // The setting of SecFlagCompress should happen before markSectionStart.
427   if (Type == SecProfileSymbolList && ProfSymList && ProfSymList->toCompress())
428     setToCompressSection(SecProfileSymbolList);
429   if (Type == SecFuncMetadata && FunctionSamples::ProfileIsProbeBased)
430     addSectionFlag(SecFuncMetadata, SecFuncMetadataFlags::SecFlagIsProbeBased);
431   if (Type == SecFuncMetadata &&
432       (FunctionSamples::ProfileIsCS || FunctionSamples::ProfileIsPreInlined))
433     addSectionFlag(SecFuncMetadata, SecFuncMetadataFlags::SecFlagHasAttribute);
434   if (Type == SecProfSummary && FunctionSamples::ProfileIsCS)
435     addSectionFlag(SecProfSummary, SecProfSummaryFlags::SecFlagFullContext);
436   if (Type == SecProfSummary && FunctionSamples::ProfileIsPreInlined)
437     addSectionFlag(SecProfSummary, SecProfSummaryFlags::SecFlagIsPreInlined);
438   if (Type == SecProfSummary && FunctionSamples::ProfileIsFS)
439     addSectionFlag(SecProfSummary, SecProfSummaryFlags::SecFlagFSDiscriminator);
440 
441   uint64_t SectionStart = markSectionStart(Type, LayoutIdx);
442   switch (Type) {
443   case SecProfSummary:
444     computeSummary(ProfileMap);
445     if (auto EC = writeSummary())
446       return EC;
447     break;
448   case SecNameTable:
449     if (auto EC = writeNameTableSection(ProfileMap))
450       return EC;
451     break;
452   case SecCSNameTable:
453     if (auto EC = writeCSNameTableSection())
454       return EC;
455     break;
456   case SecLBRProfile:
457     SecLBRProfileStart = OutputStream->tell();
458     if (std::error_code EC = writeFuncProfiles(ProfileMap))
459       return EC;
460     break;
461   case SecFuncOffsetTable:
462     if (auto EC = writeFuncOffsetTable())
463       return EC;
464     break;
465   case SecFuncMetadata:
466     if (std::error_code EC = writeFuncMetadata(ProfileMap))
467       return EC;
468     break;
469   case SecProfileSymbolList:
470     if (auto EC = writeProfileSymbolListSection())
471       return EC;
472     break;
473   default:
474     if (auto EC = writeCustomSection(Type))
475       return EC;
476     break;
477   }
478   if (std::error_code EC = addNewSection(Type, LayoutIdx, SectionStart))
479     return EC;
480   return sampleprof_error::success;
481 }
482 
483 std::error_code SampleProfileWriterExtBinary::writeDefaultLayout(
484     const SampleProfileMap &ProfileMap) {
485   // The const indices passed to writeOneSection below are specifying the
486   // positions of the sections in SectionHdrLayout. Look at
487   // initSectionHdrLayout to find out where each section is located in
488   // SectionHdrLayout.
489   if (auto EC = writeOneSection(SecProfSummary, 0, ProfileMap))
490     return EC;
491   if (auto EC = writeOneSection(SecNameTable, 1, ProfileMap))
492     return EC;
493   if (auto EC = writeOneSection(SecCSNameTable, 2, ProfileMap))
494     return EC;
495   if (auto EC = writeOneSection(SecLBRProfile, 4, ProfileMap))
496     return EC;
497   if (auto EC = writeOneSection(SecProfileSymbolList, 5, ProfileMap))
498     return EC;
499   if (auto EC = writeOneSection(SecFuncOffsetTable, 3, ProfileMap))
500     return EC;
501   if (auto EC = writeOneSection(SecFuncMetadata, 6, ProfileMap))
502     return EC;
503   return sampleprof_error::success;
504 }
505 
506 static void splitProfileMapToTwo(const SampleProfileMap &ProfileMap,
507                                  SampleProfileMap &ContextProfileMap,
508                                  SampleProfileMap &NoContextProfileMap) {
509   for (const auto &I : ProfileMap) {
510     if (I.second.getCallsiteSamples().size())
511       ContextProfileMap.insert({I.first, I.second});
512     else
513       NoContextProfileMap.insert({I.first, I.second});
514   }
515 }
516 
517 std::error_code SampleProfileWriterExtBinary::writeCtxSplitLayout(
518     const SampleProfileMap &ProfileMap) {
519   SampleProfileMap ContextProfileMap, NoContextProfileMap;
520   splitProfileMapToTwo(ProfileMap, ContextProfileMap, NoContextProfileMap);
521 
522   if (auto EC = writeOneSection(SecProfSummary, 0, ProfileMap))
523     return EC;
524   if (auto EC = writeOneSection(SecNameTable, 1, ProfileMap))
525     return EC;
526   if (auto EC = writeOneSection(SecLBRProfile, 3, ContextProfileMap))
527     return EC;
528   if (auto EC = writeOneSection(SecFuncOffsetTable, 2, ContextProfileMap))
529     return EC;
530   // Mark the section to have no context. Note section flag needs to be set
531   // before writing the section.
532   addSectionFlag(5, SecCommonFlags::SecFlagFlat);
533   if (auto EC = writeOneSection(SecLBRProfile, 5, NoContextProfileMap))
534     return EC;
535   // Mark the section to have no context. Note section flag needs to be set
536   // before writing the section.
537   addSectionFlag(4, SecCommonFlags::SecFlagFlat);
538   if (auto EC = writeOneSection(SecFuncOffsetTable, 4, NoContextProfileMap))
539     return EC;
540   if (auto EC = writeOneSection(SecProfileSymbolList, 6, ProfileMap))
541     return EC;
542   if (auto EC = writeOneSection(SecFuncMetadata, 7, ProfileMap))
543     return EC;
544 
545   return sampleprof_error::success;
546 }
547 
548 std::error_code SampleProfileWriterExtBinary::writeSections(
549     const SampleProfileMap &ProfileMap) {
550   std::error_code EC;
551   if (SecLayout == DefaultLayout)
552     EC = writeDefaultLayout(ProfileMap);
553   else if (SecLayout == CtxSplitLayout)
554     EC = writeCtxSplitLayout(ProfileMap);
555   else
556     llvm_unreachable("Unsupported layout");
557   return EC;
558 }
559 
560 /// Write samples to a text file.
561 ///
562 /// Note: it may be tempting to implement this in terms of
563 /// FunctionSamples::print().  Please don't.  The dump functionality is intended
564 /// for debugging and has no specified form.
565 ///
566 /// The format used here is more structured and deliberate because
567 /// it needs to be parsed by the SampleProfileReaderText class.
568 std::error_code SampleProfileWriterText::writeSample(const FunctionSamples &S) {
569   auto &OS = *OutputStream;
570   if (FunctionSamples::ProfileIsCS)
571     OS << "[" << S.getContext().toString() << "]:" << S.getTotalSamples();
572   else
573     OS << S.getName() << ":" << S.getTotalSamples();
574 
575   if (Indent == 0)
576     OS << ":" << S.getHeadSamples();
577   OS << "\n";
578   LineCount++;
579 
580   SampleSorter<LineLocation, SampleRecord> SortedSamples(S.getBodySamples());
581   for (const auto &I : SortedSamples.get()) {
582     LineLocation Loc = I->first;
583     const SampleRecord &Sample = I->second;
584     OS.indent(Indent + 1);
585     if (Loc.Discriminator == 0)
586       OS << Loc.LineOffset << ": ";
587     else
588       OS << Loc.LineOffset << "." << Loc.Discriminator << ": ";
589 
590     OS << Sample.getSamples();
591 
592     for (const auto &J : Sample.getSortedCallTargets())
593       OS << " " << J.first << ":" << J.second;
594     OS << "\n";
595     LineCount++;
596   }
597 
598   SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
599       S.getCallsiteSamples());
600   Indent += 1;
601   for (const auto &I : SortedCallsiteSamples.get())
602     for (const auto &FS : I->second) {
603       LineLocation Loc = I->first;
604       const FunctionSamples &CalleeSamples = FS.second;
605       OS.indent(Indent);
606       if (Loc.Discriminator == 0)
607         OS << Loc.LineOffset << ": ";
608       else
609         OS << Loc.LineOffset << "." << Loc.Discriminator << ": ";
610       if (std::error_code EC = writeSample(CalleeSamples))
611         return EC;
612     }
613   Indent -= 1;
614 
615   if (FunctionSamples::ProfileIsProbeBased) {
616     OS.indent(Indent + 1);
617     OS << "!CFGChecksum: " << S.getFunctionHash() << "\n";
618     LineCount++;
619   }
620 
621   if (S.getContext().getAllAttributes()) {
622     OS.indent(Indent + 1);
623     OS << "!Attributes: " << S.getContext().getAllAttributes() << "\n";
624     LineCount++;
625   }
626 
627   return sampleprof_error::success;
628 }
629 
630 std::error_code
631 SampleProfileWriterBinary::writeContextIdx(const SampleContext &Context) {
632   assert(!Context.hasContext() && "cs profile is not supported");
633   return writeNameIdx(Context.getName());
634 }
635 
636 std::error_code SampleProfileWriterBinary::writeNameIdx(StringRef FName) {
637   auto &NTable = getNameTable();
638   const auto &Ret = NTable.find(FName);
639   if (Ret == NTable.end())
640     return sampleprof_error::truncated_name_table;
641   encodeULEB128(Ret->second, *OutputStream);
642   return sampleprof_error::success;
643 }
644 
645 void SampleProfileWriterBinary::addName(StringRef FName) {
646   auto &NTable = getNameTable();
647   NTable.insert(std::make_pair(FName, 0));
648 }
649 
650 void SampleProfileWriterBinary::addContext(const SampleContext &Context) {
651   addName(Context.getName());
652 }
653 
654 void SampleProfileWriterBinary::addNames(const FunctionSamples &S) {
655   // Add all the names in indirect call targets.
656   for (const auto &I : S.getBodySamples()) {
657     const SampleRecord &Sample = I.second;
658     for (const auto &J : Sample.getCallTargets())
659       addName(J.first());
660   }
661 
662   // Recursively add all the names for inlined callsites.
663   for (const auto &J : S.getCallsiteSamples())
664     for (const auto &FS : J.second) {
665       const FunctionSamples &CalleeSamples = FS.second;
666       addName(CalleeSamples.getName());
667       addNames(CalleeSamples);
668     }
669 }
670 
671 void SampleProfileWriterExtBinaryBase::addContext(
672     const SampleContext &Context) {
673   if (Context.hasContext()) {
674     for (auto &Callsite : Context.getContextFrames())
675       SampleProfileWriterBinary::addName(Callsite.FuncName);
676     CSNameTable.insert(std::make_pair(Context, 0));
677   } else {
678     SampleProfileWriterBinary::addName(Context.getName());
679   }
680 }
681 
682 void SampleProfileWriterBinary::stablizeNameTable(
683     MapVector<StringRef, uint32_t> &NameTable, std::set<StringRef> &V) {
684   // Sort the names to make NameTable deterministic.
685   for (const auto &I : NameTable)
686     V.insert(I.first);
687   int i = 0;
688   for (const StringRef &N : V)
689     NameTable[N] = i++;
690 }
691 
692 std::error_code SampleProfileWriterBinary::writeNameTable() {
693   auto &OS = *OutputStream;
694   std::set<StringRef> V;
695   stablizeNameTable(NameTable, V);
696 
697   // Write out the name table.
698   encodeULEB128(NameTable.size(), OS);
699   for (auto N : V) {
700     OS << N;
701     encodeULEB128(0, OS);
702   }
703   return sampleprof_error::success;
704 }
705 
706 std::error_code
707 SampleProfileWriterBinary::writeMagicIdent(SampleProfileFormat Format) {
708   auto &OS = *OutputStream;
709   // Write file magic identifier.
710   encodeULEB128(SPMagic(Format), OS);
711   encodeULEB128(SPVersion(), OS);
712   return sampleprof_error::success;
713 }
714 
715 std::error_code
716 SampleProfileWriterBinary::writeHeader(const SampleProfileMap &ProfileMap) {
717   // When calling write on a different profile map, existing names should be
718   // cleared.
719   NameTable.clear();
720 
721   writeMagicIdent(Format);
722 
723   computeSummary(ProfileMap);
724   if (auto EC = writeSummary())
725     return EC;
726 
727   // Generate the name table for all the functions referenced in the profile.
728   for (const auto &I : ProfileMap) {
729     assert(I.first == I.second.getContext() && "Inconsistent profile map");
730     addContext(I.first);
731     addNames(I.second);
732   }
733 
734   writeNameTable();
735   return sampleprof_error::success;
736 }
737 
738 void SampleProfileWriterExtBinaryBase::setToCompressAllSections() {
739   for (auto &Entry : SectionHdrLayout)
740     addSecFlag(Entry, SecCommonFlags::SecFlagCompress);
741 }
742 
743 void SampleProfileWriterExtBinaryBase::setToCompressSection(SecType Type) {
744   addSectionFlag(Type, SecCommonFlags::SecFlagCompress);
745 }
746 
747 void SampleProfileWriterExtBinaryBase::allocSecHdrTable() {
748   support::endian::Writer Writer(*OutputStream, support::little);
749 
750   Writer.write(static_cast<uint64_t>(SectionHdrLayout.size()));
751   SecHdrTableOffset = OutputStream->tell();
752   for (uint32_t i = 0; i < SectionHdrLayout.size(); i++) {
753     Writer.write(static_cast<uint64_t>(-1));
754     Writer.write(static_cast<uint64_t>(-1));
755     Writer.write(static_cast<uint64_t>(-1));
756     Writer.write(static_cast<uint64_t>(-1));
757   }
758 }
759 
760 std::error_code SampleProfileWriterExtBinaryBase::writeSecHdrTable() {
761   assert(SecHdrTable.size() == SectionHdrLayout.size() &&
762          "SecHdrTable entries doesn't match SectionHdrLayout");
763   SmallVector<uint32_t, 16> IndexMap(SecHdrTable.size(), -1);
764   for (uint32_t TableIdx = 0; TableIdx < SecHdrTable.size(); TableIdx++) {
765     IndexMap[SecHdrTable[TableIdx].LayoutIndex] = TableIdx;
766   }
767 
768   // Write the section header table in the order specified in
769   // SectionHdrLayout. SectionHdrLayout specifies the sections
770   // order in which profile reader expect to read, so the section
771   // header table should be written in the order in SectionHdrLayout.
772   // Note that the section order in SecHdrTable may be different
773   // from the order in SectionHdrLayout, for example, SecFuncOffsetTable
774   // needs to be computed after SecLBRProfile (the order in SecHdrTable),
775   // but it needs to be read before SecLBRProfile (the order in
776   // SectionHdrLayout). So we use IndexMap above to switch the order.
777   support::endian::SeekableWriter Writer(
778       static_cast<raw_pwrite_stream &>(*OutputStream), support::little);
779   for (uint32_t LayoutIdx = 0; LayoutIdx < SectionHdrLayout.size();
780        LayoutIdx++) {
781     assert(IndexMap[LayoutIdx] < SecHdrTable.size() &&
782            "Incorrect LayoutIdx in SecHdrTable");
783     auto Entry = SecHdrTable[IndexMap[LayoutIdx]];
784     Writer.pwrite(static_cast<uint64_t>(Entry.Type),
785                   SecHdrTableOffset + 4 * LayoutIdx * sizeof(uint64_t));
786     Writer.pwrite(static_cast<uint64_t>(Entry.Flags),
787                   SecHdrTableOffset + (4 * LayoutIdx + 1) * sizeof(uint64_t));
788     Writer.pwrite(static_cast<uint64_t>(Entry.Offset),
789                   SecHdrTableOffset + (4 * LayoutIdx + 2) * sizeof(uint64_t));
790     Writer.pwrite(static_cast<uint64_t>(Entry.Size),
791                   SecHdrTableOffset + (4 * LayoutIdx + 3) * sizeof(uint64_t));
792   }
793 
794   return sampleprof_error::success;
795 }
796 
797 std::error_code SampleProfileWriterExtBinaryBase::writeHeader(
798     const SampleProfileMap &ProfileMap) {
799   auto &OS = *OutputStream;
800   FileStart = OS.tell();
801   writeMagicIdent(Format);
802 
803   allocSecHdrTable();
804   return sampleprof_error::success;
805 }
806 
807 std::error_code SampleProfileWriterBinary::writeSummary() {
808   auto &OS = *OutputStream;
809   encodeULEB128(Summary->getTotalCount(), OS);
810   encodeULEB128(Summary->getMaxCount(), OS);
811   encodeULEB128(Summary->getMaxFunctionCount(), OS);
812   encodeULEB128(Summary->getNumCounts(), OS);
813   encodeULEB128(Summary->getNumFunctions(), OS);
814   const std::vector<ProfileSummaryEntry> &Entries =
815       Summary->getDetailedSummary();
816   encodeULEB128(Entries.size(), OS);
817   for (auto Entry : Entries) {
818     encodeULEB128(Entry.Cutoff, OS);
819     encodeULEB128(Entry.MinCount, OS);
820     encodeULEB128(Entry.NumCounts, OS);
821   }
822   return sampleprof_error::success;
823 }
824 std::error_code SampleProfileWriterBinary::writeBody(const FunctionSamples &S) {
825   auto &OS = *OutputStream;
826   if (std::error_code EC = writeContextIdx(S.getContext()))
827     return EC;
828 
829   encodeULEB128(S.getTotalSamples(), OS);
830 
831   // Emit all the body samples.
832   encodeULEB128(S.getBodySamples().size(), OS);
833   for (const auto &I : S.getBodySamples()) {
834     LineLocation Loc = I.first;
835     const SampleRecord &Sample = I.second;
836     encodeULEB128(Loc.LineOffset, OS);
837     encodeULEB128(Loc.Discriminator, OS);
838     encodeULEB128(Sample.getSamples(), OS);
839     encodeULEB128(Sample.getCallTargets().size(), OS);
840     for (const auto &J : Sample.getSortedCallTargets()) {
841       StringRef Callee = J.first;
842       uint64_t CalleeSamples = J.second;
843       if (std::error_code EC = writeNameIdx(Callee))
844         return EC;
845       encodeULEB128(CalleeSamples, OS);
846     }
847   }
848 
849   // Recursively emit all the callsite samples.
850   uint64_t NumCallsites = 0;
851   for (const auto &J : S.getCallsiteSamples())
852     NumCallsites += J.second.size();
853   encodeULEB128(NumCallsites, OS);
854   for (const auto &J : S.getCallsiteSamples())
855     for (const auto &FS : J.second) {
856       LineLocation Loc = J.first;
857       const FunctionSamples &CalleeSamples = FS.second;
858       encodeULEB128(Loc.LineOffset, OS);
859       encodeULEB128(Loc.Discriminator, OS);
860       if (std::error_code EC = writeBody(CalleeSamples))
861         return EC;
862     }
863 
864   return sampleprof_error::success;
865 }
866 
867 /// Write samples of a top-level function to a binary file.
868 ///
869 /// \returns true if the samples were written successfully, false otherwise.
870 std::error_code
871 SampleProfileWriterBinary::writeSample(const FunctionSamples &S) {
872   encodeULEB128(S.getHeadSamples(), *OutputStream);
873   return writeBody(S);
874 }
875 
876 /// Create a sample profile file writer based on the specified format.
877 ///
878 /// \param Filename The file to create.
879 ///
880 /// \param Format Encoding format for the profile file.
881 ///
882 /// \returns an error code indicating the status of the created writer.
883 ErrorOr<std::unique_ptr<SampleProfileWriter>>
884 SampleProfileWriter::create(StringRef Filename, SampleProfileFormat Format) {
885   std::error_code EC;
886   std::unique_ptr<raw_ostream> OS;
887   if (Format == SPF_Binary || Format == SPF_Ext_Binary)
888     OS.reset(new raw_fd_ostream(Filename, EC, sys::fs::OF_None));
889   else
890     OS.reset(new raw_fd_ostream(Filename, EC, sys::fs::OF_TextWithCRLF));
891   if (EC)
892     return EC;
893 
894   return create(OS, Format);
895 }
896 
897 /// Create a sample profile stream writer based on the specified format.
898 ///
899 /// \param OS The output stream to store the profile data to.
900 ///
901 /// \param Format Encoding format for the profile file.
902 ///
903 /// \returns an error code indicating the status of the created writer.
904 ErrorOr<std::unique_ptr<SampleProfileWriter>>
905 SampleProfileWriter::create(std::unique_ptr<raw_ostream> &OS,
906                             SampleProfileFormat Format) {
907   std::error_code EC;
908   std::unique_ptr<SampleProfileWriter> Writer;
909 
910   // Currently only Text and Extended Binary format are supported for CSSPGO.
911   if ((FunctionSamples::ProfileIsCS || FunctionSamples::ProfileIsProbeBased) &&
912       Format == SPF_Binary)
913     return sampleprof_error::unsupported_writing_format;
914 
915   if (Format == SPF_Binary)
916     Writer.reset(new SampleProfileWriterRawBinary(OS));
917   else if (Format == SPF_Ext_Binary)
918     Writer.reset(new SampleProfileWriterExtBinary(OS));
919   else if (Format == SPF_Text)
920     Writer.reset(new SampleProfileWriterText(OS));
921   else if (Format == SPF_GCC)
922     EC = sampleprof_error::unsupported_writing_format;
923   else
924     EC = sampleprof_error::unrecognized_format;
925 
926   if (EC)
927     return EC;
928 
929   Writer->Format = Format;
930   return std::move(Writer);
931 }
932 
933 void SampleProfileWriter::computeSummary(const SampleProfileMap &ProfileMap) {
934   SampleProfileSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs);
935   Summary = Builder.computeSummaryForProfiles(ProfileMap);
936 }
937