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