1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
|
//===-- ProfiledBinary.h - Binary decoder -----------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
#define LLVM_TOOLS_LLVM_PROFGEN_PROFILEDBINARY_H
#include "CallContext.h"
#include "ErrorHandling.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/DebugInfo/DWARF/DWARFContext.h"
#include "llvm/DebugInfo/Symbolize/Symbolize.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/MC/MCContext.h"
#include "llvm/MC/MCDisassembler/MCDisassembler.h"
#include "llvm/MC/MCInst.h"
#include "llvm/MC/MCInstPrinter.h"
#include "llvm/MC/MCInstrAnalysis.h"
#include "llvm/MC/MCInstrInfo.h"
#include "llvm/MC/MCObjectFileInfo.h"
#include "llvm/MC/MCPseudoProbe.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/MC/MCSubtargetInfo.h"
#include "llvm/MC/MCTargetOptions.h"
#include "llvm/Object/ELFObjectFile.h"
#include "llvm/ProfileData/SampleProf.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Path.h"
#include "llvm/Transforms/IPO/SampleContextTracker.h"
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
extern cl::opt<bool> EnableCSPreInliner;
extern cl::opt<bool> UseContextCostForPreInliner;
using namespace llvm;
using namespace sampleprof;
using namespace llvm::object;
namespace llvm {
namespace sampleprof {
class ProfiledBinary;
struct InstructionPointer {
const ProfiledBinary *Binary;
union {
// Offset of the executable segment of the binary.
uint64_t Offset = 0;
// Also used as address in unwinder
uint64_t Address;
};
// Index to the sorted code address array of the binary.
uint64_t Index = 0;
InstructionPointer(const ProfiledBinary *Binary, uint64_t Address,
bool RoundToNext = false);
bool advance();
bool backward();
void update(uint64_t Addr);
};
// The special frame addresses.
enum SpecialFrameAddr {
// Dummy root of frame trie.
DummyRoot = 0,
// Represent all the addresses outside of current binary.
// This's also used to indicate the call stack should be truncated since this
// isn't a real call context the compiler will see.
ExternalAddr = 1,
};
using RangesTy = std::vector<std::pair<uint64_t, uint64_t>>;
struct BinaryFunction {
StringRef FuncName;
// End of range is an exclusive bound.
RangesTy Ranges;
uint64_t getFuncSize() {
uint64_t Sum = 0;
for (auto &R : Ranges) {
Sum += R.second - R.first;
}
return Sum;
}
};
// Info about function range. A function can be split into multiple
// non-continuous ranges, each range corresponds to one FuncRange.
struct FuncRange {
uint64_t StartOffset;
// EndOffset is an exclusive bound.
uint64_t EndOffset;
// Function the range belongs to
BinaryFunction *Func;
// Whether the start offset is the real entry of the function.
bool IsFuncEntry = false;
StringRef getFuncName() { return Func->FuncName; }
};
// PrologEpilog offset tracker, used to filter out broken stack samples
// Currently we use a heuristic size (two) to infer prolog and epilog
// based on the start address and return address. In the future,
// we will switch to Dwarf CFI based tracker
struct PrologEpilogTracker {
// A set of prolog and epilog offsets. Used by virtual unwinding.
std::unordered_set<uint64_t> PrologEpilogSet;
ProfiledBinary *Binary;
PrologEpilogTracker(ProfiledBinary *Bin) : Binary(Bin){};
// Take the two addresses from the start of function as prolog
void inferPrologOffsets(std::map<uint64_t, FuncRange> &FuncStartOffsetMap) {
for (auto I : FuncStartOffsetMap) {
PrologEpilogSet.insert(I.first);
InstructionPointer IP(Binary, I.first);
if (!IP.advance())
break;
PrologEpilogSet.insert(IP.Offset);
}
}
// Take the last two addresses before the return address as epilog
void inferEpilogOffsets(std::unordered_set<uint64_t> &RetAddrs) {
for (auto Addr : RetAddrs) {
PrologEpilogSet.insert(Addr);
InstructionPointer IP(Binary, Addr);
if (!IP.backward())
break;
PrologEpilogSet.insert(IP.Offset);
}
}
};
// Track function byte size under different context (outlined version as well as
// various inlined versions). It also provides query support to get function
// size with the best matching context, which is used to help pre-inliner use
// accurate post-optimization size to make decisions.
// TODO: If an inlinee is completely optimized away, ideally we should have zero
// for its context size, currently we would misss such context since it doesn't
// have instructions. To fix this, we need to mark all inlinee with entry probe
// but without instructions as having zero size.
class BinarySizeContextTracker {
public:
// Add instruction with given size to a context
void addInstructionForContext(const SampleContextFrameVector &Context,
uint32_t InstrSize);
// Get function size with a specific context. When there's no exact match
// for the given context, try to retrieve the size of that function from
// closest matching context.
uint32_t getFuncSizeForContext(const SampleContext &Context);
// For inlinees that are full optimized away, we can establish zero size using
// their remaining probes.
void trackInlineesOptimizedAway(MCPseudoProbeDecoder &ProbeDecoder);
void dump() { RootContext.dumpTree(); }
private:
using ProbeFrameStack = SmallVector<std::pair<StringRef, uint32_t>>;
void trackInlineesOptimizedAway(MCPseudoProbeDecoder &ProbeDecoder,
MCDecodedPseudoProbeInlineTree &ProbeNode,
ProbeFrameStack &Context);
// Root node for context trie tree, node that this is a reverse context trie
// with callee as parent and caller as child. This way we can traverse from
// root to find the best/longest matching context if an exact match does not
// exist. It gives us the best possible estimate for function's post-inline,
// post-optimization byte size.
ContextTrieNode RootContext;
};
using OffsetRange = std::pair<uint64_t, uint64_t>;
class ProfiledBinary {
// Absolute path of the executable binary.
std::string Path;
// Path of the debug info binary.
std::string DebugBinaryPath;
// Path of symbolizer path which should be pointed to binary with debug info.
StringRef SymbolizerPath;
// The target triple.
Triple TheTriple;
// The runtime base address that the first executable segment is loaded at.
uint64_t BaseAddress = 0;
// The runtime base address that the first loadabe segment is loaded at.
uint64_t FirstLoadableAddress = 0;
// The preferred load address of each executable segment.
std::vector<uint64_t> PreferredTextSegmentAddresses;
// The file offset of each executable segment.
std::vector<uint64_t> TextSegmentOffsets;
// Mutiple MC component info
std::unique_ptr<const MCRegisterInfo> MRI;
std::unique_ptr<const MCAsmInfo> AsmInfo;
std::unique_ptr<const MCSubtargetInfo> STI;
std::unique_ptr<const MCInstrInfo> MII;
std::unique_ptr<MCDisassembler> DisAsm;
std::unique_ptr<const MCInstrAnalysis> MIA;
std::unique_ptr<MCInstPrinter> IPrinter;
// A list of text sections sorted by start RVA and size. Used to check
// if a given RVA is a valid code address.
std::set<std::pair<uint64_t, uint64_t>> TextSections;
// A map of mapping function name to BinaryFunction info.
std::unordered_map<std::string, BinaryFunction> BinaryFunctions;
// An ordered map of mapping function's start offset to function range
// relevant info. Currently to determine if the offset of ELF is the start of
// a real function, we leverage the function range info from DWARF.
std::map<uint64_t, FuncRange> StartOffset2FuncRangeMap;
// Offset to context location map. Used to expand the context.
std::unordered_map<uint64_t, SampleContextFrameVector> Offset2LocStackMap;
// Offset to instruction size map. Also used for quick offset lookup.
std::unordered_map<uint64_t, uint64_t> Offset2InstSizeMap;
// An array of offsets of all instructions sorted in increasing order. The
// sorting is needed to fast advance to the next forward/backward instruction.
std::vector<uint64_t> CodeAddrOffsets;
// A set of call instruction offsets. Used by virtual unwinding.
std::unordered_set<uint64_t> CallOffsets;
// A set of return instruction offsets. Used by virtual unwinding.
std::unordered_set<uint64_t> RetOffsets;
// A set of branch instruction offsets.
std::unordered_set<uint64_t> BranchOffsets;
// Estimate and track function prolog and epilog ranges.
PrologEpilogTracker ProEpilogTracker;
// Track function sizes under different context
BinarySizeContextTracker FuncSizeTracker;
// The symbolizer used to get inline context for an instruction.
std::unique_ptr<symbolize::LLVMSymbolizer> Symbolizer;
// String table owning function name strings created from the symbolizer.
std::unordered_set<std::string> NameStrings;
// A collection of functions to print disassembly for.
StringSet<> DisassembleFunctionSet;
// Pseudo probe decoder
MCPseudoProbeDecoder ProbeDecoder;
bool UsePseudoProbes = false;
bool UseFSDiscriminator = false;
// Whether we need to symbolize all instructions to get function context size.
bool TrackFuncContextSize = false;
// Indicate if the base loading address is parsed from the mmap event or uses
// the preferred address
bool IsLoadedByMMap = false;
// Use to avoid redundant warning.
bool MissingMMapWarned = false;
void setPreferredTextSegmentAddresses(const ELFObjectFileBase *O);
template <class ELFT>
void setPreferredTextSegmentAddresses(const ELFFile<ELFT> &Obj, StringRef FileName);
void decodePseudoProbe(const ELFObjectFileBase *Obj);
void
checkUseFSDiscriminator(const ELFObjectFileBase *Obj,
std::map<SectionRef, SectionSymbolsTy> &AllSymbols);
// Set up disassembler and related components.
void setUpDisassembler(const ELFObjectFileBase *Obj);
void setupSymbolizer();
// Load debug info of subprograms from DWARF section.
void loadSymbolsFromDWARF(ObjectFile &Obj);
// A function may be spilt into multiple non-continuous address ranges. We use
// this to set whether start offset of a function is the real entry of the
// function and also set false to the non-function label.
void setIsFuncEntry(uint64_t Offset, StringRef RangeSymName);
// Warn if no entry range exists in the function.
void warnNoFuncEntry();
/// Dissassemble the text section and build various address maps.
void disassemble(const ELFObjectFileBase *O);
/// Helper function to dissassemble the symbol and extract info for unwinding
bool dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
SectionSymbolsTy &Symbols, const SectionRef &Section);
/// Symbolize a given instruction pointer and return a full call context.
SampleContextFrameVector symbolize(const InstructionPointer &IP,
bool UseCanonicalFnName = false,
bool UseProbeDiscriminator = false);
/// Decode the interesting parts of the binary and build internal data
/// structures. On high level, the parts of interest are:
/// 1. Text sections, including the main code section and the PLT
/// entries that will be used to handle cross-module call transitions.
/// 2. The .debug_line section, used by Dwarf-based profile generation.
/// 3. Pseudo probe related sections, used by probe-based profile
/// generation.
void load();
public:
ProfiledBinary(const StringRef ExeBinPath, const StringRef DebugBinPath)
: Path(ExeBinPath), DebugBinaryPath(DebugBinPath), ProEpilogTracker(this),
TrackFuncContextSize(EnableCSPreInliner &&
UseContextCostForPreInliner) {
// Point to executable binary if debug info binary is not specified.
SymbolizerPath = DebugBinPath.empty() ? ExeBinPath : DebugBinPath;
setupSymbolizer();
load();
}
uint64_t virtualAddrToOffset(uint64_t VirtualAddress) const {
return VirtualAddress - BaseAddress;
}
uint64_t offsetToVirtualAddr(uint64_t Offset) const {
return Offset + BaseAddress;
}
StringRef getPath() const { return Path; }
StringRef getName() const { return llvm::sys::path::filename(Path); }
uint64_t getBaseAddress() const { return BaseAddress; }
void setBaseAddress(uint64_t Address) { BaseAddress = Address; }
// Return the preferred load address for the first executable segment.
uint64_t getPreferredBaseAddress() const { return PreferredTextSegmentAddresses[0]; }
// Return the preferred load address for the first loadable segment.
uint64_t getFirstLoadableAddress() const { return FirstLoadableAddress; }
// Return the file offset for the first executable segment.
uint64_t getTextSegmentOffset() const { return TextSegmentOffsets[0]; }
const std::vector<uint64_t> &getPreferredTextSegmentAddresses() const {
return PreferredTextSegmentAddresses;
}
const std::vector<uint64_t> &getTextSegmentOffsets() const {
return TextSegmentOffsets;
}
uint64_t getInstSize(uint64_t Offset) const {
auto I = Offset2InstSizeMap.find(Offset);
if (I == Offset2InstSizeMap.end())
return 0;
return I->second;
}
bool offsetIsCode(uint64_t Offset) const {
return Offset2InstSizeMap.find(Offset) != Offset2InstSizeMap.end();
}
bool addressIsCode(uint64_t Address) const {
uint64_t Offset = virtualAddrToOffset(Address);
return offsetIsCode(Offset);
}
bool addressIsCall(uint64_t Address) const {
uint64_t Offset = virtualAddrToOffset(Address);
return CallOffsets.count(Offset);
}
bool addressIsReturn(uint64_t Address) const {
uint64_t Offset = virtualAddrToOffset(Address);
return RetOffsets.count(Offset);
}
bool addressInPrologEpilog(uint64_t Address) const {
uint64_t Offset = virtualAddrToOffset(Address);
return ProEpilogTracker.PrologEpilogSet.count(Offset);
}
bool offsetIsTransfer(uint64_t Offset) {
return BranchOffsets.count(Offset) || RetOffsets.count(Offset) ||
CallOffsets.count(Offset);
}
uint64_t getAddressforIndex(uint64_t Index) const {
return offsetToVirtualAddr(CodeAddrOffsets[Index]);
}
size_t getCodeOffsetsSize() const { return CodeAddrOffsets.size(); }
bool usePseudoProbes() const { return UsePseudoProbes; }
bool useFSDiscriminator() const { return UseFSDiscriminator; }
// Get the index in CodeAddrOffsets for the address
// As we might get an address which is not the code
// here it would round to the next valid code address by
// using lower bound operation
uint32_t getIndexForOffset(uint64_t Offset) const {
auto Low = llvm::lower_bound(CodeAddrOffsets, Offset);
return Low - CodeAddrOffsets.begin();
}
uint32_t getIndexForAddr(uint64_t Address) const {
uint64_t Offset = virtualAddrToOffset(Address);
return getIndexForOffset(Offset);
}
uint64_t getCallAddrFromFrameAddr(uint64_t FrameAddr) const {
if (FrameAddr == ExternalAddr)
return ExternalAddr;
auto I = getIndexForAddr(FrameAddr);
FrameAddr = I ? getAddressforIndex(I - 1) : 0;
if (FrameAddr && addressIsCall(FrameAddr))
return FrameAddr;
return 0;
}
FuncRange *findFuncRangeForStartOffset(uint64_t Offset) {
auto I = StartOffset2FuncRangeMap.find(Offset);
if (I == StartOffset2FuncRangeMap.end())
return nullptr;
return &I->second;
}
// Binary search the function range which includes the input offset.
FuncRange *findFuncRangeForOffset(uint64_t Offset) {
auto I = StartOffset2FuncRangeMap.upper_bound(Offset);
if (I == StartOffset2FuncRangeMap.begin())
return nullptr;
I--;
if (Offset >= I->second.EndOffset)
return nullptr;
return &I->second;
}
// Get all ranges of one function.
RangesTy getRangesForOffset(uint64_t Offset) {
auto *FRange = findFuncRangeForOffset(Offset);
// Ignore the range which falls into plt section or system lib.
if (!FRange)
return RangesTy();
return FRange->Func->Ranges;
}
const std::unordered_map<std::string, BinaryFunction> &
getAllBinaryFunctions() {
return BinaryFunctions;
}
BinaryFunction *getBinaryFunction(StringRef FName) {
auto I = BinaryFunctions.find(FName.str());
if (I == BinaryFunctions.end())
return nullptr;
return &I->second;
}
uint32_t getFuncSizeForContext(SampleContext &Context) {
return FuncSizeTracker.getFuncSizeForContext(Context);
}
// Load the symbols from debug table and populate into symbol list.
void populateSymbolListFromDWARF(ProfileSymbolList &SymbolList);
const SampleContextFrameVector &
getFrameLocationStack(uint64_t Offset, bool UseProbeDiscriminator = false) {
auto I = Offset2LocStackMap.emplace(Offset, SampleContextFrameVector());
if (I.second) {
InstructionPointer IP(this, Offset);
I.first->second = symbolize(IP, true, UseProbeDiscriminator);
}
return I.first->second;
}
Optional<SampleContextFrame> getInlineLeafFrameLoc(uint64_t Offset) {
const auto &Stack = getFrameLocationStack(Offset);
if (Stack.empty())
return {};
return Stack.back();
}
// Compare two addresses' inline context
bool inlineContextEqual(uint64_t Add1, uint64_t Add2);
// Get the full context of the current stack with inline context filled in.
// It will search the disassembling info stored in Offset2LocStackMap. This is
// used as the key of function sample map
SampleContextFrameVector
getExpandedContext(const SmallVectorImpl<uint64_t> &Stack,
bool &WasLeafInlined);
// Go through instructions among the given range and record its size for the
// inline context.
void computeInlinedContextSizeForRange(uint64_t StartOffset,
uint64_t EndOffset);
const MCDecodedPseudoProbe *getCallProbeForAddr(uint64_t Address) const {
return ProbeDecoder.getCallProbeForAddr(Address);
}
void getInlineContextForProbe(const MCDecodedPseudoProbe *Probe,
SampleContextFrameVector &InlineContextStack,
bool IncludeLeaf = false) const {
SmallVector<MCPseduoProbeFrameLocation, 16> ProbeInlineContext;
ProbeDecoder.getInlineContextForProbe(Probe, ProbeInlineContext,
IncludeLeaf);
for (uint32_t I = 0; I < ProbeInlineContext.size(); I++) {
auto &Callsite = ProbeInlineContext[I];
// Clear the current context for an unknown probe.
if (Callsite.second == 0 && I != ProbeInlineContext.size() - 1) {
InlineContextStack.clear();
continue;
}
InlineContextStack.emplace_back(Callsite.first,
LineLocation(Callsite.second, 0));
}
}
const AddressProbesMap &getAddress2ProbesMap() const {
return ProbeDecoder.getAddress2ProbesMap();
}
const MCPseudoProbeFuncDesc *getFuncDescForGUID(uint64_t GUID) {
return ProbeDecoder.getFuncDescForGUID(GUID);
}
const MCPseudoProbeFuncDesc *
getInlinerDescForProbe(const MCDecodedPseudoProbe *Probe) {
return ProbeDecoder.getInlinerDescForProbe(Probe);
}
bool getTrackFuncContextSize() { return TrackFuncContextSize; }
bool getIsLoadedByMMap() { return IsLoadedByMMap; }
void setIsLoadedByMMap(bool Value) { IsLoadedByMMap = Value; }
bool getMissingMMapWarned() { return MissingMMapWarned; }
void setMissingMMapWarned(bool Value) { MissingMMapWarned = Value; }
};
} // end namespace sampleprof
} // end namespace llvm
#endif
|