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