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