1//===----------------------------------------------------------------------===//
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/// \file
10/// This file implements shared utilities for basic-block address maps.
11///
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Object/BBAddrMap.h"
15#include "llvm/Object/Error.h"
16
17using namespace llvm;
18using namespace object;
19
20namespace {
21
22// Helper to extract and decode the next ULEB128 value as an unsigned integer
23// type. Returns zero and sets ULEBSizeErr if the ULEB128 value exceeds the
24// destination type's limit.
25// Also returns zero if ULEBSizeErr is already in an error state.
26// ULEBSizeErr is an out variable if an error occurs.
27template <typename IntTy, std::enable_if_t<std::is_unsigned_v<IntTy>, int> = 0>
28static IntTy readULEB128As(const DataExtractor &Data,
29 DataExtractor::Cursor &Cur, Error &ULEBSizeErr) {
30 // Bail out and do not extract data if ULEBSizeErr is already set.
31 if (ULEBSizeErr)
32 return 0;
33 uint64_t Offset = Cur.tell();
34 uint64_t Value = Data.getULEB128(C&: Cur);
35 if (Value > std::numeric_limits<IntTy>::max()) {
36 ULEBSizeErr = createError(Err: "ULEB128 value at offset 0x" +
37 Twine::utohexstr(Val: Offset) + " exceeds UINT" +
38 Twine(std::numeric_limits<IntTy>::digits) +
39 "_MAX (0x" + Twine::utohexstr(Val: Value) + ")");
40 return 0;
41 }
42 return static_cast<IntTy>(Value);
43}
44} // end anonymous namespace
45
46Expected<std::vector<BBAddrMap>>
47llvm::object::decodeBBAddrMapPayload(AddressExtractor &Extractor,
48 std::vector<PGOAnalysisMap> *PGOAnalyses) {
49 const DataExtractor &Data = Extractor.getDataExtractor();
50 std::vector<BBAddrMap> FunctionEntries;
51
52 DataExtractor::Cursor Cur(0);
53 Error ULEBSizeErr = Error::success();
54 Error MetadataDecodeErr = Error::success();
55
56 // Use int for Version to avoid Twine treating uint8_t as char.
57 int Version = 0;
58 uint16_t Feature = 0;
59 BBAddrMap::Features FeatEnable{};
60 while (!ULEBSizeErr && !MetadataDecodeErr && Cur &&
61 Cur.tell() < Data.getData().size()) {
62 Version = Data.getU8(C&: Cur);
63 if (!Cur)
64 break;
65 if (Version < 2 || Version > 5)
66 return createError(Err: "unsupported BB address map version: " +
67 Twine(Version));
68 Feature = Version < 5 ? Data.getU8(C&: Cur) : Data.getU16(C&: Cur);
69 if (!Cur)
70 break;
71 auto FeatEnableOrErr = BBAddrMap::Features::decode(Val: Feature);
72 if (!FeatEnableOrErr)
73 return FeatEnableOrErr.takeError();
74 FeatEnable = *FeatEnableOrErr;
75 if (FeatEnable.CallsiteEndOffsets && Version < 3)
76 return createError(Err: "version should be >= 3 for BB address map when "
77 "callsite offsets feature is enabled: version = " +
78 Twine(Version) + " feature = " + Twine(Feature));
79 if (FeatEnable.BBHash && Version < 4)
80 return createError(Err: "version should be >= 4 for BB address map when "
81 "basic block hash feature is enabled: version = " +
82 Twine(Version) + " feature = " + Twine(Feature));
83 if (FeatEnable.PostLinkCfg && Version < 5)
84 return createError(Err: "version should be >= 5 for BB address map when "
85 "post link cfg feature is enabled: version = " +
86 Twine(Version) + " feature = " + Twine(Feature));
87 uint32_t NumBlocksInBBRange = 0;
88 uint32_t NumBBRanges = 1;
89 uint64_t RangeBaseAddress = 0;
90 if (FeatEnable.MultiBBRange) {
91 NumBBRanges = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
92 if (!Cur || ULEBSizeErr)
93 break;
94 if (!NumBBRanges)
95 return createError(Err: "invalid zero number of BB ranges at offset " +
96 Twine::utohexstr(Val: Cur.tell()));
97 } else {
98 auto AddressOrErr = Extractor.extractAddress(Cur);
99 if (!AddressOrErr)
100 return AddressOrErr.takeError();
101 RangeBaseAddress = *AddressOrErr;
102 NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
103 }
104 std::vector<BBAddrMap::BBRangeEntry> BBRangeEntries;
105 uint32_t TotalNumBlocks = 0;
106 for (uint32_t BBRangeIndex = 0; BBRangeIndex < NumBBRanges;
107 ++BBRangeIndex) {
108 uint32_t PrevBBEndOffset = 0;
109 if (FeatEnable.MultiBBRange) {
110 auto AddressOrErr = Extractor.extractAddress(Cur);
111 if (!AddressOrErr)
112 return AddressOrErr.takeError();
113 RangeBaseAddress = *AddressOrErr;
114 NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
115 }
116 std::vector<BBAddrMap::BBEntry> BBEntries;
117 if (!FeatEnable.OmitBBEntries) {
118 for (uint32_t BlockIndex = 0; !MetadataDecodeErr && !ULEBSizeErr &&
119 Cur && (BlockIndex < NumBlocksInBBRange);
120 ++BlockIndex) {
121 uint32_t ID = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
122 uint32_t Offset = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
123 // Read the callsite offsets.
124 uint32_t LastCallsiteEndOffset = 0;
125 SmallVector<uint32_t, 1> CallsiteEndOffsets;
126 if (FeatEnable.CallsiteEndOffsets) {
127 uint32_t NumCallsites =
128 readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
129 CallsiteEndOffsets.reserve(N: NumCallsites);
130 for (uint32_t CallsiteIndex = 0;
131 !ULEBSizeErr && Cur && (CallsiteIndex < NumCallsites);
132 ++CallsiteIndex) {
133 LastCallsiteEndOffset +=
134 readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
135 CallsiteEndOffsets.push_back(Elt: LastCallsiteEndOffset);
136 }
137 }
138 uint32_t Size = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr) +
139 LastCallsiteEndOffset;
140 uint32_t MD = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
141 uint64_t Hash = FeatEnable.BBHash ? Data.getU64(C&: Cur) : 0;
142 Expected<BBAddrMap::BBEntry::Metadata> MetadataOrErr =
143 BBAddrMap::BBEntry::Metadata::decode(V: MD);
144 if (!MetadataOrErr) {
145 MetadataDecodeErr = MetadataOrErr.takeError();
146 break;
147 }
148 BBEntries.push_back(x: {ID, Offset + PrevBBEndOffset, Size,
149 *MetadataOrErr, CallsiteEndOffsets, Hash});
150 PrevBBEndOffset += Offset + Size;
151 }
152 TotalNumBlocks += BBEntries.size();
153 }
154 BBRangeEntries.push_back(x: {.BaseAddress: RangeBaseAddress, .BBEntries: std::move(BBEntries)});
155 }
156 FunctionEntries.push_back(x: {.BBRanges: std::move(BBRangeEntries)});
157
158 if (PGOAnalyses || FeatEnable.hasPGOAnalysis()) {
159 // Function entry count
160 uint64_t FuncEntryCount =
161 FeatEnable.FuncEntryCount
162 ? readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr)
163 : 0;
164
165 std::vector<PGOAnalysisMap::PGOBBEntry> PGOBBEntries;
166 for (uint32_t BlockIndex = 0;
167 FeatEnable.hasPGOAnalysisBBData() && !MetadataDecodeErr &&
168 !ULEBSizeErr && Cur && (BlockIndex < TotalNumBlocks);
169 ++BlockIndex) {
170 // Block frequency
171 uint64_t BBF = FeatEnable.BBFreq
172 ? readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr)
173 : 0;
174 uint32_t PostLinkBBFreq =
175 FeatEnable.PostLinkCfg
176 ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
177 : 0;
178
179 // Branch probability
180 llvm::SmallVector<PGOAnalysisMap::PGOBBEntry::SuccessorEntry, 2>
181 Successors;
182 if (FeatEnable.BrProb) {
183 auto SuccCount = readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr);
184 for (uint64_t I = 0; I < SuccCount; ++I) {
185 uint32_t BBID = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
186 uint32_t BrProb = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
187 uint32_t PostLinkFreq =
188 FeatEnable.PostLinkCfg
189 ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
190 : 0;
191
192 if (PGOAnalyses)
193 Successors.push_back(
194 Elt: {.ID: BBID, .Prob: BranchProbability::getRaw(N: BrProb), .PostLinkFreq: PostLinkFreq});
195 }
196 }
197
198 if (PGOAnalyses)
199 PGOBBEntries.push_back(
200 x: {.BlockFreq: BlockFrequency(BBF), .PostLinkBlockFreq: PostLinkBBFreq, .Successors: std::move(Successors)});
201 }
202
203 if (PGOAnalyses)
204 PGOAnalyses->push_back(
205 x: {.FuncEntryCount: FuncEntryCount, .BBEntries: std::move(PGOBBEntries), .FeatEnable: FeatEnable});
206 }
207 }
208
209 // Either Cur is in the error state, or we have an error in ULEBSizeErr or
210 // MetadataDecodeErr (but not both), but we join all errors here to be safe.
211 if (!Cur || ULEBSizeErr || MetadataDecodeErr)
212 return joinErrors(E1: joinErrors(E1: Cur.takeError(), E2: std::move(ULEBSizeErr)),
213 E2: std::move(MetadataDecodeErr));
214 return FunctionEntries;
215}
216