263 lines · cpp
1//===-- BasicBlockPathCloning.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/// \file10/// BasicBlockPathCloning implementation.11///12/// The purpose of this pass is to clone basic block paths based on information13/// provided by the -fbasic-block-sections=list option.14/// Please refer to BasicBlockSectionsProfileReader.cpp to see a path cloning15/// example.16//===----------------------------------------------------------------------===//17// This pass clones the machine basic blocks alongs the given paths and sets up18// the CFG. It assigns BBIDs to the cloned blocks so that the19// `BasicBlockSections` pass can correctly map the cluster information to the20// blocks. The cloned block's BBID will have the same BaseID as the original21// block, but will get a unique non-zero CloneID (original blocks all have zero22// CloneIDs). This pass applies a path cloning if it satisfies the following23// conditions:24// 1. All BBIDs in the path should be mapped to existing blocks.25// 2. Each two consecutive BBIDs in the path must have a successor26// relationship in the CFG.27// 3. The path should not include a block with indirect branches, except for28// the last block.29// If a path does not satisfy all three conditions, it will be rejected, but the30// CloneIDs for its (supposed to be cloned) blocks will be bypassed to make sure31// that the `BasicBlockSections` pass can map cluster info correctly to the32// actually-cloned blocks.33//===----------------------------------------------------------------------===//34 35#include "llvm/ADT/SmallVector.h"36#include "llvm/ADT/StringRef.h"37#include "llvm/CodeGen/BasicBlockSectionUtils.h"38#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"39#include "llvm/CodeGen/MachineFunction.h"40#include "llvm/CodeGen/MachineFunctionPass.h"41#include "llvm/CodeGen/Passes.h"42#include "llvm/CodeGen/TargetInstrInfo.h"43#include "llvm/InitializePasses.h"44#include "llvm/Support/UniqueBBID.h"45#include "llvm/Support/WithColor.h"46#include "llvm/Target/TargetMachine.h"47 48using namespace llvm;49 50namespace {51 52// Clones the given block and assigns the given `CloneID` to its BBID. Copies53// the instructions into the new block and sets up its successors.54MachineBasicBlock *CloneMachineBasicBlock(MachineBasicBlock &OrigBB,55 unsigned CloneID) {56 auto &MF = *OrigBB.getParent();57 auto TII = MF.getSubtarget().getInstrInfo();58 // Create the clone block and set its BBID based on the original block.59 MachineBasicBlock *CloneBB = MF.CreateMachineBasicBlock(60 OrigBB.getBasicBlock(), UniqueBBID{OrigBB.getBBID()->BaseID, CloneID});61 MF.push_back(CloneBB);62 63 // Copy the instructions.64 for (auto &I : OrigBB.instrs()) {65 // Bundled instructions are duplicated together.66 if (I.isBundledWithPred())67 continue;68 TII->duplicate(*CloneBB, CloneBB->end(), I);69 }70 71 // Add the successors of the original block as the new block's successors.72 // We set the predecessor after returning from this call.73 for (auto SI = OrigBB.succ_begin(), SE = OrigBB.succ_end(); SI != SE; ++SI)74 CloneBB->copySuccessor(&OrigBB, SI);75 76 if (auto FT = OrigBB.getFallThrough(/*JumpToFallThrough=*/false)) {77 // The original block has an implicit fall through.78 // Insert an explicit unconditional jump from the cloned block to the79 // fallthrough block. Technically, this is only needed for the last block80 // of the path, but we do it for all clones for consistency.81 TII->insertUnconditionalBranch(*CloneBB, FT, CloneBB->findBranchDebugLoc());82 }83 return CloneBB;84}85 86// Returns if we can legally apply the cloning represented by `ClonePath`.87// `BBIDToBlock` contains the original basic blocks in function `MF` keyed by88// their `BBID::BaseID`.89bool IsValidCloning(const MachineFunction &MF,90 const DenseMap<unsigned, MachineBasicBlock *> &BBIDToBlock,91 const SmallVector<unsigned> &ClonePath) {92 const MachineBasicBlock *PrevBB = nullptr;93 for (size_t I = 0; I < ClonePath.size(); ++I) {94 unsigned BBID = ClonePath[I];95 const MachineBasicBlock *PathBB = BBIDToBlock.lookup(BBID);96 if (!PathBB) {97 WithColor::warning() << "no block with id " << BBID << " in function "98 << MF.getName() << "\n";99 return false;100 }101 102 if (PrevBB) {103 if (!PrevBB->isSuccessor(PathBB)) {104 WithColor::warning()105 << "block #" << BBID << " is not a successor of block #"106 << PrevBB->getBBID()->BaseID << " in function " << MF.getName()107 << "\n";108 return false;109 }110 111 for (auto &MI : *PathBB) {112 // Avoid cloning when the block contains non-duplicable instructions.113 // CFI instructions are marked as non-duplicable only because of Darwin,114 // so we exclude them from this check.115 if (MI.isNotDuplicable() && !MI.isCFIInstruction()) {116 WithColor::warning()117 << "block #" << BBID118 << " has non-duplicable instructions in function " << MF.getName()119 << "\n";120 return false;121 }122 }123 if (PathBB->isMachineBlockAddressTaken()) {124 // Avoid cloning blocks which have their address taken since we can't125 // rewire branches to those blocks as easily.126 WithColor::warning()127 << "block #" << BBID128 << " has its machine block address taken in function "129 << MF.getName() << "\n";130 return false;131 }132 if (PathBB->isInlineAsmBrIndirectTarget()) {133 // Similarly for branches to the block within an asm goto.134 WithColor::warning()135 << "block #" << BBID136 << " is a branch target of an 'asm goto' in function "137 << MF.getName() << "\n";138 return false;139 }140 }141 142 if (I != ClonePath.size() - 1 && !PathBB->empty() &&143 PathBB->back().isIndirectBranch()) {144 WithColor::warning()145 << "block #" << BBID146 << " has indirect branch and appears as the non-tail block of a "147 "path in function "148 << MF.getName() << "\n";149 return false;150 }151 PrevBB = PathBB;152 }153 return true;154}155 156// Applies all clonings specified in `ClonePaths` to `MF`. Returns true157// if any clonings have been applied.158bool ApplyCloning(MachineFunction &MF,159 const SmallVector<SmallVector<unsigned>> &ClonePaths) {160 if (ClonePaths.empty())161 return false;162 bool AnyPathsCloned = false;163 // Map from the final BB IDs to the `MachineBasicBlock`s.164 DenseMap<unsigned, MachineBasicBlock *> BBIDToBlock;165 for (auto &BB : MF)166 BBIDToBlock.try_emplace(BB.getBBID()->BaseID, &BB);167 168 DenseMap<unsigned, unsigned> NClonesForBBID;169 auto TII = MF.getSubtarget().getInstrInfo();170 for (const auto &ClonePath : ClonePaths) {171 if (!IsValidCloning(MF, BBIDToBlock, ClonePath)) {172 // We still need to increment the number of clones so we can map173 // to the cluster info correctly.174 for (unsigned BBID : ClonePath)175 ++NClonesForBBID[BBID];176 continue;177 }178 MachineBasicBlock *PrevBB = nullptr;179 for (unsigned BBID : ClonePath) {180 MachineBasicBlock *OrigBB = BBIDToBlock.at(BBID);181 if (PrevBB == nullptr) {182 // The first block in the path is not cloned. We only need to make it183 // branch to the next cloned block in the path. Here, we make its184 // fallthrough explicit so we can change it later.185 if (auto FT = OrigBB->getFallThrough(/*JumpToFallThrough=*/false)) {186 TII->insertUnconditionalBranch(*OrigBB, FT,187 OrigBB->findBranchDebugLoc());188 }189 PrevBB = OrigBB;190 continue;191 }192 MachineBasicBlock *CloneBB =193 CloneMachineBasicBlock(*OrigBB, ++NClonesForBBID[BBID]);194 195 // Set up the previous block in the path to jump to the clone. This also196 // transfers the successor/predecessor relationship of PrevBB and OrigBB197 // to that of PrevBB and CloneBB.198 PrevBB->ReplaceUsesOfBlockWith(OrigBB, CloneBB);199 200 // Copy the livein set.201 for (auto &LiveIn : OrigBB->liveins())202 CloneBB->addLiveIn(LiveIn);203 204 PrevBB = CloneBB;205 }206 AnyPathsCloned = true;207 }208 return AnyPathsCloned;209}210 211class BasicBlockPathCloning : public MachineFunctionPass {212public:213 static char ID;214 215 BasicBlockSectionsProfileReaderWrapperPass *BBSectionsProfileReader = nullptr;216 217 BasicBlockPathCloning() : MachineFunctionPass(ID) {218 initializeBasicBlockPathCloningPass(*PassRegistry::getPassRegistry());219 }220 221 StringRef getPassName() const override { return "Basic Block Path Cloning"; }222 223 void getAnalysisUsage(AnalysisUsage &AU) const override;224 225 /// Identify basic blocks that need separate sections and prepare to emit them226 /// accordingly.227 bool runOnMachineFunction(MachineFunction &MF) override;228};229 230} // namespace231 232char BasicBlockPathCloning::ID = 0;233INITIALIZE_PASS_BEGIN(234 BasicBlockPathCloning, "bb-path-cloning",235 "Applies path clonings for the -basic-block-sections=list option", false,236 false)237INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)238INITIALIZE_PASS_END(239 BasicBlockPathCloning, "bb-path-cloning",240 "Applies path clonings for the -basic-block-sections=list option", false,241 false)242 243bool BasicBlockPathCloning::runOnMachineFunction(MachineFunction &MF) {244 assert(MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&245 "BB Sections list not enabled!");246 if (hasInstrProfHashMismatch(MF))247 return false;248 249 return ApplyCloning(MF,250 getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()251 .getClonePathsForFunction(MF.getName()));252}253 254void BasicBlockPathCloning::getAnalysisUsage(AnalysisUsage &AU) const {255 AU.setPreservesAll();256 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();257 MachineFunctionPass::getAnalysisUsage(AU);258}259 260MachineFunctionPass *llvm::createBasicBlockPathCloningPass() {261 return new BasicBlockPathCloning();262}263