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