bolt/docs/BAT.md

   1 # BOLT Address Translation (BAT)
   2 # Purpose
   3 A regular profile collection for BOLT involves collecting samples from
   4 unoptimized binary. BOLT Address Translation allows collecting profile
   5 from BOLT-optimized binary and using it for optimizing the input (pre-BOLT)
   6 binary.
   7
   8 # Overview
   9 BOLT Address Translation is an extra section (`.note.bolt_bat`) inserted by BOLT
  10 into the output binary containing translation tables and split functions linkage
  11 information. This information enables mapping the profile back from optimized
  12 binary onto the original binary.
  13
  14 # Usage
  15 `--enable-bat` flag controls the generation of BAT section. Sampled profile
  16 needs to be passed along with the optimized binary containing BAT section to
  17 `perf2bolt` which reads BAT section and produces profile for the original
  18 binary.
  19
  20 # Internals
  21 ## Section contents
  22 The section is organized as follows:
  23 - Hot functions table
  24   - Address translation tables
  25 - Cold functions table
  26
  27 ## Construction and parsing
  28 BAT section is created from `BoltAddressTranslation` class which captures
  29 address translation information provided by BOLT linker. It is then encoded as a
  30 note section in the output binary.
  31
  32 During profile conversion when BAT-enabled binary is passed to perf2bolt,
  33 `BoltAddressTranslation` class is populated from BAT section. The class is then
  34 queried by `DataAggregator` during sample processing to reconstruct addresses/
  35 offsets in the input binary.
  36
  37 ## Encoding format
  38 The encoding is specified in
  39 [BoltAddressTranslation.h](/bolt/include/bolt/Profile/BoltAddressTranslation.h)
  40 and [BoltAddressTranslation.cpp](/bolt/lib/Profile/BoltAddressTranslation.cpp).
  41
  42 ### Layout
  43 The general layout is as follows:
  44 ```
  45 Hot functions table
  46 Cold functions table
  47
  48 Functions table:
  49 |------------------|
  50 |  Function entry  |
  51 |                  |
  52 |     Address      |
  53 |   translation    |
  54 |      table       |
  55 |                  |
  56 | Secondary entry  |
  57 |      points      |
  58 |------------------|
  59
  60 ```
  61
  62 ### Functions table
  63 Hot and cold functions tables share the encoding except differences marked below.
  64 Header:
  65 | Entry  | Encoding | Description |
  66 | ------ | ----- | ----------- |
  67 | `NumFuncs` | ULEB128 | Number of functions in the functions table |
  68
  69 The header is followed by Functions table with `NumFuncs` entries.
  70 Output binary addresses are delta encoded, meaning that only the difference with
  71 the last previous output address is stored. Addresses implicitly start at zero.
  72 Output addresses are continuous through function start addresses and function
  73 internal offsets, and between hot and cold fragments, to better spread deltas
  74 and save space.
  75
  76 Hot indices are delta encoded, implicitly starting at zero.
  77 | Entry  | Encoding | Description | Hot/Cold |
  78 | ------ | ------| ----------- | ------ |
  79 | `Address` | Continuous, Delta, ULEB128 | Function address in the output binary | Both |
  80 | `HotIndex` | Delta, ULEB128 | Index of corresponding hot function in hot functions table | Cold |
  81 | `FuncHash` | 8b | Function hash for input function | Hot |
  82 | `NumBlocks` | ULEB128 | Number of basic blocks in the original function | Hot |
  83 | `NumSecEntryPoints` | ULEB128 | Number of secondary entry points in the original function | Hot |
  84 | `ColdInputSkew` | ULEB128 | Skew to apply to all input offsets | Cold |
  85 | `NumEntries` | ULEB128 | Number of address translation entries for a function | Both |
  86 | `EqualElems` | ULEB128 | Number of equal offsets in the beginning of a function | Both |
  87 | `BranchEntries` | Bitmask, `alignTo(EqualElems, 8)` bits | If `EqualElems` is non-zero, bitmask denoting entries with `BRANCHENTRY` bit | Both |
  88
  89 Function header is followed by *Address Translation Table* with `NumEntries`
  90 total entries, and *Secondary Entry Points* table with `NumSecEntryPoints`
  91 entries (hot functions only).
  92
  93 ### Address translation table
  94 Delta encoding means that only the difference with the previous corresponding
  95 entry is encoded. Input offsets implicitly start at zero.
  96 | Entry  | Encoding | Description | Branch/BB |
  97 | ------ | ------| ----------- | ------ |
  98 | `OutputOffset` | Continuous, Delta, ULEB128 | Function offset in output binary | Both |
  99 | `InputOffset` | Optional, Delta, SLEB128 | Function offset in input binary with `BRANCHENTRY` LSB bit | Both |
 100 | `BBHash` | Optional, 8b | Basic block hash in input binary | BB |
 101 | `BBIdx`  | Optional, Delta, ULEB128 | Basic block index in input binary | BB |
 102
 103 The table omits the first `EqualElems` input offsets where the input offset
 104 equals output offset.
 105
 106 `BRANCHENTRY` bit denotes whether a given offset pair is a control flow source
 107 (branch or call instruction). If not set, it signifies a control flow target
 108 (basic block offset).
 109
 110 `InputAddr` is omitted for equal offsets in input and output function. In this
 111 case, `BRANCHENTRY` bits are encoded separately in a `BranchEntries` bitvector.
 112
 113 Deleted basic blocks are emitted as having `OutputOffset` equal to the size of
 114 the function. They don't affect address translation and only participate in
 115 input basic block mapping.
 116
 117 ### Secondary Entry Points table
 118 The table is emitted for hot fragments only. It contains `NumSecEntryPoints`
 119 offsets denoting secondary entry points, delta encoded, implicitly starting at zero.
 120 | Entry | Encoding | Description |
 121 | ----- | -------- | ----------- |
 122 | `SecEntryPoint` | Delta, ULEB128 | Secondary entry point offset |