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