587 lines · cpp
1//===- bolt/Core/BinaryBasicBlock.cpp - Low-level basic block -------------===//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 BinaryBasicBlock class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Core/BinaryBasicBlock.h"14#include "bolt/Core/BinaryContext.h"15#include "bolt/Core/BinaryFunction.h"16#include "llvm/ADT/SmallPtrSet.h"17#include "llvm/MC/MCInst.h"18#include "llvm/Support/Errc.h"19 20#define DEBUG_TYPE "bolt"21 22namespace llvm {23namespace bolt {24 25bool operator<(const BinaryBasicBlock &LHS, const BinaryBasicBlock &RHS) {26 return LHS.Index < RHS.Index;27}28 29bool BinaryBasicBlock::hasCFG() const { return getParent()->hasCFG(); }30 31bool BinaryBasicBlock::isEntryPoint() const {32 return getParent()->isEntryPoint(*this);33}34 35bool BinaryBasicBlock::hasInstructions() const {36 return getParent()->hasInstructions();37}38 39const JumpTable *BinaryBasicBlock::getJumpTable() const {40 const MCInst *Inst = getLastNonPseudoInstr();41 const JumpTable *JT = Inst ? Function->getJumpTable(*Inst) : nullptr;42 return JT;43}44 45void BinaryBasicBlock::adjustNumPseudos(const MCInst &Inst, int Sign) {46 BinaryContext &BC = Function->getBinaryContext();47 if (BC.MIB->isPseudo(Inst))48 NumPseudos += Sign;49}50 51BinaryBasicBlock::iterator BinaryBasicBlock::getFirstNonPseudo() {52 const BinaryContext &BC = Function->getBinaryContext();53 for (auto II = Instructions.begin(), E = Instructions.end(); II != E; ++II) {54 if (!BC.MIB->isPseudo(*II))55 return II;56 }57 return end();58}59 60BinaryBasicBlock::reverse_iterator BinaryBasicBlock::getLastNonPseudo() {61 const BinaryContext &BC = Function->getBinaryContext();62 for (auto RII = Instructions.rbegin(), E = Instructions.rend(); RII != E;63 ++RII) {64 if (!BC.MIB->isPseudo(*RII))65 return RII;66 }67 return rend();68}69 70bool BinaryBasicBlock::validateSuccessorInvariants() {71 const MCInst *Inst = getLastNonPseudoInstr();72 const JumpTable *JT = Inst ? Function->getJumpTable(*Inst) : nullptr;73 BinaryContext &BC = Function->getBinaryContext();74 bool Valid = true;75 76 if (JT) {77 // Note: for now we assume that successors do not reference labels from78 // any overlapping jump tables. We only look at the entries for the jump79 // table that is referenced at the last instruction.80 const auto Range = JT->getEntriesForAddress(BC.MIB->getJumpTable(*Inst));81 const std::vector<const MCSymbol *> Entries(82 std::next(JT->Entries.begin(), Range.first),83 std::next(JT->Entries.begin(), Range.second));84 std::set<const MCSymbol *> UniqueSyms(Entries.begin(), Entries.end());85 for (BinaryBasicBlock *Succ : Successors) {86 auto Itr = UniqueSyms.find(Succ->getLabel());87 if (Itr != UniqueSyms.end()) {88 UniqueSyms.erase(Itr);89 } else {90 // Work on the assumption that jump table blocks don't91 // have a conditional successor.92 Valid = false;93 BC.errs() << "BOLT-WARNING: Jump table successor " << Succ->getName()94 << " not contained in the jump table.\n";95 }96 }97 // If there are any leftover entries in the jump table, they98 // must be one of the function end labels.99 if (Valid) {100 for (const MCSymbol *Sym : UniqueSyms) {101 Valid &= (Sym == Function->getFunctionEndLabel() ||102 Sym == Function->getFunctionEndLabel(getFragmentNum()));103 if (!Valid) {104 const BinaryFunction *TargetBF = BC.getFunctionForSymbol(Sym);105 if (TargetBF) {106 // It's possible for another function to be in the jump table entry107 // as a result of built-in unreachable.108 Valid = true;109 } else {110 BC.errs() << "BOLT-WARNING: Jump table contains illegal entry: "111 << Sym->getName() << "\n";112 }113 }114 if (!Valid)115 break;116 }117 }118 } else {119 // Unknown control flow.120 if (Inst && BC.MIB->isIndirectBranch(*Inst))121 return true;122 123 const MCSymbol *TBB = nullptr;124 const MCSymbol *FBB = nullptr;125 MCInst *CondBranch = nullptr;126 MCInst *UncondBranch = nullptr;127 128 if (analyzeBranch(TBB, FBB, CondBranch, UncondBranch)) {129 switch (Successors.size()) {130 case 0:131 Valid = !CondBranch && !UncondBranch;132 break;133 case 1: {134 const bool HasCondBlock =135 CondBranch && Function->getBasicBlockForLabel(136 BC.MIB->getTargetSymbol(*CondBranch));137 Valid = !CondBranch || !HasCondBlock;138 break;139 }140 case 2:141 Valid =142 CondBranch && TBB == getConditionalSuccessor(true)->getLabel() &&143 (UncondBranch ? FBB == getConditionalSuccessor(false)->getLabel()144 : !FBB);145 break;146 }147 }148 }149 if (!Valid) {150 BC.errs() << "BOLT-WARNING: CFG invalid in " << *getFunction() << " @ "151 << getName() << "\n";152 if (JT) {153 BC.errs() << "Jump Table instruction addr = 0x"154 << Twine::utohexstr(BC.MIB->getJumpTable(*Inst)) << "\n";155 JT->print(errs());156 }157 getFunction()->dump();158 }159 return Valid;160}161 162BinaryBasicBlock *BinaryBasicBlock::getSuccessor(const MCSymbol *Label) const {163 if (!Label && succ_size() == 1)164 return *succ_begin();165 166 for (BinaryBasicBlock *BB : successors())167 if (BB->getLabel() == Label)168 return BB;169 170 return nullptr;171}172 173BinaryBasicBlock *BinaryBasicBlock::getSuccessor(const MCSymbol *Label,174 BinaryBranchInfo &BI) const {175 auto BIIter = branch_info_begin();176 for (BinaryBasicBlock *BB : successors()) {177 if (BB->getLabel() == Label) {178 BI = *BIIter;179 return BB;180 }181 ++BIIter;182 }183 184 return nullptr;185}186 187BinaryBasicBlock *BinaryBasicBlock::getLandingPad(const MCSymbol *Label) const {188 for (BinaryBasicBlock *BB : landing_pads())189 if (BB->getLabel() == Label)190 return BB;191 192 return nullptr;193}194 195int32_t BinaryBasicBlock::getCFIStateAtInstr(const MCInst *Instr) const {196 assert(197 getFunction()->getState() >= BinaryFunction::State::CFG &&198 "can only calculate CFI state when function is in or past the CFG state");199 200 const BinaryFunction::CFIInstrMapType &FDEProgram =201 getFunction()->getFDEProgram();202 203 // Find the last CFI preceding Instr in this basic block.204 const MCInst *LastCFI = nullptr;205 bool InstrSeen = (Instr == nullptr);206 for (const MCInst &Inst : llvm::reverse(Instructions)) {207 if (!InstrSeen) {208 InstrSeen = (&Inst == Instr);209 continue;210 }211 // Ignoring OpNegateRAState CFIs here, as they dont have a "State"212 // number associated with them.213 if (Function->getBinaryContext().MIB->isCFI(Inst) &&214 (Function->getCFIFor(Inst)->getOperation() !=215 MCCFIInstruction::OpNegateRAState)) {216 LastCFI = &Inst;217 break;218 }219 }220 221 assert(InstrSeen && "instruction expected in basic block");222 223 // CFI state is the same as at basic block entry point.224 if (!LastCFI)225 return getCFIState();226 227 // Fold all RememberState/RestoreState sequences, such as for:228 //229 // [ CFI #(K-1) ]230 // RememberState (#K)231 // ....232 // RestoreState233 // RememberState234 // ....235 // RestoreState236 // [ GNU_args_size ]237 // RememberState238 // ....239 // RestoreState <- LastCFI240 //241 // we return K - the most efficient state to (re-)generate.242 int64_t State = LastCFI->getOperand(0).getImm();243 while (State >= 0 &&244 FDEProgram[State].getOperation() == MCCFIInstruction::OpRestoreState) {245 int32_t Depth = 1;246 --State;247 assert(State >= 0 && "first CFI cannot be RestoreState");248 while (Depth && State >= 0) {249 const MCCFIInstruction &CFIInstr = FDEProgram[State];250 if (CFIInstr.getOperation() == MCCFIInstruction::OpRestoreState)251 ++Depth;252 else if (CFIInstr.getOperation() == MCCFIInstruction::OpRememberState)253 --Depth;254 --State;255 }256 assert(Depth == 0 && "unbalanced RememberState/RestoreState stack");257 258 // Skip any GNU_args_size.259 while (State >= 0 && FDEProgram[State].getOperation() ==260 MCCFIInstruction::OpGnuArgsSize) {261 --State;262 }263 }264 265 assert((State + 1 >= 0) && "miscalculated CFI state");266 return State + 1;267}268 269void BinaryBasicBlock::addSuccessor(BinaryBasicBlock *Succ, uint64_t Count,270 uint64_t MispredictedCount) {271 Successors.push_back(Succ);272 BranchInfo.push_back({Count, MispredictedCount});273 Succ->Predecessors.push_back(this);274}275 276void BinaryBasicBlock::replaceSuccessor(BinaryBasicBlock *Succ,277 BinaryBasicBlock *NewSucc,278 uint64_t Count,279 uint64_t MispredictedCount) {280 Succ->removePredecessor(this, /*Multiple=*/false);281 auto I = succ_begin();282 auto BI = BranchInfo.begin();283 for (; I != succ_end(); ++I) {284 assert(BI != BranchInfo.end() && "missing BranchInfo entry");285 if (*I == Succ)286 break;287 ++BI;288 }289 assert(I != succ_end() && "no such successor!");290 291 *I = NewSucc;292 *BI = BinaryBranchInfo{Count, MispredictedCount};293 NewSucc->addPredecessor(this);294}295 296void BinaryBasicBlock::removeAllSuccessors() {297 SmallPtrSet<BinaryBasicBlock *, 2> UniqSuccessors(succ_begin(), succ_end());298 for (BinaryBasicBlock *SuccessorBB : UniqSuccessors)299 SuccessorBB->removePredecessor(this);300 Successors.clear();301 BranchInfo.clear();302}303 304void BinaryBasicBlock::removeSuccessor(BinaryBasicBlock *Succ) {305 Succ->removePredecessor(this, /*Multiple=*/false);306 auto I = succ_begin();307 auto BI = BranchInfo.begin();308 for (; I != succ_end(); ++I) {309 assert(BI != BranchInfo.end() && "missing BranchInfo entry");310 if (*I == Succ)311 break;312 ++BI;313 }314 assert(I != succ_end() && "no such successor!");315 316 Successors.erase(I);317 BranchInfo.erase(BI);318}319 320void BinaryBasicBlock::addPredecessor(BinaryBasicBlock *Pred) {321 Predecessors.push_back(Pred);322}323 324void BinaryBasicBlock::removePredecessor(BinaryBasicBlock *Pred,325 bool Multiple) {326 // Note: the predecessor could be listed multiple times.327 bool Erased = false;328 for (auto PredI = Predecessors.begin(); PredI != Predecessors.end();) {329 if (*PredI == Pred) {330 Erased = true;331 PredI = Predecessors.erase(PredI);332 if (!Multiple)333 return;334 } else {335 ++PredI;336 }337 }338 assert(Erased && "Pred is not a predecessor of this block!");339 (void)Erased;340}341 342void BinaryBasicBlock::removeDuplicateConditionalSuccessor(MCInst *CondBranch) {343 assert(succ_size() == 2 && Successors[0] == Successors[1] &&344 "conditional successors expected");345 346 BinaryBasicBlock *Succ = Successors[0];347 const BinaryBranchInfo CondBI = BranchInfo[0];348 const BinaryBranchInfo UncondBI = BranchInfo[1];349 350 eraseInstruction(findInstruction(CondBranch));351 352 Successors.clear();353 BranchInfo.clear();354 355 Successors.push_back(Succ);356 357 uint64_t Count = COUNT_NO_PROFILE;358 if (CondBI.Count != COUNT_NO_PROFILE && UncondBI.Count != COUNT_NO_PROFILE)359 Count = CondBI.Count + UncondBI.Count;360 BranchInfo.push_back({Count, 0});361}362 363void BinaryBasicBlock::updateJumpTableSuccessors() {364 const JumpTable *JT = getJumpTable();365 assert(JT && "Expected jump table instruction.");366 367 // Clear existing successors.368 removeAllSuccessors();369 370 // Generate the list of successors in deterministic order without duplicates.371 SmallVector<BinaryBasicBlock *, 16> SuccessorBBs;372 for (const MCSymbol *Label : JT->Entries) {373 BinaryBasicBlock *BB = getFunction()->getBasicBlockForLabel(Label);374 // Ignore __builtin_unreachable()375 if (!BB) {376 assert(Label == getFunction()->getFunctionEndLabel() &&377 "JT label should match a block or end of function.");378 continue;379 }380 SuccessorBBs.emplace_back(BB);381 }382 llvm::sort(SuccessorBBs,383 [](const BinaryBasicBlock *BB1, const BinaryBasicBlock *BB2) {384 return BB1->getInputOffset() < BB2->getInputOffset();385 });386 SuccessorBBs.erase(llvm::unique(SuccessorBBs), SuccessorBBs.end());387 388 for (BinaryBasicBlock *BB : SuccessorBBs)389 addSuccessor(BB);390}391 392void BinaryBasicBlock::adjustExecutionCount(double Ratio) {393 auto adjustedCount = [&](uint64_t Count) -> uint64_t {394 double NewCount = Count * Ratio;395 if (!NewCount && Count && (Ratio > 0.0))396 NewCount = 1;397 return NewCount;398 };399 400 setExecutionCount(adjustedCount(getKnownExecutionCount()));401 for (BinaryBranchInfo &BI : branch_info()) {402 if (BI.Count != COUNT_NO_PROFILE)403 BI.Count = adjustedCount(BI.Count);404 if (BI.MispredictedCount != COUNT_INFERRED)405 BI.MispredictedCount = adjustedCount(BI.MispredictedCount);406 }407}408 409bool BinaryBasicBlock::analyzeBranch(const MCSymbol *&TBB, const MCSymbol *&FBB,410 MCInst *&CondBranch,411 MCInst *&UncondBranch) {412 auto &MIB = Function->getBinaryContext().MIB;413 return MIB->analyzeBranch(Instructions.begin(), Instructions.end(), TBB, FBB,414 CondBranch, UncondBranch);415}416 417MCInst *BinaryBasicBlock::getTerminatorBefore(MCInst *Pos) {418 BinaryContext &BC = Function->getBinaryContext();419 auto Itr = rbegin();420 bool Check = Pos ? false : true;421 MCInst *FirstTerminator = nullptr;422 while (Itr != rend()) {423 if (!Check) {424 if (&*Itr == Pos)425 Check = true;426 ++Itr;427 continue;428 }429 if (BC.MIB->isTerminator(*Itr))430 FirstTerminator = &*Itr;431 ++Itr;432 }433 return FirstTerminator;434}435 436bool BinaryBasicBlock::hasTerminatorAfter(MCInst *Pos) {437 BinaryContext &BC = Function->getBinaryContext();438 auto Itr = rbegin();439 while (Itr != rend()) {440 if (&*Itr == Pos)441 return false;442 if (BC.MIB->isTerminator(*Itr))443 return true;444 ++Itr;445 }446 return false;447}448 449bool BinaryBasicBlock::swapConditionalSuccessors() {450 if (succ_size() != 2)451 return false;452 453 std::swap(Successors[0], Successors[1]);454 std::swap(BranchInfo[0], BranchInfo[1]);455 return true;456}457 458void BinaryBasicBlock::addBranchInstruction(const BinaryBasicBlock *Successor) {459 assert(isSuccessor(Successor));460 BinaryContext &BC = Function->getBinaryContext();461 MCInst NewInst;462 std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex);463 BC.MIB->createUncondBranch(NewInst, Successor->getLabel(), BC.Ctx.get());464 Instructions.emplace_back(std::move(NewInst));465}466 467void BinaryBasicBlock::addTailCallInstruction(const MCSymbol *Target) {468 BinaryContext &BC = Function->getBinaryContext();469 MCInst NewInst;470 BC.MIB->createTailCall(NewInst, Target, BC.Ctx.get());471 Instructions.emplace_back(std::move(NewInst));472}473 474uint32_t BinaryBasicBlock::getNumCalls() const {475 uint32_t N = 0;476 BinaryContext &BC = Function->getBinaryContext();477 for (const MCInst &Instr : Instructions) {478 if (BC.MIB->isCall(Instr))479 ++N;480 }481 return N;482}483 484uint32_t BinaryBasicBlock::getNumPseudos() const {485#ifndef NDEBUG486 BinaryContext &BC = Function->getBinaryContext();487 uint32_t N = 0;488 for (const MCInst &Instr : Instructions)489 if (BC.MIB->isPseudo(Instr))490 ++N;491 492 if (N != NumPseudos) {493 BC.errs() << "BOLT-ERROR: instructions for basic block " << getName()494 << " in function " << *Function << ": calculated pseudos " << N495 << ", set pseudos " << NumPseudos << ", size " << size() << '\n';496 llvm_unreachable("pseudos mismatch");497 }498#endif499 return NumPseudos;500}501 502ErrorOr<std::pair<double, double>>503BinaryBasicBlock::getBranchStats(const BinaryBasicBlock *Succ) const {504 if (Function->hasValidProfile()) {505 uint64_t TotalCount = 0;506 uint64_t TotalMispreds = 0;507 for (const BinaryBranchInfo &BI : BranchInfo) {508 if (BI.Count != COUNT_NO_PROFILE) {509 TotalCount += BI.Count;510 TotalMispreds += BI.MispredictedCount;511 }512 }513 514 if (TotalCount > 0) {515 auto Itr = llvm::find(Successors, Succ);516 assert(Itr != Successors.end());517 const BinaryBranchInfo &BI = BranchInfo[Itr - Successors.begin()];518 if (BI.Count && BI.Count != COUNT_NO_PROFILE) {519 if (TotalMispreds == 0)520 TotalMispreds = 1;521 return std::make_pair(double(BI.Count) / TotalCount,522 double(BI.MispredictedCount) / TotalMispreds);523 }524 }525 }526 return make_error_code(llvm::errc::result_out_of_range);527}528 529void BinaryBasicBlock::dump() const {530 BinaryContext &BC = Function->getBinaryContext();531 if (Label)532 BC.outs() << Label->getName() << ":\n";533 BC.printInstructions(BC.outs(), Instructions.begin(), Instructions.end(),534 getOffset(), Function);535 BC.outs() << "preds:";536 for (auto itr = pred_begin(); itr != pred_end(); ++itr) {537 BC.outs() << " " << (*itr)->getName();538 }539 BC.outs() << "\nsuccs:";540 for (auto itr = succ_begin(); itr != succ_end(); ++itr) {541 BC.outs() << " " << (*itr)->getName();542 }543 BC.outs() << "\n";544}545 546uint64_t BinaryBasicBlock::estimateSize(const MCCodeEmitter *Emitter) const {547 return Function->getBinaryContext().computeCodeSize(begin(), end(), Emitter);548}549 550BinaryBasicBlock::BinaryBranchInfo &551BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) {552 return const_cast<BinaryBranchInfo &>(553 static_cast<const BinaryBasicBlock &>(*this).getBranchInfo(Succ));554}555 556const BinaryBasicBlock::BinaryBranchInfo &557BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) const {558 const auto Zip = llvm::zip(successors(), branch_info());559 const auto Result = llvm::find_if(560 Zip, [&](const auto &Tuple) { return std::get<0>(Tuple) == &Succ; });561 assert(Result != Zip.end() && "Cannot find target in successors");562 return std::get<1>(*Result);563}564 565BinaryBasicBlock *BinaryBasicBlock::splitAt(iterator II) {566 assert(II != end() && "expected iterator pointing to instruction");567 568 BinaryBasicBlock *NewBlock = getFunction()->addBasicBlock();569 570 // Adjust successors/predecessors and propagate the execution count.571 moveAllSuccessorsTo(NewBlock);572 addSuccessor(NewBlock, getExecutionCount(), 0);573 574 // Set correct CFI state for the new block.575 NewBlock->setCFIState(getCFIStateAtInstr(&*II));576 577 // Move instructions over.578 adjustNumPseudos(II, end(), -1);579 NewBlock->addInstructions(II, end());580 Instructions.erase(II, end());581 582 return NewBlock;583}584 585} // namespace bolt586} // namespace llvm587