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