MachineBlockPlacement.cpp revision 56b150b1969637892ab3484e08e69e9d12c9cf24
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> 49using namespace llvm; 50 51namespace { 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. 57struct 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 67namespace { 68class BlockChain; 69/// \brief Type for our function-wide basic block -> block chain mapping. 70typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 71} 72 73namespace { 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. 89class 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 104public: 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 159namespace { 160class 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 203public: 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 222char MachineBlockPlacement::ID = 0; 223INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 224 "Branch Probability Basic Block Placement", false, false) 225INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 226INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 227INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 228INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 229 "Branch Probability Basic Block Placement", false, false) 230 231FunctionPass *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. 239static 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. 251static 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. 265BlockChain *MachineBlockPlacement::CreateChain(MachineBasicBlock *BB) { 266 BlockChain *Chain = 267 new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 268 //assert(ActiveChains.insert(Chain)); 269 return Chain; 270} 271 272/// \brief Merge a chain with any viable successor. 273/// 274/// This routine walks the predecessors of the current block, looking for 275/// viable merge candidates. It has strict rules it uses to determine when 276/// a predecessor can be merged with the current block, which center around 277/// preserving the CFG structure. It performs the merge if any viable candidate 278/// is found. 279void MachineBlockPlacement::mergeSuccessor(MachineBasicBlock *BB, 280 BlockChain *Chain, 281 BlockFilterSet *Filter) { 282 assert(BB); 283 assert(Chain); 284 285 // If this block is not at the end of its chain, it cannot merge with any 286 // other chain. 287 if (Chain && *llvm::prior(Chain->end()) != BB) 288 return; 289 290 // Walk through the successors looking for the highest probability edge. 291 // FIXME: This is an annoying way to do the comparison, but it's correct. 292 // Support should be added to BranchProbability to properly compare two. 293 MachineBasicBlock *Successor = 0; 294 BlockFrequency BestFreq; 295 DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 296 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 297 SE = BB->succ_end(); 298 SI != SE; ++SI) { 299 if (BB == *SI || (Filter && !Filter->count(*SI))) 300 continue; 301 302 BlockFrequency SuccFreq(BlockFrequency::getEntryFrequency()); 303 SuccFreq *= MBPI->getEdgeProbability(BB, *SI); 304 DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccFreq << "\n"); 305 if (!Successor || SuccFreq > BestFreq || (!(SuccFreq < BestFreq) && 306 BB->isLayoutSuccessor(*SI))) { 307 Successor = *SI; 308 BestFreq = SuccFreq; 309 } 310 } 311 if (!Successor) 312 return; 313 314 // Grab a chain if it exists already for this successor and make sure the 315 // successor is at the start of the chain as we can't merge mid-chain. Also, 316 // if the successor chain is the same as our chain, we're already merged. 317 BlockChain *SuccChain = BlockToChain[Successor]; 318 if (SuccChain && (SuccChain == Chain || Successor != *SuccChain->begin())) 319 return; 320 321 // We only merge chains across a CFG merge when the desired merge path is 322 // significantly hotter than the incoming edge. We define a hot edge more 323 // strictly than the BranchProbabilityInfo does, as the two predecessor 324 // blocks may have dramatically different incoming probabilities we need to 325 // account for. Therefor we use the "global" edge weight which is the 326 // branch's probability times the block frequency of the predecessor. 327 BlockFrequency MergeWeight = MBFI->getBlockFreq(BB); 328 MergeWeight *= MBPI->getEdgeProbability(BB, Successor); 329 // We only want to consider breaking the CFG when the merge weight is much 330 // higher (80% vs. 20%), so multiply it by 1/4. This will require the merged 331 // edge to be 4x more likely before we disrupt the CFG. This number matches 332 // the definition of "hot" in BranchProbabilityAnalysis (80% vs. 20%). 333 MergeWeight *= BranchProbability(1, 4); 334 for (MachineBasicBlock::pred_iterator PI = Successor->pred_begin(), 335 PE = Successor->pred_end(); 336 PI != PE; ++PI) { 337 if (BB == *PI || Successor == *PI) continue; 338 BlockFrequency PredWeight = MBFI->getBlockFreq(*PI); 339 PredWeight *= MBPI->getEdgeProbability(*PI, Successor); 340 341 // Return on the first predecessor we find which outstrips our merge weight. 342 if (MergeWeight < PredWeight) 343 return; 344 DEBUG(dbgs() << "Breaking CFG edge!\n" 345 << " Edge from " << getBlockNum(BB) << " to " 346 << getBlockNum(Successor) << ": " << MergeWeight << "\n" 347 << " vs. " << getBlockNum(BB) << " to " 348 << getBlockNum(*PI) << ": " << PredWeight << "\n"); 349 } 350 351 DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to " 352 << getBlockNum(Successor) << "\n"); 353 Chain->merge(Successor, SuccChain); 354} 355 356/// \brief Forms basic block chains from the natural loop structures. 357/// 358/// These chains are designed to preserve the existing *structure* of the code 359/// as much as possible. We can then stitch the chains together in a way which 360/// both preserves the topological structure and minimizes taken conditional 361/// branches. 362void MachineBlockPlacement::buildLoopChains(MachineFunction &F, MachineLoop &L) { 363 // First recurse through any nested loops, building chains for those inner 364 // loops. 365 for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 366 buildLoopChains(F, **LI); 367 368 SmallPtrSet<MachineBasicBlock *, 16> LoopBlockSet(L.block_begin(), 369 L.block_end()); 370 371 // Begin building up a set of chains of blocks within this loop which should 372 // remain contiguous. Some of the blocks already belong to a chain which 373 // represents an inner loop. 374 for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end(); 375 BI != BE; ++BI) { 376 MachineBasicBlock *BB = *BI; 377 BlockChain *Chain = BlockToChain[BB]; 378 if (!Chain) Chain = CreateChain(BB); 379 mergeSuccessor(BB, Chain, &LoopBlockSet); 380 } 381} 382 383void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 384 // First build any loop-based chains. 385 for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 386 ++LI) 387 buildLoopChains(F, **LI); 388 389 // Now walk the blocks of the function forming chains where they don't 390 // violate any CFG structure. 391 for (MachineFunction::iterator BI = F.begin(), BE = F.end(); 392 BI != BE; ++BI) { 393 MachineBasicBlock *BB = BI; 394 BlockChain *Chain = BlockToChain[BB]; 395 if (!Chain) Chain = CreateChain(BB); 396 mergeSuccessor(BB, Chain); 397 } 398} 399 400void MachineBlockPlacement::placeChainsTopologically(MachineFunction &F) { 401 MachineBasicBlock *EntryB = &F.front(); 402 BlockChain *EntryChain = BlockToChain[EntryB]; 403 assert(EntryChain && "Missing chain for entry block"); 404 assert(*EntryChain->begin() == EntryB && 405 "Entry block is not the head of the entry block chain"); 406 407 // Walk the blocks in RPO, and insert each block for a chain in order the 408 // first time we see that chain. 409 MachineFunction::iterator InsertPos = F.begin(); 410 SmallPtrSet<BlockChain *, 16> VisitedChains; 411 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(EntryB); 412 typedef ReversePostOrderTraversal<MachineBasicBlock *>::rpo_iterator 413 rpo_iterator; 414 for (rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 415 BlockChain *Chain = BlockToChain[*I]; 416 assert(Chain); 417 if(!VisitedChains.insert(Chain)) 418 continue; 419 for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); BI != BE; 420 ++BI) { 421 DEBUG(dbgs() << (BI == Chain->begin() ? "Placing chain " 422 : " ... ") 423 << getBlockName(*BI) << "\n"); 424 if (InsertPos != MachineFunction::iterator(*BI)) 425 F.splice(InsertPos, *BI); 426 else 427 ++InsertPos; 428 } 429 } 430 431 // Now that every block is in its final position, update all of the 432 // terminators. 433 SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 434 for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 435 // FIXME: It would be awesome of updateTerminator would just return rather 436 // than assert when the branch cannot be analyzed in order to remove this 437 // boiler plate. 438 Cond.clear(); 439 MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 440 if (!TII->AnalyzeBranch(*FI, TBB, FBB, Cond)) 441 FI->updateTerminator(); 442 } 443} 444 445/// \brief Recursive helper to align a loop and any nested loops. 446static void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) { 447 // Recurse through nested loops. 448 for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 449 AlignLoop(F, *I, Align); 450 451 L->getTopBlock()->setAlignment(Align); 452} 453 454/// \brief Align loop headers to target preferred alignments. 455void MachineBlockPlacement::AlignLoops(MachineFunction &F) { 456 if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 457 return; 458 459 unsigned Align = TLI->getPrefLoopAlignment(); 460 if (!Align) 461 return; // Don't care about loop alignment. 462 463 for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) 464 AlignLoop(F, *I, Align); 465} 466 467bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 468 // Check for single-block functions and skip them. 469 if (llvm::next(F.begin()) == F.end()) 470 return false; 471 472 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 473 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 474 MLI = &getAnalysis<MachineLoopInfo>(); 475 TII = F.getTarget().getInstrInfo(); 476 TLI = F.getTarget().getTargetLowering(); 477 assert(BlockToChain.empty()); 478 479 buildCFGChains(F); 480 placeChainsTopologically(F); 481 AlignLoops(F); 482 483 BlockToChain.clear(); 484 485 // We always return true as we have no way to track whether the final order 486 // differs from the original order. 487 return true; 488} 489