671 lines · cpp
1//===- bolt/Passes/TailDuplication.cpp ------------------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the TailDuplication class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/TailDuplication.h"14#include "llvm/ADT/DenseMap.h"15#include "llvm/MC/MCRegisterInfo.h"16 17#include <numeric>18#include <queue>19 20#define DEBUG_TYPE "taildup"21 22using namespace llvm;23 24namespace opts {25 26extern cl::OptionCategory BoltOptCategory;27extern cl::opt<bool> NoThreads;28 29static cl::opt<bolt::TailDuplication::DuplicationMode> TailDuplicationMode(30 "tail-duplication",31 cl::desc("duplicate unconditional branches that cross a cache line"),32 cl::init(bolt::TailDuplication::TD_NONE),33 cl::values(clEnumValN(bolt::TailDuplication::TD_NONE, "none",34 "do not apply"),35 clEnumValN(bolt::TailDuplication::TD_AGGRESSIVE, "aggressive",36 "aggressive strategy"),37 clEnumValN(bolt::TailDuplication::TD_MODERATE, "moderate",38 "moderate strategy"),39 clEnumValN(bolt::TailDuplication::TD_CACHE, "cache",40 "cache-aware duplication strategy")),41 cl::ZeroOrMore, cl::Hidden, cl::cat(BoltOptCategory));42 43static cl::opt<unsigned>44 TailDuplicationMinimumOffset("tail-duplication-minimum-offset",45 cl::desc("minimum offset needed between block "46 "and successor to allow duplication"),47 cl::ReallyHidden, cl::init(64),48 cl::cat(BoltOptCategory));49 50static cl::opt<unsigned> TailDuplicationMaximumDuplication(51 "tail-duplication-maximum-duplication",52 cl::desc("tail blocks whose size (in bytes) exceeds the value are never "53 "duplicated"),54 cl::ZeroOrMore, cl::ReallyHidden, cl::init(24), cl::cat(BoltOptCategory));55 56static cl::opt<unsigned> TailDuplicationMinimumDuplication(57 "tail-duplication-minimum-duplication",58 cl::desc("tail blocks with size (in bytes) not exceeding the value are "59 "always duplicated"),60 cl::ReallyHidden, cl::init(2), cl::cat(BoltOptCategory));61 62static cl::opt<bool> TailDuplicationConstCopyPropagation(63 "tail-duplication-const-copy-propagation",64 cl::desc("enable const and copy propagation after tail duplication"),65 cl::ReallyHidden, cl::init(false), cl::cat(BoltOptCategory));66 67static cl::opt<unsigned> TailDuplicationMaxCacheDistance(68 "tail-duplication-max-cache-distance",69 cl::desc("The weight of backward jumps for ExtTSP value"), cl::init(256),70 cl::ReallyHidden, cl::cat(BoltOptCategory));71 72static cl::opt<double> TailDuplicationCacheBackwardWeight(73 "tail-duplication-cache-backward-weight",74 cl::desc(75 "The maximum distance (in bytes) of backward jumps for ExtTSP value"),76 cl::init(0.5), cl::ReallyHidden, cl::cat(BoltOptCategory));77 78} // namespace opts79 80namespace llvm {81namespace bolt {82 83void TailDuplication::getCallerSavedRegs(const MCInst &Inst, BitVector &Regs,84 BinaryContext &BC) const {85 if (!BC.MIB->isCall(Inst))86 return;87 BitVector CallRegs = BitVector(BC.MRI->getNumRegs(), false);88 BC.MIB->getCalleeSavedRegs(CallRegs);89 CallRegs.flip();90 Regs |= CallRegs;91}92 93bool TailDuplication::regIsPossiblyOverwritten(const MCInst &Inst, unsigned Reg,94 BinaryContext &BC) const {95 BitVector WrittenRegs = BitVector(BC.MRI->getNumRegs(), false);96 BC.MIB->getWrittenRegs(Inst, WrittenRegs);97 getCallerSavedRegs(Inst, WrittenRegs, BC);98 if (BC.MIB->isRep(Inst))99 BC.MIB->getRepRegs(WrittenRegs);100 WrittenRegs &= BC.MIB->getAliases(Reg, false);101 return WrittenRegs.any();102}103 104bool TailDuplication::regIsDefinitelyOverwritten(const MCInst &Inst,105 unsigned Reg,106 BinaryContext &BC) const {107 BitVector WrittenRegs = BitVector(BC.MRI->getNumRegs(), false);108 BC.MIB->getWrittenRegs(Inst, WrittenRegs);109 getCallerSavedRegs(Inst, WrittenRegs, BC);110 if (BC.MIB->isRep(Inst))111 BC.MIB->getRepRegs(WrittenRegs);112 return (!regIsUsed(Inst, Reg, BC) && WrittenRegs.test(Reg) &&113 !BC.MIB->isConditionalMove(Inst));114}115 116bool TailDuplication::regIsUsed(const MCInst &Inst, unsigned Reg,117 BinaryContext &BC) const {118 BitVector SrcRegs = BitVector(BC.MRI->getNumRegs(), false);119 BC.MIB->getSrcRegs(Inst, SrcRegs);120 SrcRegs &= BC.MIB->getAliases(Reg, true);121 return SrcRegs.any();122}123 124bool TailDuplication::isOverwrittenBeforeUsed(BinaryBasicBlock &StartBB,125 unsigned Reg) const {126 BinaryFunction *BF = StartBB.getFunction();127 BinaryContext &BC = BF->getBinaryContext();128 std::queue<BinaryBasicBlock *> Q;129 for (auto Itr = StartBB.succ_begin(); Itr != StartBB.succ_end(); ++Itr) {130 BinaryBasicBlock *NextBB = *Itr;131 Q.push(NextBB);132 }133 std::set<BinaryBasicBlock *> Visited;134 // Breadth first search through successive blocks and see if Reg is ever used135 // before its overwritten136 while (Q.size() > 0) {137 BinaryBasicBlock *CurrBB = Q.front();138 Q.pop();139 if (Visited.count(CurrBB))140 continue;141 Visited.insert(CurrBB);142 bool Overwritten = false;143 for (auto Itr = CurrBB->begin(); Itr != CurrBB->end(); ++Itr) {144 MCInst &Inst = *Itr;145 if (regIsUsed(Inst, Reg, BC))146 return false;147 if (regIsDefinitelyOverwritten(Inst, Reg, BC)) {148 Overwritten = true;149 break;150 }151 }152 if (Overwritten)153 continue;154 for (auto Itr = CurrBB->succ_begin(); Itr != CurrBB->succ_end(); ++Itr) {155 BinaryBasicBlock *NextBB = *Itr;156 Q.push(NextBB);157 }158 }159 return true;160}161 162void TailDuplication::constantAndCopyPropagate(163 BinaryBasicBlock &OriginalBB,164 std::vector<BinaryBasicBlock *> &BlocksToPropagate) {165 BinaryFunction *BF = OriginalBB.getFunction();166 BinaryContext &BC = BF->getBinaryContext();167 168 BlocksToPropagate.insert(BlocksToPropagate.begin(), &OriginalBB);169 // Iterate through the original instructions to find one to propagate170 for (auto Itr = OriginalBB.begin(); Itr != OriginalBB.end(); ++Itr) {171 MCInst &OriginalInst = *Itr;172 // It must be a non conditional173 if (BC.MIB->isConditionalMove(OriginalInst))174 continue;175 176 // Move immediate or move register177 if ((!BC.MII->get(OriginalInst.getOpcode()).isMoveImmediate() ||178 !OriginalInst.getOperand(1).isImm()) &&179 (!BC.MII->get(OriginalInst.getOpcode()).isMoveReg() ||180 !OriginalInst.getOperand(1).isReg()))181 continue;182 183 // True if this is constant propagation and not copy propagation184 bool ConstantProp = BC.MII->get(OriginalInst.getOpcode()).isMoveImmediate();185 // The Register to replaced186 unsigned Reg = OriginalInst.getOperand(0).getReg();187 // True if the register to replace was replaced everywhere it was used188 bool ReplacedEverywhere = true;189 // True if the register was definitely overwritten190 bool Overwritten = false;191 // True if the register to replace and the register to replace with (for192 // copy propagation) has not been overwritten and is still usable193 bool RegsActive = true;194 195 // Iterate through successor blocks and through their instructions196 for (BinaryBasicBlock *NextBB : BlocksToPropagate) {197 for (auto PropagateItr =198 ((NextBB == &OriginalBB) ? Itr + 1 : NextBB->begin());199 PropagateItr < NextBB->end(); ++PropagateItr) {200 MCInst &PropagateInst = *PropagateItr;201 if (regIsUsed(PropagateInst, Reg, BC)) {202 bool Replaced = false;203 // If both registers are active for copy propagation or the register204 // to replace is active for constant propagation205 if (RegsActive) {206 // Set Replaced and so ReplacedEverwhere to false if it cannot be207 // replaced (no replacing that opcode, Register is src and dest)208 if (ConstantProp)209 Replaced = BC.MIB->replaceRegWithImm(210 PropagateInst, Reg, OriginalInst.getOperand(1).getImm());211 else212 Replaced = BC.MIB->replaceRegWithReg(213 PropagateInst, Reg, OriginalInst.getOperand(1).getReg());214 }215 ReplacedEverywhere = ReplacedEverywhere && Replaced;216 }217 // For copy propagation, make sure no propagation happens after the218 // register to replace with is overwritten219 if (!ConstantProp &&220 regIsPossiblyOverwritten(PropagateInst,221 OriginalInst.getOperand(1).getReg(), BC))222 RegsActive = false;223 224 // Make sure no propagation happens after the register to replace is225 // overwritten226 if (regIsPossiblyOverwritten(PropagateInst, Reg, BC))227 RegsActive = false;228 229 // Record if the register to replace is overwritten230 if (regIsDefinitelyOverwritten(PropagateInst, Reg, BC)) {231 Overwritten = true;232 break;233 }234 }235 if (Overwritten)236 break;237 }238 239 // If the register was replaced everywhere and it was overwritten in either240 // one of the iterated through blocks or one of the successor blocks, delete241 // the original move instruction242 if (ReplacedEverywhere &&243 (Overwritten ||244 isOverwrittenBeforeUsed(245 *BlocksToPropagate[BlocksToPropagate.size() - 1], Reg))) {246 // If both registers are active for copy propagation or the register247 // to replace is active for constant propagation248 StaticInstructionDeletionCount++;249 DynamicInstructionDeletionCount += OriginalBB.getExecutionCount();250 Itr = std::prev(OriginalBB.eraseInstruction(Itr));251 }252 }253}254 255bool TailDuplication::isInCacheLine(const BinaryBasicBlock &BB,256 const BinaryBasicBlock &Succ) const {257 if (&BB == &Succ)258 return true;259 260 uint64_t Distance = 0;261 int Direction = (Succ.getLayoutIndex() > BB.getLayoutIndex()) ? 1 : -1;262 263 for (unsigned I = BB.getLayoutIndex() + Direction; I != Succ.getLayoutIndex();264 I += Direction) {265 Distance += BB.getFunction()->getLayout().getBlock(I)->getOriginalSize();266 if (Distance > opts::TailDuplicationMinimumOffset)267 return false;268 }269 return true;270}271 272std::vector<BinaryBasicBlock *>273TailDuplication::moderateDuplicate(BinaryBasicBlock &BB,274 BinaryBasicBlock &Tail) const {275 std::vector<BinaryBasicBlock *> BlocksToDuplicate;276 // The block must be hot277 if (BB.getKnownExecutionCount() == 0)278 return BlocksToDuplicate;279 // and its successor is not already in the same cache line280 if (isInCacheLine(BB, Tail))281 return BlocksToDuplicate;282 // and its size do not exceed the maximum allowed size283 if (Tail.getOriginalSize() > opts::TailDuplicationMaximumDuplication)284 return BlocksToDuplicate;285 // If duplicating would introduce a new branch, don't duplicate286 for (auto Itr = Tail.succ_begin(); Itr != Tail.succ_end(); ++Itr) {287 if ((*Itr)->getLayoutIndex() == Tail.getLayoutIndex() + 1)288 return BlocksToDuplicate;289 }290 291 BlocksToDuplicate.push_back(&Tail);292 return BlocksToDuplicate;293}294 295std::vector<BinaryBasicBlock *>296TailDuplication::aggressiveDuplicate(BinaryBasicBlock &BB,297 BinaryBasicBlock &Tail) const {298 std::vector<BinaryBasicBlock *> BlocksToDuplicate;299 // The block must be hot300 if (BB.getKnownExecutionCount() == 0)301 return BlocksToDuplicate;302 // and its successor is not already in the same cache line303 if (isInCacheLine(BB, Tail))304 return BlocksToDuplicate;305 306 BinaryBasicBlock *CurrBB = &Tail;307 while (CurrBB) {308 LLVM_DEBUG(dbgs() << "Aggressive tail duplication: adding "309 << CurrBB->getName() << " to duplication list\n";);310 BlocksToDuplicate.push_back(CurrBB);311 312 if (CurrBB->hasJumpTable()) {313 LLVM_DEBUG(dbgs() << "Aggressive tail duplication: clearing duplication "314 "list due to a JT in "315 << CurrBB->getName() << '\n';);316 BlocksToDuplicate.clear();317 break;318 }319 320 // With no successors, we've reached the end and should duplicate all of321 // BlocksToDuplicate322 if (CurrBB->succ_size() == 0)323 break;324 325 // With two successors, if they're both a jump, we should duplicate all326 // blocks in BlocksToDuplicate. Otherwise, we cannot find a simple stream of327 // blocks to copy328 if (CurrBB->succ_size() >= 2) {329 if (CurrBB->getConditionalSuccessor(false)->getLayoutIndex() ==330 CurrBB->getLayoutIndex() + 1 ||331 CurrBB->getConditionalSuccessor(true)->getLayoutIndex() ==332 CurrBB->getLayoutIndex() + 1) {333 LLVM_DEBUG(dbgs() << "Aggressive tail duplication: clearing "334 "duplication list, can't find a simple stream at "335 << CurrBB->getName() << '\n';);336 BlocksToDuplicate.clear();337 }338 break;339 }340 341 // With one successor, if its a jump, we should duplicate all blocks in342 // BlocksToDuplicate. Otherwise, we should keep going343 BinaryBasicBlock *SuccBB = CurrBB->getSuccessor();344 if (SuccBB->getLayoutIndex() != CurrBB->getLayoutIndex() + 1)345 break;346 CurrBB = SuccBB;347 }348 // Don't duplicate if its too much code349 unsigned DuplicationByteCount = std::accumulate(350 std::begin(BlocksToDuplicate), std::end(BlocksToDuplicate), 0,351 [](int value, BinaryBasicBlock *p) {352 return value + p->getOriginalSize();353 });354 if (DuplicationByteCount > opts::TailDuplicationMaximumDuplication) {355 LLVM_DEBUG(dbgs() << "Aggressive tail duplication: duplication byte count ("356 << DuplicationByteCount << ") exceeds maximum "357 << opts::TailDuplicationMaximumDuplication << '\n';);358 BlocksToDuplicate.clear();359 }360 LLVM_DEBUG(dbgs() << "Aggressive tail duplication: found "361 << BlocksToDuplicate.size() << " blocks to duplicate\n";);362 return BlocksToDuplicate;363}364 365bool TailDuplication::shouldDuplicate(BinaryBasicBlock *Pred,366 BinaryBasicBlock *Tail) const {367 if (Pred == Tail)368 return false;369 // Cannot duplicate non-tail blocks370 if (Tail->succ_size() != 0)371 return false;372 // The blocks are already in the order373 if (Pred->getLayoutIndex() + 1 == Tail->getLayoutIndex())374 return false;375 // No tail duplication for blocks with jump tables376 if (Pred->hasJumpTable())377 return false;378 if (Tail->hasJumpTable())379 return false;380 381 return true;382}383 384double TailDuplication::cacheScore(uint64_t SrcAddr, uint64_t SrcSize,385 uint64_t DstAddr, uint64_t DstSize,386 uint64_t Count) const {387 assert(Count != BinaryBasicBlock::COUNT_NO_PROFILE);388 389 bool IsForwardJump = SrcAddr <= DstAddr;390 uint64_t JumpDistance = 0;391 // Computing the length of the jump so that it takes the sizes of the two392 // blocks into consideration393 if (IsForwardJump) {394 JumpDistance = (DstAddr + DstSize) - (SrcAddr);395 } else {396 JumpDistance = (SrcAddr + SrcSize) - (DstAddr);397 }398 399 if (JumpDistance >= opts::TailDuplicationMaxCacheDistance)400 return 0;401 double Prob = 1.0 - static_cast<double>(JumpDistance) /402 opts::TailDuplicationMaxCacheDistance;403 return (IsForwardJump ? 1.0 : opts::TailDuplicationCacheBackwardWeight) *404 Prob * Count;405}406 407bool TailDuplication::cacheScoreImproved(const MCCodeEmitter *Emitter,408 BinaryFunction &BF,409 BinaryBasicBlock *Pred,410 BinaryBasicBlock *Tail) const {411 // Collect (estimated) basic block sizes412 DenseMap<const BinaryBasicBlock *, uint64_t> BBSize;413 for (const BinaryBasicBlock &BB : BF) {414 BBSize[&BB] = std::max<uint64_t>(BB.estimateSize(Emitter), 1);415 }416 417 // Build current addresses of basic blocks starting at the entry block418 DenseMap<BinaryBasicBlock *, uint64_t> CurAddr;419 uint64_t Addr = 0;420 for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {421 CurAddr[SrcBB] = Addr;422 Addr += BBSize[SrcBB];423 }424 425 // Build new addresses (after duplication) starting at the entry block426 DenseMap<BinaryBasicBlock *, uint64_t> NewAddr;427 Addr = 0;428 for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {429 NewAddr[SrcBB] = Addr;430 Addr += BBSize[SrcBB];431 if (SrcBB == Pred)432 Addr += BBSize[Tail];433 }434 435 // Compute the cache score for the existing layout of basic blocks436 double CurScore = 0;437 for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {438 auto BI = SrcBB->branch_info_begin();439 for (BinaryBasicBlock *DstBB : SrcBB->successors()) {440 if (SrcBB != DstBB) {441 CurScore += cacheScore(CurAddr[SrcBB], BBSize[SrcBB], CurAddr[DstBB],442 BBSize[DstBB], BI->Count);443 }444 ++BI;445 }446 }447 448 // Compute the cache score for the layout of blocks after tail duplication449 double NewScore = 0;450 for (BinaryBasicBlock *SrcBB : BF.getLayout().blocks()) {451 auto BI = SrcBB->branch_info_begin();452 for (BinaryBasicBlock *DstBB : SrcBB->successors()) {453 if (SrcBB != DstBB) {454 if (SrcBB == Pred && DstBB == Tail) {455 NewScore += cacheScore(NewAddr[SrcBB], BBSize[SrcBB],456 NewAddr[SrcBB] + BBSize[SrcBB], BBSize[DstBB],457 BI->Count);458 } else {459 NewScore += cacheScore(NewAddr[SrcBB], BBSize[SrcBB], NewAddr[DstBB],460 BBSize[DstBB], BI->Count);461 }462 }463 ++BI;464 }465 }466 467 return NewScore > CurScore;468}469 470std::vector<BinaryBasicBlock *>471TailDuplication::cacheDuplicate(const MCCodeEmitter *Emitter,472 BinaryFunction &BF, BinaryBasicBlock *Pred,473 BinaryBasicBlock *Tail) const {474 std::vector<BinaryBasicBlock *> BlocksToDuplicate;475 476 // No need to duplicate cold basic blocks477 if (Pred->isCold() || Tail->isCold()) {478 return BlocksToDuplicate;479 }480 // Always duplicate "small" tail basic blocks, which might be beneficial for481 // code size, since a jump instruction is eliminated482 if (Tail->estimateSize(Emitter) <= opts::TailDuplicationMinimumDuplication) {483 BlocksToDuplicate.push_back(Tail);484 return BlocksToDuplicate;485 }486 // Never duplicate "large" tail basic blocks487 if (Tail->estimateSize(Emitter) > opts::TailDuplicationMaximumDuplication) {488 return BlocksToDuplicate;489 }490 // Do not append basic blocks after the last hot block in the current layout491 auto NextBlock = BF.getLayout().getBasicBlockAfter(Pred);492 if (NextBlock == nullptr || (!Pred->isCold() && NextBlock->isCold())) {493 return BlocksToDuplicate;494 }495 496 // Duplicate the tail only if it improves the cache score497 if (cacheScoreImproved(Emitter, BF, Pred, Tail)) {498 BlocksToDuplicate.push_back(Tail);499 }500 501 return BlocksToDuplicate;502}503 504std::vector<BinaryBasicBlock *> TailDuplication::duplicateBlocks(505 BinaryBasicBlock &BB,506 const std::vector<BinaryBasicBlock *> &BlocksToDuplicate) const {507 BinaryFunction *BF = BB.getFunction();508 BinaryContext &BC = BF->getBinaryContext();509 510 // Ratio of this new branches execution count to the total size of the511 // successor's execution count. Used to set this new branches execution count512 // and lower the old successor's execution count513 double ExecutionCountRatio =514 BB.getExecutionCount() >= BB.getSuccessor()->getExecutionCount()515 ? 1.0516 : (double)BB.getExecutionCount() /517 BB.getSuccessor()->getExecutionCount();518 519 // Use the last branch info when adding a successor to LastBB520 BinaryBasicBlock::BinaryBranchInfo &LastBI =521 BB.getBranchInfo(*(BB.getSuccessor()));522 523 BinaryBasicBlock *LastOriginalBB = &BB;524 BinaryBasicBlock *LastDuplicatedBB = &BB;525 assert(LastDuplicatedBB->succ_size() == 1 &&526 "tail duplication cannot act on a block with more than 1 successor");527 LastDuplicatedBB->removeSuccessor(LastDuplicatedBB->getSuccessor());528 529 std::vector<std::unique_ptr<BinaryBasicBlock>> DuplicatedBlocks;530 std::vector<BinaryBasicBlock *> DuplicatedBlocksToReturn;531 532 for (BinaryBasicBlock *CurBB : BlocksToDuplicate) {533 DuplicatedBlocks.emplace_back(534 BF->createBasicBlock((BC.Ctx)->createNamedTempSymbol("tail-dup")));535 BinaryBasicBlock *NewBB = DuplicatedBlocks.back().get();536 537 NewBB->addInstructions(CurBB->begin(), CurBB->end());538 // Set execution count as if it was just a copy of the original539 NewBB->setExecutionCount(CurBB->getExecutionCount());540 NewBB->setIsCold(CurBB->isCold());541 LastDuplicatedBB->addSuccessor(NewBB, LastBI);542 543 DuplicatedBlocksToReturn.push_back(NewBB);544 545 // As long as its not the first block, adjust both original and duplicated546 // to what they should be547 if (LastDuplicatedBB != &BB) {548 LastOriginalBB->adjustExecutionCount(1.0 - ExecutionCountRatio);549 LastDuplicatedBB->adjustExecutionCount(ExecutionCountRatio);550 }551 552 if (CurBB->succ_size() == 1)553 LastBI = CurBB->getBranchInfo(*(CurBB->getSuccessor()));554 555 LastOriginalBB = CurBB;556 LastDuplicatedBB = NewBB;557 }558 559 LastDuplicatedBB->addSuccessors(560 LastOriginalBB->succ_begin(), LastOriginalBB->succ_end(),561 LastOriginalBB->branch_info_begin(), LastOriginalBB->branch_info_end());562 563 LastOriginalBB->adjustExecutionCount(1.0 - ExecutionCountRatio);564 LastDuplicatedBB->adjustExecutionCount(ExecutionCountRatio);565 566 BF->insertBasicBlocks(&BB, std::move(DuplicatedBlocks));567 568 return DuplicatedBlocksToReturn;569}570 571void TailDuplication::runOnFunction(BinaryFunction &Function) {572 // Create a separate MCCodeEmitter to allow lock-free execution573 BinaryContext::IndependentCodeEmitter Emitter;574 if (!opts::NoThreads) {575 Emitter = Function.getBinaryContext().createIndependentMCCodeEmitter();576 }577 578 Function.getLayout().updateLayoutIndices();579 580 // New blocks will be added and layout will change,581 // so make a copy here to iterate over the original layout582 BinaryFunction::BasicBlockOrderType BlockLayout(583 Function.getLayout().block_begin(), Function.getLayout().block_end());584 bool ModifiedFunction = false;585 for (BinaryBasicBlock *BB : BlockLayout) {586 AllDynamicCount += BB->getKnownExecutionCount();587 588 // The block must be with one successor589 if (BB->succ_size() != 1)590 continue;591 BinaryBasicBlock *Tail = BB->getSuccessor();592 // Verify that the tail should be duplicated593 if (!shouldDuplicate(BB, Tail))594 continue;595 596 std::vector<BinaryBasicBlock *> BlocksToDuplicate;597 if (opts::TailDuplicationMode == TailDuplication::TD_AGGRESSIVE) {598 BlocksToDuplicate = aggressiveDuplicate(*BB, *Tail);599 } else if (opts::TailDuplicationMode == TailDuplication::TD_MODERATE) {600 BlocksToDuplicate = moderateDuplicate(*BB, *Tail);601 } else if (opts::TailDuplicationMode == TailDuplication::TD_CACHE) {602 BlocksToDuplicate = cacheDuplicate(Emitter.MCE.get(), Function, BB, Tail);603 } else {604 llvm_unreachable("unknown tail duplication mode");605 }606 607 if (BlocksToDuplicate.empty())608 continue;609 610 // Apply the duplication611 ModifiedFunction = true;612 DuplicationsDynamicCount += BB->getExecutionCount();613 auto DuplicatedBlocks = duplicateBlocks(*BB, BlocksToDuplicate);614 for (BinaryBasicBlock *BB : DuplicatedBlocks) {615 DuplicatedBlockCount++;616 DuplicatedByteCount += BB->estimateSize(Emitter.MCE.get());617 }618 619 if (opts::TailDuplicationConstCopyPropagation) {620 constantAndCopyPropagate(*BB, DuplicatedBlocks);621 BinaryBasicBlock *FirstBB = BlocksToDuplicate[0];622 if (FirstBB->pred_size() == 1) {623 BinaryBasicBlock *PredBB = *FirstBB->pred_begin();624 if (PredBB->succ_size() == 1)625 constantAndCopyPropagate(*PredBB, BlocksToDuplicate);626 }627 }628 629 // Layout indices might be stale after duplication630 Function.getLayout().updateLayoutIndices();631 }632 if (ModifiedFunction)633 ModifiedFunctions++;634}635 636Error TailDuplication::runOnFunctions(BinaryContext &BC) {637 if (opts::TailDuplicationMode == TailDuplication::TD_NONE)638 return Error::success();639 640 for (auto &It : BC.getBinaryFunctions()) {641 BinaryFunction &Function = It.second;642 if (!shouldOptimize(Function))643 continue;644 runOnFunction(Function);645 }646 647 BC.outs()648 << "BOLT-INFO: tail duplication"649 << format(" modified %zu (%.2f%%) functions;", ModifiedFunctions,650 100.0 * ModifiedFunctions / BC.getBinaryFunctions().size())651 << format(" duplicated %zu blocks (%zu bytes) responsible for",652 DuplicatedBlockCount, DuplicatedByteCount)653 << format(" %zu dynamic executions (%.2f%% of all block executions)",654 DuplicationsDynamicCount,655 100.0 * DuplicationsDynamicCount / AllDynamicCount)656 << "\n";657 658 if (opts::TailDuplicationConstCopyPropagation) {659 BC.outs() << "BOLT-INFO: tail duplication "660 << format(661 "applied %zu static and %zu dynamic propagation deletions",662 StaticInstructionDeletionCount,663 DynamicInstructionDeletionCount)664 << "\n";665 }666 return Error::success();667}668 669} // end namespace bolt670} // end namespace llvm671