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 STATISTIC(NumCondBranches, "Number of conditional branches");
  52 STATISTIC(NumUncondBranches, "Number of uncondittional branches");
  53 STATISTIC(CondBranchTakenFreq,
  54           "Potential frequency of taking conditional branches");
  55 STATISTIC(UncondBranchTakenFreq,
  56           "Potential frequency of taking unconditional branches");
  57
  58 namespace {
  59 /// \brief A structure for storing a weighted edge.
  60 ///
  61 /// This stores an edge and its weight, computed as the product of the
  62 /// frequency that the starting block is entered with the probability of
  63 /// a particular exit block.
  64 struct WeightedEdge {
  65   BlockFrequency EdgeFrequency;
  66   MachineBasicBlock *From, *To;
  67
  68   bool operator<(const WeightedEdge &RHS) const {
  69     return EdgeFrequency < RHS.EdgeFrequency;
  70   }
  71 };
  72 }
  73
  74 namespace {
  75 class BlockChain;
  76 /// \brief Type for our function-wide basic block -> block chain mapping.
  77 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
  78 }
  79
  80 namespace {
  81 /// \brief A chain of blocks which will be laid out contiguously.
  82 ///
  83 /// This is the datastructure representing a chain of consecutive blocks that
  84 /// are profitable to layout together in order to maximize fallthrough
  85 /// probabilities. We also can use a block chain to represent a sequence of
  86 /// basic blocks which have some external (correctness) requirement for
  87 /// sequential layout.
  88 ///
  89 /// Eventually, the block chains will form a directed graph over the function.
  90 /// We provide an SCC-supporting-iterator in order to quicky build and walk the
  91 /// SCCs of block chains within a function.
  92 ///
  93 /// The block chains also have support for calculating and caching probability
  94 /// information related to the chain itself versus other chains. This is used
  95 /// for ranking during the final layout of block chains.
  96 class BlockChain {
  97   /// \brief The sequence of blocks belonging to this chain.
  98   ///
  99   /// This is the sequence of blocks for a particular chain. These will be laid
 100   /// out in-order within the function.
 101   SmallVector<MachineBasicBlock *, 4> Blocks;
 102
 103   /// \brief A handle to the function-wide basic block to block chain mapping.
 104   ///
 105   /// This is retained in each block chain to simplify the computation of child
 106   /// block chains for SCC-formation and iteration. We store the edges to child
 107   /// basic blocks, and map them back to their associated chains using this
 108   /// structure.
 109   BlockToChainMapType &BlockToChain;
 110
 111 public:
 112   /// \brief Construct a new BlockChain.
 113   ///
 114   /// This builds a new block chain representing a single basic block in the
 115   /// function. It also registers itself as the chain that block participates
 116   /// in with the BlockToChain mapping.
 117   BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB)
 118     : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) {
 119     assert(BB && "Cannot create a chain with a null basic block");
 120     BlockToChain[BB] = this;
 121   }
 122
 123   /// \brief Iterator over blocks within the chain.
 124   typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator iterator;
 125
 126   /// \brief Beginning of blocks within the chain.
 127   iterator begin() const { return Blocks.begin(); }
 128
 129   /// \brief End of blocks within the chain.
 130   iterator end() const { return Blocks.end(); }
 131
 132   /// \brief Merge a block chain into this one.
 133   ///
 134   /// This routine merges a block chain into this one. It takes care of forming
 135   /// a contiguous sequence of basic blocks, updating the edge list, and
 136   /// updating the block -> chain mapping. It does not free or tear down the
 137   /// old chain, but the old chain's block list is no longer valid.
 138   void merge(MachineBasicBlock *BB, BlockChain *Chain) {
 139     assert(BB);
 140     assert(!Blocks.empty());
 141
 142     // Fast path in case we don't have a chain already.
 143     if (!Chain) {
 144       assert(!BlockToChain[BB]);
 145       Blocks.push_back(BB);
 146       BlockToChain[BB] = this;
 147       return;
 148     }
 149
 150     assert(BB == *Chain->begin());
 151     assert(Chain->begin() != Chain->end());
 152
 153     // Update the incoming blocks to point to this chain, and add them to the
 154     // chain structure.
 155     for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
 156          BI != BE; ++BI) {
 157       Blocks.push_back(*BI);
 158       assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
 159       BlockToChain[*BI] = this;
 160     }
 161   }
 162
 163   /// \brief Count of predecessors within the loop currently being processed.
 164   ///
 165   /// This count is updated at each loop we process to represent the number of
 166   /// in-loop predecessors of this chain.
 167   unsigned LoopPredecessors;
 168 };
 169 }
 170
 171 namespace {
 172 class MachineBlockPlacement : public MachineFunctionPass {
 173   /// \brief A typedef for a block filter set.
 174   typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
 175
 176   /// \brief A handle to the branch probability pass.
 177   const MachineBranchProbabilityInfo *MBPI;
 178
 179   /// \brief A handle to the function-wide block frequency pass.
 180   const MachineBlockFrequencyInfo *MBFI;
 181
 182   /// \brief A handle to the loop info.
 183   const MachineLoopInfo *MLI;
 184
 185   /// \brief A handle to the target's instruction info.
 186   const TargetInstrInfo *TII;
 187
 188   /// \brief A handle to the target's lowering info.
 189   const TargetLowering *TLI;
 190
 191   /// \brief Allocator and owner of BlockChain structures.
 192   ///
 193   /// We build BlockChains lazily by merging together high probability BB
 194   /// sequences acording to the "Algo2" in the paper mentioned at the top of
 195   /// the file. To reduce malloc traffic, we allocate them using this slab-like
 196   /// allocator, and destroy them after the pass completes.
 197   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
 198
 199   /// \brief Function wide BasicBlock to BlockChain mapping.
 200   ///
 201   /// This mapping allows efficiently moving from any given basic block to the
 202   /// BlockChain it participates in, if any. We use it to, among other things,
 203   /// allow implicitly defining edges between chains as the existing edges
 204   /// between basic blocks.
 205   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 206
 207   void markChainSuccessors(BlockChain &Chain,
 208                            MachineBasicBlock *LoopHeaderBB,
 209                            SmallVectorImpl<MachineBasicBlock *> &Blocks,
 210                            const BlockFilterSet *BlockFilter = 0);
 211   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
 212                                          BlockChain &Chain,
 213                                          const BlockFilterSet *BlockFilter);
 214   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
 215                   SmallVectorImpl<MachineBasicBlock *> &Blocks,
 216                   const BlockFilterSet *BlockFilter = 0);
 217   void buildLoopChains(MachineFunction &F, MachineLoop &L);
 218   void buildCFGChains(MachineFunction &F);
 219   void AlignLoops(MachineFunction &F);
 220
 221 public:
 222   static char ID; // Pass identification, replacement for typeid
 223   MachineBlockPlacement() : MachineFunctionPass(ID) {
 224     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
 225   }
 226
 227   bool runOnMachineFunction(MachineFunction &F);
 228
 229   void getAnalysisUsage(AnalysisUsage &AU) const {
 230     AU.addRequired<MachineBranchProbabilityInfo>();
 231     AU.addRequired<MachineBlockFrequencyInfo>();
 232     AU.addRequired<MachineLoopInfo>();
 233     MachineFunctionPass::getAnalysisUsage(AU);
 234   }
 235
 236   const char *getPassName() const { return "Block Placement"; }
 237 };
 238 }
 239
 240 char MachineBlockPlacement::ID = 0;
 241 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
 242                       "Branch Probability Basic Block Placement", false, false)
 243 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 244 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 245 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 246 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
 247                     "Branch Probability Basic Block Placement", false, false)
 248
 249 FunctionPass *llvm::createMachineBlockPlacementPass() {
 250   return new MachineBlockPlacement();
 251 }
 252
 253 #ifndef NDEBUG
 254 /// \brief Helper to print the name of a MBB.
 255 ///
 256 /// Only used by debug logging.
 257 static std::string getBlockName(MachineBasicBlock *BB) {
 258   std::string Result;
 259   raw_string_ostream OS(Result);
 260   OS << "BB#" << BB->getNumber()
 261      << " (derived from LLVM BB '" << BB->getName() << "')";
 262   OS.flush();
 263   return Result;
 264 }
 265
 266 /// \brief Helper to print the number of a MBB.
 267 ///
 268 /// Only used by debug logging.
 269 static std::string getBlockNum(MachineBasicBlock *BB) {
 270   std::string Result;
 271   raw_string_ostream OS(Result);
 272   OS << "BB#" << BB->getNumber();
 273   OS.flush();
 274   return Result;
 275 }
 276 #endif
 277
 278 /// \brief Mark a chain's successors as having one fewer preds.
 279 ///
 280 /// When a chain is being merged into the "placed" chain, this routine will
 281 /// quickly walk the successors of each block in the chain and mark them as
 282 /// having one fewer active predecessor. It also adds any successors of this
 283 /// chain which reach the zero-predecessor state to the worklist passed in.
 284 void MachineBlockPlacement::markChainSuccessors(
 285     BlockChain &Chain,
 286     MachineBasicBlock *LoopHeaderBB,
 287     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
 288     const BlockFilterSet *BlockFilter) {
 289   // Walk all the blocks in this chain, marking their successors as having
 290   // a predecessor placed.
 291   for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end();
 292        CBI != CBE; ++CBI) {
 293     // Add any successors for which this is the only un-placed in-loop
 294     // predecessor to the worklist as a viable candidate for CFG-neutral
 295     // placement. No subsequent placement of this block will violate the CFG
 296     // shape, so we get to use heuristics to choose a favorable placement.
 297     for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(),
 298                                           SE = (*CBI)->succ_end();
 299          SI != SE; ++SI) {
 300       if (BlockFilter && !BlockFilter->count(*SI))
 301         continue;
 302       BlockChain &SuccChain = *BlockToChain[*SI];
 303       // Disregard edges within a fixed chain, or edges to the loop header.
 304       if (&Chain == &SuccChain || *SI == LoopHeaderBB)
 305         continue;
 306
 307       // This is a cross-chain edge that is within the loop, so decrement the
 308       // loop predecessor count of the destination chain.
 309       if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0)
 310         BlockWorkList.push_back(*SI);
 311     }
 312   }
 313 }
 314
 315 /// \brief Select the best successor for a block.
 316 ///
 317 /// This looks across all successors of a particular block and attempts to
 318 /// select the "best" one to be the layout successor. It only considers direct
 319 /// successors which also pass the block filter. It will attempt to avoid
 320 /// breaking CFG structure, but cave and break such structures in the case of
 321 /// very hot successor edges.
 322 ///
 323 /// \returns The best successor block found, or null if none are viable.
 324 MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor(
 325     MachineBasicBlock *BB, BlockChain &Chain,
 326     const BlockFilterSet *BlockFilter) {
 327   const BranchProbability HotProb(4, 5); // 80%
 328
 329   MachineBasicBlock *BestSucc = 0;
 330   BranchProbability BestProb = BranchProbability::getZero();
 331   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
 332   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 333                                         SE = BB->succ_end();
 334        SI != SE; ++SI) {
 335     if (BlockFilter && !BlockFilter->count(*SI))
 336       continue;
 337     BlockChain &SuccChain = *BlockToChain[*SI];
 338     if (&SuccChain == &Chain) {
 339       DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> Already merged!\n");
 340       continue;
 341     }
 342
 343     BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI);
 344
 345     // Only consider successors which are either "hot", or wouldn't violate
 346     // any CFG constraints.
 347     if (SuccChain.LoopPredecessors != 0 && SuccProb < HotProb) {
 348       DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> CFG conflict\n");
 349       continue;
 350     }
 351
 352     DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> " << SuccProb
 353                  << " (prob)"
 354                  << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "")
 355                  << "\n");
 356     if (BestSucc && BestProb >= SuccProb)
 357       continue;
 358     BestSucc = *SI;
 359     BestProb = SuccProb;
 360   }
 361   return BestSucc;
 362 }
 363
 364 void MachineBlockPlacement::buildChain(
 365     MachineBasicBlock *BB,
 366     BlockChain &Chain,
 367     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
 368     const BlockFilterSet *BlockFilter) {
 369   assert(BB);
 370   assert(BlockToChain[BB] == &Chain);
 371   assert(*Chain.begin() == BB);
 372   MachineBasicBlock *LoopHeaderBB = BB;
 373   markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter);
 374   BB = *llvm::prior(Chain.end());
 375   for (;;) {
 376     assert(BB);
 377     assert(BlockToChain[BB] == &Chain);
 378     assert(*llvm::prior(Chain.end()) == BB);
 379
 380     // Look for the best viable successor if there is one to place immediately
 381     // after this block.
 382     MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
 383
 384     // If an immediate successor isn't available, look for the best viable
 385     // block among those we've identified as not violating the loop's CFG at
 386     // this point. This won't be a fallthrough, but it will increase locality.
 387     if (!BestSucc) {
 388       BlockFrequency BestFreq;
 389       for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = BlockWorkList.begin(),
 390                                                           WBE = BlockWorkList.end();
 391            WBI != WBE; ++WBI) {
 392         if (BlockFilter && !BlockFilter->count(*WBI))
 393           continue;
 394         BlockChain &SuccChain = *BlockToChain[*WBI];
 395         if (&SuccChain == &Chain) {
 396           DEBUG(dbgs() << "    " << getBlockName(*WBI)
 397                        << " -> Already merged!\n");
 398           continue;
 399         }
 400         assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block");
 401
 402         BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI);
 403         DEBUG(dbgs() << "    " << getBlockName(*WBI) << " -> " << CandidateFreq
 404                      << " (freq)\n");
 405         if (BestSucc && BestFreq >= CandidateFreq)
 406           continue;
 407         BestSucc = *WBI;
 408         BestFreq = CandidateFreq;
 409       }
 410     }
 411     if (!BestSucc) {
 412       DEBUG(dbgs() << "Finished forming chain for header block "
 413                    << getBlockNum(*Chain.begin()) << "\n");
 414       return;
 415     }
 416
 417     // Place this block, updating the datastructures to reflect its placement.
 418     BlockChain &SuccChain = *BlockToChain[BestSucc];
 419     DEBUG(dbgs() << "Merging from " << getBlockNum(BB)
 420                  << " to " << getBlockNum(BestSucc) << "\n");
 421     markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter);
 422     Chain.merge(BestSucc, &SuccChain);
 423     BB = *llvm::prior(Chain.end());
 424   }
 425 }
 426
 427 /// \brief Forms basic block chains from the natural loop structures.
 428 ///
 429 /// These chains are designed to preserve the existing *structure* of the code
 430 /// as much as possible. We can then stitch the chains together in a way which
 431 /// both preserves the topological structure and minimizes taken conditional
 432 /// branches.
 433 void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
 434                                             MachineLoop &L) {
 435   // First recurse through any nested loops, building chains for those inner
 436   // loops.
 437   for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
 438     buildLoopChains(F, **LI);
 439
 440   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
 441   BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end());
 442
 443   // FIXME: This is a really lame way of walking the chains in the loop: we
 444   // walk the blocks, and use a set to prevent visiting a particular chain
 445   // twice.
 446   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
 447   for (MachineLoop::block_iterator BI = L.block_begin(),
 448                                    BE = L.block_end();
 449        BI != BE; ++BI) {
 450     BlockChain &Chain = *BlockToChain[*BI];
 451     if (!UpdatedPreds.insert(&Chain) || BI == L.block_begin())
 452       continue;
 453
 454     assert(Chain.LoopPredecessors == 0);
 455     for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
 456          BCI != BCE; ++BCI) {
 457       assert(BlockToChain[*BCI] == &Chain);
 458       for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(),
 459                                             PE = (*BCI)->pred_end();
 460            PI != PE; ++PI) {
 461         if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI))
 462           continue;
 463         ++Chain.LoopPredecessors;
 464       }
 465     }
 466
 467     if (Chain.LoopPredecessors == 0)
 468       BlockWorkList.push_back(*BI);
 469   }
 470
 471   BlockChain &LoopChain = *BlockToChain[L.getHeader()];
 472   buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet);
 473
 474   DEBUG({
 475     if (LoopChain.LoopPredecessors)
 476       dbgs() << "Loop chain contains a block without its preds placed!\n"
 477              << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
 478              << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
 479     for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end();
 480          BCI != BCE; ++BCI)
 481       if (!LoopBlockSet.erase(*BCI))
 482         dbgs() << "Loop chain contains a block not contained by the loop!\n"
 483                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
 484                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
 485                << "  Bad block:    " << getBlockName(*BCI) << "\n";
 486
 487     if (!LoopBlockSet.empty())
 488       for (SmallPtrSet<MachineBasicBlock *, 16>::iterator LBI = LoopBlockSet.begin(), LBE = LoopBlockSet.end();
 489            LBI != LBE; ++LBI)
 490         dbgs() << "Loop contains blocks never placed into a chain!\n"
 491                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
 492                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
 493                << "  Bad block:    " << getBlockName(*LBI) << "\n";
 494   });
 495 }
 496
 497 void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
 498   // Ensure that every BB in the function has an associated chain to simplify
 499   // the assumptions of the remaining algorithm.
 500   for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 501     BlockToChain[&*FI] =
 502       new (ChainAllocator.Allocate()) BlockChain(BlockToChain, &*FI);
 503
 504   // Build any loop-based chains.
 505   for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE;
 506        ++LI)
 507     buildLoopChains(F, **LI);
 508
 509   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
 510
 511   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
 512   for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 513     MachineBasicBlock *BB = &*FI;
 514     BlockChain &Chain = *BlockToChain[BB];
 515     if (!UpdatedPreds.insert(&Chain))
 516       continue;
 517
 518     assert(Chain.LoopPredecessors == 0);
 519     for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
 520          BCI != BCE; ++BCI) {
 521       assert(BlockToChain[*BCI] == &Chain);
 522       for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(),
 523                                             PE = (*BCI)->pred_end();
 524            PI != PE; ++PI) {
 525         if (BlockToChain[*PI] == &Chain)
 526           continue;
 527         ++Chain.LoopPredecessors;
 528       }
 529     }
 530
 531     if (Chain.LoopPredecessors == 0)
 532       BlockWorkList.push_back(BB);
 533   }
 534
 535   BlockChain &FunctionChain = *BlockToChain[&F.front()];
 536   buildChain(&F.front(), FunctionChain, BlockWorkList);
 537
 538   typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType;
 539   DEBUG({
 540     FunctionBlockSetType FunctionBlockSet;
 541     for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 542       FunctionBlockSet.insert(FI);
 543
 544     for (BlockChain::iterator BCI = FunctionChain.begin(), BCE = FunctionChain.end();
 545          BCI != BCE; ++BCI)
 546       if (!FunctionBlockSet.erase(*BCI))
 547         dbgs() << "Function chain contains a block not in the function!\n"
 548                << "  Bad block:    " << getBlockName(*BCI) << "\n";
 549
 550     if (!FunctionBlockSet.empty())
 551       for (SmallPtrSet<MachineBasicBlock *, 16>::iterator FBI = FunctionBlockSet.begin(),
 552            FBE = FunctionBlockSet.end(); FBI != FBE; ++FBI)
 553         dbgs() << "Function contains blocks never placed into a chain!\n"
 554                << "  Bad block:    " << getBlockName(*FBI) << "\n";
 555   });
 556
 557   // Splice the blocks into place.
 558   MachineFunction::iterator InsertPos = F.begin();
 559   SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
 560   for (BlockChain::iterator BI = FunctionChain.begin(), BE = FunctionChain.end();
 561        BI != BE; ++BI) {
 562     DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain "
 563                                                   : "          ... ")
 564           << getBlockName(*BI) << "\n");
 565     if (InsertPos != MachineFunction::iterator(*BI))
 566       F.splice(InsertPos, *BI);
 567     else
 568       ++InsertPos;
 569
 570     // Update the terminator of the previous block.
 571     if (BI == FunctionChain.begin())
 572       continue;
 573     MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI));
 574
 575     // FIXME: It would be awesome of updateTerminator would just return rather
 576     // than assert when the branch cannot be analyzed in order to remove this
 577     // boiler plate.
 578     Cond.clear();
 579     MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
 580     if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond))
 581       PrevBB->updateTerminator();
 582   }
 583
 584   // Fixup the last block.
 585   Cond.clear();
 586   MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
 587   if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond))
 588     F.back().updateTerminator();
 589 }
 590
 591 /// \brief Recursive helper to align a loop and any nested loops.
 592 static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) {
 593   // Recurse through nested loops.
 594   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 595     AlignLoop(F, *I, Align);
 596
 597   L->getTopBlock()->setAlignment(Align);
 598 }
 599
 600 /// \brief Align loop headers to target preferred alignments.
 601 void MachineBlockPlacement::AlignLoops(MachineFunction &F) {
 602   if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
 603     return;
 604
 605   unsigned Align = TLI->getPrefLoopAlignment();
 606   if (!Align)
 607     return;  // Don't care about loop alignment.
 608
 609   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
 610     AlignLoop(F, *I, Align);
 611 }
 612
 613 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
 614   // Check for single-block functions and skip them.
 615   if (llvm::next(F.begin()) == F.end())
 616     return false;
 617
 618   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 619   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 620   MLI = &getAnalysis<MachineLoopInfo>();
 621   TII = F.getTarget().getInstrInfo();
 622   TLI = F.getTarget().getTargetLowering();
 623   assert(BlockToChain.empty());
 624
 625   buildCFGChains(F);
 626   AlignLoops(F);
 627
 628   BlockToChain.clear();
 629
 630   // We always return true as we have no way to track whether the final order
 631   // differs from the original order.
 632   return true;
 633 }
 634
 635 namespace {
 636 /// \brief A pass to compute block placement statistics.
 637 ///
 638 /// A separate pass to compute interesting statistics for evaluating block
 639 /// placement. This is separate from the actual placement pass so that they can
 640 /// be computed in the absense of any placement transformations or when using
 641 /// alternative placement strategies.
 642 class MachineBlockPlacementStats : public MachineFunctionPass {
 643   /// \brief A handle to the branch probability pass.
 644   const MachineBranchProbabilityInfo *MBPI;
 645
 646   /// \brief A handle to the function-wide block frequency pass.
 647   const MachineBlockFrequencyInfo *MBFI;
 648
 649 public:
 650   static char ID; // Pass identification, replacement for typeid
 651   MachineBlockPlacementStats() : MachineFunctionPass(ID) {
 652     initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
 653   }
 654
 655   bool runOnMachineFunction(MachineFunction &F);
 656
 657   void getAnalysisUsage(AnalysisUsage &AU) const {
 658     AU.addRequired<MachineBranchProbabilityInfo>();
 659     AU.addRequired<MachineBlockFrequencyInfo>();
 660     AU.setPreservesAll();
 661     MachineFunctionPass::getAnalysisUsage(AU);
 662   }
 663
 664   const char *getPassName() const { return "Block Placement Stats"; }
 665 };
 666 }
 667
 668 char MachineBlockPlacementStats::ID = 0;
 669 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
 670                       "Basic Block Placement Stats", false, false)
 671 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 672 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 673 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
 674                     "Basic Block Placement Stats", false, false)
 675
 676 FunctionPass *llvm::createMachineBlockPlacementStatsPass() {
 677   return new MachineBlockPlacementStats();
 678 }
 679
 680 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
 681   // Check for single-block functions and skip them.
 682   if (llvm::next(F.begin()) == F.end())
 683     return false;
 684
 685   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 686   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 687
 688   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 689     BlockFrequency BlockFreq = MBFI->getBlockFreq(I);
 690     Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches
 691                                                   : NumUncondBranches;
 692     Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq
 693                                                       : UncondBranchTakenFreq;
 694     for (MachineBasicBlock::succ_iterator SI = I->succ_begin(),
 695                                           SE = I->succ_end();
 696          SI != SE; ++SI) {
 697       // Skip if this successor is a fallthrough.
 698       if (I->isLayoutSuccessor(*SI))
 699         continue;
 700
 701       BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI);
 702       ++NumBranches;
 703       BranchTakenFreq += EdgeFreq.getFrequency();
 704     }
 705   }
 706
 707   return false;
 708 }
 709