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     }
 123
 124     if (I != ClonePath.size() - 1 && !PathBB->empty() &&
 125         PathBB->back().isIndirectBranch()) {
 126       WithColor::warning()
 127           << "block #" << BBID
 128           << " has indirect branch and appears as the non-tail block of a "
 129              "path in function "
 130           << MF.getName() << "\n";
 131       return false;
 132     }
 133     PrevBB = PathBB;
 134   }
 135   return true;
 136 }
 137
 138 // Applies all clonings specified in `ClonePaths` to `MF`. Returns true
 139 // if any clonings have been applied.
 140 bool ApplyCloning(MachineFunction &MF,
 141                   const SmallVector<SmallVector<unsigned>> &ClonePaths) {
 142   if (ClonePaths.empty())
 143     return false;
 144   bool AnyPathsCloned = false;
 145   // Map from the final BB IDs to the `MachineBasicBlock`s.
 146   DenseMap<unsigned, MachineBasicBlock *> BBIDToBlock;
 147   for (auto &BB : MF)
 148     BBIDToBlock.try_emplace(BB.getBBID()->BaseID, &BB);
 149
 150   DenseMap<unsigned, unsigned> NClonesForBBID;
 151   auto TII = MF.getSubtarget().getInstrInfo();
 152   for (const auto &ClonePath : ClonePaths) {
 153     if (!IsValidCloning(MF, BBIDToBlock, ClonePath)) {
 154       // We still need to increment the number of clones so we can map
 155       // to the cluster info correctly.
 156       for (unsigned BBID : ClonePath)
 157         ++NClonesForBBID[BBID];
 158       continue;
 159     }
 160     MachineBasicBlock *PrevBB = nullptr;
 161     for (unsigned BBID : ClonePath) {
 162       MachineBasicBlock *OrigBB = BBIDToBlock.at(BBID);
 163       if (PrevBB == nullptr) {
 164         // The first block in the path is not cloned. We only need to make it
 165         // branch to the next cloned block in the path. Here, we make its
 166         // fallthrough explicit so we can change it later.
 167         if (auto FT = OrigBB->getFallThrough(/*JumpToFallThrough=*/false)) {
 168           TII->insertUnconditionalBranch(*OrigBB, FT,
 169                                          OrigBB->findBranchDebugLoc());
 170         }
 171         PrevBB = OrigBB;
 172         continue;
 173       }
 174       MachineBasicBlock *CloneBB =
 175           CloneMachineBasicBlock(*OrigBB, ++NClonesForBBID[BBID]);
 176
 177       // Set up the previous block in the path to jump to the clone. This also
 178       // transfers the successor/predecessor relationship of PrevBB and OrigBB
 179       // to that of PrevBB and CloneBB.
 180       PrevBB->ReplaceUsesOfBlockWith(OrigBB, CloneBB);
 181
 182       // Copy the livein set.
 183       for (auto &LiveIn : OrigBB->liveins())
 184         CloneBB->addLiveIn(LiveIn);
 185
 186       PrevBB = CloneBB;
 187     }
 188     AnyPathsCloned = true;
 189   }
 190   return AnyPathsCloned;
 191 }
 192 } // end anonymous namespace
 193
 194 namespace llvm {
 195 class BasicBlockPathCloning : public MachineFunctionPass {
 196 public:
 197   static char ID;
 198
 199   BasicBlockSectionsProfileReaderWrapperPass *BBSectionsProfileReader = nullptr;
 200
 201   BasicBlockPathCloning() : MachineFunctionPass(ID) {
 202     initializeBasicBlockPathCloningPass(*PassRegistry::getPassRegistry());
 203   }
 204
 205   StringRef getPassName() const override { return "Basic Block Path Cloning"; }
 206
 207   void getAnalysisUsage(AnalysisUsage &AU) const override;
 208
 209   /// Identify basic blocks that need separate sections and prepare to emit them
 210   /// accordingly.
 211   bool runOnMachineFunction(MachineFunction &MF) override;
 212 };
 213
 214 } // namespace llvm
 215
 216 char BasicBlockPathCloning::ID = 0;
 217 INITIALIZE_PASS_BEGIN(
 218     BasicBlockPathCloning, "bb-path-cloning",
 219     "Applies path clonings for the -basic-block-sections=list option", false,
 220     false)
 221 INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
 222 INITIALIZE_PASS_END(
 223     BasicBlockPathCloning, "bb-path-cloning",
 224     "Applies path clonings for the -basic-block-sections=list option", false,
 225     false)
 226
 227 bool BasicBlockPathCloning::runOnMachineFunction(MachineFunction &MF) {
 228   assert(MF.getTarget().getBBSectionsType() == BasicBlockSection::List &&
 229          "BB Sections list not enabled!");
 230   if (hasInstrProfHashMismatch(MF))
 231     return false;
 232
 233   return ApplyCloning(MF,
 234                       getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>()
 235                           .getClonePathsForFunction(MF.getName()));
 236 }
 237
 238 void BasicBlockPathCloning::getAnalysisUsage(AnalysisUsage &AU) const {
 239   AU.setPreservesAll();
 240   AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
 241   MachineFunctionPass::getAnalysisUsage(AU);
 242 }
 243
 244 MachineFunctionPass *llvm::createBasicBlockPathCloningPass() {
 245   return new BasicBlockPathCloning();
 246 }