1# BOLT Address Translation (BAT) 2# Purpose 3A regular profile collection for BOLT involves collecting samples from 4unoptimized binary. BOLT Address Translation allows collecting profile 5from BOLT-optimized binary and using it for optimizing the input (pre-BOLT) 6binary. 7 8# Overview 9BOLT Address Translation is an extra section (`.note.bolt_bat`) inserted by BOLT 10into the output binary containing translation tables and split functions linkage 11information. This information enables mapping the profile back from optimized 12binary onto the original binary. 13 14# Usage 15`--enable-bat` flag controls the generation of BAT section. Sampled profile 16needs to be passed along with the optimized binary containing BAT section to 17`perf2bolt` which reads BAT section and produces profile for the original 18binary. 19 20# Internals 21## Section contents 22The section is organized as follows: 23- Hot functions table 24 - Address translation tables 25- Cold functions table 26 27## Construction and parsing 28BAT section is created from `BoltAddressTranslation` class which captures 29address translation information provided by BOLT linker. It is then encoded as a 30note section in the output binary. 31 32During profile conversion when BAT-enabled binary is passed to perf2bolt, 33`BoltAddressTranslation` class is populated from BAT section. The class is then 34queried by `DataAggregator` during sample processing to reconstruct addresses/ 35offsets in the input binary. 36 37## Encoding format 38The encoding is specified in 39[BoltAddressTranslation.h](/bolt/include/bolt/Profile/BoltAddressTranslation.h) 40and [BoltAddressTranslation.cpp](/bolt/lib/Profile/BoltAddressTranslation.cpp). 41 42### Layout 43The general layout is as follows: 44``` 45Hot functions table 46Cold functions table 47 48Functions 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 63Hot and cold functions tables share the encoding except differences marked below. 64Header: 65| Entry | Encoding | Description | 66| ------ | ----- | ----------- | 67| `NumFuncs` | ULEB128 | Number of functions in the functions table | 68 69The header is followed by Functions table with `NumFuncs` entries. 70Output binary addresses are delta encoded, meaning that only the difference with 71the last previous output address is stored. Addresses implicitly start at zero. 72Output addresses are continuous through function start addresses and function 73internal offsets, and between hot and cold fragments, to better spread deltas 74and save space. 75 76Hot 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 89Function header is followed by *Address Translation Table* with `NumEntries` 90total entries, and *Secondary Entry Points* table with `NumSecEntryPoints` 91entries (hot functions only). 92 93### Address translation table 94Delta encoding means that only the difference with the previous corresponding 95entry 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 103The table omits the first `EqualElems` input offsets where the input offset 104equals 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 111case, `BRANCHENTRY` bits are encoded separately in a `BranchEntries` bitvector. 112 113Deleted basic blocks are emitted as having `OutputOffset` equal to the size of 114the function. They don't affect address translation and only participate in 115input basic block mapping. 116 117### Secondary Entry Points table 118The table is emitted for hot fragments only. It contains `NumSecEntryPoints` 119offsets denoting secondary entry points, delta encoded, implicitly starting at zero. 120| Entry | Encoding | Description | 121| ----- | -------- | ----------- | 122| `SecEntryPoint` | Delta, ULEB128 | Secondary entry point offset | 123