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 > 6)
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 if (FeatEnable.FuncGUID && Version < 6)
88 return createError(Err: "version should be >= 6 for BB address map when "
89 "function GUID feature is enabled: version = " +
90 Twine(Version) + " feature = " + Twine(Feature));
91 uint64_t FuncGUID = FeatEnable.FuncGUID ? Data.getU64(C&: Cur) : 0;
92 if (!Cur)
93 break;
94 uint32_t NumBlocksInBBRange = 0;
95 uint32_t NumBBRanges = 1;
96 uint64_t RangeBaseAddress = 0;
97 if (FeatEnable.MultiBBRange) {
98 NumBBRanges = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
99 if (!Cur || ULEBSizeErr)
100 break;
101 if (!NumBBRanges)
102 return createError(Err: "invalid zero number of BB ranges at offset " +
103 Twine::utohexstr(Val: Cur.tell()));
104 } else {
105 auto AddressOrErr = Extractor.extractAddress(Cur);
106 if (!AddressOrErr)
107 return AddressOrErr.takeError();
108 RangeBaseAddress = *AddressOrErr;
109 NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
110 }
111 std::vector<BBAddrMap::BBRangeEntry> BBRangeEntries;
112 uint32_t TotalNumBlocks = 0;
113 for (uint32_t BBRangeIndex = 0; BBRangeIndex < NumBBRanges;
114 ++BBRangeIndex) {
115 uint32_t PrevBBEndOffset = 0;
116 if (FeatEnable.MultiBBRange) {
117 auto AddressOrErr = Extractor.extractAddress(Cur);
118 if (!AddressOrErr)
119 return AddressOrErr.takeError();
120 RangeBaseAddress = *AddressOrErr;
121 NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
122 }
123 std::vector<BBAddrMap::BBEntry> BBEntries;
124 if (!FeatEnable.OmitBBEntries) {
125 for (uint32_t BlockIndex = 0; !MetadataDecodeErr && !ULEBSizeErr &&
126 Cur && (BlockIndex < NumBlocksInBBRange);
127 ++BlockIndex) {
128 uint32_t ID = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
129 uint32_t Offset = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
130 // Read the callsite offsets.
131 uint32_t LastCallsiteEndOffset = 0;
132 SmallVector<uint32_t, 1> CallsiteEndOffsets;
133 if (FeatEnable.CallsiteEndOffsets) {
134 uint32_t NumCallsites =
135 readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
136 CallsiteEndOffsets.reserve(N: NumCallsites);
137 for (uint32_t CallsiteIndex = 0;
138 !ULEBSizeErr && Cur && (CallsiteIndex < NumCallsites);
139 ++CallsiteIndex) {
140 LastCallsiteEndOffset +=
141 readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
142 CallsiteEndOffsets.push_back(Elt: LastCallsiteEndOffset);
143 }
144 }
145 uint32_t Size = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr) +
146 LastCallsiteEndOffset;
147 uint32_t MD = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
148 uint64_t Hash = FeatEnable.BBHash ? Data.getU64(C&: Cur) : 0;
149 Expected<BBAddrMap::BBEntry::Metadata> MetadataOrErr =
150 BBAddrMap::BBEntry::Metadata::decode(V: MD);
151 if (!MetadataOrErr) {
152 MetadataDecodeErr = MetadataOrErr.takeError();
153 break;
154 }
155 BBEntries.push_back(x: {ID, Offset + PrevBBEndOffset, Size,
156 *MetadataOrErr, CallsiteEndOffsets, Hash});
157 PrevBBEndOffset += Offset + Size;
158 }
159 TotalNumBlocks += BBEntries.size();
160 }
161 BBRangeEntries.push_back(x: {.BaseAddress: RangeBaseAddress, .BBEntries: std::move(BBEntries)});
162 }
163 FunctionEntries.push_back(x: {.BBRanges: std::move(BBRangeEntries), .FuncGUID: FuncGUID});
164
165 if (PGOAnalyses || FeatEnable.hasPGOAnalysis()) {
166 // Function entry count
167 uint64_t FuncEntryCount =
168 FeatEnable.FuncEntryCount
169 ? readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr)
170 : 0;
171
172 std::vector<PGOAnalysisMap::PGOBBEntry> PGOBBEntries;
173 for (uint32_t BlockIndex = 0;
174 FeatEnable.hasPGOAnalysisBBData() && !MetadataDecodeErr &&
175 !ULEBSizeErr && Cur && (BlockIndex < TotalNumBlocks);
176 ++BlockIndex) {
177 // Block frequency
178 uint64_t BBF = FeatEnable.BBFreq
179 ? readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr)
180 : 0;
181 uint32_t PostLinkBBFreq =
182 FeatEnable.PostLinkCfg
183 ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
184 : 0;
185
186 // Branch probability
187 llvm::SmallVector<PGOAnalysisMap::PGOBBEntry::SuccessorEntry, 2>
188 Successors;
189 if (FeatEnable.BrProb) {
190 auto SuccCount = readULEB128As<uint64_t>(Data, Cur, ULEBSizeErr);
191 for (uint64_t I = 0; I < SuccCount; ++I) {
192 uint32_t BBID = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
193 uint32_t BrProb = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
194 uint32_t PostLinkFreq =
195 FeatEnable.PostLinkCfg
196 ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
197 : 0;
198
199 if (PGOAnalyses)
200 Successors.push_back(
201 Elt: {.ID: BBID, .Prob: BranchProbability::getRaw(N: BrProb), .PostLinkFreq: PostLinkFreq});
202 }
203 }
204
205 if (PGOAnalyses)
206 PGOBBEntries.push_back(
207 x: {.BlockFreq: BlockFrequency(BBF), .PostLinkBlockFreq: PostLinkBBFreq, .Successors: std::move(Successors)});
208 }
209
210 if (PGOAnalyses)
211 PGOAnalyses->push_back(
212 x: {.FuncEntryCount: FuncEntryCount, .BBEntries: std::move(PGOBBEntries), .FeatEnable: FeatEnable});
213 }
214 }
215
216 // Either Cur is in the error state, or we have an error in ULEBSizeErr or
217 // MetadataDecodeErr (but not both), but we join all errors here to be safe.
218 if (!Cur || ULEBSizeErr || MetadataDecodeErr)
219 return joinErrors(E1: joinErrors(E1: Cur.takeError(), E2: std::move(ULEBSizeErr)),
220 E2: std::move(MetadataDecodeErr));
221 return FunctionEntries;
222}
223