bolt/lib/Core/BinaryBasicBlock.cpp

   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
  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 const JumpTable *BinaryBasicBlock::getJumpTable() const {
  42   const MCInst *Inst = getLastNonPseudoInstr();
  43   const JumpTable *JT = Inst ? Function->getJumpTable(*Inst) : nullptr;
  44   return JT;
  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         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
 155 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
 166 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
 180 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
 188 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
 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
 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
 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
 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
 309 void BinaryBasicBlock::addPredecessor(BinaryBasicBlock *Pred) {
 310   Predecessors.push_back(Pred);
 311 }
 312
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 464 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
 474 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>>
 493 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
 519 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
 536 uint64_t BinaryBasicBlock::estimateSize(const MCCodeEmitter *Emitter) const {
 537   return Function->getBinaryContext().computeCodeSize(begin(), end(), Emitter);
 538 }
 539
 540 BinaryBasicBlock::BinaryBranchInfo &
 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 &
 547 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
 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