lib/CodeGen/MachineBlockPlacement.cpp

   1 //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements basic block placement transformations using the CFG
  11 // structure and branch probability estimates.
  12 //
  13 // The pass strives to preserve the structure of the CFG (that is, retain
  14 // a topological ordering of basic blocks) in the absense of a *strong* signal
  15 // to the contrary from probabilities. However, within the CFG structure, it
  16 // attempts to choose an ordering which favors placing more likely sequences of
  17 // blocks adjacent to each other.
  18 //
  19 // The algorithm works from the inner-most loop within a function outward, and
  20 // at each stage walks through the basic blocks, trying to coalesce them into
  21 // sequential chains where allowed by the CFG (or demanded by heavy
  22 // probabilities). Finally, it walks the blocks in topological order, and the
  23 // first time it reaches a chain of basic blocks, it schedules them in the
  24 // function in-order.
  25 //
  26 //===----------------------------------------------------------------------===//
  27
  28 #define DEBUG_TYPE "block-placement2"
  29 #include "llvm/CodeGen/MachineBasicBlock.h"
  30 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  31 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  32 #include "llvm/CodeGen/MachineFunction.h"
  33 #include "llvm/CodeGen/MachineFunctionPass.h"
  34 #include "llvm/CodeGen/MachineLoopInfo.h"
  35 #include "llvm/CodeGen/MachineModuleInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Support/Allocator.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/ADT/DenseMap.h"
  41 #include "llvm/ADT/PostOrderIterator.h"
  42 #include "llvm/ADT/SCCIterator.h"
  43 #include "llvm/ADT/SmallPtrSet.h"
  44 #include "llvm/ADT/SmallVector.h"
  45 #include "llvm/ADT/Statistic.h"
  46 #include "llvm/Target/TargetInstrInfo.h"
  47 #include "llvm/Target/TargetLowering.h"
  48 #include <algorithm>
  49 using namespace llvm;
  50
  51 namespace {
  52 /// \brief A structure for storing a weighted edge.
  53 ///
  54 /// This stores an edge and its weight, computed as the product of the
  55 /// frequency that the starting block is entered with the probability of
  56 /// a particular exit block.
  57 struct WeightedEdge {
  58   BlockFrequency EdgeFrequency;
  59   MachineBasicBlock *From, *To;
  60
  61   bool operator<(const WeightedEdge &RHS) const {
  62     return EdgeFrequency < RHS.EdgeFrequency;
  63   }
  64 };
  65 }
  66
  67 namespace {
  68 class BlockChain;
  69 /// \brief Type for our function-wide basic block -> block chain mapping.
  70 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
  71 }
  72
  73 namespace {
  74 /// \brief A chain of blocks which will be laid out contiguously.
  75 ///
  76 /// This is the datastructure representing a chain of consecutive blocks that
  77 /// are profitable to layout together in order to maximize fallthrough
  78 /// probabilities. We also can use a block chain to represent a sequence of
  79 /// basic blocks which have some external (correctness) requirement for
  80 /// sequential layout.
  81 ///
  82 /// Eventually, the block chains will form a directed graph over the function.
  83 /// We provide an SCC-supporting-iterator in order to quicky build and walk the
  84 /// SCCs of block chains within a function.
  85 ///
  86 /// The block chains also have support for calculating and caching probability
  87 /// information related to the chain itself versus other chains. This is used
  88 /// for ranking during the final layout of block chains.
  89 class BlockChain {
  90   /// \brief The sequence of blocks belonging to this chain.
  91   ///
  92   /// This is the sequence of blocks for a particular chain. These will be laid
  93   /// out in-order within the function.
  94   SmallVector<MachineBasicBlock *, 4> Blocks;
  95
  96   /// \brief A handle to the function-wide basic block to block chain mapping.
  97   ///
  98   /// This is retained in each block chain to simplify the computation of child
  99   /// block chains for SCC-formation and iteration. We store the edges to child
 100   /// basic blocks, and map them back to their associated chains using this
 101   /// structure.
 102   BlockToChainMapType &BlockToChain;
 103
 104 public:
 105   /// \brief Construct a new BlockChain.
 106   ///
 107   /// This builds a new block chain representing a single basic block in the
 108   /// function. It also registers itself as the chain that block participates
 109   /// in with the BlockToChain mapping.
 110   BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
 111     : Blocks(1, BB), BlockToChain(BlockToChain) {
 112     assert(BB && "Cannot create a chain with a null basic block");
 113     BlockToChain[BB] = this;
 114   }
 115
 116   /// \brief Iterator over blocks within the chain.
 117   typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator iterator;
 118
 119   /// \brief Beginning of blocks within the chain.
 120   iterator begin() const { return Blocks.begin(); }
 121
 122   /// \brief End of blocks within the chain.
 123   iterator end() const { return Blocks.end(); }
 124
 125   /// \brief Merge a block chain into this one.
 126   ///
 127   /// This routine merges a block chain into this one. It takes care of forming
 128   /// a contiguous sequence of basic blocks, updating the edge list, and
 129   /// updating the block -> chain mapping. It does not free or tear down the
 130   /// old chain, but the old chain's block list is no longer valid.
 131   void merge(MachineBasicBlock *BB, BlockChain *Chain) {
 132     assert(BB);
 133     assert(!Blocks.empty());
 134     assert(Blocks.back()->isSuccessor(BB));
 135
 136     // Fast path in case we don't have a chain already.
 137     if (!Chain) {
 138       assert(!BlockToChain[BB]);
 139       Blocks.push_back(BB);
 140       BlockToChain[BB] = this;
 141       return;
 142     }
 143
 144     assert(BB == *Chain->begin());
 145     assert(Chain->begin() != Chain->end());
 146
 147     // Update the incoming blocks to point to this chain, and add them to the
 148     // chain structure.
 149     for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
 150          BI != BE; ++BI) {
 151       Blocks.push_back(*BI);
 152       assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
 153       BlockToChain[*BI] = this;
 154     }
 155   }
 156 };
 157 }
 158
 159 namespace {
 160 class MachineBlockPlacement : public MachineFunctionPass {
 161   /// \brief A typedef for a block filter set.
 162   typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
 163
 164   /// \brief A handle to the branch probability pass.
 165   const MachineBranchProbabilityInfo *MBPI;
 166
 167   /// \brief A handle to the function-wide block frequency pass.
 168   const MachineBlockFrequencyInfo *MBFI;
 169
 170   /// \brief A handle to the loop info.
 171   const MachineLoopInfo *MLI;
 172
 173   /// \brief A handle to the target's instruction info.
 174   const TargetInstrInfo *TII;
 175
 176   /// \brief A handle to the target's lowering info.
 177   const TargetLowering *TLI;
 178
 179   /// \brief Allocator and owner of BlockChain structures.
 180   ///
 181   /// We build BlockChains lazily by merging together high probability BB
 182   /// sequences acording to the "Algo2" in the paper mentioned at the top of
 183   /// the file. To reduce malloc traffic, we allocate them using this slab-like
 184   /// allocator, and destroy them after the pass completes.
 185   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
 186
 187   /// \brief Function wide BasicBlock to BlockChain mapping.
 188   ///
 189   /// This mapping allows efficiently moving from any given basic block to the
 190   /// BlockChain it participates in, if any. We use it to, among other things,
 191   /// allow implicitly defining edges between chains as the existing edges
 192   /// between basic blocks.
 193   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 194
 195   BlockChain *CreateChain(MachineBasicBlock *BB);
 196   void mergeSuccessor(MachineBasicBlock *BB, BlockChain *Chain,
 197                       BlockFilterSet *Filter = 0);
 198   void buildLoopChains(MachineFunction &F, MachineLoop &L);
 199   void buildCFGChains(MachineFunction &F);
 200   void placeChainsTopologically(MachineFunction &F);
 201   void AlignLoops(MachineFunction &F);
 202
 203 public:
 204   static char ID; // Pass identification, replacement for typeid
 205   MachineBlockPlacement() : MachineFunctionPass(ID) {
 206     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
 207   }
 208
 209   bool runOnMachineFunction(MachineFunction &F);
 210
 211   void getAnalysisUsage(AnalysisUsage &AU) const {
 212     AU.addRequired<MachineBranchProbabilityInfo>();
 213     AU.addRequired<MachineBlockFrequencyInfo>();
 214     AU.addRequired<MachineLoopInfo>();
 215     MachineFunctionPass::getAnalysisUsage(AU);
 216   }
 217
 218   const char *getPassName() const { return "Block Placement"; }
 219 };
 220 }
 221
 222 char MachineBlockPlacement::ID = 0;
 223 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
 224                       "Branch Probability Basic Block Placement", false, false)
 225 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 226 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 227 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 228 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
 229                     "Branch Probability Basic Block Placement", false, false)
 230
 231 FunctionPass *llvm::createMachineBlockPlacementPass() {
 232   return new MachineBlockPlacement();
 233 }
 234
 235 #ifndef NDEBUG
 236 /// \brief Helper to print the name of a MBB.
 237 ///
 238 /// Only used by debug logging.
 239 static std::string getBlockName(MachineBasicBlock *BB) {
 240   std::string Result;
 241   raw_string_ostream OS(Result);
 242   OS << "BB#" << BB->getNumber()
 243      << " (derived from LLVM BB '" << BB->getName() << "')";
 244   OS.flush();
 245   return Result;
 246 }
 247
 248 /// \brief Helper to print the number of a MBB.
 249 ///
 250 /// Only used by debug logging.
 251 static std::string getBlockNum(MachineBasicBlock *BB) {
 252   std::string Result;
 253   raw_string_ostream OS(Result);
 254   OS << "BB#" << BB->getNumber();
 255   OS.flush();
 256   return Result;
 257 }
 258 #endif
 259
 260 /// \brief Helper to create a new chain for a single BB.
 261 ///
 262 /// Takes care of growing the Chains, setting up the BlockChain object, and any
 263 /// debug checking logic.
 264 /// \returns A pointer to the new BlockChain.
 265 BlockChain *MachineBlockPlacement::CreateChain(MachineBasicBlock *BB) {
 266   BlockChain *Chain =
 267     new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
 268   return Chain;
 269 }
 270
 271 /// \brief Merge a chain with any viable successor.
 272 ///
 273 /// This routine walks the predecessors of the current block, looking for
 274 /// viable merge candidates. It has strict rules it uses to determine when
 275 /// a predecessor can be merged with the current block, which center around
 276 /// preserving the CFG structure. It performs the merge if any viable candidate
 277 /// is found.
 278 void MachineBlockPlacement::mergeSuccessor(MachineBasicBlock *BB,
 279                                            BlockChain *Chain,
 280                                            BlockFilterSet *Filter) {
 281   assert(BB);
 282   assert(Chain);
 283
 284   // If this block is not at the end of its chain, it cannot merge with any
 285   // other chain.
 286   if (Chain && *llvm::prior(Chain->end()) != BB)
 287     return;
 288
 289   // Walk through the successors looking for the highest probability edge.
 290   MachineBasicBlock *Successor = 0;
 291   BranchProbability BestProb = BranchProbability::getZero();
 292   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
 293   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 294                                         SE = BB->succ_end();
 295        SI != SE; ++SI) {
 296     if (BB == *SI || (Filter && !Filter->count(*SI)))
 297       continue;
 298
 299     BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI);
 300     DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> " << SuccProb << "\n");
 301     if (!Successor || SuccProb > BestProb || (!(SuccProb < BestProb) &&
 302                                               BB->isLayoutSuccessor(*SI))) {
 303       Successor = *SI;
 304       BestProb = SuccProb;
 305     }
 306   }
 307   if (!Successor)
 308     return;
 309
 310   // Grab a chain if it exists already for this successor and make sure the
 311   // successor is at the start of the chain as we can't merge mid-chain. Also,
 312   // if the successor chain is the same as our chain, we're already merged.
 313   BlockChain *SuccChain = BlockToChain[Successor];
 314   if (SuccChain && (SuccChain == Chain || Successor != *SuccChain->begin()))
 315     return;
 316
 317   // We only merge chains across a CFG merge when the desired merge path is
 318   // significantly hotter than the incoming edge. We define a hot edge more
 319   // strictly than the BranchProbabilityInfo does, as the two predecessor
 320   // blocks may have dramatically different incoming probabilities we need to
 321   // account for. Therefor we use the "global" edge weight which is the
 322   // branch's probability times the block frequency of the predecessor.
 323   BlockFrequency MergeWeight = MBFI->getBlockFreq(BB);
 324   MergeWeight *= MBPI->getEdgeProbability(BB, Successor);
 325   // We only want to consider breaking the CFG when the merge weight is much
 326   // higher (80% vs. 20%), so multiply it by 1/4. This will require the merged
 327   // edge to be 4x more likely before we disrupt the CFG. This number matches
 328   // the definition of "hot" in BranchProbabilityAnalysis (80% vs. 20%).
 329   MergeWeight *= BranchProbability(1, 4);
 330   for (MachineBasicBlock::pred_iterator PI = Successor->pred_begin(),
 331                                         PE = Successor->pred_end();
 332        PI != PE; ++PI) {
 333     if (BB == *PI || Successor == *PI) continue;
 334     BlockFrequency PredWeight = MBFI->getBlockFreq(*PI);
 335     PredWeight *= MBPI->getEdgeProbability(*PI, Successor);
 336
 337     // Return on the first predecessor we find which outstrips our merge weight.
 338     if (MergeWeight < PredWeight)
 339       return;
 340     DEBUG(dbgs() << "Breaking CFG edge!\n"
 341                  << "  Edge from " << getBlockNum(BB) << " to "
 342                  << getBlockNum(Successor) << ": " << MergeWeight << "\n"
 343                  << "        vs. " << getBlockNum(BB) << " to "
 344                  << getBlockNum(*PI) << ": " << PredWeight << "\n");
 345   }
 346
 347   DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to "
 348                << getBlockNum(Successor) << "\n");
 349   Chain->merge(Successor, SuccChain);
 350 }
 351
 352 /// \brief Forms basic block chains from the natural loop structures.
 353 ///
 354 /// These chains are designed to preserve the existing *structure* of the code
 355 /// as much as possible. We can then stitch the chains together in a way which
 356 /// both preserves the topological structure and minimizes taken conditional
 357 /// branches.
 358 void MachineBlockPlacement::buildLoopChains(MachineFunction &F, MachineLoop &L) {
 359   // First recurse through any nested loops, building chains for those inner
 360   // loops.
 361   for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
 362     buildLoopChains(F, **LI);
 363
 364   SmallPtrSet<MachineBasicBlock *, 16> LoopBlockSet(L.block_begin(),
 365                                                     L.block_end());
 366
 367   // Begin building up a set of chains of blocks within this loop which should
 368   // remain contiguous. Some of the blocks already belong to a chain which
 369   // represents an inner loop.
 370   for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end();
 371        BI != BE; ++BI) {
 372     MachineBasicBlock *BB = *BI;
 373     BlockChain *Chain = BlockToChain[BB];
 374     if (!Chain) Chain = CreateChain(BB);
 375     mergeSuccessor(BB, Chain, &LoopBlockSet);
 376   }
 377 }
 378
 379 void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
 380   // First build any loop-based chains.
 381   for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE;
 382        ++LI)
 383     buildLoopChains(F, **LI);
 384
 385   // Now walk the blocks of the function forming chains where they don't
 386   // violate any CFG structure.
 387   for (MachineFunction::iterator BI = F.begin(), BE = F.end();
 388        BI != BE; ++BI) {
 389     MachineBasicBlock *BB = BI;
 390     BlockChain *Chain = BlockToChain[BB];
 391     if (!Chain) Chain = CreateChain(BB);
 392     mergeSuccessor(BB, Chain);
 393   }
 394 }
 395
 396 void MachineBlockPlacement::placeChainsTopologically(MachineFunction &F) {
 397   MachineBasicBlock *EntryB = &F.front();
 398   BlockChain *EntryChain = BlockToChain[EntryB];
 399   assert(EntryChain && "Missing chain for entry block");
 400   assert(*EntryChain->begin() == EntryB &&
 401          "Entry block is not the head of the entry block chain");
 402
 403   // Walk the blocks in RPO, and insert each block for a chain in order the
 404   // first time we see that chain.
 405   MachineFunction::iterator InsertPos = F.begin();
 406   SmallPtrSet<BlockChain *, 16> VisitedChains;
 407   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(EntryB);
 408   typedef ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
 409     rpo_iterator;
 410   for (rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
 411     BlockChain *Chain = BlockToChain[*I];
 412     assert(Chain);
 413     if(!VisitedChains.insert(Chain))
 414       continue;
 415     for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); BI != BE;
 416          ++BI) {
 417       DEBUG(dbgs() << (BI == Chain->begin() ? "Placing chain "
 418                                             : "          ... ")
 419                    << getBlockName(*BI) << "\n");
 420       if (InsertPos != MachineFunction::iterator(*BI))
 421         F.splice(InsertPos, *BI);
 422       else
 423         ++InsertPos;
 424     }
 425   }
 426
 427   // Now that every block is in its final position, update all of the
 428   // terminators.
 429   SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
 430   for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 431     // FIXME: It would be awesome of updateTerminator would just return rather
 432     // than assert when the branch cannot be analyzed in order to remove this
 433     // boiler plate.
 434     Cond.clear();
 435     MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
 436     if (!TII->AnalyzeBranch(*FI, TBB, FBB, Cond))
 437       FI->updateTerminator();
 438   }
 439 }
 440
 441 /// \brief Recursive helper to align a loop and any nested loops.
 442 static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) {
 443   // Recurse through nested loops.
 444   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 445     AlignLoop(F, *I, Align);
 446
 447   L->getTopBlock()->setAlignment(Align);
 448 }
 449
 450 /// \brief Align loop headers to target preferred alignments.
 451 void MachineBlockPlacement::AlignLoops(MachineFunction &F) {
 452   if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
 453     return;
 454
 455   unsigned Align = TLI->getPrefLoopAlignment();
 456   if (!Align)
 457     return;  // Don't care about loop alignment.
 458
 459   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
 460     AlignLoop(F, *I, Align);
 461 }
 462
 463 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
 464   // Check for single-block functions and skip them.
 465   if (llvm::next(F.begin()) == F.end())
 466     return false;
 467
 468   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 469   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 470   MLI = &getAnalysis<MachineLoopInfo>();
 471   TII = F.getTarget().getInstrInfo();
 472   TLI = F.getTarget().getTargetLowering();
 473   assert(BlockToChain.empty());
 474
 475   buildCFGChains(F);
 476   placeChainsTopologically(F);
 477   AlignLoops(F);
 478
 479   BlockToChain.clear();
 480
 481   // We always return true as we have no way to track whether the final order
 482   // differs from the original order.
 483   return true;
 484 }