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) {
 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     assert(Blocks.back()->isSuccessor(BB));
 142
 143     // Fast path in case we don't have a chain already.
 144     if (!Chain) {
 145       assert(!BlockToChain[BB]);
 146       Blocks.push_back(BB);
 147       BlockToChain[BB] = this;
 148       return;
 149     }
 150
 151     assert(BB == *Chain->begin());
 152     assert(Chain->begin() != Chain->end());
 153
 154     // Update the incoming blocks to point to this chain, and add them to the
 155     // chain structure.
 156     for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end();
 157          BI != BE; ++BI) {
 158       Blocks.push_back(*BI);
 159       assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain");
 160       BlockToChain[*BI] = this;
 161     }
 162   }
 163 };
 164 }
 165
 166 namespace {
 167 class MachineBlockPlacement : public MachineFunctionPass {
 168   /// \brief A typedef for a block filter set.
 169   typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
 170
 171   /// \brief A handle to the branch probability pass.
 172   const MachineBranchProbabilityInfo *MBPI;
 173
 174   /// \brief A handle to the function-wide block frequency pass.
 175   const MachineBlockFrequencyInfo *MBFI;
 176
 177   /// \brief A handle to the loop info.
 178   const MachineLoopInfo *MLI;
 179
 180   /// \brief A handle to the target's instruction info.
 181   const TargetInstrInfo *TII;
 182
 183   /// \brief A handle to the target's lowering info.
 184   const TargetLowering *TLI;
 185
 186   /// \brief Allocator and owner of BlockChain structures.
 187   ///
 188   /// We build BlockChains lazily by merging together high probability BB
 189   /// sequences acording to the "Algo2" in the paper mentioned at the top of
 190   /// the file. To reduce malloc traffic, we allocate them using this slab-like
 191   /// allocator, and destroy them after the pass completes.
 192   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
 193
 194   /// \brief Function wide BasicBlock to BlockChain mapping.
 195   ///
 196   /// This mapping allows efficiently moving from any given basic block to the
 197   /// BlockChain it participates in, if any. We use it to, among other things,
 198   /// allow implicitly defining edges between chains as the existing edges
 199   /// between basic blocks.
 200   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 201
 202   BlockChain *CreateChain(MachineBasicBlock *BB);
 203   void mergeSuccessor(MachineBasicBlock *BB, BlockChain *Chain,
 204                       BlockFilterSet *Filter = 0);
 205   void buildLoopChains(MachineFunction &F, MachineLoop &L);
 206   void buildCFGChains(MachineFunction &F);
 207   void placeChainsTopologically(MachineFunction &F);
 208   void AlignLoops(MachineFunction &F);
 209
 210 public:
 211   static char ID; // Pass identification, replacement for typeid
 212   MachineBlockPlacement() : MachineFunctionPass(ID) {
 213     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
 214   }
 215
 216   bool runOnMachineFunction(MachineFunction &F);
 217
 218   void getAnalysisUsage(AnalysisUsage &AU) const {
 219     AU.addRequired<MachineBranchProbabilityInfo>();
 220     AU.addRequired<MachineBlockFrequencyInfo>();
 221     AU.addRequired<MachineLoopInfo>();
 222     MachineFunctionPass::getAnalysisUsage(AU);
 223   }
 224
 225   const char *getPassName() const { return "Block Placement"; }
 226 };
 227 }
 228
 229 char MachineBlockPlacement::ID = 0;
 230 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
 231                       "Branch Probability Basic Block Placement", false, false)
 232 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 233 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 234 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 235 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
 236                     "Branch Probability Basic Block Placement", false, false)
 237
 238 FunctionPass *llvm::createMachineBlockPlacementPass() {
 239   return new MachineBlockPlacement();
 240 }
 241
 242 #ifndef NDEBUG
 243 /// \brief Helper to print the name of a MBB.
 244 ///
 245 /// Only used by debug logging.
 246 static std::string getBlockName(MachineBasicBlock *BB) {
 247   std::string Result;
 248   raw_string_ostream OS(Result);
 249   OS << "BB#" << BB->getNumber()
 250      << " (derived from LLVM BB '" << BB->getName() << "')";
 251   OS.flush();
 252   return Result;
 253 }
 254
 255 /// \brief Helper to print the number of a MBB.
 256 ///
 257 /// Only used by debug logging.
 258 static std::string getBlockNum(MachineBasicBlock *BB) {
 259   std::string Result;
 260   raw_string_ostream OS(Result);
 261   OS << "BB#" << BB->getNumber();
 262   OS.flush();
 263   return Result;
 264 }
 265 #endif
 266
 267 /// \brief Helper to create a new chain for a single BB.
 268 ///
 269 /// Takes care of growing the Chains, setting up the BlockChain object, and any
 270 /// debug checking logic.
 271 /// \returns A pointer to the new BlockChain.
 272 BlockChain *MachineBlockPlacement::CreateChain(MachineBasicBlock *BB) {
 273   BlockChain *Chain =
 274     new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB);
 275   return Chain;
 276 }
 277
 278 /// \brief Merge a chain with any viable successor.
 279 ///
 280 /// This routine walks the predecessors of the current block, looking for
 281 /// viable merge candidates. It has strict rules it uses to determine when
 282 /// a predecessor can be merged with the current block, which center around
 283 /// preserving the CFG structure. It performs the merge if any viable candidate
 284 /// is found.
 285 void MachineBlockPlacement::mergeSuccessor(MachineBasicBlock *BB,
 286                                            BlockChain *Chain,
 287                                            BlockFilterSet *Filter) {
 288   assert(BB);
 289   assert(Chain);
 290
 291   // If this block is not at the end of its chain, it cannot merge with any
 292   // other chain.
 293   if (Chain && *llvm::prior(Chain->end()) != BB)
 294     return;
 295
 296   // Walk through the successors looking for the highest probability edge.
 297   MachineBasicBlock *Successor = 0;
 298   BranchProbability BestProb = BranchProbability::getZero();
 299   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
 300   for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
 301                                         SE = BB->succ_end();
 302        SI != SE; ++SI) {
 303     if (BB == *SI || (Filter && !Filter->count(*SI)))
 304       continue;
 305
 306     BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI);
 307     DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> " << SuccProb << "\n");
 308     if (!Successor || SuccProb > BestProb || (!(SuccProb < BestProb) &&
 309                                               BB->isLayoutSuccessor(*SI))) {
 310       Successor = *SI;
 311       BestProb = SuccProb;
 312     }
 313   }
 314   if (!Successor)
 315     return;
 316
 317   // Grab a chain if it exists already for this successor and make sure the
 318   // successor is at the start of the chain as we can't merge mid-chain. Also,
 319   // if the successor chain is the same as our chain, we're already merged.
 320   BlockChain *SuccChain = BlockToChain[Successor];
 321   if (SuccChain && (SuccChain == Chain || Successor != *SuccChain->begin()))
 322     return;
 323
 324   // We only merge chains across a CFG merge when the desired merge path is
 325   // significantly hotter than the incoming edge. We define a hot edge more
 326   // strictly than the BranchProbabilityInfo does, as the two predecessor
 327   // blocks may have dramatically different incoming probabilities we need to
 328   // account for. Therefor we use the "global" edge weight which is the
 329   // branch's probability times the block frequency of the predecessor.
 330   BlockFrequency MergeWeight = MBFI->getBlockFreq(BB);
 331   MergeWeight *= MBPI->getEdgeProbability(BB, Successor);
 332   // We only want to consider breaking the CFG when the merge weight is much
 333   // higher (80% vs. 20%), so multiply it by 1/4. This will require the merged
 334   // edge to be 4x more likely before we disrupt the CFG. This number matches
 335   // the definition of "hot" in BranchProbabilityAnalysis (80% vs. 20%).
 336   MergeWeight *= BranchProbability(1, 4);
 337   for (MachineBasicBlock::pred_iterator PI = Successor->pred_begin(),
 338                                         PE = Successor->pred_end();
 339        PI != PE; ++PI) {
 340     if (BB == *PI || Successor == *PI) continue;
 341     BlockFrequency PredWeight = MBFI->getBlockFreq(*PI);
 342     PredWeight *= MBPI->getEdgeProbability(*PI, Successor);
 343
 344     // Return on the first predecessor we find which outstrips our merge weight.
 345     if (MergeWeight < PredWeight)
 346       return;
 347     DEBUG(dbgs() << "Breaking CFG edge!\n"
 348                  << "  Edge from " << getBlockNum(BB) << " to "
 349                  << getBlockNum(Successor) << ": " << MergeWeight << "\n"
 350                  << "        vs. " << getBlockNum(BB) << " to "
 351                  << getBlockNum(*PI) << ": " << PredWeight << "\n");
 352   }
 353
 354   DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to "
 355                << getBlockNum(Successor) << "\n");
 356   Chain->merge(Successor, SuccChain);
 357 }
 358
 359 /// \brief Forms basic block chains from the natural loop structures.
 360 ///
 361 /// These chains are designed to preserve the existing *structure* of the code
 362 /// as much as possible. We can then stitch the chains together in a way which
 363 /// both preserves the topological structure and minimizes taken conditional
 364 /// branches.
 365 void MachineBlockPlacement::buildLoopChains(MachineFunction &F, MachineLoop &L) {
 366   // First recurse through any nested loops, building chains for those inner
 367   // loops.
 368   for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
 369     buildLoopChains(F, **LI);
 370
 371   SmallPtrSet<MachineBasicBlock *, 16> LoopBlockSet(L.block_begin(),
 372                                                     L.block_end());
 373
 374   // Begin building up a set of chains of blocks within this loop which should
 375   // remain contiguous. Some of the blocks already belong to a chain which
 376   // represents an inner loop.
 377   for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end();
 378        BI != BE; ++BI) {
 379     MachineBasicBlock *BB = *BI;
 380     BlockChain *Chain = BlockToChain[BB];
 381     if (!Chain) Chain = CreateChain(BB);
 382     mergeSuccessor(BB, Chain, &LoopBlockSet);
 383   }
 384 }
 385
 386 void MachineBlockPlacement::buildCFGChains(MachineFunction &F) {
 387   // First build any loop-based chains.
 388   for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE;
 389        ++LI)
 390     buildLoopChains(F, **LI);
 391
 392   // Now walk the blocks of the function forming chains where they don't
 393   // violate any CFG structure.
 394   for (MachineFunction::iterator BI = F.begin(), BE = F.end();
 395        BI != BE; ++BI) {
 396     MachineBasicBlock *BB = BI;
 397     BlockChain *Chain = BlockToChain[BB];
 398     if (!Chain) Chain = CreateChain(BB);
 399     mergeSuccessor(BB, Chain);
 400   }
 401 }
 402
 403 void MachineBlockPlacement::placeChainsTopologically(MachineFunction &F) {
 404   MachineBasicBlock *EntryB = &F.front();
 405   assert(BlockToChain[EntryB] && "Missing chain for entry block");
 406   assert(*BlockToChain[EntryB]->begin() == EntryB &&
 407          "Entry block is not the head of the entry block chain");
 408
 409   // Walk the blocks in RPO, and insert each block for a chain in order the
 410   // first time we see that chain.
 411   MachineFunction::iterator InsertPos = F.begin();
 412   SmallPtrSet<BlockChain *, 16> VisitedChains;
 413   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(EntryB);
 414   typedef ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator
 415     rpo_iterator;
 416   for (rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
 417     BlockChain *Chain = BlockToChain[*I];
 418     assert(Chain);
 419     if(!VisitedChains.insert(Chain))
 420       continue;
 421     for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); BI != BE;
 422          ++BI) {
 423       DEBUG(dbgs() << (BI == Chain->begin() ? "Placing chain "
 424                                             : "          ... ")
 425                    << getBlockName(*BI) << "\n");
 426       if (InsertPos != MachineFunction::iterator(*BI))
 427         F.splice(InsertPos, *BI);
 428       else
 429         ++InsertPos;
 430     }
 431   }
 432
 433   // Now that every block is in its final position, update all of the
 434   // terminators.
 435   SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch.
 436   for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 437     // FIXME: It would be awesome of updateTerminator would just return rather
 438     // than assert when the branch cannot be analyzed in order to remove this
 439     // boiler plate.
 440     Cond.clear();
 441     MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
 442     if (!TII->AnalyzeBranch(*FI, TBB, FBB, Cond))
 443       FI->updateTerminator();
 444   }
 445 }
 446
 447 /// \brief Recursive helper to align a loop and any nested loops.
 448 static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) {
 449   // Recurse through nested loops.
 450   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 451     AlignLoop(F, *I, Align);
 452
 453   L->getTopBlock()->setAlignment(Align);
 454 }
 455
 456 /// \brief Align loop headers to target preferred alignments.
 457 void MachineBlockPlacement::AlignLoops(MachineFunction &F) {
 458   if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize))
 459     return;
 460
 461   unsigned Align = TLI->getPrefLoopAlignment();
 462   if (!Align)
 463     return;  // Don't care about loop alignment.
 464
 465   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I)
 466     AlignLoop(F, *I, Align);
 467 }
 468
 469 bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
 470   // Check for single-block functions and skip them.
 471   if (llvm::next(F.begin()) == F.end())
 472     return false;
 473
 474   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 475   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 476   MLI = &getAnalysis<MachineLoopInfo>();
 477   TII = F.getTarget().getInstrInfo();
 478   TLI = F.getTarget().getTargetLowering();
 479   assert(BlockToChain.empty());
 480
 481   buildCFGChains(F);
 482   placeChainsTopologically(F);
 483   AlignLoops(F);
 484
 485   BlockToChain.clear();
 486
 487   // We always return true as we have no way to track whether the final order
 488   // differs from the original order.
 489   return true;
 490 }
 491
 492 namespace {
 493 /// \brief A pass to compute block placement statistics.
 494 ///
 495 /// A separate pass to compute interesting statistics for evaluating block
 496 /// placement. This is separate from the actual placement pass so that they can
 497 /// be computed in the absense of any placement transformations or when using
 498 /// alternative placement strategies.
 499 class MachineBlockPlacementStats : public MachineFunctionPass {
 500   /// \brief A handle to the branch probability pass.
 501   const MachineBranchProbabilityInfo *MBPI;
 502
 503   /// \brief A handle to the function-wide block frequency pass.
 504   const MachineBlockFrequencyInfo *MBFI;
 505
 506 public:
 507   static char ID; // Pass identification, replacement for typeid
 508   MachineBlockPlacementStats() : MachineFunctionPass(ID) {
 509     initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
 510   }
 511
 512   bool runOnMachineFunction(MachineFunction &F);
 513
 514   void getAnalysisUsage(AnalysisUsage &AU) const {
 515     AU.addRequired<MachineBranchProbabilityInfo>();
 516     AU.addRequired<MachineBlockFrequencyInfo>();
 517     AU.setPreservesAll();
 518     MachineFunctionPass::getAnalysisUsage(AU);
 519   }
 520
 521   const char *getPassName() const { return "Block Placement Stats"; }
 522 };
 523 }
 524
 525 char MachineBlockPlacementStats::ID = 0;
 526 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
 527                       "Basic Block Placement Stats", false, false)
 528 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 529 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 530 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
 531                     "Basic Block Placement Stats", false, false)
 532
 533 FunctionPass *llvm::createMachineBlockPlacementStatsPass() {
 534   return new MachineBlockPlacementStats();
 535 }
 536
 537 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
 538   // Check for single-block functions and skip them.
 539   if (llvm::next(F.begin()) == F.end())
 540     return false;
 541
 542   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 543   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 544
 545   for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 546     BlockFrequency BlockFreq = MBFI->getBlockFreq(I);
 547     Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches
 548                                                   : NumUncondBranches;
 549     Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq
 550                                                       : UncondBranchTakenFreq;
 551     for (MachineBasicBlock::succ_iterator SI = I->succ_begin(),
 552                                           SE = I->succ_end();
 553          SI != SE; ++SI) {
 554       // Skip if this successor is a fallthrough.
 555       if (I->isLayoutSuccessor(*SI))
 556         continue;
 557
 558       BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI);
 559       ++NumBranches;
 560       BranchTakenFreq += EdgeFreq.getFrequency();
 561     }
 562   }
 563
 564   return false;
 565 }
 566