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

source code of bolt/lib/Core/BinaryBasicBlock.cpp