BinaryBasicBlock.cpp

//===- bolt/Core/BinaryBasicBlock.cpp - Low-level basic block -------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the BinaryBasicBlock class.
//
//===----------------------------------------------------------------------===//

#include"bolt/Core/BinaryBasicBlock.h"
#include"bolt/Core/BinaryContext.h"
#include"bolt/Core/BinaryFunction.h"
#include"llvm/ADT/SmallPtrSet.h"
#include"llvm/MC/MCInst.h"
#include"llvm/Support/Errc.h"

#defineDEBUG_TYPE"bolt"

namespacellvm {
namespacebolt {

constexpruint32_t BinaryBasicBlock::INVALID_OFFSET;

booloperator<(const BinaryBasicBlock &LHS, const BinaryBasicBlock &RHS) {
return LHS.Index < RHS.Index;
}

boolBinaryBasicBlock::hasCFG() const { returngetParent()->hasCFG(); }

boolBinaryBasicBlock::isEntryPoint() const {
returngetParent()->isEntryPoint(*this);
}

boolBinaryBasicBlock::hasInstructions() const {
returngetParent()->hasInstructions();
}

const JumpTable *BinaryBasicBlock::getJumpTable() const {
const MCInst *Inst = getLastNonPseudoInstr();
const JumpTable *JT = Inst ? Function->getJumpTable(*Inst) : nullptr;
return JT;
}

voidBinaryBasicBlock::adjustNumPseudos(const MCInst &Inst, int Sign) {
 BinaryContext &BC = Function->getBinaryContext();
if (BC.MIB->isPseudo(Inst))
 NumPseudos += Sign;
}

BinaryBasicBlock::iterator BinaryBasicBlock::getFirstNonPseudo() {
const BinaryContext &BC = Function->getBinaryContext();
for (auto II = Instructions.begin(), E = Instructions.end(); II != E; ++II) {
if (!BC.MIB->isPseudo(*II))
return II;
 }
returnend();
}

BinaryBasicBlock::reverse_iterator BinaryBasicBlock::getLastNonPseudo() {
const BinaryContext &BC = Function->getBinaryContext();
for (auto RII = Instructions.rbegin(), E = Instructions.rend(); RII != E;
 ++RII) {
if (!BC.MIB->isPseudo(*RII))
return RII;
 }
returnrend();
}

boolBinaryBasicBlock::validateSuccessorInvariants() {
const MCInst *Inst = getLastNonPseudoInstr();
const JumpTable *JT = Inst ? Function->getJumpTable(*Inst) : nullptr;
 BinaryContext &BC = Function->getBinaryContext();
bool Valid = true;

if (JT) {
// Note: for now we assume that successors do not reference labels from
// any overlapping jump tables. We only look at the entries for the jump
// table that is referenced at the last instruction.
constauto Range = JT->getEntriesForAddress(BC.MIB->getJumpTable(*Inst));
const std::vector<const MCSymbol *> Entries(
std::next(JT->Entries.begin(), Range.first),
std::next(JT->Entries.begin(), Range.second));
 std::set<const MCSymbol *> UniqueSyms(Entries.begin(), Entries.end());
for (BinaryBasicBlock *Succ : Successors) {
auto Itr = UniqueSyms.find(Succ->getLabel());
if (Itr != UniqueSyms.end()) {
 UniqueSyms.erase(Itr);
 } else {
// Work on the assumption that jump table blocks don't
// have a conditional successor.
 Valid = false;
 BC.errs() << "BOLT-WARNING: Jump table successor " << Succ->getName()
 << " not contained in the jump table.\n";
 }
 }
// If there are any leftover entries in the jump table, they
// must be one of the function end labels.
if (Valid) {
for (const MCSymbol *Sym : UniqueSyms) {
 Valid &= (Sym == Function->getFunctionEndLabel() ||
 Sym == Function->getFunctionEndLabel(getFragmentNum()));
if (!Valid) {
 BC.errs() << "BOLT-WARNING: Jump table contains illegal entry: "
 << Sym->getName() << "\n";
 }
 }
 }
 } else {
// Unknown control flow.
if (Inst && BC.MIB->isIndirectBranch(*Inst))
returntrue;

const MCSymbol *TBB = nullptr;
const MCSymbol *FBB = nullptr;
 MCInst *CondBranch = nullptr;
 MCInst *UncondBranch = nullptr;

if (analyzeBranch(TBB, FBB, CondBranch, UncondBranch)) {
switch (Successors.size()) {
case0:
 Valid = !CondBranch && !UncondBranch;
break;
case1: {
constbool HasCondBlock =
 CondBranch && Function->getBasicBlockForLabel(
 BC.MIB->getTargetSymbol(*CondBranch));
 Valid = !CondBranch || !HasCondBlock;
break;
 }
case2:
 Valid =
 CondBranch && TBB == getConditionalSuccessor(true)->getLabel() &&
 (UncondBranch ? FBB == getConditionalSuccessor(false)->getLabel()
 : !FBB);
break;
 }
 }
 }
if (!Valid) {
 BC.errs() << "BOLT-WARNING: CFG invalid in " << *getFunction() << " @ "
 << getName() << "\n";
if (JT) {
 BC.errs() << "Jump Table instruction addr = 0x"
 << Twine::utohexstr(BC.MIB->getJumpTable(*Inst)) << "\n";
 JT->print(errs());
 }
getFunction()->dump();
 }
return Valid;
}

BinaryBasicBlock *BinaryBasicBlock::getSuccessor(const MCSymbol *Label) const {
if (!Label && succ_size() == 1)
return *succ_begin();

for (BinaryBasicBlock *BB : successors())
if (BB->getLabel() == Label)
return BB;

returnnullptr;
}

BinaryBasicBlock *BinaryBasicBlock::getSuccessor(const MCSymbol *Label,
 BinaryBranchInfo &BI) const {
auto BIIter = branch_info_begin();
for (BinaryBasicBlock *BB : successors()) {
if (BB->getLabel() == Label) {
 BI = *BIIter;
return BB;
 }
 ++BIIter;
 }

returnnullptr;
}

BinaryBasicBlock *BinaryBasicBlock::getLandingPad(const MCSymbol *Label) const {
for (BinaryBasicBlock *BB : landing_pads())
if (BB->getLabel() == Label)
return BB;

returnnullptr;
}

int32_tBinaryBasicBlock::getCFIStateAtInstr(const MCInst *Instr) const {
assert(
getFunction()->getState() >= BinaryFunction::State::CFG &&
"can only calculate CFI state when function is in or past the CFG state");

const BinaryFunction::CFIInstrMapType &FDEProgram =
getFunction()->getFDEProgram();

// Find the last CFI preceding Instr in this basic block.
const MCInst *LastCFI = nullptr;
bool InstrSeen = (Instr == nullptr);
for (const MCInst &Inst : llvm::reverse(Instructions)) {
if (!InstrSeen) {
 InstrSeen = (&Inst == Instr);
continue;
 }
if (Function->getBinaryContext().MIB->isCFI(Inst)) {
 LastCFI = &Inst;
break;
 }
 }

assert(InstrSeen && "instruction expected in basic block");

// CFI state is the same as at basic block entry point.
if (!LastCFI)
returngetCFIState();

// Fold all RememberState/RestoreState sequences, such as for:
//
// [ CFI #(K-1) ]
// RememberState (#K)
// ....
// RestoreState
// RememberState
// ....
// RestoreState
// [ GNU_args_size ]
// RememberState
// ....
// RestoreState <- LastCFI
//
// we return K - the most efficient state to (re-)generate.
int64_t State = LastCFI->getOperand(0).getImm();
while (State >= 0 &&
 FDEProgram[State].getOperation() == MCCFIInstruction::OpRestoreState) {
int32_t Depth = 1;
 --State;
assert(State >= 0 && "first CFI cannot be RestoreState");
while (Depth && State >= 0) {
const MCCFIInstruction &CFIInstr = FDEProgram[State];
if (CFIInstr.getOperation() == MCCFIInstruction::OpRestoreState)
 ++Depth;
elseif (CFIInstr.getOperation() == MCCFIInstruction::OpRememberState)
 --Depth;
 --State;
 }
assert(Depth == 0 && "unbalanced RememberState/RestoreState stack");

// Skip any GNU_args_size.
while (State >= 0 && FDEProgram[State].getOperation() ==
 MCCFIInstruction::OpGnuArgsSize) {
 --State;
 }
 }

assert((State + 1 >= 0) && "miscalculated CFI state");
return State + 1;
}

voidBinaryBasicBlock::addSuccessor(BinaryBasicBlock *Succ, uint64_t Count,
uint64_t MispredictedCount) {
 Successors.push_back(Succ);
 BranchInfo.push_back({Count, MispredictedCount});
 Succ->Predecessors.push_back(this);
}

voidBinaryBasicBlock::replaceSuccessor(BinaryBasicBlock *Succ,
 BinaryBasicBlock *NewSucc,
uint64_t Count,
uint64_t MispredictedCount) {
 Succ->removePredecessor(this, /*Multiple=*/false);
auto I = succ_begin();
auto BI = BranchInfo.begin();
for (; I != succ_end(); ++I) {
assert(BI != BranchInfo.end() && "missing BranchInfo entry");
if (*I == Succ)
break;
 ++BI;
 }
assert(I != succ_end() && "no such successor!");

 *I = NewSucc;
 *BI = BinaryBranchInfo{Count, MispredictedCount};
 NewSucc->addPredecessor(this);
}

voidBinaryBasicBlock::removeAllSuccessors() {
 SmallPtrSet<BinaryBasicBlock *, 2> UniqSuccessors(succ_begin(), succ_end());
for (BinaryBasicBlock *SuccessorBB : UniqSuccessors)
 SuccessorBB->removePredecessor(this);
 Successors.clear();
 BranchInfo.clear();
}

voidBinaryBasicBlock::removeSuccessor(BinaryBasicBlock *Succ) {
 Succ->removePredecessor(this, /*Multiple=*/false);
auto I = succ_begin();
auto BI = BranchInfo.begin();
for (; I != succ_end(); ++I) {
assert(BI != BranchInfo.end() && "missing BranchInfo entry");
if (*I == Succ)
break;
 ++BI;
 }
assert(I != succ_end() && "no such successor!");

 Successors.erase(I);
 BranchInfo.erase(BI);
}

voidBinaryBasicBlock::addPredecessor(BinaryBasicBlock *Pred) {
 Predecessors.push_back(Pred);
}

voidBinaryBasicBlock::removePredecessor(BinaryBasicBlock *Pred,
bool Multiple) {
// Note: the predecessor could be listed multiple times.
bool Erased = false;
for (auto PredI = Predecessors.begin(); PredI != Predecessors.end();) {
if (*PredI == Pred) {
 Erased = true;
 PredI = Predecessors.erase(PredI);
if (!Multiple)
return;
 } else {
 ++PredI;
 }
 }
assert(Erased && "Pred is not a predecessor of this block!");
 (void)Erased;
}

voidBinaryBasicBlock::removeDuplicateConditionalSuccessor(MCInst *CondBranch) {
assert(succ_size() == 2 && Successors[0] == Successors[1] &&
"conditional successors expected");

 BinaryBasicBlock *Succ = Successors[0];
const BinaryBranchInfo CondBI = BranchInfo[0];
const BinaryBranchInfo UncondBI = BranchInfo[1];

eraseInstruction(findInstruction(CondBranch));

 Successors.clear();
 BranchInfo.clear();

 Successors.push_back(Succ);

uint64_t Count = COUNT_NO_PROFILE;
if (CondBI.Count != COUNT_NO_PROFILE && UncondBI.Count != COUNT_NO_PROFILE)
 Count = CondBI.Count + UncondBI.Count;
 BranchInfo.push_back({Count, 0});
}

voidBinaryBasicBlock::updateJumpTableSuccessors() {
const JumpTable *JT = getJumpTable();
assert(JT && "Expected jump table instruction.");

// Clear existing successors.
removeAllSuccessors();

// Generate the list of successors in deterministic order without duplicates.
 SmallVector<BinaryBasicBlock *, 16> SuccessorBBs;
for (const MCSymbol *Label : JT->Entries) {
 BinaryBasicBlock *BB = getFunction()->getBasicBlockForLabel(Label);
// Ignore __builtin_unreachable()
if (!BB) {
assert(Label == getFunction()->getFunctionEndLabel() &&
"JT label should match a block or end of function.");
continue;
 }
 SuccessorBBs.emplace_back(BB);
 }
llvm::sort(SuccessorBBs,
 [](const BinaryBasicBlock *BB1, const BinaryBasicBlock *BB2) {
return BB1->getInputOffset() < BB2->getInputOffset();
 });
 SuccessorBBs.erase(llvm::unique(SuccessorBBs), SuccessorBBs.end());

for (BinaryBasicBlock *BB : SuccessorBBs)
addSuccessor(BB);
}

voidBinaryBasicBlock::adjustExecutionCount(double Ratio) {
auto adjustedCount = [&](uint64_t Count) -> uint64_t {
double NewCount = Count * Ratio;
if (!NewCount && Count && (Ratio > 0.0))
 NewCount = 1;
return NewCount;
 };

setExecutionCount(adjustedCount(getKnownExecutionCount()));
for (BinaryBranchInfo &BI : branch_info()) {
if (BI.Count != COUNT_NO_PROFILE)
 BI.Count = adjustedCount(BI.Count);
if (BI.MispredictedCount != COUNT_INFERRED)
 BI.MispredictedCount = adjustedCount(BI.MispredictedCount);
 }
}

boolBinaryBasicBlock::analyzeBranch(const MCSymbol *&TBB, const MCSymbol *&FBB,
 MCInst *&CondBranch,
 MCInst *&UncondBranch) {
auto &MIB = Function->getBinaryContext().MIB;
return MIB->analyzeBranch(Instructions.begin(), Instructions.end(), TBB, FBB,
 CondBranch, UncondBranch);
}

MCInst *BinaryBasicBlock::getTerminatorBefore(MCInst *Pos) {
 BinaryContext &BC = Function->getBinaryContext();
auto Itr = rbegin();
bool Check = Pos ? false : true;
 MCInst *FirstTerminator = nullptr;
while (Itr != rend()) {
if (!Check) {
if (&*Itr == Pos)
 Check = true;
 ++Itr;
continue;
 }
if (BC.MIB->isTerminator(*Itr))
 FirstTerminator = &*Itr;
 ++Itr;
 }
return FirstTerminator;
}

boolBinaryBasicBlock::hasTerminatorAfter(MCInst *Pos) {
 BinaryContext &BC = Function->getBinaryContext();
auto Itr = rbegin();
while (Itr != rend()) {
if (&*Itr == Pos)
returnfalse;
if (BC.MIB->isTerminator(*Itr))
returntrue;
 ++Itr;
 }
returnfalse;
}

boolBinaryBasicBlock::swapConditionalSuccessors() {
if (succ_size() != 2)
returnfalse;

std::swap(Successors[0], Successors[1]);
std::swap(BranchInfo[0], BranchInfo[1]);
returntrue;
}

voidBinaryBasicBlock::addBranchInstruction(const BinaryBasicBlock *Successor) {
assert(isSuccessor(Successor));
 BinaryContext &BC = Function->getBinaryContext();
 MCInst NewInst;
 std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex);
 BC.MIB->createUncondBranch(NewInst, Successor->getLabel(), BC.Ctx.get());
 Instructions.emplace_back(std::move(NewInst));
}

voidBinaryBasicBlock::addTailCallInstruction(const MCSymbol *Target) {
 BinaryContext &BC = Function->getBinaryContext();
 MCInst NewInst;
 BC.MIB->createTailCall(NewInst, Target, BC.Ctx.get());
 Instructions.emplace_back(std::move(NewInst));
}

uint32_tBinaryBasicBlock::getNumCalls() const {
uint32_t N = 0;
 BinaryContext &BC = Function->getBinaryContext();
for (const MCInst &Instr : Instructions) {
if (BC.MIB->isCall(Instr))
 ++N;
 }
return N;
}

uint32_tBinaryBasicBlock::getNumPseudos() const {
#ifndef NDEBUG
 BinaryContext &BC = Function->getBinaryContext();
uint32_t N = 0;
for (const MCInst &Instr : Instructions)
if (BC.MIB->isPseudo(Instr))
 ++N;

if (N != NumPseudos) {
 BC.errs() << "BOLT-ERROR: instructions for basic block " << getName()
 << " in function " << *Function << ": calculated pseudos " << N
 << ", set pseudos " << NumPseudos << ", size " << size() << '\n';
llvm_unreachable("pseudos mismatch");
 }
#endif
return NumPseudos;
}

ErrorOr<std::pair<double, double>>
BinaryBasicBlock::getBranchStats(const BinaryBasicBlock *Succ) const {
if (Function->hasValidProfile()) {
uint64_t TotalCount = 0;
uint64_t TotalMispreds = 0;
for (const BinaryBranchInfo &BI : BranchInfo) {
if (BI.Count != COUNT_NO_PROFILE) {
 TotalCount += BI.Count;
 TotalMispreds += BI.MispredictedCount;
 }
 }

if (TotalCount > 0) {
auto Itr = llvm::find(Successors, Succ);
assert(Itr != Successors.end());
const BinaryBranchInfo &BI = BranchInfo[Itr - Successors.begin()];
if (BI.Count && BI.Count != COUNT_NO_PROFILE) {
if (TotalMispreds == 0)
 TotalMispreds = 1;
returnstd::make_pair(double(BI.Count) / TotalCount,
double(BI.MispredictedCount) / TotalMispreds);
 }
 }
 }
returnmake_error_code(llvm::errc::result_out_of_range);
}

voidBinaryBasicBlock::dump() const {
 BinaryContext &BC = Function->getBinaryContext();
if (Label)
 BC.outs() << Label->getName() << ":\n";
 BC.printInstructions(BC.outs(), Instructions.begin(), Instructions.end(),
getOffset(), Function);
 BC.outs() << "preds:";
for (auto itr = pred_begin(); itr != pred_end(); ++itr) {
 BC.outs() << "" << (*itr)->getName();
 }
 BC.outs() << "\nsuccs:";
for (auto itr = succ_begin(); itr != succ_end(); ++itr) {
 BC.outs() << "" << (*itr)->getName();
 }
 BC.outs() << "\n";
}

uint64_tBinaryBasicBlock::estimateSize(const MCCodeEmitter *Emitter) const {
return Function->getBinaryContext().computeCodeSize(begin(), end(), Emitter);
}

BinaryBasicBlock::BinaryBranchInfo &
BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) {
returnconst_cast<BinaryBranchInfo &>(
static_cast<const BinaryBasicBlock &>(*this).getBranchInfo(Succ));
}

const BinaryBasicBlock::BinaryBranchInfo &
BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) const {
constauto Zip = llvm::zip(successors(), branch_info());
constauto Result = llvm::find_if(
 Zip, [&](constauto &Tuple) { return std::get<0>(Tuple) == &Succ; });
assert(Result != Zip.end() && "Cannot find target in successors");
return std::get<1>(*Result);
}

BinaryBasicBlock *BinaryBasicBlock::splitAt(iterator II) {
assert(II != end() && "expected iterator pointing to instruction");

 BinaryBasicBlock *NewBlock = getFunction()->addBasicBlock();

// Adjust successors/predecessors and propagate the execution count.
moveAllSuccessorsTo(NewBlock);
addSuccessor(NewBlock, getExecutionCount(), 0);

// Set correct CFI state for the new block.
 NewBlock->setCFIState(getCFIStateAtInstr(&*II));

// Move instructions over.
adjustNumPseudos(II, end(), -1);
 NewBlock->addInstructions(II, end());
 Instructions.erase(II, end());

return NewBlock;
}

} // namespace bolt
} // namespace llvm