Bug Summary

File:build/source/bolt/lib/Core/BinaryFunction.cpp
Warning:line 2172, column 3
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name BinaryFunction.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16 -I tools/bolt/lib/Core -I /build/source/bolt/lib/Core -I include -I /build/source/llvm/include -I /build/source/bolt/include -I tools/bolt/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1670191760 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-12-05-012027-15999-1 -x c++ /build/source/bolt/lib/Core/BinaryFunction.cpp
1//===- bolt/Core/BinaryFunction.cpp - Low-level function ------------------===//
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// This file implements the BinaryFunction class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "bolt/Core/BinaryFunction.h"
14#include "bolt/Core/BinaryBasicBlock.h"
15#include "bolt/Core/BinaryDomTree.h"
16#include "bolt/Core/DynoStats.h"
17#include "bolt/Core/MCPlusBuilder.h"
18#include "bolt/Utils/NameResolver.h"
19#include "bolt/Utils/NameShortener.h"
20#include "bolt/Utils/Utils.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallSet.h"
23#include "llvm/ADT/StringExtras.h"
24#include "llvm/ADT/StringRef.h"
25#include "llvm/Demangle/Demangle.h"
26#include "llvm/MC/MCAsmInfo.h"
27#include "llvm/MC/MCAsmLayout.h"
28#include "llvm/MC/MCContext.h"
29#include "llvm/MC/MCDisassembler/MCDisassembler.h"
30#include "llvm/MC/MCExpr.h"
31#include "llvm/MC/MCInst.h"
32#include "llvm/MC/MCInstPrinter.h"
33#include "llvm/MC/MCRegisterInfo.h"
34#include "llvm/MC/MCSymbol.h"
35#include "llvm/Object/ObjectFile.h"
36#include "llvm/Support/CommandLine.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/GraphWriter.h"
39#include "llvm/Support/LEB128.h"
40#include "llvm/Support/Regex.h"
41#include "llvm/Support/Timer.h"
42#include "llvm/Support/raw_ostream.h"
43#include <functional>
44#include <limits>
45#include <numeric>
46#include <string>
47
48#define DEBUG_TYPE"bolt" "bolt"
49
50using namespace llvm;
51using namespace bolt;
52
53namespace opts {
54
55extern cl::OptionCategory BoltCategory;
56extern cl::OptionCategory BoltOptCategory;
57extern cl::OptionCategory BoltRelocCategory;
58
59extern cl::opt<bool> EnableBAT;
60extern cl::opt<bool> Instrument;
61extern cl::opt<bool> StrictMode;
62extern cl::opt<bool> UpdateDebugSections;
63extern cl::opt<unsigned> Verbosity;
64
65extern bool processAllFunctions();
66
67cl::opt<bool> CheckEncoding(
68 "check-encoding",
69 cl::desc("perform verification of LLVM instruction encoding/decoding. "
70 "Every instruction in the input is decoded and re-encoded. "
71 "If the resulting bytes do not match the input, a warning message "
72 "is printed."),
73 cl::Hidden, cl::cat(BoltCategory));
74
75static cl::opt<bool> DotToolTipCode(
76 "dot-tooltip-code",
77 cl::desc("add basic block instructions as tool tips on nodes"), cl::Hidden,
78 cl::cat(BoltCategory));
79
80cl::opt<JumpTableSupportLevel>
81JumpTables("jump-tables",
82 cl::desc("jump tables support (default=basic)"),
83 cl::init(JTS_BASIC),
84 cl::values(
85 clEnumValN(JTS_NONE, "none",llvm::cl::OptionEnumValue { "none", int(JTS_NONE), "do not optimize functions with jump tables"
}
86 "do not optimize functions with jump tables")llvm::cl::OptionEnumValue { "none", int(JTS_NONE), "do not optimize functions with jump tables"
}
,
87 clEnumValN(JTS_BASIC, "basic",llvm::cl::OptionEnumValue { "basic", int(JTS_BASIC), "optimize functions with jump tables"
}
88 "optimize functions with jump tables")llvm::cl::OptionEnumValue { "basic", int(JTS_BASIC), "optimize functions with jump tables"
}
,
89 clEnumValN(JTS_MOVE, "move",llvm::cl::OptionEnumValue { "move", int(JTS_MOVE), "move jump tables to a separate section"
}
90 "move jump tables to a separate section")llvm::cl::OptionEnumValue { "move", int(JTS_MOVE), "move jump tables to a separate section"
}
,
91 clEnumValN(JTS_SPLIT, "split",llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on "
"function execution frequency" }
92 "split jump tables section into hot and cold based on "llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on "
"function execution frequency" }
93 "function execution frequency")llvm::cl::OptionEnumValue { "split", int(JTS_SPLIT), "split jump tables section into hot and cold based on "
"function execution frequency" }
,
94 clEnumValN(JTS_AGGRESSIVE, "aggressive",llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE)
, "aggressively split jump tables section based on usage " "of the tables"
}
95 "aggressively split jump tables section based on usage "llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE)
, "aggressively split jump tables section based on usage " "of the tables"
}
96 "of the tables")llvm::cl::OptionEnumValue { "aggressive", int(JTS_AGGRESSIVE)
, "aggressively split jump tables section based on usage " "of the tables"
}
),
97 cl::ZeroOrMore,
98 cl::cat(BoltOptCategory));
99
100static cl::opt<bool> NoScan(
101 "no-scan",
102 cl::desc(
103 "do not scan cold functions for external references (may result in "
104 "slower binary)"),
105 cl::Hidden, cl::cat(BoltOptCategory));
106
107cl::opt<bool>
108 PreserveBlocksAlignment("preserve-blocks-alignment",
109 cl::desc("try to preserve basic block alignment"),
110 cl::cat(BoltOptCategory));
111
112cl::opt<bool>
113PrintDynoStats("dyno-stats",
114 cl::desc("print execution info based on profile"),
115 cl::cat(BoltCategory));
116
117static cl::opt<bool>
118PrintDynoStatsOnly("print-dyno-stats-only",
119 cl::desc("while printing functions output dyno-stats and skip instructions"),
120 cl::init(false),
121 cl::Hidden,
122 cl::cat(BoltCategory));
123
124static cl::list<std::string>
125PrintOnly("print-only",
126 cl::CommaSeparated,
127 cl::desc("list of functions to print"),
128 cl::value_desc("func1,func2,func3,..."),
129 cl::Hidden,
130 cl::cat(BoltCategory));
131
132cl::opt<bool>
133 TimeBuild("time-build",
134 cl::desc("print time spent constructing binary functions"),
135 cl::Hidden, cl::cat(BoltCategory));
136
137cl::opt<bool>
138TrapOnAVX512("trap-avx512",
139 cl::desc("in relocation mode trap upon entry to any function that uses "
140 "AVX-512 instructions"),
141 cl::init(false),
142 cl::ZeroOrMore,
143 cl::Hidden,
144 cl::cat(BoltCategory));
145
146bool shouldPrint(const BinaryFunction &Function) {
147 if (Function.isIgnored())
148 return false;
149
150 if (PrintOnly.empty())
151 return true;
152
153 for (std::string &Name : opts::PrintOnly) {
154 if (Function.hasNameRegex(Name)) {
155 return true;
156 }
157 }
158
159 return false;
160}
161
162} // namespace opts
163
164namespace llvm {
165namespace bolt {
166
167constexpr unsigned BinaryFunction::MinAlign;
168
169namespace {
170
171template <typename R> bool emptyRange(const R &Range) {
172 return Range.begin() == Range.end();
173}
174
175/// Gets debug line information for the instruction located at the given
176/// address in the original binary. The SMLoc's pointer is used
177/// to point to this information, which is represented by a
178/// DebugLineTableRowRef. The returned pointer is null if no debug line
179/// information for this instruction was found.
180SMLoc findDebugLineInformationForInstructionAt(
181 uint64_t Address, DWARFUnit *Unit,
182 const DWARFDebugLine::LineTable *LineTable) {
183 // We use the pointer in SMLoc to store an instance of DebugLineTableRowRef,
184 // which occupies 64 bits. Thus, we can only proceed if the struct fits into
185 // the pointer itself.
186 assert(sizeof(decltype(SMLoc().getPointer())) >=(static_cast <bool> (sizeof(decltype(SMLoc().getPointer
())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer"
) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\""
, "bolt/lib/Core/BinaryFunction.cpp", 188, __extension__ __PRETTY_FUNCTION__
))
187 sizeof(DebugLineTableRowRef) &&(static_cast <bool> (sizeof(decltype(SMLoc().getPointer
())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer"
) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\""
, "bolt/lib/Core/BinaryFunction.cpp", 188, __extension__ __PRETTY_FUNCTION__
))
188 "Cannot fit instruction debug line information into SMLoc's pointer")(static_cast <bool> (sizeof(decltype(SMLoc().getPointer
())) >= sizeof(DebugLineTableRowRef) && "Cannot fit instruction debug line information into SMLoc's pointer"
) ? void (0) : __assert_fail ("sizeof(decltype(SMLoc().getPointer())) >= sizeof(DebugLineTableRowRef) && \"Cannot fit instruction debug line information into SMLoc's pointer\""
, "bolt/lib/Core/BinaryFunction.cpp", 188, __extension__ __PRETTY_FUNCTION__
))
;
189
190 SMLoc NullResult = DebugLineTableRowRef::NULL_ROW.toSMLoc();
191 uint32_t RowIndex = LineTable->lookupAddress(
192 {Address, object::SectionedAddress::UndefSection});
193 if (RowIndex == LineTable->UnknownRowIndex)
194 return NullResult;
195
196 assert(RowIndex < LineTable->Rows.size() &&(static_cast <bool> (RowIndex < LineTable->Rows.size
() && "Line Table lookup returned invalid index.") ? void
(0) : __assert_fail ("RowIndex < LineTable->Rows.size() && \"Line Table lookup returned invalid index.\""
, "bolt/lib/Core/BinaryFunction.cpp", 197, __extension__ __PRETTY_FUNCTION__
))
197 "Line Table lookup returned invalid index.")(static_cast <bool> (RowIndex < LineTable->Rows.size
() && "Line Table lookup returned invalid index.") ? void
(0) : __assert_fail ("RowIndex < LineTable->Rows.size() && \"Line Table lookup returned invalid index.\""
, "bolt/lib/Core/BinaryFunction.cpp", 197, __extension__ __PRETTY_FUNCTION__
))
;
198
199 decltype(SMLoc().getPointer()) Ptr;
200 DebugLineTableRowRef *InstructionLocation =
201 reinterpret_cast<DebugLineTableRowRef *>(&Ptr);
202
203 InstructionLocation->DwCompileUnitIndex = Unit->getOffset();
204 InstructionLocation->RowIndex = RowIndex + 1;
205
206 return SMLoc::getFromPointer(Ptr);
207}
208
209std::string buildSectionName(StringRef Prefix, StringRef Name,
210 const BinaryContext &BC) {
211 if (BC.isELF())
212 return (Prefix + Name).str();
213 static NameShortener NS;
214 return (Prefix + Twine(NS.getID(Name))).str();
215}
216
217raw_ostream &operator<<(raw_ostream &OS, const BinaryFunction::State State) {
218 switch (State) {
219 case BinaryFunction::State::Empty: OS << "empty"; break;
220 case BinaryFunction::State::Disassembled: OS << "disassembled"; break;
221 case BinaryFunction::State::CFG: OS << "CFG constructed"; break;
222 case BinaryFunction::State::CFG_Finalized: OS << "CFG finalized"; break;
223 case BinaryFunction::State::EmittedCFG: OS << "emitted with CFG"; break;
224 case BinaryFunction::State::Emitted: OS << "emitted"; break;
225 }
226
227 return OS;
228}
229
230} // namespace
231
232std::string BinaryFunction::buildCodeSectionName(StringRef Name,
233 const BinaryContext &BC) {
234 return buildSectionName(BC.isELF() ? ".local.text." : ".l.text.", Name, BC);
235}
236
237std::string BinaryFunction::buildColdCodeSectionName(StringRef Name,
238 const BinaryContext &BC) {
239 return buildSectionName(BC.isELF() ? ".local.cold.text." : ".l.c.text.", Name,
240 BC);
241}
242
243uint64_t BinaryFunction::Count = 0;
244
245Optional<StringRef> BinaryFunction::hasNameRegex(const StringRef Name) const {
246 const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
247 Regex MatchName(RegexName);
248 Optional<StringRef> Match = forEachName(
249 [&MatchName](StringRef Name) { return MatchName.match(Name); });
250
251 return Match;
252}
253
254Optional<StringRef>
255BinaryFunction::hasRestoredNameRegex(const StringRef Name) const {
256 const std::string RegexName = (Twine("^") + StringRef(Name) + "$").str();
257 Regex MatchName(RegexName);
258 Optional<StringRef> Match = forEachName([&MatchName](StringRef Name) {
259 return MatchName.match(NameResolver::restore(Name));
260 });
261
262 return Match;
263}
264
265std::string BinaryFunction::getDemangledName() const {
266 StringRef MangledName = NameResolver::restore(getOneName());
267 return demangle(MangledName.str());
268}
269
270BinaryBasicBlock *
271BinaryFunction::getBasicBlockContainingOffset(uint64_t Offset) {
272 if (Offset > Size)
273 return nullptr;
274
275 if (BasicBlockOffsets.empty())
276 return nullptr;
277
278 /*
279 * This is commented out because it makes BOLT too slow.
280 * assert(std::is_sorted(BasicBlockOffsets.begin(),
281 * BasicBlockOffsets.end(),
282 * CompareBasicBlockOffsets())));
283 */
284 auto I =
285 llvm::upper_bound(BasicBlockOffsets, BasicBlockOffset(Offset, nullptr),
286 CompareBasicBlockOffsets());
287 assert(I != BasicBlockOffsets.begin() && "first basic block not at offset 0")(static_cast <bool> (I != BasicBlockOffsets.begin() &&
"first basic block not at offset 0") ? void (0) : __assert_fail
("I != BasicBlockOffsets.begin() && \"first basic block not at offset 0\""
, "bolt/lib/Core/BinaryFunction.cpp", 287, __extension__ __PRETTY_FUNCTION__
))
;
288 --I;
289 BinaryBasicBlock *BB = I->second;
290 return (Offset < BB->getOffset() + BB->getOriginalSize()) ? BB : nullptr;
291}
292
293void BinaryFunction::markUnreachableBlocks() {
294 std::stack<BinaryBasicBlock *> Stack;
295
296 for (BinaryBasicBlock &BB : blocks())
297 BB.markValid(false);
298
299 // Add all entries and landing pads as roots.
300 for (BinaryBasicBlock *BB : BasicBlocks) {
301 if (isEntryPoint(*BB) || BB->isLandingPad()) {
302 Stack.push(BB);
303 BB->markValid(true);
304 continue;
305 }
306 // FIXME:
307 // Also mark BBs with indirect jumps as reachable, since we do not
308 // support removing unused jump tables yet (GH-issue20).
309 for (const MCInst &Inst : *BB) {
310 if (BC.MIB->getJumpTable(Inst)) {
311 Stack.push(BB);
312 BB->markValid(true);
313 break;
314 }
315 }
316 }
317
318 // Determine reachable BBs from the entry point
319 while (!Stack.empty()) {
320 BinaryBasicBlock *BB = Stack.top();
321 Stack.pop();
322 for (BinaryBasicBlock *Succ : BB->successors()) {
323 if (Succ->isValid())
324 continue;
325 Succ->markValid(true);
326 Stack.push(Succ);
327 }
328 }
329}
330
331// Any unnecessary fallthrough jumps revealed after calling eraseInvalidBBs
332// will be cleaned up by fixBranches().
333std::pair<unsigned, uint64_t> BinaryFunction::eraseInvalidBBs() {
334 DenseSet<const BinaryBasicBlock *> InvalidBBs;
335 unsigned Count = 0;
336 uint64_t Bytes = 0;
337 for (BinaryBasicBlock *const BB : BasicBlocks) {
338 if (!BB->isValid()) {
339 assert(!isEntryPoint(*BB) && "all entry blocks must be valid")(static_cast <bool> (!isEntryPoint(*BB) && "all entry blocks must be valid"
) ? void (0) : __assert_fail ("!isEntryPoint(*BB) && \"all entry blocks must be valid\""
, "bolt/lib/Core/BinaryFunction.cpp", 339, __extension__ __PRETTY_FUNCTION__
))
;
340 InvalidBBs.insert(BB);
341 ++Count;
342 Bytes += BC.computeCodeSize(BB->begin(), BB->end());
343 }
344 }
345
346 Layout.eraseBasicBlocks(InvalidBBs);
347
348 BasicBlockListType NewBasicBlocks;
349 for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
350 BinaryBasicBlock *BB = *I;
351 if (InvalidBBs.contains(BB)) {
352 // Make sure the block is removed from the list of predecessors.
353 BB->removeAllSuccessors();
354 DeletedBasicBlocks.push_back(BB);
355 } else {
356 NewBasicBlocks.push_back(BB);
357 }
358 }
359 BasicBlocks = std::move(NewBasicBlocks);
360
361 assert(BasicBlocks.size() == Layout.block_size())(static_cast <bool> (BasicBlocks.size() == Layout.block_size
()) ? void (0) : __assert_fail ("BasicBlocks.size() == Layout.block_size()"
, "bolt/lib/Core/BinaryFunction.cpp", 361, __extension__ __PRETTY_FUNCTION__
))
;
362
363 // Update CFG state if needed
364 if (Count > 0)
365 recomputeLandingPads();
366
367 return std::make_pair(Count, Bytes);
368}
369
370bool BinaryFunction::isForwardCall(const MCSymbol *CalleeSymbol) const {
371 // This function should work properly before and after function reordering.
372 // In order to accomplish this, we use the function index (if it is valid).
373 // If the function indices are not valid, we fall back to the original
374 // addresses. This should be ok because the functions without valid indices
375 // should have been ordered with a stable sort.
376 const BinaryFunction *CalleeBF = BC.getFunctionForSymbol(CalleeSymbol);
377 if (CalleeBF) {
378 if (CalleeBF->isInjected())
379 return true;
380
381 if (hasValidIndex() && CalleeBF->hasValidIndex()) {
382 return getIndex() < CalleeBF->getIndex();
383 } else if (hasValidIndex() && !CalleeBF->hasValidIndex()) {
384 return true;
385 } else if (!hasValidIndex() && CalleeBF->hasValidIndex()) {
386 return false;
387 } else {
388 return getAddress() < CalleeBF->getAddress();
389 }
390 } else {
391 // Absolute symbol.
392 ErrorOr<uint64_t> CalleeAddressOrError = BC.getSymbolValue(*CalleeSymbol);
393 assert(CalleeAddressOrError && "unregistered symbol found")(static_cast <bool> (CalleeAddressOrError && "unregistered symbol found"
) ? void (0) : __assert_fail ("CalleeAddressOrError && \"unregistered symbol found\""
, "bolt/lib/Core/BinaryFunction.cpp", 393, __extension__ __PRETTY_FUNCTION__
))
;
394 return *CalleeAddressOrError > getAddress();
395 }
396}
397
398void BinaryFunction::dump(bool PrintInstructions) const {
399 // getDynoStats calls FunctionLayout::updateLayoutIndices and
400 // BasicBlock::analyzeBranch. The former cannot be const, but should be
401 // removed, the latter should be made const, but seems to require refactoring.
402 // Forcing all callers to have a non-const reference to BinaryFunction to call
403 // dump non-const however is not ideal either. Adding this const_cast is right
404 // now the best solution. It is safe, because BinaryFunction itself is not
405 // modified. Only BinaryBasicBlocks are actually modified (if it all) and we
406 // have mutable pointers to those regardless whether this function is
407 // const-qualified or not.
408 const_cast<BinaryFunction &>(*this).print(dbgs(), "", PrintInstructions);
409}
410
411void BinaryFunction::print(raw_ostream &OS, std::string Annotation,
412 bool PrintInstructions) {
413 if (!opts::shouldPrint(*this))
414 return;
415
416 StringRef SectionName =
417 OriginSection ? OriginSection->getName() : "<no origin section>";
418 OS << "Binary Function \"" << *this << "\" " << Annotation << " {";
419 std::vector<StringRef> AllNames = getNames();
420 if (AllNames.size() > 1) {
421 OS << "\n All names : ";
422 const char *Sep = "";
423 for (const StringRef &Name : AllNames) {
424 OS << Sep << Name;
425 Sep = "\n ";
426 }
427 }
428 OS << "\n Number : " << FunctionNumber;
429 OS << "\n State : " << CurrentState;
430 OS << "\n Address : 0x" << Twine::utohexstr(Address);
431 OS << "\n Size : 0x" << Twine::utohexstr(Size);
432 OS << "\n MaxSize : 0x" << Twine::utohexstr(MaxSize);
433 OS << "\n Offset : 0x" << Twine::utohexstr(getFileOffset());
434 OS << "\n Section : " << SectionName;
435 OS << "\n Orc Section : " << getCodeSectionName();
436 OS << "\n LSDA : 0x" << Twine::utohexstr(getLSDAAddress());
437 OS << "\n IsSimple : " << IsSimple;
438 OS << "\n IsMultiEntry: " << isMultiEntry();
439 OS << "\n IsSplit : " << isSplit();
440 OS << "\n BB Count : " << size();
441
442 if (HasFixedIndirectBranch)
443 OS << "\n HasFixedIndirectBranch : true";
444 if (HasUnknownControlFlow)
445 OS << "\n Unknown CF : true";
446 if (getPersonalityFunction())
447 OS << "\n Personality : " << getPersonalityFunction()->getName();
448 if (IsFragment)
449 OS << "\n IsFragment : true";
450 if (isFolded())
451 OS << "\n FoldedInto : " << *getFoldedIntoFunction();
452 for (BinaryFunction *ParentFragment : ParentFragments)
453 OS << "\n Parent : " << *ParentFragment;
454 if (!Fragments.empty()) {
455 OS << "\n Fragments : ";
456 ListSeparator LS;
457 for (BinaryFunction *Frag : Fragments)
458 OS << LS << *Frag;
459 }
460 if (hasCFG())
461 OS << "\n Hash : " << Twine::utohexstr(computeHash());
462 if (isMultiEntry()) {
463 OS << "\n Secondary Entry Points : ";
464 ListSeparator LS;
465 for (const auto &KV : SecondaryEntryPoints)
466 OS << LS << KV.second->getName();
467 }
468 if (FrameInstructions.size())
469 OS << "\n CFI Instrs : " << FrameInstructions.size();
470 if (!Layout.block_empty()) {
471 OS << "\n BB Layout : ";
472 ListSeparator LS;
473 for (const BinaryBasicBlock *BB : Layout.blocks())
474 OS << LS << BB->getName();
475 }
476 if (getImageAddress())
477 OS << "\n Image : 0x" << Twine::utohexstr(getImageAddress());
478 if (ExecutionCount != COUNT_NO_PROFILE) {
479 OS << "\n Exec Count : " << ExecutionCount;
480 OS << "\n Profile Acc : " << format("%.1f%%", ProfileMatchRatio * 100.0f);
481 }
482
483 if (opts::PrintDynoStats && !getLayout().block_empty()) {
484 OS << '\n';
485 DynoStats dynoStats = getDynoStats(*this);
486 OS << dynoStats;
487 }
488
489 OS << "\n}\n";
490
491 if (opts::PrintDynoStatsOnly || !PrintInstructions || !BC.InstPrinter)
492 return;
493
494 // Offset of the instruction in function.
495 uint64_t Offset = 0;
496
497 if (BasicBlocks.empty() && !Instructions.empty()) {
498 // Print before CFG was built.
499 for (const std::pair<const uint32_t, MCInst> &II : Instructions) {
500 Offset = II.first;
501
502 // Print label if exists at this offset.
503 auto LI = Labels.find(Offset);
504 if (LI != Labels.end()) {
505 if (const MCSymbol *EntrySymbol =
506 getSecondaryEntryPointSymbol(LI->second))
507 OS << EntrySymbol->getName() << " (Entry Point):\n";
508 OS << LI->second->getName() << ":\n";
509 }
510
511 BC.printInstruction(OS, II.second, Offset, this);
512 }
513 }
514
515 StringRef SplitPointMsg = "";
516 for (const FunctionFragment &FF : Layout.fragments()) {
517 OS << SplitPointMsg;
518 SplitPointMsg = "------- HOT-COLD SPLIT POINT -------\n\n";
519 for (const BinaryBasicBlock *BB : FF) {
520 OS << BB->getName() << " (" << BB->size()
521 << " instructions, align : " << BB->getAlignment() << ")\n";
522
523 if (isEntryPoint(*BB)) {
524 if (MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB))
525 OS << " Secondary Entry Point: " << EntrySymbol->getName() << '\n';
526 else
527 OS << " Entry Point\n";
528 }
529
530 if (BB->isLandingPad())
531 OS << " Landing Pad\n";
532
533 uint64_t BBExecCount = BB->getExecutionCount();
534 if (hasValidProfile()) {
535 OS << " Exec Count : ";
536 if (BB->getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE)
537 OS << BBExecCount << '\n';
538 else
539 OS << "<unknown>\n";
540 }
541 if (BB->getCFIState() >= 0)
542 OS << " CFI State : " << BB->getCFIState() << '\n';
543 if (opts::EnableBAT) {
544 OS << " Input offset: " << Twine::utohexstr(BB->getInputOffset())
545 << "\n";
546 }
547 if (!BB->pred_empty()) {
548 OS << " Predecessors: ";
549 ListSeparator LS;
550 for (BinaryBasicBlock *Pred : BB->predecessors())
551 OS << LS << Pred->getName();
552 OS << '\n';
553 }
554 if (!BB->throw_empty()) {
555 OS << " Throwers: ";
556 ListSeparator LS;
557 for (BinaryBasicBlock *Throw : BB->throwers())
558 OS << LS << Throw->getName();
559 OS << '\n';
560 }
561
562 Offset = alignTo(Offset, BB->getAlignment());
563
564 // Note: offsets are imprecise since this is happening prior to
565 // relaxation.
566 Offset = BC.printInstructions(OS, BB->begin(), BB->end(), Offset, this);
567
568 if (!BB->succ_empty()) {
569 OS << " Successors: ";
570 // For more than 2 successors, sort them based on frequency.
571 std::vector<uint64_t> Indices(BB->succ_size());
572 std::iota(Indices.begin(), Indices.end(), 0);
573 if (BB->succ_size() > 2 && BB->getKnownExecutionCount()) {
574 llvm::stable_sort(Indices, [&](const uint64_t A, const uint64_t B) {
575 return BB->BranchInfo[B] < BB->BranchInfo[A];
576 });
577 }
578 ListSeparator LS;
579 for (unsigned I = 0; I < Indices.size(); ++I) {
580 BinaryBasicBlock *Succ = BB->Successors[Indices[I]];
581 const BinaryBasicBlock::BinaryBranchInfo &BI =
582 BB->BranchInfo[Indices[I]];
583 OS << LS << Succ->getName();
584 if (ExecutionCount != COUNT_NO_PROFILE &&
585 BI.MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
586 OS << " (mispreds: " << BI.MispredictedCount
587 << ", count: " << BI.Count << ")";
588 } else if (ExecutionCount != COUNT_NO_PROFILE &&
589 BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
590 OS << " (inferred count: " << BI.Count << ")";
591 }
592 }
593 OS << '\n';
594 }
595
596 if (!BB->lp_empty()) {
597 OS << " Landing Pads: ";
598 ListSeparator LS;
599 for (BinaryBasicBlock *LP : BB->landing_pads()) {
600 OS << LS << LP->getName();
601 if (ExecutionCount != COUNT_NO_PROFILE) {
602 OS << " (count: " << LP->getExecutionCount() << ")";
603 }
604 }
605 OS << '\n';
606 }
607
608 // In CFG_Finalized state we can miscalculate CFI state at exit.
609 if (CurrentState == State::CFG) {
610 const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
611 if (CFIStateAtExit >= 0)
612 OS << " CFI State: " << CFIStateAtExit << '\n';
613 }
614
615 OS << '\n';
616 }
617 }
618
619 // Dump new exception ranges for the function.
620 if (!CallSites.empty()) {
621 OS << "EH table:\n";
622 for (const FunctionFragment &FF : getLayout().fragments()) {
623 for (const auto &FCSI : getCallSites(FF.getFragmentNum())) {
624 const CallSite &CSI = FCSI.second;
625 OS << " [" << *CSI.Start << ", " << *CSI.End << ") landing pad : ";
626 if (CSI.LP)
627 OS << *CSI.LP;
628 else
629 OS << "0";
630 OS << ", action : " << CSI.Action << '\n';
631 }
632 }
633 OS << '\n';
634 }
635
636 // Print all jump tables.
637 for (const std::pair<const uint64_t, JumpTable *> &JTI : JumpTables)
638 JTI.second->print(OS);
639
640 OS << "DWARF CFI Instructions:\n";
641 if (OffsetToCFI.size()) {
642 // Pre-buildCFG information
643 for (const std::pair<const uint32_t, uint32_t> &Elmt : OffsetToCFI) {
644 OS << format(" %08x:\t", Elmt.first);
645 assert(Elmt.second < FrameInstructions.size() && "Incorrect CFI offset")(static_cast <bool> (Elmt.second < FrameInstructions
.size() && "Incorrect CFI offset") ? void (0) : __assert_fail
("Elmt.second < FrameInstructions.size() && \"Incorrect CFI offset\""
, "bolt/lib/Core/BinaryFunction.cpp", 645, __extension__ __PRETTY_FUNCTION__
))
;
646 BinaryContext::printCFI(OS, FrameInstructions[Elmt.second]);
647 OS << "\n";
648 }
649 } else {
650 // Post-buildCFG information
651 for (uint32_t I = 0, E = FrameInstructions.size(); I != E; ++I) {
652 const MCCFIInstruction &CFI = FrameInstructions[I];
653 OS << format(" %d:\t", I);
654 BinaryContext::printCFI(OS, CFI);
655 OS << "\n";
656 }
657 }
658 if (FrameInstructions.empty())
659 OS << " <empty>\n";
660
661 OS << "End of Function \"" << *this << "\"\n\n";
662}
663
664void BinaryFunction::printRelocations(raw_ostream &OS, uint64_t Offset,
665 uint64_t Size) const {
666 const char *Sep = " # Relocs: ";
667
668 auto RI = Relocations.lower_bound(Offset);
669 while (RI != Relocations.end() && RI->first < Offset + Size) {
670 OS << Sep << "(R: " << RI->second << ")";
671 Sep = ", ";
672 ++RI;
673 }
674}
675
676namespace {
677std::string mutateDWARFExpressionTargetReg(const MCCFIInstruction &Instr,
678 MCPhysReg NewReg) {
679 StringRef ExprBytes = Instr.getValues();
680 assert(ExprBytes.size() > 1 && "DWARF expression CFI is too short")(static_cast <bool> (ExprBytes.size() > 1 &&
"DWARF expression CFI is too short") ? void (0) : __assert_fail
("ExprBytes.size() > 1 && \"DWARF expression CFI is too short\""
, "bolt/lib/Core/BinaryFunction.cpp", 680, __extension__ __PRETTY_FUNCTION__
))
;
681 uint8_t Opcode = ExprBytes[0];
682 assert((Opcode == dwarf::DW_CFA_expression ||(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression
|| Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI"
) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\""
, "bolt/lib/Core/BinaryFunction.cpp", 684, __extension__ __PRETTY_FUNCTION__
))
683 Opcode == dwarf::DW_CFA_val_expression) &&(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression
|| Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI"
) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\""
, "bolt/lib/Core/BinaryFunction.cpp", 684, __extension__ __PRETTY_FUNCTION__
))
684 "invalid DWARF expression CFI")(static_cast <bool> ((Opcode == dwarf::DW_CFA_expression
|| Opcode == dwarf::DW_CFA_val_expression) && "invalid DWARF expression CFI"
) ? void (0) : __assert_fail ("(Opcode == dwarf::DW_CFA_expression || Opcode == dwarf::DW_CFA_val_expression) && \"invalid DWARF expression CFI\""
, "bolt/lib/Core/BinaryFunction.cpp", 684, __extension__ __PRETTY_FUNCTION__
))
;
685 (void)Opcode;
686 const uint8_t *const Start =
687 reinterpret_cast<const uint8_t *>(ExprBytes.drop_front(1).data());
688 const uint8_t *const End =
689 reinterpret_cast<const uint8_t *>(Start + ExprBytes.size() - 1);
690 unsigned Size = 0;
691 decodeULEB128(Start, &Size, End);
692 assert(Size > 0 && "Invalid reg encoding for DWARF expression CFI")(static_cast <bool> (Size > 0 && "Invalid reg encoding for DWARF expression CFI"
) ? void (0) : __assert_fail ("Size > 0 && \"Invalid reg encoding for DWARF expression CFI\""
, "bolt/lib/Core/BinaryFunction.cpp", 692, __extension__ __PRETTY_FUNCTION__
))
;
693 SmallString<8> Tmp;
694 raw_svector_ostream OSE(Tmp);
695 encodeULEB128(NewReg, OSE);
696 return Twine(ExprBytes.slice(0, 1))
697 .concat(OSE.str())
698 .concat(ExprBytes.drop_front(1 + Size))
699 .str();
700}
701} // namespace
702
703void BinaryFunction::mutateCFIRegisterFor(const MCInst &Instr,
704 MCPhysReg NewReg) {
705 const MCCFIInstruction *OldCFI = getCFIFor(Instr);
706 assert(OldCFI && "invalid CFI instr")(static_cast <bool> (OldCFI && "invalid CFI instr"
) ? void (0) : __assert_fail ("OldCFI && \"invalid CFI instr\""
, "bolt/lib/Core/BinaryFunction.cpp", 706, __extension__ __PRETTY_FUNCTION__
))
;
707 switch (OldCFI->getOperation()) {
708 default:
709 llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "bolt/lib/Core/BinaryFunction.cpp"
, 709)
;
710 case MCCFIInstruction::OpDefCfa:
711 setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, NewReg,
712 OldCFI->getOffset()));
713 break;
714 case MCCFIInstruction::OpDefCfaRegister:
715 setCFIFor(Instr, MCCFIInstruction::createDefCfaRegister(nullptr, NewReg));
716 break;
717 case MCCFIInstruction::OpOffset:
718 setCFIFor(Instr, MCCFIInstruction::createOffset(nullptr, NewReg,
719 OldCFI->getOffset()));
720 break;
721 case MCCFIInstruction::OpRegister:
722 setCFIFor(Instr, MCCFIInstruction::createRegister(nullptr, NewReg,
723 OldCFI->getRegister2()));
724 break;
725 case MCCFIInstruction::OpSameValue:
726 setCFIFor(Instr, MCCFIInstruction::createSameValue(nullptr, NewReg));
727 break;
728 case MCCFIInstruction::OpEscape:
729 setCFIFor(Instr,
730 MCCFIInstruction::createEscape(
731 nullptr,
732 StringRef(mutateDWARFExpressionTargetReg(*OldCFI, NewReg))));
733 break;
734 case MCCFIInstruction::OpRestore:
735 setCFIFor(Instr, MCCFIInstruction::createRestore(nullptr, NewReg));
736 break;
737 case MCCFIInstruction::OpUndefined:
738 setCFIFor(Instr, MCCFIInstruction::createUndefined(nullptr, NewReg));
739 break;
740 }
741}
742
743const MCCFIInstruction *BinaryFunction::mutateCFIOffsetFor(const MCInst &Instr,
744 int64_t NewOffset) {
745 const MCCFIInstruction *OldCFI = getCFIFor(Instr);
746 assert(OldCFI && "invalid CFI instr")(static_cast <bool> (OldCFI && "invalid CFI instr"
) ? void (0) : __assert_fail ("OldCFI && \"invalid CFI instr\""
, "bolt/lib/Core/BinaryFunction.cpp", 746, __extension__ __PRETTY_FUNCTION__
))
;
747 switch (OldCFI->getOperation()) {
748 default:
749 llvm_unreachable("Unexpected instruction")::llvm::llvm_unreachable_internal("Unexpected instruction", "bolt/lib/Core/BinaryFunction.cpp"
, 749)
;
750 case MCCFIInstruction::OpDefCfaOffset:
751 setCFIFor(Instr, MCCFIInstruction::cfiDefCfaOffset(nullptr, NewOffset));
752 break;
753 case MCCFIInstruction::OpAdjustCfaOffset:
754 setCFIFor(Instr,
755 MCCFIInstruction::createAdjustCfaOffset(nullptr, NewOffset));
756 break;
757 case MCCFIInstruction::OpDefCfa:
758 setCFIFor(Instr, MCCFIInstruction::cfiDefCfa(nullptr, OldCFI->getRegister(),
759 NewOffset));
760 break;
761 case MCCFIInstruction::OpOffset:
762 setCFIFor(Instr, MCCFIInstruction::createOffset(
763 nullptr, OldCFI->getRegister(), NewOffset));
764 break;
765 }
766 return getCFIFor(Instr);
767}
768
769IndirectBranchType
770BinaryFunction::processIndirectBranch(MCInst &Instruction, unsigned Size,
771 uint64_t Offset,
772 uint64_t &TargetAddress) {
773 const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();
774
775 // The instruction referencing memory used by the branch instruction.
776 // It could be the branch instruction itself or one of the instructions
777 // setting the value of the register used by the branch.
778 MCInst *MemLocInstr;
779
780 // Address of the table referenced by MemLocInstr. Could be either an
781 // array of function pointers, or a jump table.
782 uint64_t ArrayStart = 0;
783
784 unsigned BaseRegNum, IndexRegNum;
785 int64_t DispValue;
786 const MCExpr *DispExpr;
787
788 // In AArch, identify the instruction adding the PC-relative offset to
789 // jump table entries to correctly decode it.
790 MCInst *PCRelBaseInstr;
791 uint64_t PCRelAddr = 0;
792
793 auto Begin = Instructions.begin();
794 if (BC.isAArch64()) {
795 PreserveNops = BC.HasRelocations;
796 // Start at the last label as an approximation of the current basic block.
797 // This is a heuristic, since the full set of labels have yet to be
798 // determined
799 for (auto LI = Labels.rbegin(); LI != Labels.rend(); ++LI) {
800 auto II = Instructions.find(LI->first);
801 if (II != Instructions.end()) {
802 Begin = II;
803 break;
804 }
805 }
806 }
807
808 IndirectBranchType BranchType = BC.MIB->analyzeIndirectBranch(
809 Instruction, Begin, Instructions.end(), PtrSize, MemLocInstr, BaseRegNum,
810 IndexRegNum, DispValue, DispExpr, PCRelBaseInstr);
811
812 if (BranchType == IndirectBranchType::UNKNOWN && !MemLocInstr)
813 return BranchType;
814
815 if (MemLocInstr != &Instruction)
816 IndexRegNum = BC.MIB->getNoRegister();
817
818 if (BC.isAArch64()) {
819 const MCSymbol *Sym = BC.MIB->getTargetSymbol(*PCRelBaseInstr, 1);
820 assert(Sym && "Symbol extraction failed")(static_cast <bool> (Sym && "Symbol extraction failed"
) ? void (0) : __assert_fail ("Sym && \"Symbol extraction failed\""
, "bolt/lib/Core/BinaryFunction.cpp", 820, __extension__ __PRETTY_FUNCTION__
))
;
821 ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*Sym);
822 if (SymValueOrError) {
823 PCRelAddr = *SymValueOrError;
824 } else {
825 for (std::pair<const uint32_t, MCSymbol *> &Elmt : Labels) {
826 if (Elmt.second == Sym) {
827 PCRelAddr = Elmt.first + getAddress();
828 break;
829 }
830 }
831 }
832 uint64_t InstrAddr = 0;
833 for (auto II = Instructions.rbegin(); II != Instructions.rend(); ++II) {
834 if (&II->second == PCRelBaseInstr) {
835 InstrAddr = II->first + getAddress();
836 break;
837 }
838 }
839 assert(InstrAddr != 0 && "instruction not found")(static_cast <bool> (InstrAddr != 0 && "instruction not found"
) ? void (0) : __assert_fail ("InstrAddr != 0 && \"instruction not found\""
, "bolt/lib/Core/BinaryFunction.cpp", 839, __extension__ __PRETTY_FUNCTION__
))
;
840 // We do this to avoid spurious references to code locations outside this
841 // function (for example, if the indirect jump lives in the last basic
842 // block of the function, it will create a reference to the next function).
843 // This replaces a symbol reference with an immediate.
844 BC.MIB->replaceMemOperandDisp(*PCRelBaseInstr,
845 MCOperand::createImm(PCRelAddr - InstrAddr));
846 // FIXME: Disable full jump table processing for AArch64 until we have a
847 // proper way of determining the jump table limits.
848 return IndirectBranchType::UNKNOWN;
849 }
850
851 // RIP-relative addressing should be converted to symbol form by now
852 // in processed instructions (but not in jump).
853 if (DispExpr) {
854 const MCSymbol *TargetSym;
855 uint64_t TargetOffset;
856 std::tie(TargetSym, TargetOffset) = BC.MIB->getTargetSymbolInfo(DispExpr);
857 ErrorOr<uint64_t> SymValueOrError = BC.getSymbolValue(*TargetSym);
858 assert(SymValueOrError && "global symbol needs a value")(static_cast <bool> (SymValueOrError && "global symbol needs a value"
) ? void (0) : __assert_fail ("SymValueOrError && \"global symbol needs a value\""
, "bolt/lib/Core/BinaryFunction.cpp", 858, __extension__ __PRETTY_FUNCTION__
))
;
859 ArrayStart = *SymValueOrError + TargetOffset;
860 BaseRegNum = BC.MIB->getNoRegister();
861 if (BC.isAArch64()) {
862 ArrayStart &= ~0xFFFULL;
863 ArrayStart += DispValue & 0xFFFULL;
864 }
865 } else {
866 ArrayStart = static_cast<uint64_t>(DispValue);
867 }
868
869 if (BaseRegNum == BC.MRI->getProgramCounter())
870 ArrayStart += getAddress() + Offset + Size;
871
872 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: addressed memory is 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: addressed memory is 0x"
<< Twine::utohexstr(ArrayStart) << '\n'; } } while
(false)
873 << Twine::utohexstr(ArrayStart) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: addressed memory is 0x"
<< Twine::utohexstr(ArrayStart) << '\n'; } } while
(false)
;
874
875 ErrorOr<BinarySection &> Section = BC.getSectionForAddress(ArrayStart);
876 if (!Section) {
877 // No section - possibly an absolute address. Since we don't allow
878 // internal function addresses to escape the function scope - we
879 // consider it a tail call.
880 if (opts::Verbosity >= 1) {
881 errs() << "BOLT-WARNING: no section for address 0x"
882 << Twine::utohexstr(ArrayStart) << " referenced from function "
883 << *this << '\n';
884 }
885 return IndirectBranchType::POSSIBLE_TAIL_CALL;
886 }
887 if (Section->isVirtual()) {
888 // The contents are filled at runtime.
889 return IndirectBranchType::POSSIBLE_TAIL_CALL;
890 }
891
892 if (BranchType == IndirectBranchType::POSSIBLE_FIXED_BRANCH) {
893 ErrorOr<uint64_t> Value = BC.getPointerAtAddress(ArrayStart);
894 if (!Value)
895 return IndirectBranchType::UNKNOWN;
896
897 if (!BC.getSectionForAddress(ArrayStart)->isReadOnly())
898 return IndirectBranchType::UNKNOWN;
899
900 outs() << "BOLT-INFO: fixed indirect branch detected in " << *this
901 << " at 0x" << Twine::utohexstr(getAddress() + Offset)
902 << " referencing data at 0x" << Twine::utohexstr(ArrayStart)
903 << " the destination value is 0x" << Twine::utohexstr(*Value)
904 << '\n';
905
906 TargetAddress = *Value;
907 return BranchType;
908 }
909
910 // Check if there's already a jump table registered at this address.
911 MemoryContentsType MemType;
912 if (JumpTable *JT = BC.getJumpTableContainingAddress(ArrayStart)) {
913 switch (JT->Type) {
914 case JumpTable::JTT_NORMAL:
915 MemType = MemoryContentsType::POSSIBLE_JUMP_TABLE;
916 break;
917 case JumpTable::JTT_PIC:
918 MemType = MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE;
919 break;
920 }
921 } else {
922 MemType = BC.analyzeMemoryAt(ArrayStart, *this);
923 }
924
925 // Check that jump table type in instruction pattern matches memory contents.
926 JumpTable::JumpTableType JTType;
927 if (BranchType == IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE) {
928 if (MemType != MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
929 return IndirectBranchType::UNKNOWN;
930 JTType = JumpTable::JTT_PIC;
931 } else {
932 if (MemType == MemoryContentsType::POSSIBLE_PIC_JUMP_TABLE)
933 return IndirectBranchType::UNKNOWN;
934
935 if (MemType == MemoryContentsType::UNKNOWN)
936 return IndirectBranchType::POSSIBLE_TAIL_CALL;
937
938 BranchType = IndirectBranchType::POSSIBLE_JUMP_TABLE;
939 JTType = JumpTable::JTT_NORMAL;
940 }
941
942 // Convert the instruction into jump table branch.
943 const MCSymbol *JTLabel = BC.getOrCreateJumpTable(*this, ArrayStart, JTType);
944 BC.MIB->replaceMemOperandDisp(*MemLocInstr, JTLabel, BC.Ctx.get());
945 BC.MIB->setJumpTable(Instruction, ArrayStart, IndexRegNum);
946
947 JTSites.emplace_back(Offset, ArrayStart);
948
949 return BranchType;
950}
951
952MCSymbol *BinaryFunction::getOrCreateLocalLabel(uint64_t Address,
953 bool CreatePastEnd) {
954 const uint64_t Offset = Address - getAddress();
955
956 if ((Offset == getSize()) && CreatePastEnd)
957 return getFunctionEndLabel();
958
959 auto LI = Labels.find(Offset);
960 if (LI != Labels.end())
961 return LI->second;
962
963 // For AArch64, check if this address is part of a constant island.
964 if (BC.isAArch64()) {
965 if (MCSymbol *IslandSym = getOrCreateIslandAccess(Address))
966 return IslandSym;
967 }
968
969 MCSymbol *Label = BC.Ctx->createNamedTempSymbol();
970 Labels[Offset] = Label;
971
972 return Label;
973}
974
975ErrorOr<ArrayRef<uint8_t>> BinaryFunction::getData() const {
976 BinarySection &Section = *getOriginSection();
977 assert(Section.containsRange(getAddress(), getMaxSize()) &&(static_cast <bool> (Section.containsRange(getAddress()
, getMaxSize()) && "wrong section for function") ? void
(0) : __assert_fail ("Section.containsRange(getAddress(), getMaxSize()) && \"wrong section for function\""
, "bolt/lib/Core/BinaryFunction.cpp", 978, __extension__ __PRETTY_FUNCTION__
))
978 "wrong section for function")(static_cast <bool> (Section.containsRange(getAddress()
, getMaxSize()) && "wrong section for function") ? void
(0) : __assert_fail ("Section.containsRange(getAddress(), getMaxSize()) && \"wrong section for function\""
, "bolt/lib/Core/BinaryFunction.cpp", 978, __extension__ __PRETTY_FUNCTION__
))
;
979
980 if (!Section.isText() || Section.isVirtual() || !Section.getSize())
981 return std::make_error_code(std::errc::bad_address);
982
983 StringRef SectionContents = Section.getContents();
984
985 assert(SectionContents.size() == Section.getSize() &&(static_cast <bool> (SectionContents.size() == Section.
getSize() && "section size mismatch") ? void (0) : __assert_fail
("SectionContents.size() == Section.getSize() && \"section size mismatch\""
, "bolt/lib/Core/BinaryFunction.cpp", 986, __extension__ __PRETTY_FUNCTION__
))
986 "section size mismatch")(static_cast <bool> (SectionContents.size() == Section.
getSize() && "section size mismatch") ? void (0) : __assert_fail
("SectionContents.size() == Section.getSize() && \"section size mismatch\""
, "bolt/lib/Core/BinaryFunction.cpp", 986, __extension__ __PRETTY_FUNCTION__
))
;
987
988 // Function offset from the section start.
989 uint64_t Offset = getAddress() - Section.getAddress();
990 auto *Bytes = reinterpret_cast<const uint8_t *>(SectionContents.data());
991 return ArrayRef<uint8_t>(Bytes + Offset, getMaxSize());
992}
993
994size_t BinaryFunction::getSizeOfDataInCodeAt(uint64_t Offset) const {
995 if (!Islands)
996 return 0;
997
998 if (Islands->DataOffsets.find(Offset) == Islands->DataOffsets.end())
999 return 0;
1000
1001 auto Iter = Islands->CodeOffsets.upper_bound(Offset);
1002 if (Iter != Islands->CodeOffsets.end())
1003 return *Iter - Offset;
1004 return getSize() - Offset;
1005}
1006
1007bool BinaryFunction::isZeroPaddingAt(uint64_t Offset) const {
1008 ArrayRef<uint8_t> FunctionData = *getData();
1009 uint64_t EndOfCode = getSize();
1010 if (Islands) {
1011 auto Iter = Islands->DataOffsets.upper_bound(Offset);
1012 if (Iter != Islands->DataOffsets.end())
1013 EndOfCode = *Iter;
1014 }
1015 for (uint64_t I = Offset; I < EndOfCode; ++I)
1016 if (FunctionData[I] != 0)
1017 return false;
1018
1019 return true;
1020}
1021
1022void BinaryFunction::handlePCRelOperand(MCInst &Instruction, uint64_t Address,
1023 uint64_t Size) {
1024 auto &MIB = BC.MIB;
1025 uint64_t TargetAddress = 0;
1026 if (!MIB->evaluateMemOperandTarget(Instruction, TargetAddress, Address,
1027 Size)) {
1028 errs() << "BOLT-ERROR: PC-relative operand can't be evaluated:\n";
1029 BC.InstPrinter->printInst(&Instruction, 0, "", *BC.STI, errs());
1030 errs() << '\n';
1031 Instruction.dump_pretty(errs(), BC.InstPrinter.get());
1032 errs() << '\n';
1033 errs() << "BOLT-ERROR: cannot handle PC-relative operand at 0x"
1034 << Twine::utohexstr(Address) << ". Skipping function " << *this
1035 << ".\n";
1036 if (BC.HasRelocations)
1037 exit(1);
1038 IsSimple = false;
1039 return;
1040 }
1041 if (TargetAddress == 0 && opts::Verbosity >= 1) {
1042 outs() << "BOLT-INFO: PC-relative operand is zero in function " << *this
1043 << '\n';
1044 }
1045
1046 const MCSymbol *TargetSymbol;
1047 uint64_t TargetOffset;
1048 std::tie(TargetSymbol, TargetOffset) =
1049 BC.handleAddressRef(TargetAddress, *this, /*IsPCRel*/ true);
1050
1051 bool ReplaceSuccess = MIB->replaceMemOperandDisp(
1052 Instruction, TargetSymbol, static_cast<int64_t>(TargetOffset), &*BC.Ctx);
1053 (void)ReplaceSuccess;
1054 assert(ReplaceSuccess && "Failed to replace mem operand with symbol+off.")(static_cast <bool> (ReplaceSuccess && "Failed to replace mem operand with symbol+off."
) ? void (0) : __assert_fail ("ReplaceSuccess && \"Failed to replace mem operand with symbol+off.\""
, "bolt/lib/Core/BinaryFunction.cpp", 1054, __extension__ __PRETTY_FUNCTION__
))
;
1055}
1056
1057MCSymbol *BinaryFunction::handleExternalReference(MCInst &Instruction,
1058 uint64_t Size,
1059 uint64_t Offset,
1060 uint64_t TargetAddress,
1061 bool &IsCall) {
1062 auto &MIB = BC.MIB;
1063
1064 const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1065 BC.addInterproceduralReference(this, TargetAddress);
1066 if (opts::Verbosity >= 2 && !IsCall && Size == 2 && !BC.HasRelocations) {
1067 errs() << "BOLT-WARNING: relaxed tail call detected at 0x"
1068 << Twine::utohexstr(AbsoluteInstrAddr) << " in function " << *this
1069 << ". Code size will be increased.\n";
1070 }
1071
1072 assert(!MIB->isTailCall(Instruction) &&(static_cast <bool> (!MIB->isTailCall(Instruction) &&
"synthetic tail call instruction found") ? void (0) : __assert_fail
("!MIB->isTailCall(Instruction) && \"synthetic tail call instruction found\""
, "bolt/lib/Core/BinaryFunction.cpp", 1073, __extension__ __PRETTY_FUNCTION__
))
1073 "synthetic tail call instruction found")(static_cast <bool> (!MIB->isTailCall(Instruction) &&
"synthetic tail call instruction found") ? void (0) : __assert_fail
("!MIB->isTailCall(Instruction) && \"synthetic tail call instruction found\""
, "bolt/lib/Core/BinaryFunction.cpp", 1073, __extension__ __PRETTY_FUNCTION__
))
;
1074
1075 // This is a call regardless of the opcode.
1076 // Assign proper opcode for tail calls, so that they could be
1077 // treated as calls.
1078 if (!IsCall) {
1079 if (!MIB->convertJmpToTailCall(Instruction)) {
1080 assert(MIB->isConditionalBranch(Instruction) &&(static_cast <bool> (MIB->isConditionalBranch(Instruction
) && "unknown tail call instruction") ? void (0) : __assert_fail
("MIB->isConditionalBranch(Instruction) && \"unknown tail call instruction\""
, "bolt/lib/Core/BinaryFunction.cpp", 1081, __extension__ __PRETTY_FUNCTION__
))
1081 "unknown tail call instruction")(static_cast <bool> (MIB->isConditionalBranch(Instruction
) && "unknown tail call instruction") ? void (0) : __assert_fail
("MIB->isConditionalBranch(Instruction) && \"unknown tail call instruction\""
, "bolt/lib/Core/BinaryFunction.cpp", 1081, __extension__ __PRETTY_FUNCTION__
))
;
1082 if (opts::Verbosity >= 2) {
1083 errs() << "BOLT-WARNING: conditional tail call detected in "
1084 << "function " << *this << " at 0x"
1085 << Twine::utohexstr(AbsoluteInstrAddr) << ".\n";
1086 }
1087 }
1088 IsCall = true;
1089 }
1090
1091 if (opts::Verbosity >= 2 && TargetAddress == 0) {
1092 // We actually see calls to address 0 in presence of weak
1093 // symbols originating from libraries. This code is never meant
1094 // to be executed.
1095 outs() << "BOLT-INFO: Function " << *this
1096 << " has a call to address zero.\n";
1097 }
1098
1099 return BC.getOrCreateGlobalSymbol(TargetAddress, "FUNCat");
1100}
1101
1102void BinaryFunction::handleIndirectBranch(MCInst &Instruction, uint64_t Size,
1103 uint64_t Offset) {
1104 auto &MIB = BC.MIB;
1105 uint64_t IndirectTarget = 0;
1106 IndirectBranchType Result =
1107 processIndirectBranch(Instruction, Size, Offset, IndirectTarget);
1108 switch (Result) {
1109 default:
1110 llvm_unreachable("unexpected result")::llvm::llvm_unreachable_internal("unexpected result", "bolt/lib/Core/BinaryFunction.cpp"
, 1110)
;
1111 case IndirectBranchType::POSSIBLE_TAIL_CALL: {
1112 bool Result = MIB->convertJmpToTailCall(Instruction);
1113 (void)Result;
1114 assert(Result)(static_cast <bool> (Result) ? void (0) : __assert_fail
("Result", "bolt/lib/Core/BinaryFunction.cpp", 1114, __extension__
__PRETTY_FUNCTION__))
;
1115 break;
1116 }
1117 case IndirectBranchType::POSSIBLE_JUMP_TABLE:
1118 case IndirectBranchType::POSSIBLE_PIC_JUMP_TABLE:
1119 if (opts::JumpTables == JTS_NONE)
1120 IsSimple = false;
1121 break;
1122 case IndirectBranchType::POSSIBLE_FIXED_BRANCH: {
1123 if (containsAddress(IndirectTarget)) {
1124 const MCSymbol *TargetSymbol = getOrCreateLocalLabel(IndirectTarget);
1125 Instruction.clear();
1126 MIB->createUncondBranch(Instruction, TargetSymbol, BC.Ctx.get());
1127 TakenBranches.emplace_back(Offset, IndirectTarget - getAddress());
1128 HasFixedIndirectBranch = true;
1129 } else {
1130 MIB->convertJmpToTailCall(Instruction);
1131 BC.addInterproceduralReference(this, IndirectTarget);
1132 }
1133 break;
1134 }
1135 case IndirectBranchType::UNKNOWN:
1136 // Keep processing. We'll do more checks and fixes in
1137 // postProcessIndirectBranches().
1138 UnknownIndirectBranchOffsets.emplace(Offset);
1139 break;
1140 }
1141}
1142
1143void BinaryFunction::handleAArch64IndirectCall(MCInst &Instruction,
1144 const uint64_t Offset) {
1145 auto &MIB = BC.MIB;
1146 const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1147 MCInst *TargetHiBits, *TargetLowBits;
1148 uint64_t TargetAddress, Count;
1149 Count = MIB->matchLinkerVeneer(Instructions.begin(), Instructions.end(),
1150 AbsoluteInstrAddr, Instruction, TargetHiBits,
1151 TargetLowBits, TargetAddress);
1152 if (Count) {
1153 MIB->addAnnotation(Instruction, "AArch64Veneer", true);
1154 --Count;
1155 for (auto It = std::prev(Instructions.end()); Count != 0;
1156 It = std::prev(It), --Count) {
1157 MIB->addAnnotation(It->second, "AArch64Veneer", true);
1158 }
1159
1160 BC.addAdrpAddRelocAArch64(*this, *TargetLowBits, *TargetHiBits,
1161 TargetAddress);
1162 }
1163}
1164
1165bool BinaryFunction::disassemble() {
1166 NamedRegionTimer T("disassemble", "Disassemble function", "buildfuncs",
1167 "Build Binary Functions", opts::TimeBuild);
1168 ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
1169 assert(ErrorOrFunctionData && "function data is not available")(static_cast <bool> (ErrorOrFunctionData && "function data is not available"
) ? void (0) : __assert_fail ("ErrorOrFunctionData && \"function data is not available\""
, "bolt/lib/Core/BinaryFunction.cpp", 1169, __extension__ __PRETTY_FUNCTION__
))
;
1170 ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
1171 assert(FunctionData.size() == getMaxSize() &&(static_cast <bool> (FunctionData.size() == getMaxSize(
) && "function size does not match raw data size") ? void
(0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\""
, "bolt/lib/Core/BinaryFunction.cpp", 1172, __extension__ __PRETTY_FUNCTION__
))
1172 "function size does not match raw data size")(static_cast <bool> (FunctionData.size() == getMaxSize(
) && "function size does not match raw data size") ? void
(0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\""
, "bolt/lib/Core/BinaryFunction.cpp", 1172, __extension__ __PRETTY_FUNCTION__
))
;
1173
1174 auto &Ctx = BC.Ctx;
1175 auto &MIB = BC.MIB;
1176
1177 BC.SymbolicDisAsm->setSymbolizer(MIB->createTargetSymbolizer(*this));
1178
1179 // Insert a label at the beginning of the function. This will be our first
1180 // basic block.
1181 Labels[0] = Ctx->createNamedTempSymbol("BB0");
1182
1183 uint64_t Size = 0; // instruction size
1184 for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
1185 MCInst Instruction;
1186 const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1187
1188 // Check for data inside code and ignore it
1189 if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
1190 Size = DataInCodeSize;
1191 continue;
1192 }
1193
1194 if (!BC.SymbolicDisAsm->getInstruction(Instruction, Size,
1195 FunctionData.slice(Offset),
1196 AbsoluteInstrAddr, nulls())) {
1197 // Functions with "soft" boundaries, e.g. coming from assembly source,
1198 // can have 0-byte padding at the end.
1199 if (isZeroPaddingAt(Offset))
1200 break;
1201
1202 errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x"
1203 << Twine::utohexstr(Offset) << " (address 0x"
1204 << Twine::utohexstr(AbsoluteInstrAddr) << ") in function " << *this
1205 << '\n';
1206 // Some AVX-512 instructions could not be disassembled at all.
1207 if (BC.HasRelocations && opts::TrapOnAVX512 && BC.isX86()) {
1208 setTrapOnEntry();
1209 BC.TrappedFunctions.push_back(this);
1210 } else {
1211 setIgnored();
1212 }
1213
1214 break;
1215 }
1216
1217 // Check integrity of LLVM assembler/disassembler.
1218 if (opts::CheckEncoding && !BC.MIB->isBranch(Instruction) &&
1219 !BC.MIB->isCall(Instruction) && !BC.MIB->isNoop(Instruction)) {
1220 if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) {
1221 errs() << "BOLT-WARNING: mismatching LLVM encoding detected in "
1222 << "function " << *this << " for instruction :\n";
1223 BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr);
1224 errs() << '\n';
1225 }
1226 }
1227
1228 // Special handling for AVX-512 instructions.
1229 if (MIB->hasEVEXEncoding(Instruction)) {
1230 if (BC.HasRelocations && opts::TrapOnAVX512) {
1231 setTrapOnEntry();
1232 BC.TrappedFunctions.push_back(this);
1233 break;
1234 }
1235
1236 if (!BC.validateInstructionEncoding(FunctionData.slice(Offset, Size))) {
1237 errs() << "BOLT-WARNING: internal assembler/disassembler error "
1238 "detected for AVX512 instruction:\n";
1239 BC.printInstruction(errs(), Instruction, AbsoluteInstrAddr);
1240 errs() << " in function " << *this << '\n';
1241 setIgnored();
1242 break;
1243 }
1244 }
1245
1246 if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
1247 uint64_t TargetAddress = 0;
1248 if (MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size,
1249 TargetAddress)) {
1250 // Check if the target is within the same function. Otherwise it's
1251 // a call, possibly a tail call.
1252 //
1253 // If the target *is* the function address it could be either a branch
1254 // or a recursive call.
1255 bool IsCall = MIB->isCall(Instruction);
1256 const bool IsCondBranch = MIB->isConditionalBranch(Instruction);
1257 MCSymbol *TargetSymbol = nullptr;
1258
1259 if (BC.MIB->isUnsupportedBranch(Instruction.getOpcode())) {
1260 setIgnored();
1261 if (BinaryFunction *TargetFunc =
1262 BC.getBinaryFunctionContainingAddress(TargetAddress))
1263 TargetFunc->setIgnored();
1264 }
1265
1266 if (IsCall && containsAddress(TargetAddress)) {
1267 if (TargetAddress == getAddress()) {
1268 // Recursive call.
1269 TargetSymbol = getSymbol();
1270 } else {
1271 if (BC.isX86()) {
1272 // Dangerous old-style x86 PIC code. We may need to freeze this
1273 // function, so preserve the function as is for now.
1274 PreserveNops = true;
1275 } else {
1276 errs() << "BOLT-WARNING: internal call detected at 0x"
1277 << Twine::utohexstr(AbsoluteInstrAddr) << " in function "
1278 << *this << ". Skipping.\n";
1279 IsSimple = false;
1280 }
1281 }
1282 }
1283
1284 if (!TargetSymbol) {
1285 // Create either local label or external symbol.
1286 if (containsAddress(TargetAddress)) {
1287 TargetSymbol = getOrCreateLocalLabel(TargetAddress);
1288 } else {
1289 if (TargetAddress == getAddress() + getSize() &&
1290 TargetAddress < getAddress() + getMaxSize() &&
1291 !(BC.isAArch64() &&
1292 BC.handleAArch64Veneer(TargetAddress, /*MatchOnly*/ true))) {
1293 // Result of __builtin_unreachable().
1294 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: jump past end detected at 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
<< Twine::utohexstr(AbsoluteInstrAddr) << " in function "
<< *this << " : replacing with nop.\n"; } } while
(false)
1295 << Twine::utohexstr(AbsoluteInstrAddr)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
<< Twine::utohexstr(AbsoluteInstrAddr) << " in function "
<< *this << " : replacing with nop.\n"; } } while
(false)
1296 << " in function " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
<< Twine::utohexstr(AbsoluteInstrAddr) << " in function "
<< *this << " : replacing with nop.\n"; } } while
(false)
1297 << " : replacing with nop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: jump past end detected at 0x"
<< Twine::utohexstr(AbsoluteInstrAddr) << " in function "
<< *this << " : replacing with nop.\n"; } } while
(false)
;
1298 BC.MIB->createNoop(Instruction);
1299 if (IsCondBranch) {
1300 // Register branch offset for profile validation.
1301 IgnoredBranches.emplace_back(Offset, Offset + Size);
1302 }
1303 goto add_instruction;
1304 }
1305 // May update Instruction and IsCall
1306 TargetSymbol = handleExternalReference(Instruction, Size, Offset,
1307 TargetAddress, IsCall);
1308 }
1309 }
1310
1311 if (!IsCall) {
1312 // Add taken branch info.
1313 TakenBranches.emplace_back(Offset, TargetAddress - getAddress());
1314 }
1315 BC.MIB->replaceBranchTarget(Instruction, TargetSymbol, &*Ctx);
1316
1317 // Mark CTC.
1318 if (IsCondBranch && IsCall)
1319 MIB->setConditionalTailCall(Instruction, TargetAddress);
1320 } else {
1321 // Could not evaluate branch. Should be an indirect call or an
1322 // indirect branch. Bail out on the latter case.
1323 if (MIB->isIndirectBranch(Instruction))
1324 handleIndirectBranch(Instruction, Size, Offset);
1325 // Indirect call. We only need to fix it if the operand is RIP-relative.
1326 if (IsSimple && MIB->hasPCRelOperand(Instruction))
1327 handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);
1328
1329 if (BC.isAArch64())
1330 handleAArch64IndirectCall(Instruction, Offset);
1331 }
1332 } else if (BC.isAArch64()) {
1333 // Check if there's a relocation associated with this instruction.
1334 bool UsedReloc = false;
1335 for (auto Itr = Relocations.lower_bound(Offset),
1336 ItrE = Relocations.lower_bound(Offset + Size);
1337 Itr != ItrE; ++Itr) {
1338 const Relocation &Relocation = Itr->second;
1339 int64_t Value = Relocation.Value;
1340 const bool Result = BC.MIB->replaceImmWithSymbolRef(
1341 Instruction, Relocation.Symbol, Relocation.Addend, Ctx.get(), Value,
1342 Relocation.Type);
1343 (void)Result;
1344 assert(Result && "cannot replace immediate with relocation")(static_cast <bool> (Result && "cannot replace immediate with relocation"
) ? void (0) : __assert_fail ("Result && \"cannot replace immediate with relocation\""
, "bolt/lib/Core/BinaryFunction.cpp", 1344, __extension__ __PRETTY_FUNCTION__
))
;
1345
1346 // For aarch64, if we replaced an immediate with a symbol from a
1347 // relocation, we mark it so we do not try to further process a
1348 // pc-relative operand. All we need is the symbol.
1349 UsedReloc = true;
1350 }
1351
1352 if (MIB->hasPCRelOperand(Instruction) && !UsedReloc)
1353 handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);
1354 }
1355
1356add_instruction:
1357 if (getDWARFLineTable()) {
1358 Instruction.setLoc(findDebugLineInformationForInstructionAt(
1359 AbsoluteInstrAddr, getDWARFUnit(), getDWARFLineTable()));
1360 }
1361
1362 // Record offset of the instruction for profile matching.
1363 if (BC.keepOffsetForInstruction(Instruction))
1364 MIB->setOffset(Instruction, static_cast<uint32_t>(Offset));
1365
1366 if (BC.MIB->isNoop(Instruction)) {
1367 // NOTE: disassembly loses the correct size information for noops.
1368 // E.g. nopw 0x0(%rax,%rax,1) is 9 bytes, but re-encoded it's only
1369 // 5 bytes. Preserve the size info using annotations.
1370 MIB->addAnnotation(Instruction, "Size", static_cast<uint32_t>(Size));
1371 }
1372
1373 addInstruction(Offset, std::move(Instruction));
1374 }
1375
1376 // Reset symbolizer for the disassembler.
1377 BC.SymbolicDisAsm->setSymbolizer(nullptr);
1378
1379 if (uint64_t Offset = getFirstInstructionOffset())
1380 Labels[Offset] = BC.Ctx->createNamedTempSymbol();
1381
1382 clearList(Relocations);
1383
1384 if (!IsSimple) {
1385 clearList(Instructions);
1386 return false;
1387 }
1388
1389 updateState(State::Disassembled);
1390
1391 return true;
1392}
1393
1394bool BinaryFunction::scanExternalRefs() {
1395 bool Success = true;
1396 bool DisassemblyFailed = false;
1397
1398 // Ignore pseudo functions.
1399 if (isPseudo())
1400 return Success;
1401
1402 if (opts::NoScan) {
1403 clearList(Relocations);
1404 clearList(ExternallyReferencedOffsets);
1405
1406 return false;
1407 }
1408
1409 // List of external references for this function.
1410 std::vector<Relocation> FunctionRelocations;
1411
1412 static BinaryContext::IndependentCodeEmitter Emitter =
1413 BC.createIndependentMCCodeEmitter();
1414
1415 ErrorOr<ArrayRef<uint8_t>> ErrorOrFunctionData = getData();
1416 assert(ErrorOrFunctionData && "function data is not available")(static_cast <bool> (ErrorOrFunctionData && "function data is not available"
) ? void (0) : __assert_fail ("ErrorOrFunctionData && \"function data is not available\""
, "bolt/lib/Core/BinaryFunction.cpp", 1416, __extension__ __PRETTY_FUNCTION__
))
;
1417 ArrayRef<uint8_t> FunctionData = *ErrorOrFunctionData;
1418 assert(FunctionData.size() == getMaxSize() &&(static_cast <bool> (FunctionData.size() == getMaxSize(
) && "function size does not match raw data size") ? void
(0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\""
, "bolt/lib/Core/BinaryFunction.cpp", 1419, __extension__ __PRETTY_FUNCTION__
))
1419 "function size does not match raw data size")(static_cast <bool> (FunctionData.size() == getMaxSize(
) && "function size does not match raw data size") ? void
(0) : __assert_fail ("FunctionData.size() == getMaxSize() && \"function size does not match raw data size\""
, "bolt/lib/Core/BinaryFunction.cpp", 1419, __extension__ __PRETTY_FUNCTION__
))
;
1420
1421 uint64_t Size = 0; // instruction size
1422 for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
1423 // Check for data inside code and ignore it
1424 if (const size_t DataInCodeSize = getSizeOfDataInCodeAt(Offset)) {
1425 Size = DataInCodeSize;
1426 continue;
1427 }
1428
1429 const uint64_t AbsoluteInstrAddr = getAddress() + Offset;
1430 MCInst Instruction;
1431 if (!BC.DisAsm->getInstruction(Instruction, Size,
1432 FunctionData.slice(Offset),
1433 AbsoluteInstrAddr, nulls())) {
1434 if (opts::Verbosity >= 1 && !isZeroPaddingAt(Offset)) {
1435 errs() << "BOLT-WARNING: unable to disassemble instruction at offset 0x"
1436 << Twine::utohexstr(Offset) << " (address 0x"
1437 << Twine::utohexstr(AbsoluteInstrAddr) << ") in function "
1438 << *this << '\n';
1439 }
1440 Success = false;
1441 DisassemblyFailed = true;
1442 break;
1443 }
1444
1445 // Return true if we can skip handling the Target function reference.
1446 auto ignoreFunctionRef = [&](const BinaryFunction &Target) {
1447 if (&Target == this)
1448 return true;
1449
1450 // Note that later we may decide not to emit Target function. In that
1451 // case, we conservatively create references that will be ignored or
1452 // resolved to the same function.
1453 if (!BC.shouldEmit(Target))
1454 return true;
1455
1456 return false;
1457 };
1458
1459 // Return true if we can ignore reference to the symbol.
1460 auto ignoreReference = [&](const MCSymbol *TargetSymbol) {
1461 if (!TargetSymbol)
1462 return true;
1463
1464 if (BC.forceSymbolRelocations(TargetSymbol->getName()))
1465 return false;
1466
1467 BinaryFunction *TargetFunction = BC.getFunctionForSymbol(TargetSymbol);
1468 if (!TargetFunction)
1469 return true;
1470
1471 return ignoreFunctionRef(*TargetFunction);
1472 };
1473
1474 // Detect if the instruction references an address.
1475 // Without relocations, we can only trust PC-relative address modes.
1476 uint64_t TargetAddress = 0;
1477 bool IsPCRel = false;
1478 bool IsBranch = false;
1479 if (BC.MIB->hasPCRelOperand(Instruction)) {
1480 IsPCRel = BC.MIB->evaluateMemOperandTarget(Instruction, TargetAddress,
1481 AbsoluteInstrAddr, Size);
1482 } else if (BC.MIB->isCall(Instruction) || BC.MIB->isBranch(Instruction)) {
1483 IsBranch = BC.MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size,
1484 TargetAddress);
1485 }
1486
1487 MCSymbol *TargetSymbol = nullptr;
1488
1489 // Create an entry point at reference address if needed.
1490 BinaryFunction *TargetFunction =
1491 BC.getBinaryFunctionContainingAddress(TargetAddress);
1492 if (TargetFunction && !ignoreFunctionRef(*TargetFunction)) {
1493 const uint64_t FunctionOffset =
1494 TargetAddress - TargetFunction->getAddress();
1495 TargetSymbol = FunctionOffset
1496 ? TargetFunction->addEntryPointAtOffset(FunctionOffset)
1497 : TargetFunction->getSymbol();
1498 }
1499
1500 // Can't find more references and not creating relocations.
1501 if (!BC.HasRelocations)
1502 continue;
1503
1504 // Create a relocation against the TargetSymbol as the symbol might get
1505 // moved.
1506 if (TargetSymbol) {
1507 if (IsBranch) {
1508 BC.MIB->replaceBranchTarget(Instruction, TargetSymbol,
1509 Emitter.LocalCtx.get());
1510 } else if (IsPCRel) {
1511 const MCExpr *Expr = MCSymbolRefExpr::create(
1512 TargetSymbol, MCSymbolRefExpr::VK_None, *Emitter.LocalCtx.get());
1513 BC.MIB->replaceMemOperandDisp(
1514 Instruction, MCOperand::createExpr(BC.MIB->getTargetExprFor(
1515 Instruction, Expr, *Emitter.LocalCtx.get(), 0)));
1516 }
1517 }
1518
1519 // Create more relocations based on input file relocations.
1520 bool HasRel = false;
1521 for (auto Itr = Relocations.lower_bound(Offset),
1522 ItrE = Relocations.lower_bound(Offset + Size);
1523 Itr != ItrE; ++Itr) {
1524 Relocation &Relocation = Itr->second;
1525 if (Relocation.isPCRelative() && BC.isX86())
1526 continue;
1527 if (ignoreReference(Relocation.Symbol))
1528 continue;
1529
1530 int64_t Value = Relocation.Value;
1531 const bool Result = BC.MIB->replaceImmWithSymbolRef(
1532 Instruction, Relocation.Symbol, Relocation.Addend,
1533 Emitter.LocalCtx.get(), Value, Relocation.Type);
1534 (void)Result;
1535 assert(Result && "cannot replace immediate with relocation")(static_cast <bool> (Result && "cannot replace immediate with relocation"
) ? void (0) : __assert_fail ("Result && \"cannot replace immediate with relocation\""
, "bolt/lib/Core/BinaryFunction.cpp", 1535, __extension__ __PRETTY_FUNCTION__
))
;
1536
1537 HasRel = true;
1538 }
1539
1540 if (!TargetSymbol && !HasRel)
1541 continue;
1542
1543 // Emit the instruction using temp emitter and generate relocations.
1544 SmallString<256> Code;
1545 SmallVector<MCFixup, 4> Fixups;
1546 raw_svector_ostream VecOS(Code);
1547 Emitter.MCE->encodeInstruction(Instruction, VecOS, Fixups, *BC.STI);
1548
1549 // Create relocation for every fixup.
1550 for (const MCFixup &Fixup : Fixups) {
1551 Optional<Relocation> Rel = BC.MIB->createRelocation(Fixup, *BC.MAB);
1552 if (!Rel) {
1553 Success = false;
1554 continue;
1555 }
1556
1557 if (Relocation::getSizeForType(Rel->Type) < 4) {
1558 // If the instruction uses a short form, then we might not be able
1559 // to handle the rewrite without relaxation, and hence cannot reliably
1560 // create an external reference relocation.
1561 Success = false;
1562 continue;
1563 }
1564 Rel->Offset += getAddress() - getOriginSection()->getAddress() + Offset;
1565 FunctionRelocations.push_back(*Rel);
1566 }
1567
1568 if (!Success)
1569 break;
1570 }
1571
1572 // Add relocations unless disassembly failed for this function.
1573 if (!DisassemblyFailed)
1574 for (Relocation &Rel : FunctionRelocations)
1575 getOriginSection()->addPendingRelocation(Rel);
1576
1577 // Inform BinaryContext that this function symbols will not be defined and
1578 // relocations should not be created against them.
1579 if (BC.HasRelocations) {
1580 for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
1581 BC.UndefinedSymbols.insert(LI.second);
1582 for (MCSymbol *const EndLabel : FunctionEndLabels)
1583 if (EndLabel)
1584 BC.UndefinedSymbols.insert(EndLabel);
1585 }
1586
1587 clearList(Relocations);
1588 clearList(ExternallyReferencedOffsets);
1589
1590 if (Success && BC.HasRelocations)
1591 HasExternalRefRelocations = true;
1592
1593 if (opts::Verbosity >= 1 && !Success)
1594 outs() << "BOLT-INFO: failed to scan refs for " << *this << '\n';
1595
1596 return Success;
1597}
1598
1599void BinaryFunction::postProcessEntryPoints() {
1600 if (!isSimple())
1601 return;
1602
1603 for (auto &KV : Labels) {
1604 MCSymbol *Label = KV.second;
1605 if (!getSecondaryEntryPointSymbol(Label))
1606 continue;
1607
1608 // In non-relocation mode there's potentially an external undetectable
1609 // reference to the entry point and hence we cannot move this entry
1610 // point. Optimizing without moving could be difficult.
1611 if (!BC.HasRelocations)
1612 setSimple(false);
1613
1614 const uint32_t Offset = KV.first;
1615
1616 // If we are at Offset 0 and there is no instruction associated with it,
1617 // this means this is an empty function. Just ignore. If we find an
1618 // instruction at this offset, this entry point is valid.
1619 if (!Offset || getInstructionAtOffset(Offset))
1620 continue;
1621
1622 // On AArch64 there are legitimate reasons to have references past the
1623 // end of the function, e.g. jump tables.
1624 if (BC.isAArch64() && Offset == getSize())
1625 continue;
1626
1627 errs() << "BOLT-WARNING: reference in the middle of instruction "
1628 "detected in function "
1629 << *this << " at offset 0x" << Twine::utohexstr(Offset) << '\n';
1630 if (BC.HasRelocations)
1631 setIgnored();
1632 setSimple(false);
1633 return;
1634 }
1635}
1636
1637void BinaryFunction::postProcessJumpTables() {
1638 // Create labels for all entries.
1639 for (auto &JTI : JumpTables) {
1640 JumpTable &JT = *JTI.second;
1641 if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) {
1642 opts::JumpTables = JTS_MOVE;
1643 outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was "
1644 "detected in function "
1645 << *this << '\n';
1646 }
1647 if (JT.Entries.empty()) {
1648 bool HasOneParent = (JT.Parents.size() == 1);
1649 for (unsigned I = 0; I < JT.EntriesAsAddress.size(); ++I) {
1650 uint64_t EntryAddress = JT.EntriesAsAddress[I];
1651 // builtin_unreachable does not belong to any function
1652 // Need to handle separately
1653 bool IsBuiltIn = false;
1654 for (BinaryFunction *Parent : JT.Parents) {
1655 if (EntryAddress == Parent->getAddress() + Parent->getSize()) {
1656 IsBuiltIn = true;
1657 // Specify second parameter as true to accept builtin_unreachable
1658 MCSymbol *Label = getOrCreateLocalLabel(EntryAddress, true);
1659 JT.Entries.push_back(Label);
1660 break;
1661 }
1662 }
1663 if (IsBuiltIn)
1664 continue;
1665 // Create local label for targets cannot be reached by other fragments
1666 // Otherwise, secondary entry point to target function
1667 BinaryFunction *TargetBF =
1668 BC.getBinaryFunctionContainingAddress(EntryAddress);
1669 if (TargetBF->getAddress() != EntryAddress) {
1670 MCSymbol *Label =
1671 (HasOneParent && TargetBF == this)
1672 ? getOrCreateLocalLabel(JT.EntriesAsAddress[I], true)
1673 : TargetBF->addEntryPointAtOffset(EntryAddress -
1674 TargetBF->getAddress());
1675 JT.Entries.push_back(Label);
1676 }
1677 }
1678 }
1679
1680 const uint64_t BDSize =
1681 BC.getBinaryDataAtAddress(JT.getAddress())->getSize();
1682 if (!BDSize) {
1683 BC.setBinaryDataSize(JT.getAddress(), JT.getSize());
1684 } else {
1685 assert(BDSize >= JT.getSize() &&(static_cast <bool> (BDSize >= JT.getSize() &&
"jump table cannot be larger than the containing object") ? void
(0) : __assert_fail ("BDSize >= JT.getSize() && \"jump table cannot be larger than the containing object\""
, "bolt/lib/Core/BinaryFunction.cpp", 1686, __extension__ __PRETTY_FUNCTION__
))
1686 "jump table cannot be larger than the containing object")(static_cast <bool> (BDSize >= JT.getSize() &&
"jump table cannot be larger than the containing object") ? void
(0) : __assert_fail ("BDSize >= JT.getSize() && \"jump table cannot be larger than the containing object\""
, "bolt/lib/Core/BinaryFunction.cpp", 1686, __extension__ __PRETTY_FUNCTION__
))
;
1687 }
1688 }
1689
1690 // Add TakenBranches from JumpTables.
1691 //
1692 // We want to do it after initial processing since we don't know jump tables'
1693 // boundaries until we process them all.
1694 for (auto &JTSite : JTSites) {
1695 const uint64_t JTSiteOffset = JTSite.first;
1696 const uint64_t JTAddress = JTSite.second;
1697 const JumpTable *JT = getJumpTableContainingAddress(JTAddress);
1698 assert(JT && "cannot find jump table for address")(static_cast <bool> (JT && "cannot find jump table for address"
) ? void (0) : __assert_fail ("JT && \"cannot find jump table for address\""
, "bolt/lib/Core/BinaryFunction.cpp", 1698, __extension__ __PRETTY_FUNCTION__
))
;
1699
1700 uint64_t EntryOffset = JTAddress - JT->getAddress();
1701 while (EntryOffset < JT->getSize()) {
1702 uint64_t EntryAddress = JT->EntriesAsAddress[EntryOffset / JT->EntrySize];
1703 uint64_t TargetOffset = EntryAddress - getAddress();
1704 if (TargetOffset < getSize()) {
1705 TakenBranches.emplace_back(JTSiteOffset, TargetOffset);
1706
1707 if (opts::StrictMode)
1708 registerReferencedOffset(TargetOffset);
1709 }
1710
1711 EntryOffset += JT->EntrySize;
1712
1713 // A label at the next entry means the end of this jump table.
1714 if (JT->Labels.count(EntryOffset))
1715 break;
1716 }
1717 }
1718 clearList(JTSites);
1719
1720 // Conservatively populate all possible destinations for unknown indirect
1721 // branches.
1722 if (opts::StrictMode && hasInternalReference()) {
1723 for (uint64_t Offset : UnknownIndirectBranchOffsets) {
1724 for (uint64_t PossibleDestination : ExternallyReferencedOffsets) {
1725 // Ignore __builtin_unreachable().
1726 if (PossibleDestination == getSize())
1727 continue;
1728 TakenBranches.emplace_back(Offset, PossibleDestination);
1729 }
1730 }
1731 }
1732
1733 // Remove duplicates branches. We can get a bunch of them from jump tables.
1734 // Without doing jump table value profiling we don't have use for extra
1735 // (duplicate) branches.
1736 llvm::sort(TakenBranches);
1737 auto NewEnd = std::unique(TakenBranches.begin(), TakenBranches.end());
1738 TakenBranches.erase(NewEnd, TakenBranches.end());
1739}
1740
1741bool BinaryFunction::validateExternallyReferencedOffsets() {
1742 SmallPtrSet<MCSymbol *, 4> JTTargets;
1743 for (const JumpTable *JT : llvm::make_second_range(JumpTables))
1744 JTTargets.insert(JT->Entries.begin(), JT->Entries.end());
1745
1746 bool HasUnclaimedReference = false;
1747 for (uint64_t Destination : ExternallyReferencedOffsets) {
1748 // Ignore __builtin_unreachable().
1749 if (Destination == getSize())
1750 continue;
1751 // Ignore constant islands
1752 if (isInConstantIsland(Destination + getAddress()))
1753 continue;
1754
1755 if (BinaryBasicBlock *BB = getBasicBlockAtOffset(Destination)) {
1756 // Check if the externally referenced offset is a recognized jump table
1757 // target.
1758 if (JTTargets.contains(BB->getLabel()))
1759 continue;
1760
1761 if (opts::Verbosity >= 1) {
1762 errs() << "BOLT-WARNING: unclaimed data to code reference (possibly "
1763 << "an unrecognized jump table entry) to " << BB->getName()
1764 << " in " << *this << "\n";
1765 }
1766 auto L = BC.scopeLock();
1767 addEntryPoint(*BB);
1768 } else {
1769 errs() << "BOLT-WARNING: unknown data to code reference to offset "
1770 << Twine::utohexstr(Destination) << " in " << *this << "\n";
1771 setIgnored();
1772 }
1773 HasUnclaimedReference = true;
1774 }
1775 return !HasUnclaimedReference;
1776}
1777
1778bool BinaryFunction::postProcessIndirectBranches(
1779 MCPlusBuilder::AllocatorIdTy AllocId) {
1780 auto addUnknownControlFlow = [&](BinaryBasicBlock &BB) {
1781 HasUnknownControlFlow = true;
1782 BB.removeAllSuccessors();
1783 for (uint64_t PossibleDestination : ExternallyReferencedOffsets)
1784 if (BinaryBasicBlock *SuccBB = getBasicBlockAtOffset(PossibleDestination))
1785 BB.addSuccessor(SuccBB);
1786 };
1787
1788 uint64_t NumIndirectJumps = 0;
1789 MCInst *LastIndirectJump = nullptr;
1790 BinaryBasicBlock *LastIndirectJumpBB = nullptr;
1791 uint64_t LastJT = 0;
1792 uint16_t LastJTIndexReg = BC.MIB->getNoRegister();
1793 for (BinaryBasicBlock &BB : blocks()) {
1794 for (MCInst &Instr : BB) {
1795 if (!BC.MIB->isIndirectBranch(Instr))
1796 continue;
1797
1798 // If there's an indirect branch in a single-block function -
1799 // it must be a tail call.
1800 if (BasicBlocks.size() == 1) {
1801 BC.MIB->convertJmpToTailCall(Instr);
1802 return true;
1803 }
1804
1805 ++NumIndirectJumps;
1806
1807 if (opts::StrictMode && !hasInternalReference()) {
1808 BC.MIB->convertJmpToTailCall(Instr);
1809 break;
1810 }
1811
1812 // Validate the tail call or jump table assumptions now that we know
1813 // basic block boundaries.
1814 if (BC.MIB->isTailCall(Instr) || BC.MIB->getJumpTable(Instr)) {
1815 const unsigned PtrSize = BC.AsmInfo->getCodePointerSize();
1816 MCInst *MemLocInstr;
1817 unsigned BaseRegNum, IndexRegNum;
1818 int64_t DispValue;
1819 const MCExpr *DispExpr;
1820 MCInst *PCRelBaseInstr;
1821 IndirectBranchType Type = BC.MIB->analyzeIndirectBranch(
1822 Instr, BB.begin(), BB.end(), PtrSize, MemLocInstr, BaseRegNum,
1823 IndexRegNum, DispValue, DispExpr, PCRelBaseInstr);
1824 if (Type != IndirectBranchType::UNKNOWN || MemLocInstr != nullptr)
1825 continue;
1826
1827 if (!opts::StrictMode)
1828 return false;
1829
1830 if (BC.MIB->isTailCall(Instr)) {
1831 BC.MIB->convertTailCallToJmp(Instr);
1832 } else {
1833 LastIndirectJump = &Instr;
1834 LastIndirectJumpBB = &BB;
1835 LastJT = BC.MIB->getJumpTable(Instr);
1836 LastJTIndexReg = BC.MIB->getJumpTableIndexReg(Instr);
1837 BC.MIB->unsetJumpTable(Instr);
1838
1839 JumpTable *JT = BC.getJumpTableContainingAddress(LastJT);
1840 if (JT->Type == JumpTable::JTT_NORMAL) {
1841 // Invalidating the jump table may also invalidate other jump table
1842 // boundaries. Until we have/need a support for this, mark the
1843 // function as non-simple.
1844 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: rejected jump table reference"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: rejected jump table reference"
<< JT->getName() << " in " << *this <<
'\n'; } } while (false)
1845 << JT->getName() << " in " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: rejected jump table reference"
<< JT->getName() << " in " << *this <<
'\n'; } } while (false)
;
1846 return false;
1847 }
1848 }
1849
1850 addUnknownControlFlow(BB);
1851 continue;
1852 }
1853
1854 // If this block contains an epilogue code and has an indirect branch,
1855 // then most likely it's a tail call. Otherwise, we cannot tell for sure
1856 // what it is and conservatively reject the function's CFG.
1857 bool IsEpilogue = llvm::any_of(BB, [&](const MCInst &Instr) {
1858 return BC.MIB->isLeave(Instr) || BC.MIB->isPop(Instr);
1859 });
1860 if (IsEpilogue) {
1861 BC.MIB->convertJmpToTailCall(Instr);
1862 BB.removeAllSuccessors();
1863 continue;
1864 }
1865
1866 if (opts::Verbosity >= 2) {
1867 outs() << "BOLT-INFO: rejected potential indirect tail call in "
1868 << "function " << *this << " in basic block " << BB.getName()
1869 << ".\n";
1870 LLVM_DEBUG(BC.printInstructions(dbgs(), BB.begin(), BB.end(),do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { BC.printInstructions(dbgs(), BB.begin(), BB.end()
, BB.getOffset(), this, true); } } while (false)
1871 BB.getOffset(), this, true))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { BC.printInstructions(dbgs(), BB.begin(), BB.end()
, BB.getOffset(), this, true); } } while (false)
;
1872 }
1873
1874 if (!opts::StrictMode)
1875 return false;
1876
1877 addUnknownControlFlow(BB);
1878 }
1879 }
1880
1881 if (HasInternalLabelReference)
1882 return false;
1883
1884 // If there's only one jump table, and one indirect jump, and no other
1885 // references, then we should be able to derive the jump table even if we
1886 // fail to match the pattern.
1887 if (HasUnknownControlFlow && NumIndirectJumps == 1 &&
1888 JumpTables.size() == 1 && LastIndirectJump) {
1889 BC.MIB->setJumpTable(*LastIndirectJump, LastJT, LastJTIndexReg, AllocId);
1890 HasUnknownControlFlow = false;
1891
1892 LastIndirectJumpBB->updateJumpTableSuccessors();
1893 }
1894
1895 if (HasFixedIndirectBranch)
1896 return false;
1897
1898 // Validate that all data references to function offsets are claimed by
1899 // recognized jump tables. Register externally referenced blocks as entry
1900 // points.
1901 if (!opts::StrictMode && hasInternalReference()) {
1902 if (!validateExternallyReferencedOffsets())
1903 return false;
1904 }
1905
1906 if (HasUnknownControlFlow && !BC.HasRelocations)
1907 return false;
1908
1909 return true;
1910}
1911
1912void BinaryFunction::recomputeLandingPads() {
1913 updateBBIndices(0);
1914
1915 for (BinaryBasicBlock *BB : BasicBlocks) {
1916 BB->LandingPads.clear();
1917 BB->Throwers.clear();
1918 }
1919
1920 for (BinaryBasicBlock *BB : BasicBlocks) {
1921 std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
1922 for (MCInst &Instr : *BB) {
1923 if (!BC.MIB->isInvoke(Instr))
1924 continue;
1925
1926 const Optional<MCPlus::MCLandingPad> EHInfo = BC.MIB->getEHInfo(Instr);
1927 if (!EHInfo || !EHInfo->first)
1928 continue;
1929
1930 BinaryBasicBlock *LPBlock = getBasicBlockForLabel(EHInfo->first);
1931 if (!BBLandingPads.count(LPBlock)) {
1932 BBLandingPads.insert(LPBlock);
1933 BB->LandingPads.emplace_back(LPBlock);
1934 LPBlock->Throwers.emplace_back(BB);
1935 }
1936 }
1937 }
1938}
1939
1940bool BinaryFunction::buildCFG(MCPlusBuilder::AllocatorIdTy AllocatorId) {
1941 auto &MIB = BC.MIB;
1942
1943 if (!isSimple()) {
1
Assuming the condition is false
2
Taking false branch
1944 assert(!BC.HasRelocations &&(static_cast <bool> (!BC.HasRelocations && "cannot process file with non-simple function in relocs mode"
) ? void (0) : __assert_fail ("!BC.HasRelocations && \"cannot process file with non-simple function in relocs mode\""
, "bolt/lib/Core/BinaryFunction.cpp", 1945, __extension__ __PRETTY_FUNCTION__
))
1945 "cannot process file with non-simple function in relocs mode")(static_cast <bool> (!BC.HasRelocations && "cannot process file with non-simple function in relocs mode"
) ? void (0) : __assert_fail ("!BC.HasRelocations && \"cannot process file with non-simple function in relocs mode\""
, "bolt/lib/Core/BinaryFunction.cpp", 1945, __extension__ __PRETTY_FUNCTION__
))
;
1946 return false;
1947 }
1948
1949 if (CurrentState != State::Disassembled)
3
Assuming field 'CurrentState' is equal to Disassembled
1950 return false;
1951
1952 assert(BasicBlocks.empty() && "basic block list should be empty")(static_cast <bool> (BasicBlocks.empty() && "basic block list should be empty"
) ? void (0) : __assert_fail ("BasicBlocks.empty() && \"basic block list should be empty\""
, "bolt/lib/Core/BinaryFunction.cpp", 1952, __extension__ __PRETTY_FUNCTION__
))
;
4
Taking false branch
5
'?' condition is true
1953 assert((Labels.find(getFirstInstructionOffset()) != Labels.end()) &&(static_cast <bool> ((Labels.find(getFirstInstructionOffset
()) != Labels.end()) && "first instruction should always have a label"
) ? void (0) : __assert_fail ("(Labels.find(getFirstInstructionOffset()) != Labels.end()) && \"first instruction should always have a label\""
, "bolt/lib/Core/BinaryFunction.cpp", 1954, __extension__ __PRETTY_FUNCTION__
))
6
'?' condition is true
1954 "first instruction should always have a label")(static_cast <bool> ((Labels.find(getFirstInstructionOffset
()) != Labels.end()) && "first instruction should always have a label"
) ? void (0) : __assert_fail ("(Labels.find(getFirstInstructionOffset()) != Labels.end()) && \"first instruction should always have a label\""
, "bolt/lib/Core/BinaryFunction.cpp", 1954, __extension__ __PRETTY_FUNCTION__
))
;
1955
1956 // Create basic blocks in the original layout order:
1957 //
1958 // * Every instruction with associated label marks
1959 // the beginning of a basic block.
1960 // * Conditional instruction marks the end of a basic block,
1961 // except when the following instruction is an
1962 // unconditional branch, and the unconditional branch is not
1963 // a destination of another branch. In the latter case, the
1964 // basic block will consist of a single unconditional branch
1965 // (missed "double-jump" optimization).
1966 //
1967 // Created basic blocks are sorted in layout order since they are
1968 // created in the same order as instructions, and instructions are
1969 // sorted by offsets.
1970 BinaryBasicBlock *InsertBB = nullptr;
1971 BinaryBasicBlock *PrevBB = nullptr;
1972 bool IsLastInstrNop = false;
1973 // Offset of the last non-nop instruction.
1974 uint64_t LastInstrOffset = 0;
1975
1976 auto addCFIPlaceholders = [this](uint64_t CFIOffset,
1977 BinaryBasicBlock *InsertBB) {
1978 for (auto FI = OffsetToCFI.lower_bound(CFIOffset),
1979 FE = OffsetToCFI.upper_bound(CFIOffset);
1980 FI != FE; ++FI) {
1981 addCFIPseudo(InsertBB, InsertBB->end(), FI->second);
1982 }
1983 };
1984
1985 // For profiling purposes we need to save the offset of the last instruction
1986 // in the basic block.
1987 // NOTE: nops always have an Offset annotation. Annotate the last non-nop as
1988 // older profiles ignored nops.
1989 auto updateOffset = [&](uint64_t Offset) {
1990 assert(PrevBB && PrevBB != InsertBB && "invalid previous block")(static_cast <bool> (PrevBB && PrevBB != InsertBB
&& "invalid previous block") ? void (0) : __assert_fail
("PrevBB && PrevBB != InsertBB && \"invalid previous block\""
, "bolt/lib/Core/BinaryFunction.cpp", 1990, __extension__ __PRETTY_FUNCTION__
))
;
1991 MCInst *LastNonNop = nullptr;
1992 for (BinaryBasicBlock::reverse_iterator RII = PrevBB->getLastNonPseudo(),
1993 E = PrevBB->rend();
1994 RII != E; ++RII) {
1995 if (!BC.MIB->isPseudo(*RII) && !BC.MIB->isNoop(*RII)) {
1996 LastNonNop = &*RII;
1997 break;
1998 }
1999 }
2000 if (LastNonNop && !MIB->getOffset(*LastNonNop))
2001 MIB->setOffset(*LastNonNop, static_cast<uint32_t>(Offset), AllocatorId);
2002 };
2003
2004 for (auto I = Instructions.begin(), E = Instructions.end(); I != E; ++I) {
7
Loop condition is false. Execution continues on line 2090
2005 const uint32_t Offset = I->first;
2006 MCInst &Instr = I->second;
2007
2008 auto LI = Labels.find(Offset);
2009 if (LI != Labels.end()) {
2010 // Always create new BB at branch destination.
2011 PrevBB = InsertBB ? InsertBB : PrevBB;
2012 InsertBB = addBasicBlockAt(LI->first, LI->second);
2013 if (opts::PreserveBlocksAlignment && IsLastInstrNop)
2014 InsertBB->setDerivedAlignment();
2015
2016 if (PrevBB)
2017 updateOffset(LastInstrOffset);
2018 }
2019
2020 const uint64_t InstrInputAddr = I->first + Address;
2021 bool IsSDTMarker =
2022 MIB->isNoop(Instr) && BC.SDTMarkers.count(InstrInputAddr);
2023 bool IsLKMarker = BC.LKMarkers.count(InstrInputAddr);
2024 // Mark all nops with Offset for profile tracking purposes.
2025 if (MIB->isNoop(Instr) || IsLKMarker) {
2026 if (!MIB->getOffset(Instr))
2027 MIB->setOffset(Instr, static_cast<uint32_t>(Offset), AllocatorId);
2028 if (IsSDTMarker || IsLKMarker)
2029 HasSDTMarker = true;
2030 else
2031 // Annotate ordinary nops, so we can safely delete them if required.
2032 MIB->addAnnotation(Instr, "NOP", static_cast<uint32_t>(1), AllocatorId);
2033 }
2034
2035 if (!InsertBB) {
2036 // It must be a fallthrough or unreachable code. Create a new block unless
2037 // we see an unconditional branch following a conditional one. The latter
2038 // should not be a conditional tail call.
2039 assert(PrevBB && "no previous basic block for a fall through")(static_cast <bool> (PrevBB && "no previous basic block for a fall through"
) ? void (0) : __assert_fail ("PrevBB && \"no previous basic block for a fall through\""
, "bolt/lib/Core/BinaryFunction.cpp", 2039, __extension__ __PRETTY_FUNCTION__
))
;
2040 MCInst *PrevInstr = PrevBB->getLastNonPseudoInstr();
2041 assert(PrevInstr && "no previous instruction for a fall through")(static_cast <bool> (PrevInstr && "no previous instruction for a fall through"
) ? void (0) : __assert_fail ("PrevInstr && \"no previous instruction for a fall through\""
, "bolt/lib/Core/BinaryFunction.cpp", 2041, __extension__ __PRETTY_FUNCTION__
))
;
2042 if (MIB->isUnconditionalBranch(Instr) &&
2043 !MIB->isUnconditionalBranch(*PrevInstr) &&
2044 !MIB->getConditionalTailCall(*PrevInstr) &&
2045 !MIB->isReturn(*PrevInstr)) {
2046 // Temporarily restore inserter basic block.
2047 InsertBB = PrevBB;
2048 } else {
2049 MCSymbol *Label;
2050 {
2051 auto L = BC.scopeLock();
2052 Label = BC.Ctx->createNamedTempSymbol("FT");
2053 }
2054 InsertBB = addBasicBlockAt(Offset, Label);
2055 if (opts::PreserveBlocksAlignment && IsLastInstrNop)
2056 InsertBB->setDerivedAlignment();
2057 updateOffset(LastInstrOffset);
2058 }
2059 }
2060 if (Offset == getFirstInstructionOffset()) {
2061 // Add associated CFI pseudos in the first offset
2062 addCFIPlaceholders(Offset, InsertBB);
2063 }
2064
2065 const bool IsBlockEnd = MIB->isTerminator(Instr);
2066 IsLastInstrNop = MIB->isNoop(Instr);
2067 if (!IsLastInstrNop)
2068 LastInstrOffset = Offset;
2069 InsertBB->addInstruction(std::move(Instr));
2070
2071 // Add associated CFI instrs. We always add the CFI instruction that is
2072 // located immediately after this instruction, since the next CFI
2073 // instruction reflects the change in state caused by this instruction.
2074 auto NextInstr = std::next(I);
2075 uint64_t CFIOffset;
2076 if (NextInstr != E)
2077 CFIOffset = NextInstr->first;
2078 else
2079 CFIOffset = getSize();
2080
2081 // Note: this potentially invalidates instruction pointers/iterators.
2082 addCFIPlaceholders(CFIOffset, InsertBB);
2083
2084 if (IsBlockEnd) {
2085 PrevBB = InsertBB;
2086 InsertBB = nullptr;
2087 }
2088 }
2089
2090 if (BasicBlocks.empty()) {
2091 setSimple(false);
2092 return false;
2093 }
2094
2095 // Intermediate dump.
2096 LLVM_DEBUG(print(dbgs(), "after creating basic blocks"))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { print(dbgs(), "after creating basic blocks"); } }
while (false)
;
8
Taking false branch
9
Assuming 'DebugFlag' is false
10
Loop condition is false. Exiting loop
2097
2098 // TODO: handle properly calls to no-return functions,
2099 // e.g. exit(3), etc. Otherwise we'll see a false fall-through
2100 // blocks.
2101
2102 for (std::pair<uint32_t, uint32_t> &Branch : TakenBranches) {
11
Assuming '__begin2' is equal to '__end2'
2103 LLVM_DEBUG(dbgs() << "registering branch [0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "registering branch [0x" <<
Twine::utohexstr(Branch.first) << "] -> [0x" <<
Twine::utohexstr(Branch.second) << "]\n"; } } while (false
)
2104 << Twine::utohexstr(Branch.first) << "] -> [0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "registering branch [0x" <<
Twine::utohexstr(Branch.first) << "] -> [0x" <<
Twine::utohexstr(Branch.second) << "]\n"; } } while (false
)
2105 << Twine::utohexstr(Branch.second) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "registering branch [0x" <<
Twine::utohexstr(Branch.first) << "] -> [0x" <<
Twine::utohexstr(Branch.second) << "]\n"; } } while (false
)
;
2106 BinaryBasicBlock *FromBB = getBasicBlockContainingOffset(Branch.first);
2107 BinaryBasicBlock *ToBB = getBasicBlockAtOffset(Branch.second);
2108 if (!FromBB || !ToBB) {
2109 if (!FromBB)
2110 errs() << "BOLT-ERROR: cannot find BB containing the branch.\n";
2111 if (!ToBB)
2112 errs() << "BOLT-ERROR: cannot find BB containing branch destination.\n";
2113 BC.exitWithBugReport("disassembly failed - inconsistent branch found.",
2114 *this);
2115 }
2116
2117 FromBB->addSuccessor(ToBB);
2118 }
2119
2120 // Add fall-through branches.
2121 PrevBB = nullptr;
2122 bool IsPrevFT = false; // Is previous block a fall-through.
2123 for (BinaryBasicBlock *BB : BasicBlocks) {
12
Assuming '__begin2' is equal to '__end2'
2124 if (IsPrevFT)
2125 PrevBB->addSuccessor(BB);
2126
2127 if (BB->empty()) {
2128 IsPrevFT = true;
2129 PrevBB = BB;
2130 continue;
2131 }
2132
2133 MCInst *LastInstr = BB->getLastNonPseudoInstr();
2134 assert(LastInstr &&(static_cast <bool> (LastInstr && "should have non-pseudo instruction in non-empty block"
) ? void (0) : __assert_fail ("LastInstr && \"should have non-pseudo instruction in non-empty block\""
, "bolt/lib/Core/BinaryFunction.cpp", 2135, __extension__ __PRETTY_FUNCTION__
))
2135 "should have non-pseudo instruction in non-empty block")(static_cast <bool> (LastInstr && "should have non-pseudo instruction in non-empty block"
) ? void (0) : __assert_fail ("LastInstr && \"should have non-pseudo instruction in non-empty block\""
, "bolt/lib/Core/BinaryFunction.cpp", 2135, __extension__ __PRETTY_FUNCTION__
))
;
2136
2137 if (BB->succ_size() == 0) {
2138 // Since there's no existing successors, we know the last instruction is
2139 // not a conditional branch. Thus if it's a terminator, it shouldn't be a
2140 // fall-through.
2141 //
2142 // Conditional tail call is a special case since we don't add a taken
2143 // branch successor for it.
2144 IsPrevFT = !MIB->isTerminator(*LastInstr) ||
2145 MIB->getConditionalTailCall(*LastInstr);
2146 } else if (BB->succ_size() == 1) {
2147 IsPrevFT = MIB->isConditionalBranch(*LastInstr);
2148 } else {
2149 IsPrevFT = false;
2150 }
2151
2152 PrevBB = BB;
2153 }
2154
2155 // Assign landing pads and throwers info.
2156 recomputeLandingPads();
2157
2158 // Assign CFI information to each BB entry.
2159 annotateCFIState();
2160
2161 // Annotate invoke instructions with GNU_args_size data.
2162 propagateGnuArgsSizeInfo(AllocatorId);
2163
2164 // Set the basic block layout to the original order and set end offsets.
2165 PrevBB = nullptr;
13
Null pointer value stored to 'PrevBB'
2166 for (BinaryBasicBlock *BB : BasicBlocks) {
14
Assuming '__begin2' is equal to '__end2'
2167 Layout.addBasicBlock(BB);
2168 if (PrevBB)
2169 PrevBB->setEndOffset(BB->getOffset());
2170 PrevBB = BB;
2171 }
2172 PrevBB->setEndOffset(getSize());
15
Called C++ object pointer is null
2173
2174 Layout.updateLayoutIndices();
2175
2176 normalizeCFIState();
2177
2178 // Clean-up memory taken by intermediate structures.
2179 //
2180 // NB: don't clear Labels list as we may need them if we mark the function
2181 // as non-simple later in the process of discovering extra entry points.
2182 clearList(Instructions);
2183 clearList(OffsetToCFI);
2184 clearList(TakenBranches);
2185
2186 // Update the state.
2187 CurrentState = State::CFG;
2188
2189 // Make any necessary adjustments for indirect branches.
2190 if (!postProcessIndirectBranches(AllocatorId)) {
2191 if (opts::Verbosity) {
2192 errs() << "BOLT-WARNING: failed to post-process indirect branches for "
2193 << *this << '\n';
2194 }
2195 // In relocation mode we want to keep processing the function but avoid
2196 // optimizing it.
2197 setSimple(false);
2198 }
2199
2200 clearList(ExternallyReferencedOffsets);
2201 clearList(UnknownIndirectBranchOffsets);
2202
2203 return true;
2204}
2205
2206void BinaryFunction::postProcessCFG() {
2207 if (isSimple() && !BasicBlocks.empty()) {
2208 // Convert conditional tail call branches to conditional branches that jump
2209 // to a tail call.
2210 removeConditionalTailCalls();
2211
2212 postProcessProfile();
2213
2214 // Eliminate inconsistencies between branch instructions and CFG.
2215 postProcessBranches();
2216 }
2217
2218 calculateMacroOpFusionStats();
2219
2220 // The final cleanup of intermediate structures.
2221 clearList(IgnoredBranches);
2222
2223 // Remove "Offset" annotations, unless we need an address-translation table
2224 // later. This has no cost, since annotations are allocated by a bumpptr
2225 // allocator and won't be released anyway until late in the pipeline.
2226 if (!requiresAddressTranslation() && !opts::Instrument) {
2227 for (BinaryBasicBlock &BB : blocks())
2228 for (MCInst &Inst : BB)
2229 BC.MIB->clearOffset(Inst);
2230 }
2231
2232 assert((!isSimple() || validateCFG()) &&(static_cast <bool> ((!isSimple() || validateCFG()) &&
"invalid CFG detected after post-processing") ? void (0) : __assert_fail
("(!isSimple() || validateCFG()) && \"invalid CFG detected after post-processing\""
, "bolt/lib/Core/BinaryFunction.cpp", 2233, __extension__ __PRETTY_FUNCTION__
))
2233 "invalid CFG detected after post-processing")(static_cast <bool> ((!isSimple() || validateCFG()) &&
"invalid CFG detected after post-processing") ? void (0) : __assert_fail
("(!isSimple() || validateCFG()) && \"invalid CFG detected after post-processing\""
, "bolt/lib/Core/BinaryFunction.cpp", 2233, __extension__ __PRETTY_FUNCTION__
))
;
2234}
2235
2236void BinaryFunction::calculateMacroOpFusionStats() {
2237 if (!getBinaryContext().isX86())
2238 return;
2239 for (const BinaryBasicBlock &BB : blocks()) {
2240 auto II = BB.getMacroOpFusionPair();
2241 if (II == BB.end())
2242 continue;
2243
2244 // Check offset of the second instruction.
2245 // FIXME: arch-specific.
2246 const uint32_t Offset = BC.MIB->getOffsetWithDefault(*std::next(II), 0);
2247 if (!Offset || (getAddress() + Offset) % 64)
2248 continue;
2249
2250 LLVM_DEBUG(dbgs() << "\nmissed macro-op fusion at address 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x"
<< Twine::utohexstr(getAddress() + Offset) << " in function "
<< *this << "; executed " << BB.getKnownExecutionCount
() << " times.\n"; } } while (false)
2251 << Twine::utohexstr(getAddress() + Offset)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x"
<< Twine::utohexstr(getAddress() + Offset) << " in function "
<< *this << "; executed " << BB.getKnownExecutionCount
() << " times.\n"; } } while (false)
2252 << " in function " << *this << "; executed "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x"
<< Twine::utohexstr(getAddress() + Offset) << " in function "
<< *this << "; executed " << BB.getKnownExecutionCount
() << " times.\n"; } } while (false)
2253 << BB.getKnownExecutionCount() << " times.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "\nmissed macro-op fusion at address 0x"
<< Twine::utohexstr(getAddress() + Offset) << " in function "
<< *this << "; executed " << BB.getKnownExecutionCount
() << " times.\n"; } } while (false)
;
2254 ++BC.MissedMacroFusionPairs;
2255 BC.MissedMacroFusionExecCount += BB.getKnownExecutionCount();
2256 }
2257}
2258
2259void BinaryFunction::removeTagsFromProfile() {
2260 for (BinaryBasicBlock *BB : BasicBlocks) {
2261 if (BB->ExecutionCount == BinaryBasicBlock::COUNT_NO_PROFILE)
2262 BB->ExecutionCount = 0;
2263 for (BinaryBasicBlock::BinaryBranchInfo &BI : BB->branch_info()) {
2264 if (BI.Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
2265 BI.MispredictedCount != BinaryBasicBlock::COUNT_NO_PROFILE)
2266 continue;
2267 BI.Count = 0;
2268 BI.MispredictedCount = 0;
2269 }
2270 }
2271}
2272
2273void BinaryFunction::removeConditionalTailCalls() {
2274 // Blocks to be appended at the end.
2275 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBlocks;
2276
2277 for (auto BBI = begin(); BBI != end(); ++BBI) {
2278 BinaryBasicBlock &BB = *BBI;
2279 MCInst *CTCInstr = BB.getLastNonPseudoInstr();
2280 if (!CTCInstr)
2281 continue;
2282
2283 Optional<uint64_t> TargetAddressOrNone =
2284 BC.MIB->getConditionalTailCall(*CTCInstr);
2285 if (!TargetAddressOrNone)
2286 continue;
2287
2288 // Gather all necessary information about CTC instruction before
2289 // annotations are destroyed.
2290 const int32_t CFIStateBeforeCTC = BB.getCFIStateAtInstr(CTCInstr);
2291 uint64_t CTCTakenCount = BinaryBasicBlock::COUNT_NO_PROFILE;
2292 uint64_t CTCMispredCount = BinaryBasicBlock::COUNT_NO_PROFILE;
2293 if (hasValidProfile()) {
2294 CTCTakenCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
2295 *CTCInstr, "CTCTakenCount");
2296 CTCMispredCount = BC.MIB->getAnnotationWithDefault<uint64_t>(
2297 *CTCInstr, "CTCMispredCount");
2298 }
2299
2300 // Assert that the tail call does not throw.
2301 assert(!BC.MIB->getEHInfo(*CTCInstr) &&(static_cast <bool> (!BC.MIB->getEHInfo(*CTCInstr) &&
"found tail call with associated landing pad") ? void (0) : __assert_fail
("!BC.MIB->getEHInfo(*CTCInstr) && \"found tail call with associated landing pad\""
, "bolt/lib/Core/BinaryFunction.cpp", 2302, __extension__ __PRETTY_FUNCTION__
))
2302 "found tail call with associated landing pad")(static_cast <bool> (!BC.MIB->getEHInfo(*CTCInstr) &&
"found tail call with associated landing pad") ? void (0) : __assert_fail
("!BC.MIB->getEHInfo(*CTCInstr) && \"found tail call with associated landing pad\""
, "bolt/lib/Core/BinaryFunction.cpp", 2302, __extension__ __PRETTY_FUNCTION__
))
;
2303
2304 // Create a basic block with an unconditional tail call instruction using
2305 // the same destination.
2306 const MCSymbol *CTCTargetLabel = BC.MIB->getTargetSymbol(*CTCInstr);
2307 assert(CTCTargetLabel && "symbol expected for conditional tail call")(static_cast <bool> (CTCTargetLabel && "symbol expected for conditional tail call"
) ? void (0) : __assert_fail ("CTCTargetLabel && \"symbol expected for conditional tail call\""
, "bolt/lib/Core/BinaryFunction.cpp", 2307, __extension__ __PRETTY_FUNCTION__
))
;
2308 MCInst TailCallInstr;
2309 BC.MIB->createTailCall(TailCallInstr, CTCTargetLabel, BC.Ctx.get());
2310 // Link new BBs to the original input offset of the BB where the CTC
2311 // is, so we can map samples recorded in new BBs back to the original BB
2312 // seem in the input binary (if using BAT)
2313 std::unique_ptr<BinaryBasicBlock> TailCallBB =
2314 createBasicBlock(BC.Ctx->createNamedTempSymbol("TC"));
2315 TailCallBB->setOffset(BB.getInputOffset());
2316 TailCallBB->addInstruction(TailCallInstr);
2317 TailCallBB->setCFIState(CFIStateBeforeCTC);
2318
2319 // Add CFG edge with profile info from BB to TailCallBB.
2320 BB.addSuccessor(TailCallBB.get(), CTCTakenCount, CTCMispredCount);
2321
2322 // Add execution count for the block.
2323 TailCallBB->setExecutionCount(CTCTakenCount);
2324
2325 BC.MIB->convertTailCallToJmp(*CTCInstr);
2326
2327 BC.MIB->replaceBranchTarget(*CTCInstr, TailCallBB->getLabel(),
2328 BC.Ctx.get());
2329
2330 // Add basic block to the list that will be added to the end.
2331 NewBlocks.emplace_back(std::move(TailCallBB));
2332
2333 // Swap edges as the TailCallBB corresponds to the taken branch.
2334 BB.swapConditionalSuccessors();
2335
2336 // This branch is no longer a conditional tail call.
2337 BC.MIB->unsetConditionalTailCall(*CTCInstr);
2338 }
2339
2340 insertBasicBlocks(std::prev(end()), std::move(NewBlocks),
2341 /* UpdateLayout */ true,
2342 /* UpdateCFIState */ false);
2343}
2344
2345uint64_t BinaryFunction::getFunctionScore() const {
2346 if (FunctionScore != -1)
2347 return FunctionScore;
2348
2349 if (!isSimple() || !hasValidProfile()) {
2350 FunctionScore = 0;
2351 return FunctionScore;
2352 }
2353
2354 uint64_t TotalScore = 0ULL;
2355 for (const BinaryBasicBlock &BB : blocks()) {
2356 uint64_t BBExecCount = BB.getExecutionCount();
2357 if (BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
2358 continue;
2359 TotalScore += BBExecCount * BB.getNumNonPseudos();
2360 }
2361 FunctionScore = TotalScore;
2362 return FunctionScore;
2363}
2364
2365void BinaryFunction::annotateCFIState() {
2366 assert(CurrentState == State::Disassembled && "unexpected function state")(static_cast <bool> (CurrentState == State::Disassembled
&& "unexpected function state") ? void (0) : __assert_fail
("CurrentState == State::Disassembled && \"unexpected function state\""
, "bolt/lib/Core/BinaryFunction.cpp", 2366, __extension__ __PRETTY_FUNCTION__
))
;
2367 assert(!BasicBlocks.empty() && "basic block list should not be empty")(static_cast <bool> (!BasicBlocks.empty() && "basic block list should not be empty"
) ? void (0) : __assert_fail ("!BasicBlocks.empty() && \"basic block list should not be empty\""
, "bolt/lib/Core/BinaryFunction.cpp", 2367, __extension__ __PRETTY_FUNCTION__
))
;
2368
2369 // This is an index of the last processed CFI in FDE CFI program.
2370 uint32_t State = 0;
2371
2372 // This is an index of RememberState CFI reflecting effective state right
2373 // after execution of RestoreState CFI.
2374 //
2375 // It differs from State iff the CFI at (State-1)
2376 // was RestoreState (modulo GNU_args_size CFIs, which are ignored).
2377 //
2378 // This allows us to generate shorter replay sequences when producing new
2379 // CFI programs.
2380 uint32_t EffectiveState = 0;
2381
2382 // For tracking RememberState/RestoreState sequences.
2383 std::stack<uint32_t> StateStack;
2384
2385 for (BinaryBasicBlock *BB : BasicBlocks) {
2386 BB->setCFIState(EffectiveState);
2387
2388 for (const MCInst &Instr : *BB) {
2389 const MCCFIInstruction *CFI = getCFIFor(Instr);
2390 if (!CFI)
2391 continue;
2392
2393 ++State;
2394
2395 switch (CFI->getOperation()) {
2396 case MCCFIInstruction::OpRememberState:
2397 StateStack.push(EffectiveState);
2398 EffectiveState = State;
2399 break;
2400 case MCCFIInstruction::OpRestoreState:
2401 assert(!StateStack.empty() && "corrupt CFI stack")(static_cast <bool> (!StateStack.empty() && "corrupt CFI stack"
) ? void (0) : __assert_fail ("!StateStack.empty() && \"corrupt CFI stack\""
, "bolt/lib/Core/BinaryFunction.cpp", 2401, __extension__ __PRETTY_FUNCTION__
))
;
2402 EffectiveState = StateStack.top();
2403 StateStack.pop();
2404 break;
2405 case MCCFIInstruction::OpGnuArgsSize:
2406 // OpGnuArgsSize CFIs do not affect the CFI state.
2407 break;
2408 default:
2409 // Any other CFI updates the state.
2410 EffectiveState = State;
2411 break;
2412 }
2413 }
2414 }
2415
2416 assert(StateStack.empty() && "corrupt CFI stack")(static_cast <bool> (StateStack.empty() && "corrupt CFI stack"
) ? void (0) : __assert_fail ("StateStack.empty() && \"corrupt CFI stack\""
, "bolt/lib/Core/BinaryFunction.cpp", 2416, __extension__ __PRETTY_FUNCTION__
))
;
2417}
2418
2419namespace {
2420
2421/// Our full interpretation of a DWARF CFI machine state at a given point
2422struct CFISnapshot {
2423 /// CFA register number and offset defining the canonical frame at this
2424 /// point, or the number of a rule (CFI state) that computes it with a
2425 /// DWARF expression. This number will be negative if it refers to a CFI
2426 /// located in the CIE instead of the FDE.
2427 uint32_t CFAReg;
2428 int32_t CFAOffset;
2429 int32_t CFARule;
2430 /// Mapping of rules (CFI states) that define the location of each
2431 /// register. If absent, no rule defining the location of such register
2432 /// was ever read. This number will be negative if it refers to a CFI
2433 /// located in the CIE instead of the FDE.
2434 DenseMap<int32_t, int32_t> RegRule;
2435
2436 /// References to CIE, FDE and expanded instructions after a restore state
2437 const BinaryFunction::CFIInstrMapType &CIE;
2438 const BinaryFunction::CFIInstrMapType &FDE;
2439 const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents;
2440
2441 /// Current FDE CFI number representing the state where the snapshot is at
2442 int32_t CurState;
2443
2444 /// Used when we don't have information about which state/rule to apply
2445 /// to recover the location of either the CFA or a specific register
2446 constexpr static int32_t UNKNOWN = std::numeric_limits<int32_t>::min();
2447
2448private:
2449 /// Update our snapshot by executing a single CFI
2450 void update(const MCCFIInstruction &Instr, int32_t RuleNumber) {
2451 switch (Instr.getOperation()) {
2452 case MCCFIInstruction::OpSameValue:
2453 case MCCFIInstruction::OpRelOffset:
2454 case MCCFIInstruction::OpOffset:
2455 case MCCFIInstruction::OpRestore:
2456 case MCCFIInstruction::OpUndefined:
2457 case MCCFIInstruction::OpRegister:
2458 RegRule[Instr.getRegister()] = RuleNumber;
2459 break;
2460 case MCCFIInstruction::OpDefCfaRegister:
2461 CFAReg = Instr.getRegister();
2462 CFARule = UNKNOWN;
2463 break;
2464 case MCCFIInstruction::OpDefCfaOffset:
2465 CFAOffset = Instr.getOffset();
2466 CFARule = UNKNOWN;
2467 break;
2468 case MCCFIInstruction::OpDefCfa:
2469 CFAReg = Instr.getRegister();
2470 CFAOffset = Instr.getOffset();
2471 CFARule = UNKNOWN;
2472 break;
2473 case MCCFIInstruction::OpEscape: {
2474 Optional<uint8_t> Reg = readDWARFExpressionTargetReg(Instr.getValues());
2475 // Handle DW_CFA_def_cfa_expression
2476 if (!Reg) {
2477 CFARule = RuleNumber;
2478 break;
2479 }
2480 RegRule[*Reg] = RuleNumber;
2481 break;
2482 }
2483 case MCCFIInstruction::OpAdjustCfaOffset:
2484 case MCCFIInstruction::OpWindowSave:
2485 case MCCFIInstruction::OpNegateRAState:
2486 case MCCFIInstruction::OpLLVMDefAspaceCfa:
2487 llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp"
, 2487)
;
2488 break;
2489 case MCCFIInstruction::OpRememberState:
2490 case MCCFIInstruction::OpRestoreState:
2491 case MCCFIInstruction::OpGnuArgsSize:
2492 // do not affect CFI state
2493 break;
2494 }
2495 }
2496
2497public:
2498 /// Advance state reading FDE CFI instructions up to State number
2499 void advanceTo(int32_t State) {
2500 for (int32_t I = CurState, E = State; I != E; ++I) {
2501 const MCCFIInstruction &Instr = FDE[I];
2502 if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
2503 update(Instr, I);
2504 continue;
2505 }
2506 // If restore state instruction, fetch the equivalent CFIs that have
2507 // the same effect of this restore. This is used to ensure remember-
2508 // restore pairs are completely removed.
2509 auto Iter = FrameRestoreEquivalents.find(I);
2510 if (Iter == FrameRestoreEquivalents.end())
2511 continue;
2512 for (int32_t RuleNumber : Iter->second)
2513 update(FDE[RuleNumber], RuleNumber);
2514 }
2515
2516 assert(((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) ||(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN &&
CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?"
) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\""
, "bolt/lib/Core/BinaryFunction.cpp", 2518, __extension__ __PRETTY_FUNCTION__
))
2517 CFARule != UNKNOWN) &&(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN &&
CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?"
) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\""
, "bolt/lib/Core/BinaryFunction.cpp", 2518, __extension__ __PRETTY_FUNCTION__
))
2518 "CIE did not define default CFA?")(static_cast <bool> (((CFAReg != (uint32_t)UNKNOWN &&
CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && "CIE did not define default CFA?"
) ? void (0) : __assert_fail ("((CFAReg != (uint32_t)UNKNOWN && CFAOffset != UNKNOWN) || CFARule != UNKNOWN) && \"CIE did not define default CFA?\""
, "bolt/lib/Core/BinaryFunction.cpp", 2518, __extension__ __PRETTY_FUNCTION__
))
;
2519
2520 CurState = State;
2521 }
2522
2523 /// Interpret all CIE and FDE instructions up until CFI State number and
2524 /// populate this snapshot
2525 CFISnapshot(
2526 const BinaryFunction::CFIInstrMapType &CIE,
2527 const BinaryFunction::CFIInstrMapType &FDE,
2528 const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
2529 int32_t State)
2530 : CIE(CIE), FDE(FDE), FrameRestoreEquivalents(FrameRestoreEquivalents) {
2531 CFAReg = UNKNOWN;
2532 CFAOffset = UNKNOWN;
2533 CFARule = UNKNOWN;
2534 CurState = 0;
2535
2536 for (int32_t I = 0, E = CIE.size(); I != E; ++I) {
2537 const MCCFIInstruction &Instr = CIE[I];
2538 update(Instr, -I);
2539 }
2540
2541 advanceTo(State);
2542 }
2543};
2544
2545/// A CFI snapshot with the capability of checking if incremental additions to
2546/// it are redundant. This is used to ensure we do not emit two CFI instructions
2547/// back-to-back that are doing the same state change, or to avoid emitting a
2548/// CFI at all when the state at that point would not be modified after that CFI
2549struct CFISnapshotDiff : public CFISnapshot {
2550 bool RestoredCFAReg{false};
2551 bool RestoredCFAOffset{false};
2552 DenseMap<int32_t, bool> RestoredRegs;
2553
2554 CFISnapshotDiff(const CFISnapshot &S) : CFISnapshot(S) {}
2555
2556 CFISnapshotDiff(
2557 const BinaryFunction::CFIInstrMapType &CIE,
2558 const BinaryFunction::CFIInstrMapType &FDE,
2559 const DenseMap<int32_t, SmallVector<int32_t, 4>> &FrameRestoreEquivalents,
2560 int32_t State)
2561 : CFISnapshot(CIE, FDE, FrameRestoreEquivalents, State) {}
2562
2563 /// Return true if applying Instr to this state is redundant and can be
2564 /// dismissed.
2565 bool isRedundant(const MCCFIInstruction &Instr) {
2566 switch (Instr.getOperation()) {
2567 case MCCFIInstruction::OpSameValue:
2568 case MCCFIInstruction::OpRelOffset:
2569 case MCCFIInstruction::OpOffset:
2570 case MCCFIInstruction::OpRestore:
2571 case MCCFIInstruction::OpUndefined:
2572 case MCCFIInstruction::OpRegister:
2573 case MCCFIInstruction::OpEscape: {
2574 uint32_t Reg;
2575 if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
2576 Reg = Instr.getRegister();
2577 } else {
2578 Optional<uint8_t> R = readDWARFExpressionTargetReg(Instr.getValues());
2579 // Handle DW_CFA_def_cfa_expression
2580 if (!R) {
2581 if (RestoredCFAReg && RestoredCFAOffset)
2582 return true;
2583 RestoredCFAReg = true;
2584 RestoredCFAOffset = true;
2585 return false;
2586 }
2587 Reg = *R;
2588 }
2589 if (RestoredRegs[Reg])
2590 return true;
2591 RestoredRegs[Reg] = true;
2592 const int32_t CurRegRule =
2593 RegRule.find(Reg) != RegRule.end() ? RegRule[Reg] : UNKNOWN;
2594 if (CurRegRule == UNKNOWN) {
2595 if (Instr.getOperation() == MCCFIInstruction::OpRestore ||
2596 Instr.getOperation() == MCCFIInstruction::OpSameValue)
2597 return true;
2598 return false;
2599 }
2600 const MCCFIInstruction &LastDef =
2601 CurRegRule < 0 ? CIE[-CurRegRule] : FDE[CurRegRule];
2602 return LastDef == Instr;
2603 }
2604 case MCCFIInstruction::OpDefCfaRegister:
2605 if (RestoredCFAReg)
2606 return true;
2607 RestoredCFAReg = true;
2608 return CFAReg == Instr.getRegister();
2609 case MCCFIInstruction::OpDefCfaOffset:
2610 if (RestoredCFAOffset)
2611 return true;
2612 RestoredCFAOffset = true;
2613 return CFAOffset == Instr.getOffset();
2614 case MCCFIInstruction::OpDefCfa:
2615 if (RestoredCFAReg && RestoredCFAOffset)
2616 return true;
2617 RestoredCFAReg = true;
2618 RestoredCFAOffset = true;
2619 return CFAReg == Instr.getRegister() && CFAOffset == Instr.getOffset();
2620 case MCCFIInstruction::OpAdjustCfaOffset:
2621 case MCCFIInstruction::OpWindowSave:
2622 case MCCFIInstruction::OpNegateRAState:
2623 case MCCFIInstruction::OpLLVMDefAspaceCfa:
2624 llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp"
, 2624)
;
2625 return false;
2626 case MCCFIInstruction::OpRememberState:
2627 case MCCFIInstruction::OpRestoreState:
2628 case MCCFIInstruction::OpGnuArgsSize:
2629 // do not affect CFI state
2630 return true;
2631 }
2632 return false;
2633 }
2634};
2635
2636} // end anonymous namespace
2637
2638bool BinaryFunction::replayCFIInstrs(int32_t FromState, int32_t ToState,
2639 BinaryBasicBlock *InBB,
2640 BinaryBasicBlock::iterator InsertIt) {
2641 if (FromState == ToState)
2642 return true;
2643 assert(FromState < ToState && "can only replay CFIs forward")(static_cast <bool> (FromState < ToState && "can only replay CFIs forward"
) ? void (0) : __assert_fail ("FromState < ToState && \"can only replay CFIs forward\""
, "bolt/lib/Core/BinaryFunction.cpp", 2643, __extension__ __PRETTY_FUNCTION__
))
;
2644
2645 CFISnapshotDiff CFIDiff(CIEFrameInstructions, FrameInstructions,
2646 FrameRestoreEquivalents, FromState);
2647
2648 std::vector<uint32_t> NewCFIs;
2649 for (int32_t CurState = FromState; CurState < ToState; ++CurState) {
2650 MCCFIInstruction *Instr = &FrameInstructions[CurState];
2651 if (Instr->getOperation() == MCCFIInstruction::OpRestoreState) {
2652 auto Iter = FrameRestoreEquivalents.find(CurState);
2653 assert(Iter != FrameRestoreEquivalents.end())(static_cast <bool> (Iter != FrameRestoreEquivalents.end
()) ? void (0) : __assert_fail ("Iter != FrameRestoreEquivalents.end()"
, "bolt/lib/Core/BinaryFunction.cpp", 2653, __extension__ __PRETTY_FUNCTION__
))
;
2654 NewCFIs.insert(NewCFIs.end(), Iter->second.begin(), Iter->second.end());
2655 // RestoreState / Remember will be filtered out later by CFISnapshotDiff,
2656 // so we might as well fall-through here.
2657 }
2658 NewCFIs.push_back(CurState);
2659 }
2660
2661 // Replay instructions while avoiding duplicates
2662 for (auto I = NewCFIs.rbegin(), E = NewCFIs.rend(); I != E; ++I) {
2663 if (CFIDiff.isRedundant(FrameInstructions[*I]))
2664 continue;
2665 InsertIt = addCFIPseudo(InBB, InsertIt, *I);
2666 }
2667
2668 return true;
2669}
2670
2671SmallVector<int32_t, 4>
2672BinaryFunction::unwindCFIState(int32_t FromState, int32_t ToState,
2673 BinaryBasicBlock *InBB,
2674 BinaryBasicBlock::iterator &InsertIt) {
2675 SmallVector<int32_t, 4> NewStates;
2676
2677 CFISnapshot ToCFITable(CIEFrameInstructions, FrameInstructions,
2678 FrameRestoreEquivalents, ToState);
2679 CFISnapshotDiff FromCFITable(ToCFITable);
2680 FromCFITable.advanceTo(FromState);
2681
2682 auto undoStateDefCfa = [&]() {
2683 if (ToCFITable.CFARule == CFISnapshot::UNKNOWN) {
2684 FrameInstructions.emplace_back(MCCFIInstruction::cfiDefCfa(
2685 nullptr, ToCFITable.CFAReg, ToCFITable.CFAOffset));
2686 if (FromCFITable.isRedundant(FrameInstructions.back())) {
2687 FrameInstructions.pop_back();
2688 return;
2689 }
2690 NewStates.push_back(FrameInstructions.size() - 1);
2691 InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1);
2692 ++InsertIt;
2693 } else if (ToCFITable.CFARule < 0) {
2694 if (FromCFITable.isRedundant(CIEFrameInstructions[-ToCFITable.CFARule]))
2695 return;
2696 NewStates.push_back(FrameInstructions.size());
2697 InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size());
2698 ++InsertIt;
2699 FrameInstructions.emplace_back(CIEFrameInstructions[-ToCFITable.CFARule]);
2700 } else if (!FromCFITable.isRedundant(
2701 FrameInstructions[ToCFITable.CFARule])) {
2702 NewStates.push_back(ToCFITable.CFARule);
2703 InsertIt = addCFIPseudo(InBB, InsertIt, ToCFITable.CFARule);
2704 ++InsertIt;
2705 }
2706 };
2707
2708 auto undoState = [&](const MCCFIInstruction &Instr) {
2709 switch (Instr.getOperation()) {
2710 case MCCFIInstruction::OpRememberState:
2711 case MCCFIInstruction::OpRestoreState:
2712 break;
2713 case MCCFIInstruction::OpSameValue:
2714 case MCCFIInstruction::OpRelOffset:
2715 case MCCFIInstruction::OpOffset:
2716 case MCCFIInstruction::OpRestore:
2717 case MCCFIInstruction::OpUndefined:
2718 case MCCFIInstruction::OpEscape:
2719 case MCCFIInstruction::OpRegister: {
2720 uint32_t Reg;
2721 if (Instr.getOperation() != MCCFIInstruction::OpEscape) {
2722 Reg = Instr.getRegister();
2723 } else {
2724 Optional<uint8_t> R = readDWARFExpressionTargetReg(Instr.getValues());
2725 // Handle DW_CFA_def_cfa_expression
2726 if (!R) {
2727 undoStateDefCfa();
2728 return;
2729 }
2730 Reg = *R;
2731 }
2732
2733 if (ToCFITable.RegRule.find(Reg) == ToCFITable.RegRule.end()) {
2734 FrameInstructions.emplace_back(
2735 MCCFIInstruction::createRestore(nullptr, Reg));
2736 if (FromCFITable.isRedundant(FrameInstructions.back())) {
2737 FrameInstructions.pop_back();
2738 break;
2739 }
2740 NewStates.push_back(FrameInstructions.size() - 1);
2741 InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size() - 1);
2742 ++InsertIt;
2743 break;
2744 }
2745 const int32_t Rule = ToCFITable.RegRule[Reg];
2746 if (Rule < 0) {
2747 if (FromCFITable.isRedundant(CIEFrameInstructions[-Rule]))
2748 break;
2749 NewStates.push_back(FrameInstructions.size());
2750 InsertIt = addCFIPseudo(InBB, InsertIt, FrameInstructions.size());
2751 ++InsertIt;
2752 FrameInstructions.emplace_back(CIEFrameInstructions[-Rule]);
2753 break;
2754 }
2755 if (FromCFITable.isRedundant(FrameInstructions[Rule]))
2756 break;
2757 NewStates.push_back(Rule);
2758 InsertIt = addCFIPseudo(InBB, InsertIt, Rule);
2759 ++InsertIt;
2760 break;
2761 }
2762 case MCCFIInstruction::OpDefCfaRegister:
2763 case MCCFIInstruction::OpDefCfaOffset:
2764 case MCCFIInstruction::OpDefCfa:
2765 undoStateDefCfa();
2766 break;
2767 case MCCFIInstruction::OpAdjustCfaOffset:
2768 case MCCFIInstruction::OpWindowSave:
2769 case MCCFIInstruction::OpNegateRAState:
2770 case MCCFIInstruction::OpLLVMDefAspaceCfa:
2771 llvm_unreachable("unsupported CFI opcode")::llvm::llvm_unreachable_internal("unsupported CFI opcode", "bolt/lib/Core/BinaryFunction.cpp"
, 2771)
;
2772 break;
2773 case MCCFIInstruction::OpGnuArgsSize:
2774 // do not affect CFI state
2775 break;
2776 }
2777 };
2778
2779 // Undo all modifications from ToState to FromState
2780 for (int32_t I = ToState, E = FromState; I != E; ++I) {
2781 const MCCFIInstruction &Instr = FrameInstructions[I];
2782 if (Instr.getOperation() != MCCFIInstruction::OpRestoreState) {
2783 undoState(Instr);
2784 continue;
2785 }
2786 auto Iter = FrameRestoreEquivalents.find(I);
2787 if (Iter == FrameRestoreEquivalents.end())
2788 continue;
2789 for (int32_t State : Iter->second)
2790 undoState(FrameInstructions[State]);
2791 }
2792
2793 return NewStates;
2794}
2795
2796void BinaryFunction::normalizeCFIState() {
2797 // Reordering blocks with remember-restore state instructions can be specially
2798 // tricky. When rewriting the CFI, we omit remember-restore state instructions
2799 // entirely. For restore state, we build a map expanding each restore to the
2800 // equivalent unwindCFIState sequence required at that point to achieve the
2801 // same effect of the restore. All remember state are then just ignored.
2802 std::stack<int32_t> Stack;
2803 for (BinaryBasicBlock *CurBB : Layout.blocks()) {
2804 for (auto II = CurBB->begin(); II != CurBB->end(); ++II) {
2805 if (const MCCFIInstruction *CFI = getCFIFor(*II)) {
2806 if (CFI->getOperation() == MCCFIInstruction::OpRememberState) {
2807 Stack.push(II->getOperand(0).getImm());
2808 continue;
2809 }
2810 if (CFI->getOperation() == MCCFIInstruction::OpRestoreState) {
2811 const int32_t RememberState = Stack.top();
2812 const int32_t CurState = II->getOperand(0).getImm();
2813 FrameRestoreEquivalents[CurState] =
2814 unwindCFIState(CurState, RememberState, CurBB, II);
2815 Stack.pop();
2816 }
2817 }
2818 }
2819 }
2820}
2821
2822bool BinaryFunction::finalizeCFIState() {
2823 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "Trying to fix CFI states for each BB after reordering.\n"
; } } while (false)
2824 dbgs() << "Trying to fix CFI states for each BB after reordering.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "Trying to fix CFI states for each BB after reordering.\n"
; } } while (false)
;
2825 LLVM_DEBUG(dbgs() << "This is the list of CFI states for each BB of " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "This is the list of CFI states for each BB of "
<< *this << ": "; } } while (false)
2826 << ": ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "This is the list of CFI states for each BB of "
<< *this << ": "; } } while (false)
;
2827
2828 const char *Sep = "";
2829 (void)Sep;
2830 for (FunctionFragment &FF : Layout.fragments()) {
2831 // Hot-cold border: at start of each region (with a different FDE) we need
2832 // to reset the CFI state.
2833 int32_t State = 0;
2834
2835 for (BinaryBasicBlock *BB : FF) {
2836 const int32_t CFIStateAtExit = BB->getCFIStateAtExit();
2837
2838 // We need to recover the correct state if it doesn't match expected
2839 // state at BB entry point.
2840 if (BB->getCFIState() < State) {
2841 // In this case, State is currently higher than what this BB expect it
2842 // to be. To solve this, we need to insert CFI instructions to undo
2843 // the effect of all CFI from BB's state to current State.
2844 auto InsertIt = BB->begin();
2845 unwindCFIState(State, BB->getCFIState(), BB, InsertIt);
2846 } else if (BB->getCFIState() > State) {
2847 // If BB's CFI state is greater than State, it means we are behind in
2848 // the state. Just emit all instructions to reach this state at the
2849 // beginning of this BB. If this sequence of instructions involve
2850 // remember state or restore state, bail out.
2851 if (!replayCFIInstrs(State, BB->getCFIState(), BB, BB->begin()))
2852 return false;
2853 }
2854
2855 State = CFIStateAtExit;
2856 LLVM_DEBUG(dbgs() << Sep << State; Sep = ", ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << Sep << State; Sep = ", "; }
} while (false)
;
2857 }
2858 }
2859 LLVM_DEBUG(dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "\n"; } } while (false)
;
2860
2861 for (BinaryBasicBlock &BB : blocks()) {
2862 for (auto II = BB.begin(); II != BB.end();) {
2863 const MCCFIInstruction *CFI = getCFIFor(*II);
2864 if (CFI && (CFI->getOperation() == MCCFIInstruction::OpRememberState ||
2865 CFI->getOperation() == MCCFIInstruction::OpRestoreState)) {
2866 II = BB.eraseInstruction(II);
2867 } else {
2868 ++II;
2869 }
2870 }
2871 }
2872
2873 return true;
2874}
2875
2876bool BinaryFunction::requiresAddressTranslation() const {
2877 return opts::EnableBAT || hasSDTMarker() || hasPseudoProbe();
2878}
2879
2880uint64_t BinaryFunction::getInstructionCount() const {
2881 uint64_t Count = 0;
2882 for (const BinaryBasicBlock &BB : blocks())
2883 Count += BB.getNumNonPseudos();
2884 return Count;
2885}
2886
2887void BinaryFunction::clearDisasmState() {
2888 clearList(Instructions);
2889 clearList(IgnoredBranches);
2890 clearList(TakenBranches);
2891
2892 if (BC.HasRelocations) {
2893 for (std::pair<const uint32_t, MCSymbol *> &LI : Labels)
2894 BC.UndefinedSymbols.insert(LI.second);
2895 for (MCSymbol *const EndLabel : FunctionEndLabels)
2896 if (EndLabel)
2897 BC.UndefinedSymbols.insert(EndLabel);
2898 }
2899}
2900
2901void BinaryFunction::setTrapOnEntry() {
2902 clearDisasmState();
2903
2904 auto addTrapAtOffset = [&](uint64_t Offset) {
2905 MCInst TrapInstr;
2906 BC.MIB->createTrap(TrapInstr);
2907 addInstruction(Offset, std::move(TrapInstr));
2908 };
2909
2910 addTrapAtOffset(0);
2911 for (const std::pair<const uint32_t, MCSymbol *> &KV : getLabels())
2912 if (getSecondaryEntryPointSymbol(KV.second))
2913 addTrapAtOffset(KV.first);
2914
2915 TrapsOnEntry = true;
2916}
2917
2918void BinaryFunction::setIgnored() {
2919 if (opts::processAllFunctions()) {
2920 // We can accept ignored functions before they've been disassembled.
2921 // In that case, they would still get disassembled and emited, but not
2922 // optimized.
2923 assert(CurrentState == State::Empty &&(static_cast <bool> (CurrentState == State::Empty &&
"cannot ignore non-empty functions in current mode") ? void (
0) : __assert_fail ("CurrentState == State::Empty && \"cannot ignore non-empty functions in current mode\""
, "bolt/lib/Core/BinaryFunction.cpp", 2924, __extension__ __PRETTY_FUNCTION__
))
2924 "cannot ignore non-empty functions in current mode")(static_cast <bool> (CurrentState == State::Empty &&
"cannot ignore non-empty functions in current mode") ? void (
0) : __assert_fail ("CurrentState == State::Empty && \"cannot ignore non-empty functions in current mode\""
, "bolt/lib/Core/BinaryFunction.cpp", 2924, __extension__ __PRETTY_FUNCTION__
))
;
2925 IsIgnored = true;
2926 return;
2927 }
2928
2929 clearDisasmState();
2930
2931 // Clear CFG state too.
2932 if (hasCFG()) {
2933 releaseCFG();
2934
2935 for (BinaryBasicBlock *BB : BasicBlocks)
2936 delete BB;
2937 clearList(BasicBlocks);
2938
2939 for (BinaryBasicBlock *BB : DeletedBasicBlocks)
2940 delete BB;
2941 clearList(DeletedBasicBlocks);
2942
2943 Layout.clear();
2944 }
2945
2946 CurrentState = State::Empty;
2947
2948 IsIgnored = true;
2949 IsSimple = false;
2950 LLVM_DEBUG(dbgs() << "Ignoring " << getPrintName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "Ignoring " << getPrintName
() << '\n'; } } while (false)
;
2951}
2952
2953void BinaryFunction::duplicateConstantIslands() {
2954 assert(Islands && "function expected to have constant islands")(static_cast <bool> (Islands && "function expected to have constant islands"
) ? void (0) : __assert_fail ("Islands && \"function expected to have constant islands\""
, "bolt/lib/Core/BinaryFunction.cpp", 2954, __extension__ __PRETTY_FUNCTION__
))
;
2955
2956 for (BinaryBasicBlock *BB : getLayout().blocks()) {
2957 if (!BB->isCold())
2958 continue;
2959
2960 for (MCInst &Inst : *BB) {
2961 int OpNum = 0;
2962 for (MCOperand &Operand : Inst) {
2963 if (!Operand.isExpr()) {
2964 ++OpNum;
2965 continue;
2966 }
2967 const MCSymbol *Symbol = BC.MIB->getTargetSymbol(Inst, OpNum);
2968 // Check if this is an island symbol
2969 if (!Islands->Symbols.count(Symbol) &&
2970 !Islands->ProxySymbols.count(Symbol))
2971 continue;
2972
2973 // Create cold symbol, if missing
2974 auto ISym = Islands->ColdSymbols.find(Symbol);
2975 MCSymbol *ColdSymbol;
2976 if (ISym != Islands->ColdSymbols.end()) {
2977 ColdSymbol = ISym->second;
2978 } else {
2979 ColdSymbol = BC.Ctx->getOrCreateSymbol(Symbol->getName() + ".cold");
2980 Islands->ColdSymbols[Symbol] = ColdSymbol;
2981 // Check if this is a proxy island symbol and update owner proxy map
2982 if (Islands->ProxySymbols.count(Symbol)) {
2983 BinaryFunction *Owner = Islands->ProxySymbols[Symbol];
2984 auto IProxiedSym = Owner->Islands->Proxies[this].find(Symbol);
2985 Owner->Islands->ColdProxies[this][IProxiedSym->second] = ColdSymbol;
2986 }
2987 }
2988
2989 // Update instruction reference
2990 Operand = MCOperand::createExpr(BC.MIB->getTargetExprFor(
2991 Inst,
2992 MCSymbolRefExpr::create(ColdSymbol, MCSymbolRefExpr::VK_None,
2993 *BC.Ctx),
2994 *BC.Ctx, 0));
2995 ++OpNum;
2996 }
2997 }
2998 }
2999}
3000
3001namespace {
3002
3003#ifndef MAX_PATH255
3004#define MAX_PATH255 255
3005#endif
3006
3007std::string constructFilename(std::string Filename, std::string Annotation,
3008 std::string Suffix) {
3009 std::replace(Filename.begin(), Filename.end(), '/', '-');
3010 if (!Annotation.empty())
3011 Annotation.insert(0, "-");
3012 if (Filename.size() + Annotation.size() + Suffix.size() > MAX_PATH255) {
3013 assert(Suffix.size() + Annotation.size() <= MAX_PATH)(static_cast <bool> (Suffix.size() + Annotation.size() <=
255) ? void (0) : __assert_fail ("Suffix.size() + Annotation.size() <= MAX_PATH"
, "bolt/lib/Core/BinaryFunction.cpp", 3013, __extension__ __PRETTY_FUNCTION__
))
;
3014 if (opts::Verbosity >= 1) {
3015 errs() << "BOLT-WARNING: Filename \"" << Filename << Annotation << Suffix
3016 << "\" exceeds the " << MAX_PATH255 << " size limit, truncating.\n";
3017 }
3018 Filename.resize(MAX_PATH255 - (Suffix.size() + Annotation.size()));
3019 }
3020 Filename += Annotation;
3021 Filename += Suffix;
3022 return Filename;
3023}
3024
3025std::string formatEscapes(const std::string &Str) {
3026 std::string Result;
3027 for (unsigned I = 0; I < Str.size(); ++I) {
3028 char C = Str[I];
3029 switch (C) {
3030 case '\n':
3031 Result += "&#13;";
3032 break;
3033 case '"':
3034 break;
3035 default:
3036 Result += C;
3037 break;
3038 }
3039 }
3040 return Result;
3041}
3042
3043} // namespace
3044
3045void BinaryFunction::dumpGraph(raw_ostream &OS) const {
3046 OS << "digraph \"" << getPrintName() << "\" {\n"
3047 << "node [fontname=courier, shape=box, style=filled, colorscheme=brbg9]\n";
3048 uint64_t Offset = Address;
3049 for (BinaryBasicBlock *BB : BasicBlocks) {
3050 auto LayoutPos = find(Layout.blocks(), BB);
3051 unsigned LayoutIndex = LayoutPos - Layout.block_begin();
3052 const char *ColdStr = BB->isCold() ? " (cold)" : "";
3053 std::vector<std::string> Attrs;
3054 // Bold box for entry points
3055 if (isEntryPoint(*BB))
3056 Attrs.push_back("penwidth=2");
3057 if (BLI && BLI->getLoopFor(BB)) {
3058 // Distinguish innermost loops
3059 const BinaryLoop *Loop = BLI->getLoopFor(BB);
3060 if (Loop->isInnermost())
3061 Attrs.push_back("fillcolor=6");
3062 else // some outer loop
3063 Attrs.push_back("fillcolor=4");
3064 } else { // non-loopy code
3065 Attrs.push_back("fillcolor=5");
3066 }
3067 ListSeparator LS;
3068 OS << "\"" << BB->getName() << "\" [";
3069 for (StringRef Attr : Attrs)
3070 OS << LS << Attr;
3071 OS << "]\n";
3072 OS << format("\"%s\" [label=\"%s%s\\n(C:%lu,O:%lu,I:%u,L:%u,CFI:%u)\\n",
3073 BB->getName().data(), BB->getName().data(), ColdStr,
3074 BB->getKnownExecutionCount(), BB->getOffset(), getIndex(BB),
3075 LayoutIndex, BB->getCFIState());
3076
3077 if (opts::DotToolTipCode) {
3078 std::string Str;
3079 raw_string_ostream CS(Str);
3080 Offset = BC.printInstructions(CS, BB->begin(), BB->end(), Offset, this,
3081 /* PrintMCInst = */ false,
3082 /* PrintMemData = */ false,
3083 /* PrintRelocations = */ false,
3084 /* Endl = */ R"(\\l)");
3085 OS << formatEscapes(CS.str()) << '\n';
3086 }
3087 OS << "\"]\n";
3088
3089 // analyzeBranch is just used to get the names of the branch
3090 // opcodes.
3091 const MCSymbol *TBB = nullptr;
3092 const MCSymbol *FBB = nullptr;
3093 MCInst *CondBranch = nullptr;
3094 MCInst *UncondBranch = nullptr;
3095 const bool Success = BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch);
3096
3097 const MCInst *LastInstr = BB->getLastNonPseudoInstr();
3098 const bool IsJumpTable = LastInstr && BC.MIB->getJumpTable(*LastInstr);
3099
3100 auto BI = BB->branch_info_begin();
3101 for (BinaryBasicBlock *Succ : BB->successors()) {
3102 std::string Branch;
3103 if (Success) {
3104 if (Succ == BB->getConditionalSuccessor(true)) {
3105 Branch = CondBranch ? std::string(BC.InstPrinter->getOpcodeName(
3106 CondBranch->getOpcode()))
3107 : "TB";
3108 } else if (Succ == BB->getConditionalSuccessor(false)) {
3109 Branch = UncondBranch ? std::string(BC.InstPrinter->getOpcodeName(
3110 UncondBranch->getOpcode()))
3111 : "FB";
3112 } else {
3113 Branch = "FT";
3114 }
3115 }
3116 if (IsJumpTable)
3117 Branch = "JT";
3118 OS << format("\"%s\" -> \"%s\" [label=\"%s", BB->getName().data(),
3119 Succ->getName().data(), Branch.c_str());
3120
3121 if (BB->getExecutionCount() != COUNT_NO_PROFILE &&
3122 BI->MispredictedCount != BinaryBasicBlock::COUNT_INFERRED) {
3123 OS << "\\n(C:" << BI->Count << ",M:" << BI->MispredictedCount << ")";
3124 } else if (ExecutionCount != COUNT_NO_PROFILE &&
3125 BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE) {
3126 OS << "\\n(IC:" << BI->Count << ")";
3127 }
3128 OS << "\"]\n";
3129
3130 ++BI;
3131 }
3132 for (BinaryBasicBlock *LP : BB->landing_pads()) {
3133 OS << format("\"%s\" -> \"%s\" [constraint=false style=dashed]\n",
3134 BB->getName().data(), LP->getName().data());
3135 }
3136 }
3137 OS << "}\n";
3138}
3139
3140void BinaryFunction::viewGraph() const {
3141 SmallString<MAX_PATH255> Filename;
3142 if (std::error_code EC =
3143 sys::fs::createTemporaryFile("bolt-cfg", "dot", Filename)) {
3144 errs() << "BOLT-ERROR: " << EC.message() << ", unable to create "
3145 << " bolt-cfg-XXXXX.dot temporary file.\n";
3146 return;
3147 }
3148 dumpGraphToFile(std::string(Filename));
3149 if (DisplayGraph(Filename))
3150 errs() << "BOLT-ERROR: Can't display " << Filename << " with graphviz.\n";
3151 if (std::error_code EC = sys::fs::remove(Filename)) {
3152 errs() << "BOLT-WARNING: " << EC.message() << ", failed to remove "
3153 << Filename << "\n";
3154 }
3155}
3156
3157void BinaryFunction::dumpGraphForPass(std::string Annotation) const {
3158 if (!opts::shouldPrint(*this))
3159 return;
3160
3161 std::string Filename = constructFilename(getPrintName(), Annotation, ".dot");
3162 if (opts::Verbosity >= 1)
3163 outs() << "BOLT-INFO: dumping CFG to " << Filename << "\n";
3164 dumpGraphToFile(Filename);
3165}
3166
3167void BinaryFunction::dumpGraphToFile(std::string Filename) const {
3168 std::error_code EC;
3169 raw_fd_ostream of(Filename, EC, sys::fs::OF_None);
3170 if (EC) {
3171 if (opts::Verbosity >= 1) {
3172 errs() << "BOLT-WARNING: " << EC.message() << ", unable to open "
3173 << Filename << " for output.\n";
3174 }
3175 return;
3176 }
3177 dumpGraph(of);
3178}
3179
3180bool BinaryFunction::validateCFG() const {
3181 bool Valid = true;
3182 for (BinaryBasicBlock *BB : BasicBlocks)
3183 Valid &= BB->validateSuccessorInvariants();
3184
3185 if (!Valid)
3186 return Valid;
3187
3188 // Make sure all blocks in CFG are valid.
3189 auto validateBlock = [this](const BinaryBasicBlock *BB, StringRef Desc) {
3190 if (!BB->isValid()) {
3191 errs() << "BOLT-ERROR: deleted " << Desc << " " << BB->getName()
3192 << " detected in:\n";
3193 this->dump();
3194 return false;
3195 }
3196 return true;
3197 };
3198 for (const BinaryBasicBlock *BB : BasicBlocks) {
3199 if (!validateBlock(BB, "block"))
3200 return false;
3201 for (const BinaryBasicBlock *PredBB : BB->predecessors())
3202 if (!validateBlock(PredBB, "predecessor"))
3203 return false;
3204 for (const BinaryBasicBlock *SuccBB : BB->successors())
3205 if (!validateBlock(SuccBB, "successor"))
3206 return false;
3207 for (const BinaryBasicBlock *LP : BB->landing_pads())
3208 if (!validateBlock(LP, "landing pad"))
3209 return false;
3210 for (const BinaryBasicBlock *Thrower : BB->throwers())
3211 if (!validateBlock(Thrower, "thrower"))
3212 return false;
3213 }
3214
3215 for (const BinaryBasicBlock *BB : BasicBlocks) {
3216 std::unordered_set<const BinaryBasicBlock *> BBLandingPads;
3217 for (const BinaryBasicBlock *LP : BB->landing_pads()) {
3218 if (BBLandingPads.count(LP)) {
3219 errs() << "BOLT-ERROR: duplicate landing pad detected in"
3220 << BB->getName() << " in function " << *this << '\n';
3221 return false;
3222 }
3223 BBLandingPads.insert(LP);
3224 }
3225
3226 std::unordered_set<const BinaryBasicBlock *> BBThrowers;
3227 for (const BinaryBasicBlock *Thrower : BB->throwers()) {
3228 if (BBThrowers.count(Thrower)) {
3229 errs() << "BOLT-ERROR: duplicate thrower detected in" << BB->getName()
3230 << " in function " << *this << '\n';
3231 return false;
3232 }
3233 BBThrowers.insert(Thrower);
3234 }
3235
3236 for (const BinaryBasicBlock *LPBlock : BB->landing_pads()) {
3237 if (!llvm::is_contained(LPBlock->throwers(), BB)) {
3238 errs() << "BOLT-ERROR: inconsistent landing pad detected in " << *this
3239 << ": " << BB->getName() << " is in LandingPads but not in "
3240 << LPBlock->getName() << " Throwers\n";
3241 return false;
3242 }
3243 }
3244 for (const BinaryBasicBlock *Thrower : BB->throwers()) {
3245 if (!llvm::is_contained(Thrower->landing_pads(), BB)) {
3246 errs() << "BOLT-ERROR: inconsistent thrower detected in " << *this
3247 << ": " << BB->getName() << " is in Throwers list but not in "
3248 << Thrower->getName() << " LandingPads\n";
3249 return false;
3250 }
3251 }
3252 }
3253
3254 return Valid;
3255}
3256
3257void BinaryFunction::fixBranches() {
3258 auto &MIB = BC.MIB;
3259 MCContext *Ctx = BC.Ctx.get();
3260
3261 for (BinaryBasicBlock *BB : BasicBlocks) {
3262 const MCSymbol *TBB = nullptr;
3263 const MCSymbol *FBB = nullptr;
3264 MCInst *CondBranch = nullptr;
3265 MCInst *UncondBranch = nullptr;
3266 if (!BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch))
3267 continue;
3268
3269 // We will create unconditional branch with correct destination if needed.
3270 if (UncondBranch)
3271 BB->eraseInstruction(BB->findInstruction(UncondBranch));
3272
3273 // Basic block that follows the current one in the final layout.
3274 const BinaryBasicBlock *NextBB =
3275 Layout.getBasicBlockAfter(BB, /*IgnoreSplits=*/false);
3276
3277 if (BB->succ_size() == 1) {
3278 // __builtin_unreachable() could create a conditional branch that
3279 // falls-through into the next function - hence the block will have only
3280 // one valid successor. Since behaviour is undefined - we replace
3281 // the conditional branch with an unconditional if required.
3282 if (CondBranch)
3283 BB->eraseInstruction(BB->findInstruction(CondBranch));
3284 if (BB->getSuccessor() == NextBB)
3285 continue;
3286 BB->addBranchInstruction(BB->getSuccessor());
3287 } else if (BB->succ_size() == 2) {
3288 assert(CondBranch && "conditional branch expected")(static_cast <bool> (CondBranch && "conditional branch expected"
) ? void (0) : __assert_fail ("CondBranch && \"conditional branch expected\""
, "bolt/lib/Core/BinaryFunction.cpp", 3288, __extension__ __PRETTY_FUNCTION__
))
;
3289 const BinaryBasicBlock *TSuccessor = BB->getConditionalSuccessor(true);
3290 const BinaryBasicBlock *FSuccessor = BB->getConditionalSuccessor(false);
3291 // Check whether we support reversing this branch direction
3292 const bool IsSupported =
3293 !MIB->isUnsupportedBranch(CondBranch->getOpcode());
3294 if (NextBB && NextBB == TSuccessor && IsSupported) {
3295 std::swap(TSuccessor, FSuccessor);
3296 {
3297 auto L = BC.scopeLock();
3298 MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(), Ctx);
3299 }
3300 BB->swapConditionalSuccessors();
3301 } else {
3302 auto L = BC.scopeLock();
3303 MIB->replaceBranchTarget(*CondBranch, TSuccessor->getLabel(), Ctx);
3304 }
3305 if (TSuccessor == FSuccessor)
3306 BB->removeDuplicateConditionalSuccessor(CondBranch);
3307 if (!NextBB ||
3308 ((NextBB != TSuccessor || !IsSupported) && NextBB != FSuccessor)) {
3309 // If one of the branches is guaranteed to be "long" while the other
3310 // could be "short", then prioritize short for "taken". This will
3311 // generate a sequence 1 byte shorter on x86.
3312 if (IsSupported && BC.isX86() &&
3313 TSuccessor->getFragmentNum() != FSuccessor->getFragmentNum() &&
3314 BB->getFragmentNum() != TSuccessor->getFragmentNum()) {
3315 std::swap(TSuccessor, FSuccessor);
3316 {
3317 auto L = BC.scopeLock();
3318 MIB->reverseBranchCondition(*CondBranch, TSuccessor->getLabel(),
3319 Ctx);
3320 }
3321 BB->swapConditionalSuccessors();
3322 }
3323 BB->addBranchInstruction(FSuccessor);
3324 }
3325 }
3326 // Cases where the number of successors is 0 (block ends with a
3327 // terminator) or more than 2 (switch table) don't require branch
3328 // instruction adjustments.
3329 }
3330 assert((!isSimple() || validateCFG()) &&(static_cast <bool> ((!isSimple() || validateCFG()) &&
"Invalid CFG detected after fixing branches") ? void (0) : __assert_fail
("(!isSimple() || validateCFG()) && \"Invalid CFG detected after fixing branches\""
, "bolt/lib/Core/BinaryFunction.cpp", 3331, __extension__ __PRETTY_FUNCTION__
))
3331 "Invalid CFG detected after fixing branches")(static_cast <bool> ((!isSimple() || validateCFG()) &&
"Invalid CFG detected after fixing branches") ? void (0) : __assert_fail
("(!isSimple() || validateCFG()) && \"Invalid CFG detected after fixing branches\""
, "bolt/lib/Core/BinaryFunction.cpp", 3331, __extension__ __PRETTY_FUNCTION__
))
;
3332}
3333
3334void BinaryFunction::propagateGnuArgsSizeInfo(
3335 MCPlusBuilder::AllocatorIdTy AllocId) {
3336 assert(CurrentState == State::Disassembled && "unexpected function state")(static_cast <bool> (CurrentState == State::Disassembled
&& "unexpected function state") ? void (0) : __assert_fail
("CurrentState == State::Disassembled && \"unexpected function state\""
, "bolt/lib/Core/BinaryFunction.cpp", 3336, __extension__ __PRETTY_FUNCTION__
))
;
3337
3338 if (!hasEHRanges() || !usesGnuArgsSize())
3339 return;
3340
3341 // The current value of DW_CFA_GNU_args_size affects all following
3342 // invoke instructions until the next CFI overrides it.
3343 // It is important to iterate basic blocks in the original order when
3344 // assigning the value.
3345 uint64_t CurrentGnuArgsSize = 0;
3346 for (BinaryBasicBlock *BB : BasicBlocks) {
3347 for (auto II = BB->begin(); II != BB->end();) {
3348 MCInst &Instr = *II;
3349 if (BC.MIB->isCFI(Instr)) {
3350 const MCCFIInstruction *CFI = getCFIFor(Instr);
3351 if (CFI->getOperation() == MCCFIInstruction::OpGnuArgsSize) {
3352 CurrentGnuArgsSize = CFI->getOffset();
3353 // Delete DW_CFA_GNU_args_size instructions and only regenerate
3354 // during the final code emission. The information is embedded
3355 // inside call instructions.
3356 II = BB->erasePseudoInstruction(II);
3357 continue;
3358 }
3359 } else if (BC.MIB->isInvoke(Instr)) {
3360 // Add the value of GNU_args_size as an extra operand to invokes.
3361 BC.MIB->addGnuArgsSize(Instr, CurrentGnuArgsSize, AllocId);
3362 }
3363 ++II;
3364 }
3365 }
3366}
3367
3368void BinaryFunction::postProcessBranches() {
3369 if (!isSimple())
3370 return;
3371 for (BinaryBasicBlock &BB : blocks()) {
3372 auto LastInstrRI = BB.getLastNonPseudo();
3373 if (BB.succ_size() == 1) {
3374 if (LastInstrRI != BB.rend() &&
3375 BC.MIB->isConditionalBranch(*LastInstrRI)) {
3376 // __builtin_unreachable() could create a conditional branch that
3377 // falls-through into the next function - hence the block will have only
3378 // one valid successor. Such behaviour is undefined and thus we remove
3379 // the conditional branch while leaving a valid successor.
3380 BB.eraseInstruction(std::prev(LastInstrRI.base()));
3381 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: erasing conditional branch in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: erasing conditional branch in "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
3382 << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: erasing conditional branch in "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
;
3383 }
3384 } else if (BB.succ_size() == 0) {
3385 // Ignore unreachable basic blocks.
3386 if (BB.pred_size() == 0 || BB.isLandingPad())
3387 continue;
3388
3389 // If it's the basic block that does not end up with a terminator - we
3390 // insert a return instruction unless it's a call instruction.
3391 if (LastInstrRI == BB.rend()) {
3392 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
3393 dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
3394 << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: at least one instruction expected in BB "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
;
3395 continue;
3396 }
3397 if (!BC.MIB->isTerminator(*LastInstrRI) &&
3398 !BC.MIB->isCall(*LastInstrRI)) {
3399 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: adding return to basic block "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: adding return to basic block "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
3400 << BB.getName() << " in function " << *this << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: adding return to basic block "
<< BB.getName() << " in function " << *this
<< '\n'; } } while (false)
;
3401 MCInst ReturnInstr;
3402 BC.MIB->createReturn(ReturnInstr);
3403 BB.addInstruction(ReturnInstr);
3404 }
3405 }
3406 }
3407 assert(validateCFG() && "invalid CFG")(static_cast <bool> (validateCFG() && "invalid CFG"
) ? void (0) : __assert_fail ("validateCFG() && \"invalid CFG\""
, "bolt/lib/Core/BinaryFunction.cpp", 3407, __extension__ __PRETTY_FUNCTION__
))
;
3408}
3409
3410MCSymbol *BinaryFunction::addEntryPointAtOffset(uint64_t Offset) {
3411 assert(Offset && "cannot add primary entry point")(static_cast <bool> (Offset && "cannot add primary entry point"
) ? void (0) : __assert_fail ("Offset && \"cannot add primary entry point\""
, "bolt/lib/Core/BinaryFunction.cpp", 3411, __extension__ __PRETTY_FUNCTION__
))
;
3412 assert(CurrentState == State::Empty || CurrentState == State::Disassembled)(static_cast <bool> (CurrentState == State::Empty || CurrentState
== State::Disassembled) ? void (0) : __assert_fail ("CurrentState == State::Empty || CurrentState == State::Disassembled"
, "bolt/lib/Core/BinaryFunction.cpp", 3412, __extension__ __PRETTY_FUNCTION__
))
;
3413
3414 const uint64_t EntryPointAddress = getAddress() + Offset;
3415 MCSymbol *LocalSymbol = getOrCreateLocalLabel(EntryPointAddress);
3416
3417 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(LocalSymbol);
3418 if (EntrySymbol)
3419 return EntrySymbol;
3420
3421 if (BinaryData *EntryBD = BC.getBinaryDataAtAddress(EntryPointAddress)) {
3422 EntrySymbol = EntryBD->getSymbol();
3423 } else {
3424 EntrySymbol = BC.getOrCreateGlobalSymbol(
3425 EntryPointAddress, Twine("__ENTRY_") + getOneName() + "@");
3426 }
3427 SecondaryEntryPoints[LocalSymbol] = EntrySymbol;
3428
3429 BC.setSymbolToFunctionMap(EntrySymbol, this);
3430
3431 return EntrySymbol;
3432}
3433
3434MCSymbol *BinaryFunction::addEntryPoint(const BinaryBasicBlock &BB) {
3435 assert(CurrentState == State::CFG &&(static_cast <bool> (CurrentState == State::CFG &&
"basic block can be added as an entry only in a function with CFG"
) ? void (0) : __assert_fail ("CurrentState == State::CFG && \"basic block can be added as an entry only in a function with CFG\""
, "bolt/lib/Core/BinaryFunction.cpp", 3436, __extension__ __PRETTY_FUNCTION__
))
3436 "basic block can be added as an entry only in a function with CFG")(static_cast <bool> (CurrentState == State::CFG &&
"basic block can be added as an entry only in a function with CFG"
) ? void (0) : __assert_fail ("CurrentState == State::CFG && \"basic block can be added as an entry only in a function with CFG\""
, "bolt/lib/Core/BinaryFunction.cpp", 3436, __extension__ __PRETTY_FUNCTION__
))
;
3437
3438 if (&BB == BasicBlocks.front())
3439 return getSymbol();
3440
3441 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(BB);
3442 if (EntrySymbol)
3443 return EntrySymbol;
3444
3445 EntrySymbol =
3446 BC.Ctx->getOrCreateSymbol("__ENTRY_" + BB.getLabel()->getName());
3447
3448 SecondaryEntryPoints[BB.getLabel()] = EntrySymbol;
3449
3450 BC.setSymbolToFunctionMap(EntrySymbol, this);
3451
3452 return EntrySymbol;
3453}
3454
3455MCSymbol *BinaryFunction::getSymbolForEntryID(uint64_t EntryID) {
3456 if (EntryID == 0)
3457 return getSymbol();
3458
3459 if (!isMultiEntry())
3460 return nullptr;
3461
3462 uint64_t NumEntries = 0;
3463 if (hasCFG()) {
3464 for (BinaryBasicBlock *BB : BasicBlocks) {
3465 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB);
3466 if (!EntrySymbol)
3467 continue;
3468 if (NumEntries == EntryID)
3469 return EntrySymbol;
3470 ++NumEntries;
3471 }
3472 } else {
3473 for (std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3474 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
3475 if (!EntrySymbol)
3476 continue;
3477 if (NumEntries == EntryID)
3478 return EntrySymbol;
3479 ++NumEntries;
3480 }
3481 }
3482
3483 return nullptr;
3484}
3485
3486uint64_t BinaryFunction::getEntryIDForSymbol(const MCSymbol *Symbol) const {
3487 if (!isMultiEntry())
3488 return 0;
3489
3490 for (const MCSymbol *FunctionSymbol : getSymbols())
3491 if (FunctionSymbol == Symbol)
3492 return 0;
3493
3494 // Check all secondary entries available as either basic blocks or lables.
3495 uint64_t NumEntries = 0;
3496 for (const BinaryBasicBlock *BB : BasicBlocks) {
3497 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(*BB);
3498 if (!EntrySymbol)
3499 continue;
3500 if (EntrySymbol == Symbol)
3501 return NumEntries;
3502 ++NumEntries;
3503 }
3504 NumEntries = 0;
3505 for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3506 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
3507 if (!EntrySymbol)
3508 continue;
3509 if (EntrySymbol == Symbol)
3510 return NumEntries;
3511 ++NumEntries;
3512 }
3513
3514 llvm_unreachable("symbol not found")::llvm::llvm_unreachable_internal("symbol not found", "bolt/lib/Core/BinaryFunction.cpp"
, 3514)
;
3515}
3516
3517bool BinaryFunction::forEachEntryPoint(EntryPointCallbackTy Callback) const {
3518 bool Status = Callback(0, getSymbol());
3519 if (!isMultiEntry())
3520 return Status;
3521
3522 for (const std::pair<const uint32_t, MCSymbol *> &KV : Labels) {
3523 if (!Status)
3524 break;
3525
3526 MCSymbol *EntrySymbol = getSecondaryEntryPointSymbol(KV.second);
3527 if (!EntrySymbol)
3528 continue;
3529
3530 Status = Callback(KV.first, EntrySymbol);
3531 }
3532
3533 return Status;
3534}
3535
3536BinaryFunction::BasicBlockListType BinaryFunction::dfs() const {
3537 BasicBlockListType DFS;
3538 unsigned Index = 0;
3539 std::stack<BinaryBasicBlock *> Stack;
3540
3541 // Push entry points to the stack in reverse order.
3542 //
3543 // NB: we rely on the original order of entries to match.
3544 SmallVector<BinaryBasicBlock *> EntryPoints;
3545 llvm::copy_if(BasicBlocks, std::back_inserter(EntryPoints),
3546 [&](const BinaryBasicBlock *const BB) { return isEntryPoint(*BB); });
3547 // Sort entry points by their offset to make sure we got them in the right
3548 // order.
3549 llvm::stable_sort(EntryPoints, [](const BinaryBasicBlock *const A,
3550 const BinaryBasicBlock *const B) {
3551 return A->getOffset() < B->getOffset();
3552 });
3553 for (BinaryBasicBlock *const BB : reverse(EntryPoints))
3554 Stack.push(BB);
3555
3556 for (BinaryBasicBlock &BB : blocks())
3557 BB.setLayoutIndex(BinaryBasicBlock::InvalidIndex);
3558
3559 while (!Stack.empty()) {
3560 BinaryBasicBlock *BB = Stack.top();
3561 Stack.pop();
3562
3563 if (BB->getLayoutIndex() != BinaryBasicBlock::InvalidIndex)
3564 continue;
3565
3566 BB->setLayoutIndex(Index++);
3567 DFS.push_back(BB);
3568
3569 for (BinaryBasicBlock *SuccBB : BB->landing_pads()) {
3570 Stack.push(SuccBB);
3571 }
3572
3573 const MCSymbol *TBB = nullptr;
3574 const MCSymbol *FBB = nullptr;
3575 MCInst *CondBranch = nullptr;
3576 MCInst *UncondBranch = nullptr;
3577 if (BB->analyzeBranch(TBB, FBB, CondBranch, UncondBranch) && CondBranch &&
3578 BB->succ_size() == 2) {
3579 if (BC.MIB->getCanonicalBranchCondCode(BC.MIB->getCondCode(
3580 *CondBranch)) == BC.MIB->getCondCode(*CondBranch)) {
3581 Stack.push(BB->getConditionalSuccessor(true));
3582 Stack.push(BB->getConditionalSuccessor(false));
3583 } else {
3584 Stack.push(BB->getConditionalSuccessor(false));
3585 Stack.push(BB->getConditionalSuccessor(true));
3586 }
3587 } else {
3588 for (BinaryBasicBlock *SuccBB : BB->successors()) {
3589 Stack.push(SuccBB);
3590 }
3591 }
3592 }
3593
3594 return DFS;
3595}
3596
3597size_t BinaryFunction::computeHash(bool UseDFS,
3598 OperandHashFuncTy OperandHashFunc) const {
3599 if (size() == 0)
3600 return 0;
3601
3602 assert(hasCFG() && "function is expected to have CFG")(static_cast <bool> (hasCFG() && "function is expected to have CFG"
) ? void (0) : __assert_fail ("hasCFG() && \"function is expected to have CFG\""
, "bolt/lib/Core/BinaryFunction.cpp", 3602, __extension__ __PRETTY_FUNCTION__
))
;
3603
3604 SmallVector<const BinaryBasicBlock *, 0> Order;
3605 if (UseDFS)
3606 llvm::copy(dfs(), std::back_inserter(Order));
3607 else
3608 llvm::copy(Layout.blocks(), std::back_inserter(Order));
3609
3610 // The hash is computed by creating a string of all instruction opcodes and
3611 // possibly their operands and then hashing that string with std::hash.
3612 std::string HashString;
3613 for (const BinaryBasicBlock *BB : Order) {
3614 for (const MCInst &Inst : *BB) {
3615 unsigned Opcode = Inst.getOpcode();
3616
3617 if (BC.MIB->isPseudo(Inst))
3618 continue;
3619
3620 // Ignore unconditional jumps since we check CFG consistency by processing
3621 // basic blocks in order and do not rely on branches to be in-sync with
3622 // CFG. Note that we still use condition code of conditional jumps.
3623 if (BC.MIB->isUnconditionalBranch(Inst))
3624 continue;
3625
3626 if (Opcode == 0)
3627 HashString.push_back(0);
3628
3629 while (Opcode) {
3630 uint8_t LSB = Opcode & 0xff;
3631 HashString.push_back(LSB);
3632 Opcode = Opcode >> 8;
3633 }
3634
3635 for (const MCOperand &Op : MCPlus::primeOperands(Inst))
3636 HashString.append(OperandHashFunc(Op));
3637 }
3638 }
3639
3640 return Hash = std::hash<std::string>{}(HashString);
3641}
3642
3643void BinaryFunction::insertBasicBlocks(
3644 BinaryBasicBlock *Start,
3645 std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
3646 const bool UpdateLayout, const bool UpdateCFIState,
3647 const bool RecomputeLandingPads) {
3648 const int64_t StartIndex = Start ? getIndex(Start) : -1LL;
3649 const size_t NumNewBlocks = NewBBs.size();
3650
3651 BasicBlocks.insert(BasicBlocks.begin() + (StartIndex + 1), NumNewBlocks,
3652 nullptr);
3653
3654 int64_t I = StartIndex + 1;
3655 for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
3656 assert(!BasicBlocks[I])(static_cast <bool> (!BasicBlocks[I]) ? void (0) : __assert_fail
("!BasicBlocks[I]", "bolt/lib/Core/BinaryFunction.cpp", 3656
, __extension__ __PRETTY_FUNCTION__))
;
3657 BasicBlocks[I++] = BB.release();
3658 }
3659
3660 if (RecomputeLandingPads)
3661 recomputeLandingPads();
3662 else
3663 updateBBIndices(0);
3664
3665 if (UpdateLayout)
3666 updateLayout(Start, NumNewBlocks);
3667
3668 if (UpdateCFIState)
3669 updateCFIState(Start, NumNewBlocks);
3670}
3671
3672BinaryFunction::iterator BinaryFunction::insertBasicBlocks(
3673 BinaryFunction::iterator StartBB,
3674 std::vector<std::unique_ptr<BinaryBasicBlock>> &&NewBBs,
3675 const bool UpdateLayout, const bool UpdateCFIState,
3676 const bool RecomputeLandingPads) {
3677 const unsigned StartIndex = getIndex(&*StartBB);
3678 const size_t NumNewBlocks = NewBBs.size();
3679
3680 BasicBlocks.insert(BasicBlocks.begin() + StartIndex + 1, NumNewBlocks,
3681 nullptr);
3682 auto RetIter = BasicBlocks.begin() + StartIndex + 1;
3683
3684 unsigned I = StartIndex + 1;
3685 for (std::unique_ptr<BinaryBasicBlock> &BB : NewBBs) {
3686 assert(!BasicBlocks[I])(static_cast <bool> (!BasicBlocks[I]) ? void (0) : __assert_fail
("!BasicBlocks[I]", "bolt/lib/Core/BinaryFunction.cpp", 3686
, __extension__ __PRETTY_FUNCTION__))
;
3687 BasicBlocks[I++] = BB.release();
3688 }
3689
3690 if (RecomputeLandingPads)
3691 recomputeLandingPads();
3692 else
3693 updateBBIndices(0);
3694
3695 if (UpdateLayout)
3696 updateLayout(*std::prev(RetIter), NumNewBlocks);
3697
3698 if (UpdateCFIState)
3699 updateCFIState(*std::prev(RetIter), NumNewBlocks);
3700
3701 return RetIter;
3702}
3703
3704void BinaryFunction::updateBBIndices(const unsigned StartIndex) {
3705 for (unsigned I = StartIndex; I < BasicBlocks.size(); ++I)
3706 BasicBlocks[I]->Index = I;
3707}
3708
3709void BinaryFunction::updateCFIState(BinaryBasicBlock *Start,
3710 const unsigned NumNewBlocks) {
3711 const int32_t CFIState = Start->getCFIStateAtExit();
3712 const unsigned StartIndex = getIndex(Start) + 1;
3713 for (unsigned I = 0; I < NumNewBlocks; ++I)
3714 BasicBlocks[StartIndex + I]->setCFIState(CFIState);
3715}
3716
3717void BinaryFunction::updateLayout(BinaryBasicBlock *Start,
3718 const unsigned NumNewBlocks) {
3719 BasicBlockListType::iterator Begin;
3720 BasicBlockListType::iterator End;
3721
3722 // If start not provided copy new blocks from the beginning of BasicBlocks
3723 if (!Start) {
3724 Begin = BasicBlocks.begin();
3725 End = BasicBlocks.begin() + NumNewBlocks;
3726 } else {
3727 unsigned StartIndex = getIndex(Start);
3728 Begin = std::next(BasicBlocks.begin(), StartIndex + 1);
3729 End = std::next(BasicBlocks.begin(), StartIndex + NumNewBlocks + 1);
3730 }
3731
3732 // Insert new blocks in the layout immediately after Start.
3733 Layout.insertBasicBlocks(Start, {Begin, End});
3734 Layout.updateLayoutIndices();
3735}
3736
3737bool BinaryFunction::checkForAmbiguousJumpTables() {
3738 SmallSet<uint64_t, 4> JumpTables;
3739 for (BinaryBasicBlock *&BB : BasicBlocks) {
3740 for (MCInst &Inst : *BB) {
3741 if (!BC.MIB->isIndirectBranch(Inst))
3742 continue;
3743 uint64_t JTAddress = BC.MIB->getJumpTable(Inst);
3744 if (!JTAddress)
3745 continue;
3746 // This address can be inside another jump table, but we only consider
3747 // it ambiguous when the same start address is used, not the same JT
3748 // object.
3749 if (!JumpTables.count(JTAddress)) {
3750 JumpTables.insert(JTAddress);
3751 continue;
3752 }
3753 return true;
3754 }
3755 }
3756 return false;
3757}
3758
3759void BinaryFunction::disambiguateJumpTables(
3760 MCPlusBuilder::AllocatorIdTy AllocId) {
3761 assert((opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations)(static_cast <bool> ((opts::JumpTables != JTS_BASIC &&
isSimple()) || !BC.HasRelocations) ? void (0) : __assert_fail
("(opts::JumpTables != JTS_BASIC && isSimple()) || !BC.HasRelocations"
, "bolt/lib/Core/BinaryFunction.cpp", 3761, __extension__ __PRETTY_FUNCTION__
))
;
3762 SmallPtrSet<JumpTable *, 4> JumpTables;
3763 for (BinaryBasicBlock *&BB : BasicBlocks) {
3764 for (MCInst &Inst : *BB) {
3765 if (!BC.MIB->isIndirectBranch(Inst))
3766 continue;
3767 JumpTable *JT = getJumpTable(Inst);
3768 if (!JT)
3769 continue;
3770 auto Iter = JumpTables.find(JT);
3771 if (Iter == JumpTables.end()) {
3772 JumpTables.insert(JT);
3773 continue;
3774 }
3775 // This instruction is an indirect jump using a jump table, but it is
3776 // using the same jump table of another jump. Try all our tricks to
3777 // extract the jump table symbol and make it point to a new, duplicated JT
3778 MCPhysReg BaseReg1;
3779 uint64_t Scale;
3780 const MCSymbol *Target;
3781 // In case we match if our first matcher, first instruction is the one to
3782 // patch
3783 MCInst *JTLoadInst = &Inst;
3784 // Try a standard indirect jump matcher, scale 8
3785 std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher =
3786 BC.MIB->matchIndJmp(BC.MIB->matchReg(BaseReg1),
3787 BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
3788 /*Offset=*/BC.MIB->matchSymbol(Target));
3789 if (!IndJmpMatcher->match(
3790 *BC.MRI, *BC.MIB,
3791 MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
3792 BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
3793 MCPhysReg BaseReg2;
3794 uint64_t Offset;
3795 // Standard JT matching failed. Trying now:
3796 // movq "jt.2397/1"(,%rax,8), %rax
3797 // jmpq *%rax
3798 std::unique_ptr<MCPlusBuilder::MCInstMatcher> LoadMatcherOwner =
3799 BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg1),
3800 BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
3801 /*Offset=*/BC.MIB->matchSymbol(Target));
3802 MCPlusBuilder::MCInstMatcher *LoadMatcher = LoadMatcherOwner.get();
3803 std::unique_ptr<MCPlusBuilder::MCInstMatcher> IndJmpMatcher2 =
3804 BC.MIB->matchIndJmp(std::move(LoadMatcherOwner));
3805 if (!IndJmpMatcher2->match(
3806 *BC.MRI, *BC.MIB,
3807 MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
3808 BaseReg1 != BC.MIB->getNoRegister() || Scale != 8) {
3809 // JT matching failed. Trying now:
3810 // PIC-style matcher, scale 4
3811 // addq %rdx, %rsi
3812 // addq %rdx, %rdi
3813 // leaq DATAat0x402450(%rip), %r11
3814 // movslq (%r11,%rdx,4), %rcx
3815 // addq %r11, %rcx
3816 // jmpq *%rcx # JUMPTABLE @0x402450
3817 std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICIndJmpMatcher =
3818 BC.MIB->matchIndJmp(BC.MIB->matchAdd(
3819 BC.MIB->matchReg(BaseReg1),
3820 BC.MIB->matchLoad(BC.MIB->matchReg(BaseReg2),
3821 BC.MIB->matchImm(Scale), BC.MIB->matchReg(),
3822 BC.MIB->matchImm(Offset))));
3823 std::unique_ptr<MCPlusBuilder::MCInstMatcher> LEAMatcherOwner =
3824 BC.MIB->matchLoadAddr(BC.MIB->matchSymbol(Target));
3825 MCPlusBuilder::MCInstMatcher *LEAMatcher = LEAMatcherOwner.get();
3826 std::unique_ptr<MCPlusBuilder::MCInstMatcher> PICBaseAddrMatcher =
3827 BC.MIB->matchIndJmp(BC.MIB->matchAdd(std::move(LEAMatcherOwner),
3828 BC.MIB->matchAnyOperand()));
3829 if (!PICIndJmpMatcher->match(
3830 *BC.MRI, *BC.MIB,
3831 MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1) ||
3832 Scale != 4 || BaseReg1 != BaseReg2 || Offset != 0 ||
3833 !PICBaseAddrMatcher->match(
3834 *BC.MRI, *BC.MIB,
3835 MutableArrayRef<MCInst>(&*BB->begin(), &Inst + 1), -1)) {
3836 llvm_unreachable("Failed to extract jump table base")::llvm::llvm_unreachable_internal("Failed to extract jump table base"
, "bolt/lib/Core/BinaryFunction.cpp", 3836)
;
3837 continue;
3838 }
3839 // Matched PIC, identify the instruction with the reference to the JT
3840 JTLoadInst = LEAMatcher->CurInst;
3841 } else {
3842 // Matched non-PIC
3843 JTLoadInst = LoadMatcher->CurInst;
3844 }
3845 }
3846
3847 uint64_t NewJumpTableID = 0;
3848 const MCSymbol *NewJTLabel;
3849 std::tie(NewJumpTableID, NewJTLabel) =
3850 BC.duplicateJumpTable(*this, JT, Target);
3851 {
3852 auto L = BC.scopeLock();
3853 BC.MIB->replaceMemOperandDisp(*JTLoadInst, NewJTLabel, BC.Ctx.get());
3854 }
3855 // We use a unique ID with the high bit set as address for this "injected"
3856 // jump table (not originally in the input binary).
3857 BC.MIB->setJumpTable(Inst, NewJumpTableID, 0, AllocId);
3858 }
3859 }
3860}
3861
3862bool BinaryFunction::replaceJumpTableEntryIn(BinaryBasicBlock *BB,
3863 BinaryBasicBlock *OldDest,
3864 BinaryBasicBlock *NewDest) {
3865 MCInst *Instr = BB->getLastNonPseudoInstr();
3866 if (!Instr || !BC.MIB->isIndirectBranch(*Instr))
3867 return false;
3868 uint64_t JTAddress = BC.MIB->getJumpTable(*Instr);
3869 assert(JTAddress && "Invalid jump table address")(static_cast <bool> (JTAddress && "Invalid jump table address"
) ? void (0) : __assert_fail ("JTAddress && \"Invalid jump table address\""
, "bolt/lib/Core/BinaryFunction.cpp", 3869, __extension__ __PRETTY_FUNCTION__
))
;
3870 JumpTable *JT = getJumpTableContainingAddress(JTAddress);
3871 assert(JT && "No jump table structure for this indirect branch")(static_cast <bool> (JT && "No jump table structure for this indirect branch"
) ? void (0) : __assert_fail ("JT && \"No jump table structure for this indirect branch\""
, "bolt/lib/Core/BinaryFunction.cpp", 3871, __extension__ __PRETTY_FUNCTION__
))
;
3872 bool Patched = JT->replaceDestination(JTAddress, OldDest->getLabel(),
3873 NewDest->getLabel());
3874 (void)Patched;
3875 assert(Patched && "Invalid entry to be replaced in jump table")(static_cast <bool> (Patched && "Invalid entry to be replaced in jump table"
) ? void (0) : __assert_fail ("Patched && \"Invalid entry to be replaced in jump table\""
, "bolt/lib/Core/BinaryFunction.cpp", 3875, __extension__ __PRETTY_FUNCTION__
))
;
3876 return true;
3877}
3878
3879BinaryBasicBlock *BinaryFunction::splitEdge(BinaryBasicBlock *From,
3880 BinaryBasicBlock *To) {
3881 // Create intermediate BB
3882 MCSymbol *Tmp;
3883 {
3884 auto L = BC.scopeLock();
3885 Tmp = BC.Ctx->createNamedTempSymbol("SplitEdge");
3886 }
3887 // Link new BBs to the original input offset of the From BB, so we can map
3888 // samples recorded in new BBs back to the original BB seem in the input
3889 // binary (if using BAT)
3890 std::unique_ptr<BinaryBasicBlock> NewBB = createBasicBlock(Tmp);
3891 NewBB->setOffset(From->getInputOffset());
3892 BinaryBasicBlock *NewBBPtr = NewBB.get();
3893
3894 // Update "From" BB
3895 auto I = From->succ_begin();
3896 auto BI = From->branch_info_begin();
3897 for (; I != From->succ_end(); ++I) {
3898 if (*I == To)
3899 break;
3900 ++BI;
3901 }
3902 assert(I != From->succ_end() && "Invalid CFG edge in splitEdge!")(static_cast <bool> (I != From->succ_end() &&
"Invalid CFG edge in splitEdge!") ? void (0) : __assert_fail
("I != From->succ_end() && \"Invalid CFG edge in splitEdge!\""
, "bolt/lib/Core/BinaryFunction.cpp", 3902, __extension__ __PRETTY_FUNCTION__
))
;
3903 uint64_t OrigCount = BI->Count;
3904 uint64_t OrigMispreds = BI->MispredictedCount;
3905 replaceJumpTableEntryIn(From, To, NewBBPtr);
3906 From->replaceSuccessor(To, NewBBPtr, OrigCount, OrigMispreds);
3907
3908 NewBB->addSuccessor(To, OrigCount, OrigMispreds);
3909 NewBB->setExecutionCount(OrigCount);
3910 NewBB->setIsCold(From->isCold());
3911
3912 // Update CFI and BB layout with new intermediate BB
3913 std::vector<std::unique_ptr<BinaryBasicBlock>> NewBBs;
3914 NewBBs.emplace_back(std::move(NewBB));
3915 insertBasicBlocks(From, std::move(NewBBs), true, true,
3916 /*RecomputeLandingPads=*/false);
3917 return NewBBPtr;
3918}
3919
3920void BinaryFunction::deleteConservativeEdges() {
3921 // Our goal is to aggressively remove edges from the CFG that we believe are
3922 // wrong. This is used for instrumentation, where it is safe to remove
3923 // fallthrough edges because we won't reorder blocks.
3924 for (auto I = BasicBlocks.begin(), E = BasicBlocks.end(); I != E; ++I) {
3925 BinaryBasicBlock *BB = *I;
3926 if (BB->succ_size() != 1 || BB->size() == 0)
3927 continue;
3928
3929 auto NextBB = std::next(I);
3930 MCInst *Last = BB->getLastNonPseudoInstr();
3931 // Fallthrough is a landing pad? Delete this edge (as long as we don't
3932 // have a direct jump to it)
3933 if ((*BB->succ_begin())->isLandingPad() && NextBB != E &&
3934 *BB->succ_begin() == *NextBB && Last && !BC.MIB->isBranch(*Last)) {
3935 BB->removeAllSuccessors();
3936 continue;
3937 }
3938
3939 // Look for suspicious calls at the end of BB where gcc may optimize it and
3940 // remove the jump to the epilogue when it knows the call won't return.
3941 if (!Last || !BC.MIB->isCall(*Last))
3942 continue;
3943
3944 const MCSymbol *CalleeSymbol = BC.MIB->getTargetSymbol(*Last);
3945 if (!CalleeSymbol)
3946 continue;
3947
3948 StringRef CalleeName = CalleeSymbol->getName();
3949 if (CalleeName != "__cxa_throw@PLT" && CalleeName != "_Unwind_Resume@PLT" &&
3950 CalleeName != "__cxa_rethrow@PLT" && CalleeName != "exit@PLT" &&
3951 CalleeName != "abort@PLT")
3952 continue;
3953
3954 BB->removeAllSuccessors();
3955 }
3956}
3957
3958bool BinaryFunction::isSymbolValidInScope(const SymbolRef &Symbol,
3959 uint64_t SymbolSize) const {
3960 // If this symbol is in a different section from the one where the
3961 // function symbol is, don't consider it as valid.
3962 if (!getOriginSection()->containsAddress(
3963 cantFail(Symbol.getAddress(), "cannot get symbol address")))
3964 return false;
3965
3966 // Some symbols are tolerated inside function bodies, others are not.
3967 // The real function boundaries may not be known at this point.
3968 if (BC.isMarker(Symbol))
3969 return true;
3970
3971 // It's okay to have a zero-sized symbol in the middle of non-zero-sized
3972 // function.
3973 if (SymbolSize == 0 && containsAddress(cantFail(Symbol.getAddress())))
3974 return true;
3975
3976 if (cantFail(Symbol.getType()) != SymbolRef::ST_Unknown)
3977 return false;
3978
3979 if (cantFail(Symbol.getFlags()) & SymbolRef::SF_Global)
3980 return false;
3981
3982 return true;
3983}
3984
3985void BinaryFunction::adjustExecutionCount(uint64_t Count) {
3986 if (getKnownExecutionCount() == 0 || Count == 0)
3987 return;
3988
3989 if (ExecutionCount < Count)
3990 Count = ExecutionCount;
3991
3992 double AdjustmentRatio = ((double)ExecutionCount - Count) / ExecutionCount;
3993 if (AdjustmentRatio < 0.0)
3994 AdjustmentRatio = 0.0;
3995
3996 for (BinaryBasicBlock &BB : blocks())
3997 BB.adjustExecutionCount(AdjustmentRatio);
3998
3999 ExecutionCount -= Count;
4000}
4001
4002BinaryFunction::~BinaryFunction() {
4003 for (BinaryBasicBlock *BB : BasicBlocks)
4004 delete BB;
4005 for (BinaryBasicBlock *BB : DeletedBasicBlocks)
4006 delete BB;
4007}
4008
4009void BinaryFunction::calculateLoopInfo() {
4010 // Discover loops.
4011 BinaryDominatorTree DomTree;
4012 DomTree.recalculate(*this);
4013 BLI.reset(new BinaryLoopInfo());
4014 BLI->analyze(DomTree);
4015
4016 // Traverse discovered loops and add depth and profile information.
4017 std::stack<BinaryLoop *> St;
4018 for (auto I = BLI->begin(), E = BLI->end(); I != E; ++I) {
4019 St.push(*I);
4020 ++BLI->OuterLoops;
4021 }
4022
4023 while (!St.empty()) {
4024 BinaryLoop *L = St.top();
4025 St.pop();
4026 ++BLI->TotalLoops;
4027 BLI->MaximumDepth = std::max(L->getLoopDepth(), BLI->MaximumDepth);
4028
4029 // Add nested loops in the stack.
4030 for (BinaryLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
4031 St.push(*I);
4032
4033 // Skip if no valid profile is found.
4034 if (!hasValidProfile()) {
4035 L->EntryCount = COUNT_NO_PROFILE;
4036 L->ExitCount = COUNT_NO_PROFILE;
4037 L->TotalBackEdgeCount = COUNT_NO_PROFILE;
4038 continue;
4039 }
4040
4041 // Compute back edge count.
4042 SmallVector<BinaryBasicBlock *, 1> Latches;
4043 L->getLoopLatches(Latches);
4044
4045 for (BinaryBasicBlock *Latch : Latches) {
4046 auto BI = Latch->branch_info_begin();
4047 for (BinaryBasicBlock *Succ : Latch->successors()) {
4048 if (Succ == L->getHeader()) {
4049 assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&(static_cast <bool> (BI->Count != BinaryBasicBlock::
COUNT_NO_PROFILE && "profile data not found") ? void (
0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\""
, "bolt/lib/Core/BinaryFunction.cpp", 4050, __extension__ __PRETTY_FUNCTION__
))
4050 "profile data not found")(static_cast <bool> (BI->Count != BinaryBasicBlock::
COUNT_NO_PROFILE && "profile data not found") ? void (
0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\""
, "bolt/lib/Core/BinaryFunction.cpp", 4050, __extension__ __PRETTY_FUNCTION__
))
;
4051 L->TotalBackEdgeCount += BI->Count;
4052 }
4053 ++BI;
4054 }
4055 }
4056
4057 // Compute entry count.
4058 L->EntryCount = L->getHeader()->getExecutionCount() - L->TotalBackEdgeCount;
4059
4060 // Compute exit count.
4061 SmallVector<BinaryLoop::Edge, 1> ExitEdges;
4062 L->getExitEdges(ExitEdges);
4063 for (BinaryLoop::Edge &Exit : ExitEdges) {
4064 const BinaryBasicBlock *Exiting = Exit.first;
4065 const BinaryBasicBlock *ExitTarget = Exit.second;
4066 auto BI = Exiting->branch_info_begin();
4067 for (BinaryBasicBlock *Succ : Exiting->successors()) {
4068 if (Succ == ExitTarget) {
4069 assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&(static_cast <bool> (BI->Count != BinaryBasicBlock::
COUNT_NO_PROFILE && "profile data not found") ? void (
0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\""
, "bolt/lib/Core/BinaryFunction.cpp", 4070, __extension__ __PRETTY_FUNCTION__
))
4070 "profile data not found")(static_cast <bool> (BI->Count != BinaryBasicBlock::
COUNT_NO_PROFILE && "profile data not found") ? void (
0) : __assert_fail ("BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE && \"profile data not found\""
, "bolt/lib/Core/BinaryFunction.cpp", 4070, __extension__ __PRETTY_FUNCTION__
))
;
4071 L->ExitCount += BI->Count;
4072 }
4073 ++BI;
4074 }
4075 }
4076 }
4077}
4078
4079void BinaryFunction::updateOutputValues(const MCAsmLayout &Layout) {
4080 if (!isEmitted()) {
4081 assert(!isInjected() && "injected function should be emitted")(static_cast <bool> (!isInjected() && "injected function should be emitted"
) ? void (0) : __assert_fail ("!isInjected() && \"injected function should be emitted\""
, "bolt/lib/Core/BinaryFunction.cpp", 4081, __extension__ __PRETTY_FUNCTION__
))
;
4082 setOutputAddress(getAddress());
4083 setOutputSize(getSize());
4084 return;
4085 }
4086
4087 const uint64_t BaseAddress = getCodeSection()->getOutputAddress();
4088 if (BC.HasRelocations || isInjected()) {
4089 const uint64_t StartOffset = Layout.getSymbolOffset(*getSymbol());
4090 const uint64_t EndOffset = Layout.getSymbolOffset(*getFunctionEndLabel());
4091 setOutputAddress(BaseAddress + StartOffset);
4092 setOutputSize(EndOffset - StartOffset);
4093 if (hasConstantIsland()) {
4094 const uint64_t DataOffset =
4095 Layout.getSymbolOffset(*getFunctionConstantIslandLabel());
4096 setOutputDataAddress(BaseAddress + DataOffset);
4097 }
4098 if (isSplit()) {
4099 for (FunctionFragment &FF : getLayout().getSplitFragments()) {
4100 ErrorOr<BinarySection &> ColdSection =
4101 getCodeSection(FF.getFragmentNum());
4102 // If fragment is empty, cold section might not exist
4103 if (FF.empty() && ColdSection.getError())
4104 continue;
4105 const uint64_t ColdBaseAddress = ColdSection->getOutputAddress();
4106
4107 const MCSymbol *ColdStartSymbol = getSymbol(FF.getFragmentNum());
4108 // If fragment is empty, symbol might have not been emitted
4109 if (FF.empty() && (!ColdStartSymbol || !ColdStartSymbol->isDefined()) &&
4110 !hasConstantIsland())
4111 continue;
4112 assert(ColdStartSymbol && ColdStartSymbol->isDefined() &&(static_cast <bool> (ColdStartSymbol && ColdStartSymbol
->isDefined() && "split function should have defined cold symbol"
) ? void (0) : __assert_fail ("ColdStartSymbol && ColdStartSymbol->isDefined() && \"split function should have defined cold symbol\""
, "bolt/lib/Core/BinaryFunction.cpp", 4113, __extension__ __PRETTY_FUNCTION__
))
4113 "split function should have defined cold symbol")(static_cast <bool> (ColdStartSymbol && ColdStartSymbol
->isDefined() && "split function should have defined cold symbol"
) ? void (0) : __assert_fail ("ColdStartSymbol && ColdStartSymbol->isDefined() && \"split function should have defined cold symbol\""
, "bolt/lib/Core/BinaryFunction.cpp", 4113, __extension__ __PRETTY_FUNCTION__
))
;
4114 const MCSymbol *ColdEndSymbol =
4115 getFunctionEndLabel(FF.getFragmentNum());
4116 assert(ColdEndSymbol && ColdEndSymbol->isDefined() &&(static_cast <bool> (ColdEndSymbol && ColdEndSymbol
->isDefined() && "split function should have defined cold end symbol"
) ? void (0) : __assert_fail ("ColdEndSymbol && ColdEndSymbol->isDefined() && \"split function should have defined cold end symbol\""
, "bolt/lib/Core/BinaryFunction.cpp", 4117, __extension__ __PRETTY_FUNCTION__
))
4117 "split function should have defined cold end symbol")(static_cast <bool> (ColdEndSymbol && ColdEndSymbol
->isDefined() && "split function should have defined cold end symbol"
) ? void (0) : __assert_fail ("ColdEndSymbol && ColdEndSymbol->isDefined() && \"split function should have defined cold end symbol\""
, "bolt/lib/Core/BinaryFunction.cpp", 4117, __extension__ __PRETTY_FUNCTION__
))
;
4118 const uint64_t ColdStartOffset =
4119 Layout.getSymbolOffset(*ColdStartSymbol);
4120 const uint64_t ColdEndOffset = Layout.getSymbolOffset(*ColdEndSymbol);
4121 FF.setAddress(ColdBaseAddress + ColdStartOffset);
4122 FF.setImageSize(ColdEndOffset - ColdStartOffset);
4123 if (hasConstantIsland()) {
4124 const uint64_t DataOffset =
4125 Layout.getSymbolOffset(*getFunctionColdConstantIslandLabel());
4126 setOutputColdDataAddress(ColdBaseAddress + DataOffset);
4127 }
4128 }
4129 }
4130 } else {
4131 setOutputAddress(getAddress());
4132 setOutputSize(Layout.getSymbolOffset(*getFunctionEndLabel()));
4133 }
4134
4135 // Update basic block output ranges for the debug info, if we have
4136 // secondary entry points in the symbol table to update or if writing BAT.
4137 if (!opts::UpdateDebugSections && !isMultiEntry() &&
4138 !requiresAddressTranslation())
4139 return;
4140
4141 // Output ranges should match the input if the body hasn't changed.
4142 if (!isSimple() && !BC.HasRelocations)
4143 return;
4144
4145 // AArch64 may have functions that only contains a constant island (no code).
4146 if (getLayout().block_empty())
4147 return;
4148
4149 for (FunctionFragment &FF : getLayout().fragments()) {
4150 if (FF.empty())
4151 continue;
4152
4153 const uint64_t FragmentBaseAddress =
4154 getCodeSection(isSimple() ? FF.getFragmentNum() : FragmentNum::main())
4155 ->getOutputAddress();
4156
4157 BinaryBasicBlock *PrevBB = nullptr;
4158 for (BinaryBasicBlock *const BB : FF) {
4159 assert(BB->getLabel()->isDefined() && "symbol should be defined")(static_cast <bool> (BB->getLabel()->isDefined() &&
"symbol should be defined") ? void (0) : __assert_fail ("BB->getLabel()->isDefined() && \"symbol should be defined\""
, "bolt/lib/Core/BinaryFunction.cpp", 4159, __extension__ __PRETTY_FUNCTION__
))
;
4160 if (!BC.HasRelocations) {
4161 if (BB->isSplit())
4162 assert(FragmentBaseAddress == FF.getAddress())(static_cast <bool> (FragmentBaseAddress == FF.getAddress
()) ? void (0) : __assert_fail ("FragmentBaseAddress == FF.getAddress()"
, "bolt/lib/Core/BinaryFunction.cpp", 4162, __extension__ __PRETTY_FUNCTION__
))
;
4163 else
4164 assert(FragmentBaseAddress == getOutputAddress())(static_cast <bool> (FragmentBaseAddress == getOutputAddress
()) ? void (0) : __assert_fail ("FragmentBaseAddress == getOutputAddress()"
, "bolt/lib/Core/BinaryFunction.cpp", 4164, __extension__ __PRETTY_FUNCTION__
))
;
4165 }
4166
4167 const uint64_t BBOffset = Layout.getSymbolOffset(*BB->getLabel());
4168 const uint64_t BBAddress = FragmentBaseAddress + BBOffset;
4169 BB->setOutputStartAddress(BBAddress);
4170
4171 if (PrevBB)
4172 PrevBB->setOutputEndAddress(BBAddress);
4173 PrevBB = BB;
4174
4175 BB->updateOutputValues(Layout);
4176 }
4177
4178 PrevBB->setOutputEndAddress(PrevBB->isSplit()
4179 ? FF.getAddress() + FF.getImageSize()
4180 : getOutputAddress() + getOutputSize());
4181 }
4182}
4183
4184DebugAddressRangesVector BinaryFunction::getOutputAddressRanges() const {
4185 DebugAddressRangesVector OutputRanges;
4186
4187 if (isFolded())
4188 return OutputRanges;
4189
4190 if (IsFragment)
4191 return OutputRanges;
4192
4193 OutputRanges.emplace_back(getOutputAddress(),
4194 getOutputAddress() + getOutputSize());
4195 if (isSplit()) {
4196 assert(isEmitted() && "split function should be emitted")(static_cast <bool> (isEmitted() && "split function should be emitted"
) ? void (0) : __assert_fail ("isEmitted() && \"split function should be emitted\""
, "bolt/lib/Core/BinaryFunction.cpp", 4196, __extension__ __PRETTY_FUNCTION__
))
;
4197 for (const FunctionFragment &FF : getLayout().getSplitFragments())
4198 OutputRanges.emplace_back(FF.getAddress(),
4199 FF.getAddress() + FF.getImageSize());
4200 }
4201
4202 if (isSimple())
4203 return OutputRanges;
4204
4205 for (BinaryFunction *Frag : Fragments) {
4206 assert(!Frag->isSimple() &&(static_cast <bool> (!Frag->isSimple() && "fragment of non-simple function should also be non-simple"
) ? void (0) : __assert_fail ("!Frag->isSimple() && \"fragment of non-simple function should also be non-simple\""
, "bolt/lib/Core/BinaryFunction.cpp", 4207, __extension__ __PRETTY_FUNCTION__
))
4207 "fragment of non-simple function should also be non-simple")(static_cast <bool> (!Frag->isSimple() && "fragment of non-simple function should also be non-simple"
) ? void (0) : __assert_fail ("!Frag->isSimple() && \"fragment of non-simple function should also be non-simple\""
, "bolt/lib/Core/BinaryFunction.cpp", 4207, __extension__ __PRETTY_FUNCTION__
))
;
4208 OutputRanges.emplace_back(Frag->getOutputAddress(),
4209 Frag->getOutputAddress() + Frag->getOutputSize());
4210 }
4211
4212 return OutputRanges;
4213}
4214
4215uint64_t BinaryFunction::translateInputToOutputAddress(uint64_t Address) const {
4216 if (isFolded())
4217 return 0;
4218
4219 // If the function hasn't changed return the same address.
4220 if (!isEmitted())
4221 return Address;
4222
4223 if (Address < getAddress())
4224 return 0;
4225
4226 // Check if the address is associated with an instruction that is tracked
4227 // by address translation.
4228 auto KV = InputOffsetToAddressMap.find(Address - getAddress());
4229 if (KV != InputOffsetToAddressMap.end())
4230 return KV->second;
4231
4232 // FIXME: #18950828 - we rely on relative offsets inside basic blocks to stay
4233 // intact. Instead we can use pseudo instructions and/or annotations.
4234 const uint64_t Offset = Address - getAddress();
4235 const BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
4236 if (!BB) {
4237 // Special case for address immediately past the end of the function.
4238 if (Offset == getSize())
4239 return getOutputAddress() + getOutputSize();
4240
4241 return 0;
4242 }
4243
4244 return std::min(BB->getOutputAddressRange().first + Offset - BB->getOffset(),
4245 BB->getOutputAddressRange().second);
4246}
4247
4248DebugAddressRangesVector BinaryFunction::translateInputToOutputRanges(
4249 const DWARFAddressRangesVector &InputRanges) const {
4250 DebugAddressRangesVector OutputRanges;
4251
4252 if (isFolded())
4253 return OutputRanges;
4254
4255 // If the function hasn't changed return the same ranges.
4256 if (!isEmitted()) {
4257 OutputRanges.resize(InputRanges.size());
4258 llvm::transform(InputRanges, OutputRanges.begin(),
4259 [](const DWARFAddressRange &Range) {
4260 return DebugAddressRange(Range.LowPC, Range.HighPC);
4261 });
4262 return OutputRanges;
4263 }
4264
4265 // Even though we will merge ranges in a post-processing pass, we attempt to
4266 // merge them in a main processing loop as it improves the processing time.
4267 uint64_t PrevEndAddress = 0;
4268 for (const DWARFAddressRange &Range : InputRanges) {
4269 if (!containsAddress(Range.LowPC)) {
4270 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4271 dbgs() << "BOLT-DEBUG: invalid debug address range detected for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4272 << *this << " : [0x" << Twine::utohexstr(Range.LowPC) << ", 0x"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4273 << Twine::utohexstr(Range.HighPC) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
;
4274 PrevEndAddress = 0;
4275 continue;
4276 }
4277 uint64_t InputOffset = Range.LowPC - getAddress();
4278 const uint64_t InputEndOffset =
4279 std::min(Range.HighPC - getAddress(), getSize());
4280
4281 auto BBI = llvm::upper_bound(BasicBlockOffsets,
4282 BasicBlockOffset(InputOffset, nullptr),
4283 CompareBasicBlockOffsets());
4284 --BBI;
4285 do {
4286 const BinaryBasicBlock *BB = BBI->second;
4287 if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) {
4288 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4289 dbgs() << "BOLT-DEBUG: invalid debug address range detected for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4290 << *this << " : [0x" << Twine::utohexstr(Range.LowPC)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
4291 << ", 0x" << Twine::utohexstr(Range.HighPC) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected for "
<< *this << " : [0x" << Twine::utohexstr(Range
.LowPC) << ", 0x" << Twine::utohexstr(Range.HighPC
) << "]\n"; } } while (false)
;
4292 PrevEndAddress = 0;
4293 break;
4294 }
4295
4296 // Skip the range if the block was deleted.
4297 if (const uint64_t OutputStart = BB->getOutputAddressRange().first) {
4298 const uint64_t StartAddress =
4299 OutputStart + InputOffset - BB->getOffset();
4300 uint64_t EndAddress = BB->getOutputAddressRange().second;
4301 if (InputEndOffset < BB->getEndOffset())
4302 EndAddress = StartAddress + InputEndOffset - InputOffset;
4303
4304 if (StartAddress == PrevEndAddress) {
4305 OutputRanges.back().HighPC =
4306 std::max(OutputRanges.back().HighPC, EndAddress);
4307 } else {
4308 OutputRanges.emplace_back(StartAddress,
4309 std::max(StartAddress, EndAddress));
4310 }
4311 PrevEndAddress = OutputRanges.back().HighPC;
4312 }
4313
4314 InputOffset = BB->getEndOffset();
4315 ++BBI;
4316 } while (InputOffset < InputEndOffset);
4317 }
4318
4319 // Post-processing pass to sort and merge ranges.
4320 llvm::sort(OutputRanges);
4321 DebugAddressRangesVector MergedRanges;
4322 PrevEndAddress = 0;
4323 for (const DebugAddressRange &Range : OutputRanges) {
4324 if (Range.LowPC <= PrevEndAddress) {
4325 MergedRanges.back().HighPC =
4326 std::max(MergedRanges.back().HighPC, Range.HighPC);
4327 } else {
4328 MergedRanges.emplace_back(Range.LowPC, Range.HighPC);
4329 }
4330 PrevEndAddress = MergedRanges.back().HighPC;
4331 }
4332
4333 return MergedRanges;
4334}
4335
4336MCInst *BinaryFunction::getInstructionAtOffset(uint64_t Offset) {
4337 if (CurrentState == State::Disassembled) {
4338 auto II = Instructions.find(Offset);
4339 return (II == Instructions.end()) ? nullptr : &II->second;
4340 } else if (CurrentState == State::CFG) {
4341 BinaryBasicBlock *BB = getBasicBlockContainingOffset(Offset);
4342 if (!BB)
4343 return nullptr;
4344
4345 for (MCInst &Inst : *BB) {
4346 constexpr uint32_t InvalidOffset = std::numeric_limits<uint32_t>::max();
4347 if (Offset == BC.MIB->getOffsetWithDefault(Inst, InvalidOffset))
4348 return &Inst;
4349 }
4350
4351 if (MCInst *LastInstr = BB->getLastNonPseudoInstr()) {
4352 const uint32_t Size =
4353 BC.MIB->getAnnotationWithDefault<uint32_t>(*LastInstr, "Size");
4354 if (BB->getEndOffset() - Offset == Size)
4355 return LastInstr;
4356 }
4357
4358 return nullptr;
4359 } else {
4360 llvm_unreachable("invalid CFG state to use getInstructionAtOffset()")::llvm::llvm_unreachable_internal("invalid CFG state to use getInstructionAtOffset()"
, "bolt/lib/Core/BinaryFunction.cpp", 4360)
;
4361 }
4362}
4363
4364DebugLocationsVector BinaryFunction::translateInputToOutputLocationList(
4365 const DebugLocationsVector &InputLL) const {
4366 DebugLocationsVector OutputLL;
4367
4368 if (isFolded())
4369 return OutputLL;
4370
4371 // If the function hasn't changed - there's nothing to update.
4372 if (!isEmitted())
4373 return InputLL;
4374
4375 uint64_t PrevEndAddress = 0;
4376 SmallVectorImpl<uint8_t> *PrevExpr = nullptr;
4377 for (const DebugLocationEntry &Entry : InputLL) {
4378 const uint64_t Start = Entry.LowPC;
4379 const uint64_t End = Entry.HighPC;
4380 if (!containsAddress(Start)) {
4381 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4382 "for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4383 << *this << " : [0x" << Twine::utohexstr(Start)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4384 << ", 0x" << Twine::utohexstr(End) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
;
4385 continue;
4386 }
4387 uint64_t InputOffset = Start - getAddress();
4388 const uint64_t InputEndOffset = std::min(End - getAddress(), getSize());
4389 auto BBI = llvm::upper_bound(BasicBlockOffsets,
4390 BasicBlockOffset(InputOffset, nullptr),
4391 CompareBasicBlockOffsets());
4392 --BBI;
4393 do {
4394 const BinaryBasicBlock *BB = BBI->second;
4395 if (InputOffset < BB->getOffset() || InputOffset >= BB->getEndOffset()) {
4396 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: invalid debug address range detected "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4397 "for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4398 << *this << " : [0x" << Twine::utohexstr(Start)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
4399 << ", 0x" << Twine::utohexstr(End) << "]\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("bolt")) { dbgs() << "BOLT-DEBUG: invalid debug address range detected "
"for " << *this << " : [0x" << Twine::utohexstr
(Start) << ", 0x" << Twine::utohexstr(End) <<
"]\n"; } } while (false)
;
4400 PrevEndAddress = 0;
4401 break;
4402 }
4403
4404 // Skip the range if the block was deleted.
4405 if (const uint64_t OutputStart = BB->getOutputAddressRange().first) {
4406 const uint64_t StartAddress =
4407 OutputStart + InputOffset - BB->getOffset();
4408 uint64_t EndAddress = BB->getOutputAddressRange().second;
4409 if (InputEndOffset < BB->getEndOffset())
4410 EndAddress = StartAddress + InputEndOffset - InputOffset;
4411
4412 if (StartAddress == PrevEndAddress && Entry.Expr == *PrevExpr) {
4413 OutputLL.back().HighPC = std::max(OutputLL.back().HighPC, EndAddress);
4414 } else {
4415 OutputLL.emplace_back(DebugLocationEntry{
4416 StartAddress, std::max(StartAddress, EndAddress), Entry.Expr});
4417 }
4418 PrevEndAddress = OutputLL.back().HighPC;
4419 PrevExpr = &OutputLL.back().Expr;
4420 }
4421
4422 ++BBI;
4423 InputOffset = BB->getEndOffset();
4424 } while (InputOffset < InputEndOffset);
4425 }
4426
4427 // Sort and merge adjacent entries with identical location.
4428 llvm::stable_sort(
4429 OutputLL, [](const DebugLocationEntry &A, const DebugLocationEntry &B) {
4430 return A.LowPC < B.LowPC;
4431 });
4432 DebugLocationsVector MergedLL;
4433 PrevEndAddress = 0;
4434 PrevExpr = nullptr;
4435 for (const DebugLocationEntry &Entry : OutputLL) {
4436 if (Entry.LowPC <= PrevEndAddress && *PrevExpr == Entry.Expr) {
4437 MergedLL.back().HighPC = std::max(Entry.HighPC, MergedLL.back().HighPC);
4438 } else {
4439 const uint64_t Begin = std::max(Entry.LowPC, PrevEndAddress);
4440 const uint64_t End = std::max(Begin, Entry.HighPC);
4441 MergedLL.emplace_back(DebugLocationEntry{Begin, End, Entry.Expr});
4442 }
4443 PrevEndAddress = MergedLL.back().HighPC;
4444 PrevExpr = &MergedLL.back().Expr;
4445 }
4446
4447 return MergedLL;
4448}
4449
4450void BinaryFunction::printLoopInfo(raw_ostream &OS) const {
4451 if (!opts::shouldPrint(*this))
4452 return;
4453
4454 OS << "Loop Info for Function \"" << *this << "\"";
4455 if (hasValidProfile())
4456 OS << " (count: " << getExecutionCount() << ")";
4457 OS << "\n";
4458
4459 std::stack<BinaryLoop *> St;
4460 for (BinaryLoop *L : *BLI)
4461 St.push(L);
4462 while (!St.empty()) {
4463 BinaryLoop *L = St.top();
4464 St.pop();
4465
4466 for (BinaryLoop *Inner : *L)
4467 St.push(Inner);
4468
4469 if (!hasValidProfile())
4470 continue;
4471
4472 OS << (L->getLoopDepth() > 1 ? "Nested" : "Outer")
4473 << " loop header: " << L->getHeader()->getName();
4474 OS << "\n";
4475 OS << "Loop basic blocks: ";
4476 ListSeparator LS;
4477 for (BinaryBasicBlock *BB : L->blocks())
4478 OS << LS << BB->getName();
4479 OS << "\n";
4480 if (hasValidProfile()) {
4481 OS << "Total back edge count: " << L->TotalBackEdgeCount << "\n";
4482 OS << "Loop entry count: " << L->EntryCount << "\n";
4483 OS << "Loop exit count: " << L->ExitCount << "\n";
4484 if (L->EntryCount > 0) {
4485 OS << "Average iters per entry: "
4486 << format("%.4lf", (double)L->TotalBackEdgeCount / L->EntryCount)
4487 << "\n";
4488 }
4489 }
4490 OS << "----\n";
4491 }
4492
4493 OS << "Total number of loops: " << BLI->TotalLoops << "\n";
4494 OS << "Number of outer loops: " << BLI->OuterLoops << "\n";
4495 OS << "Maximum nested loop depth: " << BLI->MaximumDepth << "\n\n";
4496}
4497
4498bool BinaryFunction::isAArch64Veneer() const {
4499 if (empty() || hasIslandsInfo())
4500 return false;
4501
4502 BinaryBasicBlock &BB = **BasicBlocks.begin();
4503 for (MCInst &Inst : BB)
4504 if (!BC.MIB->hasAnnotation(Inst, "AArch64Veneer"))
4505 return false;
4506
4507 for (auto I = BasicBlocks.begin() + 1, E = BasicBlocks.end(); I != E; ++I) {
4508 for (MCInst &Inst : **I)
4509 if (!BC.MIB->isNoop(Inst))
4510 return false;
4511 }
4512
4513 return true;
4514}
4515
4516} // namespace bolt
4517} // namespace llvm