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 =
135 CondBranch && TBB == getConditionalSuccessor(Condition: true)->getLabel() &&
136 (UncondBranch ? FBB == getConditionalSuccessor(Condition: 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(Val: BC.MIB->getJumpTable(Inst: *Inst)) << "\n";
148 JT->print(OS&: errs());
149 }
150 getFunction()->dump();
151 }
152 return Valid;
153}
154
155BinaryBasicBlock *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
166BinaryBasicBlock *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
180BinaryBasicBlock *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
188int32_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(C: 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(i: 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
258void BinaryBasicBlock::addSuccessor(BinaryBasicBlock *Succ, uint64_t Count,
259 uint64_t MispredictedCount) {
260 Successors.push_back(Elt: Succ);
261 BranchInfo.push_back(Elt: {.Count: Count, .MispredictedCount: MispredictedCount});
262 Succ->Predecessors.push_back(Elt: this);
263}
264
265void BinaryBasicBlock::replaceSuccessor(BinaryBasicBlock *Succ,
266 BinaryBasicBlock *NewSucc,
267 uint64_t Count,
268 uint64_t MispredictedCount) {
269 Succ->removePredecessor(Pred: 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: Count, .MispredictedCount: MispredictedCount};
282 NewSucc->addPredecessor(Pred: this);
283}
284
285void BinaryBasicBlock::removeAllSuccessors() {
286 SmallPtrSet<BinaryBasicBlock *, 2> UniqSuccessors(succ_begin(), succ_end());
287 for (BinaryBasicBlock *SuccessorBB : UniqSuccessors)
288 SuccessorBB->removePredecessor(Pred: this);
289 Successors.clear();
290 BranchInfo.clear();
291}
292
293void BinaryBasicBlock::removeSuccessor(BinaryBasicBlock *Succ) {
294 Succ->removePredecessor(Pred: 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(CI: I);
306 BranchInfo.erase(CI: BI);
307}
308
309void BinaryBasicBlock::addPredecessor(BinaryBasicBlock *Pred) {
310 Predecessors.push_back(Elt: Pred);
311}
312
313void 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(CI: 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
331void 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(II: findInstruction(Inst: CondBranch));
340
341 Successors.clear();
342 BranchInfo.clear();
343
344 Successors.push_back(Elt: 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(Elt: {.Count: Count, .MispredictedCount: 0});
350}
351
352void 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(Args&: BB);
370 }
371 llvm::sort(C&: SuccessorBBs,
372 Comp: [](const BinaryBasicBlock *BB1, const BinaryBasicBlock *BB2) {
373 return BB1->getInputOffset() < BB2->getInputOffset();
374 });
375 SuccessorBBs.erase(CS: llvm::unique(R&: SuccessorBBs), CE: SuccessorBBs.end());
376
377 for (BinaryBasicBlock *BB : SuccessorBBs)
378 addSuccessor(Succ: BB);
379}
380
381void BinaryBasicBlock::adjustExecutionCount(double Ratio) {
382 auto adjustedCount = [&](uint64_t Count) -> uint64_t {
383 double NewCount = Count * Ratio;
384 if (!NewCount && Count && (Ratio > 0.0))
385 NewCount = 1;
386 return NewCount;
387 };
388
389 setExecutionCount(adjustedCount(getKnownExecutionCount()));
390 for (BinaryBranchInfo &BI : branch_info()) {
391 if (BI.Count != COUNT_NO_PROFILE)
392 BI.Count = adjustedCount(BI.Count);
393 if (BI.MispredictedCount != COUNT_INFERRED)
394 BI.MispredictedCount = adjustedCount(BI.MispredictedCount);
395 }
396}
397
398bool BinaryBasicBlock::analyzeBranch(const MCSymbol *&TBB, const MCSymbol *&FBB,
399 MCInst *&CondBranch,
400 MCInst *&UncondBranch) {
401 auto &MIB = Function->getBinaryContext().MIB;
402 return MIB->analyzeBranch(Begin: Instructions.begin(), End: Instructions.end(), TBB, FBB,
403 CondBranch, UncondBranch);
404}
405
406MCInst *BinaryBasicBlock::getTerminatorBefore(MCInst *Pos) {
407 BinaryContext &BC = Function->getBinaryContext();
408 auto Itr = rbegin();
409 bool Check = Pos ? false : true;
410 MCInst *FirstTerminator = nullptr;
411 while (Itr != rend()) {
412 if (!Check) {
413 if (&*Itr == Pos)
414 Check = true;
415 ++Itr;
416 continue;
417 }
418 if (BC.MIB->isTerminator(Inst: *Itr))
419 FirstTerminator = &*Itr;
420 ++Itr;
421 }
422 return FirstTerminator;
423}
424
425bool BinaryBasicBlock::hasTerminatorAfter(MCInst *Pos) {
426 BinaryContext &BC = Function->getBinaryContext();
427 auto Itr = rbegin();
428 while (Itr != rend()) {
429 if (&*Itr == Pos)
430 return false;
431 if (BC.MIB->isTerminator(Inst: *Itr))
432 return true;
433 ++Itr;
434 }
435 return false;
436}
437
438bool BinaryBasicBlock::swapConditionalSuccessors() {
439 if (succ_size() != 2)
440 return false;
441
442 std::swap(a&: Successors[0], b&: Successors[1]);
443 std::swap(a&: BranchInfo[0], b&: BranchInfo[1]);
444 return true;
445}
446
447void BinaryBasicBlock::addBranchInstruction(const BinaryBasicBlock *Successor) {
448 assert(isSuccessor(Successor));
449 BinaryContext &BC = Function->getBinaryContext();
450 MCInst NewInst;
451 std::unique_lock<llvm::sys::RWMutex> Lock(BC.CtxMutex);
452 BC.MIB->createUncondBranch(Inst&: NewInst, TBB: Successor->getLabel(), Ctx: BC.Ctx.get());
453 Instructions.emplace_back(args: std::move(NewInst));
454}
455
456void BinaryBasicBlock::addTailCallInstruction(const MCSymbol *Target) {
457 BinaryContext &BC = Function->getBinaryContext();
458 MCInst NewInst;
459 BC.MIB->createTailCall(Inst&: NewInst, Target, Ctx: BC.Ctx.get());
460 Instructions.emplace_back(args: std::move(NewInst));
461}
462
463uint32_t BinaryBasicBlock::getNumCalls() const {
464 uint32_t N = 0;
465 BinaryContext &BC = Function->getBinaryContext();
466 for (const MCInst &Instr : Instructions) {
467 if (BC.MIB->isCall(Inst: Instr))
468 ++N;
469 }
470 return N;
471}
472
473uint32_t BinaryBasicBlock::getNumPseudos() const {
474#ifndef NDEBUG
475 BinaryContext &BC = Function->getBinaryContext();
476 uint32_t N = 0;
477 for (const MCInst &Instr : Instructions)
478 if (BC.MIB->isPseudo(Inst: Instr))
479 ++N;
480
481 if (N != NumPseudos) {
482 BC.errs() << "BOLT-ERROR: instructions for basic block " << getName()
483 << " in function " << *Function << ": calculated pseudos " << N
484 << ", set pseudos " << NumPseudos << ", size " << size() << '\n';
485 llvm_unreachable("pseudos mismatch");
486 }
487#endif
488 return NumPseudos;
489}
490
491ErrorOr<std::pair<double, double>>
492BinaryBasicBlock::getBranchStats(const BinaryBasicBlock *Succ) const {
493 if (Function->hasValidProfile()) {
494 uint64_t TotalCount = 0;
495 uint64_t TotalMispreds = 0;
496 for (const BinaryBranchInfo &BI : BranchInfo) {
497 if (BI.Count != COUNT_NO_PROFILE) {
498 TotalCount += BI.Count;
499 TotalMispreds += BI.MispredictedCount;
500 }
501 }
502
503 if (TotalCount > 0) {
504 auto Itr = llvm::find(Range: Successors, Val: Succ);
505 assert(Itr != Successors.end());
506 const BinaryBranchInfo &BI = BranchInfo[Itr - Successors.begin()];
507 if (BI.Count && BI.Count != COUNT_NO_PROFILE) {
508 if (TotalMispreds == 0)
509 TotalMispreds = 1;
510 return std::make_pair(x: double(BI.Count) / TotalCount,
511 y: double(BI.MispredictedCount) / TotalMispreds);
512 }
513 }
514 }
515 return make_error_code(E: llvm::errc::result_out_of_range);
516}
517
518void BinaryBasicBlock::dump() const {
519 BinaryContext &BC = Function->getBinaryContext();
520 if (Label)
521 BC.outs() << Label->getName() << ":\n";
522 BC.printInstructions(OS&: BC.outs(), Begin: Instructions.begin(), End: Instructions.end(),
523 Offset: getOffset(), Function);
524 BC.outs() << "preds:";
525 for (auto itr = pred_begin(); itr != pred_end(); ++itr) {
526 BC.outs() << " " << (*itr)->getName();
527 }
528 BC.outs() << "\nsuccs:";
529 for (auto itr = succ_begin(); itr != succ_end(); ++itr) {
530 BC.outs() << " " << (*itr)->getName();
531 }
532 BC.outs() << "\n";
533}
534
535uint64_t BinaryBasicBlock::estimateSize(const MCCodeEmitter *Emitter) const {
536 return Function->getBinaryContext().computeCodeSize(Beg: begin(), End: end(), Emitter);
537}
538
539BinaryBasicBlock::BinaryBranchInfo &
540BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) {
541 return const_cast<BinaryBranchInfo &>(
542 static_cast<const BinaryBasicBlock &>(*this).getBranchInfo(Succ));
543}
544
545const BinaryBasicBlock::BinaryBranchInfo &
546BinaryBasicBlock::getBranchInfo(const BinaryBasicBlock &Succ) const {
547 const auto Zip = llvm::zip(t: successors(), u: branch_info());
548 const auto Result = llvm::find_if(
549 Range: Zip, P: [&](const auto &Tuple) { return std::get<0>(Tuple) == &Succ; });
550 assert(Result != Zip.end() && "Cannot find target in successors");
551 return std::get<1>(t: *Result);
552}
553
554BinaryBasicBlock *BinaryBasicBlock::splitAt(iterator II) {
555 assert(II != end() && "expected iterator pointing to instruction");
556
557 BinaryBasicBlock *NewBlock = getFunction()->addBasicBlock();
558
559 // Adjust successors/predecessors and propagate the execution count.
560 moveAllSuccessorsTo(New: NewBlock);
561 addSuccessor(Succ: NewBlock, Count: getExecutionCount(), MispredictedCount: 0);
562
563 // Set correct CFI state for the new block.
564 NewBlock->setCFIState(getCFIStateAtInstr(Instr: &*II));
565
566 // Move instructions over.
567 adjustNumPseudos(Begin: II, End: end(), Sign: -1);
568 NewBlock->addInstructions(Begin: II, End: end());
569 Instructions.erase(first: II, last: end());
570
571 return NewBlock;
572}
573
574} // namespace bolt
575} // namespace llvm
576

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