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