MachineBlockPlacement.cpp revision 729bec89bd8c4368a741359fb882967ce01a6909
1db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth//===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===// 2db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 3db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// The LLVM Compiler Infrastructure 4db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 5db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// This file is distributed under the University of Illinois Open Source 6db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// License. See LICENSE.TXT for details. 7db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 8db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth//===----------------------------------------------------------------------===// 9db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 103071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// This file implements basic block placement transformations using the CFG 113071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// structure and branch probability estimates. 12db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 133071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// The pass strives to preserve the structure of the CFG (that is, retain 143071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// a topological ordering of basic blocks) in the absense of a *strong* signal 153071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// to the contrary from probabilities. However, within the CFG structure, it 163071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// attempts to choose an ordering which favors placing more likely sequences of 173071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// blocks adjacent to each other. 183071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// 193071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// The algorithm works from the inner-most loop within a function outward, and 203071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// at each stage walks through the basic blocks, trying to coalesce them into 213071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// sequential chains where allowed by the CFG (or demanded by heavy 223071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// probabilities). Finally, it walks the blocks in topological order, and the 233071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// first time it reaches a chain of basic blocks, it schedules them in the 243071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth// function in-order. 25db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth// 26db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth//===----------------------------------------------------------------------===// 27db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 28db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#define DEBUG_TYPE "block-placement2" 294a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 30db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 31db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 32db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunction.h" 33db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 344a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 354a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineModuleInfo.h" 364a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/Passes.h" 37db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Support/Allocator.h" 383071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#include "llvm/Support/Debug.h" 39db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Support/ErrorHandling.h" 40db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/ADT/DenseMap.h" 413071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#include "llvm/ADT/PostOrderIterator.h" 42db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/ADT/SCCIterator.h" 43db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/ADT/SmallPtrSet.h" 44db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/ADT/SmallVector.h" 45db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/ADT/Statistic.h" 46db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Target/TargetInstrInfo.h" 474a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/Target/TargetLowering.h" 48db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include <algorithm> 49db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthusing namespace llvm; 50db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 5137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumCondBranches, "Number of conditional branches"); 5237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumUncondBranches, "Number of uncondittional branches"); 5337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(CondBranchTakenFreq, 5437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking conditional branches"); 5537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(UncondBranchTakenFreq, 5637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking unconditional branches"); 5737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 58db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 59db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief A structure for storing a weighted edge. 60db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 61db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// This stores an edge and its weight, computed as the product of the 62db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// frequency that the starting block is entered with the probability of 63db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// a particular exit block. 64db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthstruct WeightedEdge { 65db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockFrequency EdgeFrequency; 66db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBasicBlock *From, *To; 67db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 68db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth bool operator<(const WeightedEdge &RHS) const { 69db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return EdgeFrequency < RHS.EdgeFrequency; 70db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 71db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 72db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 73db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 74db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain; 76db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief Type for our function-wide basic block -> block chain mapping. 77db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthtypedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 78db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 79db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 80db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 81db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief A chain of blocks which will be laid out contiguously. 82db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 83db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// This is the datastructure representing a chain of consecutive blocks that 84db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// are profitable to layout together in order to maximize fallthrough 85db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// probabilities. We also can use a block chain to represent a sequence of 86db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// basic blocks which have some external (correctness) requirement for 87db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// sequential layout. 88db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 89db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// Eventually, the block chains will form a directed graph over the function. 90db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// We provide an SCC-supporting-iterator in order to quicky build and walk the 91db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// SCCs of block chains within a function. 92db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 93db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// The block chains also have support for calculating and caching probability 94db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// information related to the chain itself versus other chains. This is used 95db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// for ranking during the final layout of block chains. 963071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain { 973071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief The sequence of blocks belonging to this chain. 98db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 993071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// This is the sequence of blocks for a particular chain. These will be laid 1003071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// out in-order within the function. 1013071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth SmallVector<MachineBasicBlock *, 4> Blocks; 102db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 103db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide basic block to block chain mapping. 104db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 105db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This is retained in each block chain to simplify the computation of child 106db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// block chains for SCC-formation and iteration. We store the edges to child 107db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// basic blocks, and map them back to their associated chains using this 108db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// structure. 109db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChainMapType &BlockToChain; 110db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1113071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthpublic: 112db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Construct a new BlockChain. 113db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 114db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This builds a new block chain representing a single basic block in the 115db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// function. It also registers itself as the chain that block participates 116db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// in with the BlockToChain mapping. 117db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) 118df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { 119db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BB && "Cannot create a chain with a null basic block"); 120db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain[BB] = this; 121db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 122db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1233071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Iterator over blocks within the chain. 1243071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator iterator; 1253071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1263071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Beginning of blocks within the chain. 1273071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth iterator begin() const { return Blocks.begin(); } 1283071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1293071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief End of blocks within the chain. 1303071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth iterator end() const { return Blocks.end(); } 1313071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1323071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Merge a block chain into this one. 133db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 134db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This routine merges a block chain into this one. It takes care of forming 135db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// a contiguous sequence of basic blocks, updating the edge list, and 136db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// updating the block -> chain mapping. It does not free or tear down the 137db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// old chain, but the old chain's block list is no longer valid. 1383071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth void merge(MachineBasicBlock *BB, BlockChain *Chain) { 1393071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB); 1403071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!Blocks.empty()); 1413071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1423071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Fast path in case we don't have a chain already. 1433071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth if (!Chain) { 1443071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!BlockToChain[BB]); 1453071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(BB); 1463071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[BB] = this; 1473071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return; 148db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 149db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1503071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB == *Chain->begin()); 1513071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(Chain->begin() != Chain->end()); 152db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1533071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Update the incoming blocks to point to this chain, and add them to the 1543071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // chain structure. 1553071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); 1563071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 1573071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(*BI); 1583071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain"); 1593071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[*BI] = this; 1603071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 161db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 162df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 163df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// \brief Count of predecessors within the loop currently being processed. 164df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// 165df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// This count is updated at each loop we process to represent the number of 166df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// in-loop predecessors of this chain. 167df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth unsigned LoopPredecessors; 168db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 169db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 170db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 171db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 172db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthclass MachineBlockPlacement : public MachineFunctionPass { 1733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief A typedef for a block filter set. 1743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet; 1753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 176db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the branch probability pass. 177db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 178db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 179db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 180db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 181db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1824a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the loop info. 1834a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth const MachineLoopInfo *MLI; 1844a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 185db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the target's instruction info. 186db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const TargetInstrInfo *TII; 187db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1884a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the target's lowering info. 1894a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth const TargetLowering *TLI; 1904a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 191db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Allocator and owner of BlockChain structures. 192db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 193db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// We build BlockChains lazily by merging together high probability BB 194db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// sequences acording to the "Algo2" in the paper mentioned at the top of 195db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// the file. To reduce malloc traffic, we allocate them using this slab-like 196db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// allocator, and destroy them after the pass completes. 197db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth SpecificBumpPtrAllocator<BlockChain> ChainAllocator; 198db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 199db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Function wide BasicBlock to BlockChain mapping. 200db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 201db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This mapping allows efficiently moving from any given basic block to the 202db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// BlockChain it participates in, if any. We use it to, among other things, 203db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// allow implicitly defining edges between chains as the existing edges 204db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// between basic blocks. 205db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain; 206db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 207df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth void markChainSuccessors(BlockChain &Chain, 208df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *LoopHeaderBB, 209df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &Blocks, 210df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth const BlockFilterSet *BlockFilter = 0); 2119fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, 2129fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BlockChain &Chain, 2139fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth const BlockFilterSet *BlockFilter); 214df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 215df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &Blocks, 216df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth const BlockFilterSet *BlockFilter = 0); 2173071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth void buildLoopChains(MachineFunction &F, MachineLoop &L); 2183071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth void buildCFGChains(MachineFunction &F); 2194a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth void AlignLoops(MachineFunction &F); 220db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 221db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthpublic: 222db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth static char ID; // Pass identification, replacement for typeid 223db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBlockPlacement() : MachineFunctionPass(ID) { 224db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); 225db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 226db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 227db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth bool runOnMachineFunction(MachineFunction &F); 228db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 229db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth void getAnalysisUsage(AnalysisUsage &AU) const { 230db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 231db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 2324a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AU.addRequired<MachineLoopInfo>(); 233db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 234db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 235db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 236db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const char *getPassName() const { return "Block Placement"; } 237db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 238db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 239db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 240db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthchar MachineBlockPlacement::ID = 0; 241db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 242db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 243db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 244db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 2454a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 246db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 247db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 248db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 249db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthFunctionPass *llvm::createMachineBlockPlacementPass() { 250db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return new MachineBlockPlacement(); 251db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 252db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2533071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#ifndef NDEBUG 2543071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the name of a MBB. 2553071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2563071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 2573071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthstatic std::string getBlockName(MachineBasicBlock *BB) { 2583071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2593071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2603071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber() 2613071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth << " (derived from LLVM BB '" << BB->getName() << "')"; 2623071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2633071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 2643071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 265db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2663071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the number of a MBB. 2673071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2683071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 2693071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthstatic std::string getBlockNum(MachineBasicBlock *BB) { 2703071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2713071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2723071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber(); 2733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 275db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 2763071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#endif 277db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 278729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// \brief Mark a chain's successors as having one fewer preds. 279729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// 280729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// When a chain is being merged into the "placed" chain, this routine will 281729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// quickly walk the successors of each block in the chain and mark them as 282729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// having one fewer active predecessor. It also adds any successors of this 283729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// chain which reach the zero-predecessor state to the worklist passed in. 284df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::markChainSuccessors( 285df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain, 286df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *LoopHeaderBB, 287df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 288df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth const BlockFilterSet *BlockFilter) { 289df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Walk all the blocks in this chain, marking their successors as having 290df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // a predecessor placed. 291df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); 292df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth CBI != CBE; ++CBI) { 293df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Add any successors for which this is the only un-placed in-loop 294df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // predecessor to the worklist as a viable candidate for CFG-neutral 295df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // placement. No subsequent placement of this block will violate the CFG 296df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // shape, so we get to use heuristics to choose a favorable placement. 297df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), 298df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SE = (*CBI)->succ_end(); 299df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SI != SE; ++SI) { 300df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 301df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 302df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &SuccChain = *BlockToChain[*SI]; 303df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Disregard edges within a fixed chain, or edges to the loop header. 304df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (&Chain == &SuccChain || *SI == LoopHeaderBB) 305df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 306df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 307df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // This is a cross-chain edge that is within the loop, so decrement the 308df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // loop predecessor count of the destination chain. 309df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) 310df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockWorkList.push_back(*SI); 311df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 312df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 313db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 314db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 3159fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \brief Select the best successor for a block. 3169fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3179fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// This looks across all successors of a particular block and attempts to 3189fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// select the "best" one to be the layout successor. It only considers direct 3199fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// successors which also pass the block filter. It will attempt to avoid 3209fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// breaking CFG structure, but cave and break such structures in the case of 3219fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// very hot successor edges. 3229fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3239fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \returns The best successor block found, or null if none are viable. 3249fd4e056e433b286f0e6576046ef2242365bfc38Chandler CarruthMachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 3259fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth MachineBasicBlock *BB, BlockChain &Chain, 3269fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth const BlockFilterSet *BlockFilter) { 3279fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth const BranchProbability HotProb(4, 5); // 80% 3289fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3299fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth MachineBasicBlock *BestSucc = 0; 3309fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BranchProbability BestProb = BranchProbability::getZero(); 3319fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 3329fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 3339fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth SE = BB->succ_end(); 3349fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth SI != SE; ++SI) { 3359fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 3369fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3379fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BlockChain &SuccChain = *BlockToChain[*SI]; 3389fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (&SuccChain == &Chain) { 3399fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); 3409fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3419fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 3429fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3439fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BranchProbability SuccProb = MBPI->getEdgeProbability(BB, *SI); 3449fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3459fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // Only consider successors which are either "hot", or wouldn't violate 3469fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // any CFG constraints. 3479fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (SuccChain.LoopPredecessors != 0 && SuccProb < HotProb) { 3489fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); 3499fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3509fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 3519fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3529fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 3539fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << " (prob)" 3549fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") 3559fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << "\n"); 3569fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (BestSucc && BestProb >= SuccProb) 3579fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3589fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BestSucc = *SI; 3599fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BestProb = SuccProb; 3609fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 3619fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth return BestSucc; 3629fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth} 3639fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 364df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::buildChain( 365df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *BB, 366df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain, 367df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 368df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth const BlockFilterSet *BlockFilter) { 3693071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB); 370df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[BB] == &Chain); 371df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(*Chain.begin() == BB); 372df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *LoopHeaderBB = BB; 373df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); 374df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BB = *llvm::prior(Chain.end()); 375df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (;;) { 376df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BB); 377df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[BB] == &Chain); 378df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(*llvm::prior(Chain.end()) == BB); 379df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 380df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Look for the best viable successor if there is one to place immediately 381df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // after this block. 3829fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); 3833071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 384df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // If an immediate successor isn't available, look for the best viable 385df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // block among those we've identified as not violating the loop's CFG at 386df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // this point. This won't be a fallthrough, but it will increase locality. 387df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!BestSucc) { 388df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockFrequency BestFreq; 389df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = BlockWorkList.begin(), 390df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth WBE = BlockWorkList.end(); 391df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth WBI != WBE; ++WBI) { 392df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockFilter && !BlockFilter->count(*WBI)) 393df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 394df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &SuccChain = *BlockToChain[*WBI]; 395df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (&SuccChain == &Chain) { 396df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*WBI) 397df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " -> Already merged!\n"); 398df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 399df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 400df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); 401df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 402df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); 403df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq 404df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " (freq)\n"); 405df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BestSucc && BestFreq >= CandidateFreq) 406df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 407df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BestSucc = *WBI; 408df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BestFreq = CandidateFreq; 409df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 410df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 411df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!BestSucc) { 412df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << "Finished forming chain for header block " 413df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << getBlockNum(*Chain.begin()) << "\n"); 4143071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return; 415df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 416db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 417df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Place this block, updating the datastructures to reflect its placement. 418df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &SuccChain = *BlockToChain[BestSucc]; 419df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << "Merging from " << getBlockNum(BB) 420df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " to " << getBlockNum(BestSucc) << "\n"); 421df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); 422df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth Chain.merge(BestSucc, &SuccChain); 423df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BB = *llvm::prior(Chain.end()); 424df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 4253071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 426db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 4273071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Forms basic block chains from the natural loop structures. 4283071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 4293071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// These chains are designed to preserve the existing *structure* of the code 4303071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// as much as possible. We can then stitch the chains together in a way which 4313071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// both preserves the topological structure and minimizes taken conditional 4323071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// branches. 433df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::buildLoopChains(MachineFunction &F, 434df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineLoop &L) { 4353071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // First recurse through any nested loops, building chains for those inner 4363071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // loops. 4373071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 4383071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 4393071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 440df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 441df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 4423071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 443df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // FIXME: This is a really lame way of walking the chains in the loop: we 444df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // walk the blocks, and use a set to prevent visiting a particular chain 445df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // twice. 446df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallPtrSet<BlockChain *, 4> UpdatedPreds; 447df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineLoop::block_iterator BI = L.block_begin(), 448df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BE = L.block_end(); 4493071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 450df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain = *BlockToChain[*BI]; 451df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!UpdatedPreds.insert(&Chain) || BI == L.block_begin()) 452df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 453df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 454df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 455df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 456df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 457df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[*BCI] == &Chain); 458df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 459df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 460df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 461df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 462df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 463df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 464df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 465df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 466df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 467df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 468df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockWorkList.push_back(*BI); 4693071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 470df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 471df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &LoopChain = *BlockToChain[L.getHeader()]; 472df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); 473df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 474df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 475df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (LoopChain.LoopPredecessors) 476df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block without its preds placed!\n" 477df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 478df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 479df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 480df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) 481df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!LoopBlockSet.erase(*BCI)) 482df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block not contained by the loop!\n" 483df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 484df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 485df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 486df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 487df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!LoopBlockSet.empty()) 488df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (SmallPtrSet<MachineBasicBlock *, 16>::iterator LBI = LoopBlockSet.begin(), LBE = LoopBlockSet.end(); 489df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth LBI != LBE; ++LBI) 490df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop contains blocks never placed into a chain!\n" 491df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 492df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 493df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*LBI) << "\n"; 494df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 4953071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 496db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 4973071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthvoid MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 498df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Ensure that every BB in the function has an associated chain to simplify 499df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // the assumptions of the remaining algorithm. 500df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 501df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockToChain[&*FI] = 502df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth new (ChainAllocator.Allocate()) BlockChain(BlockToChain, &*FI); 503df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 504df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Build any loop-based chains. 5053071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 5063071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth ++LI) 5073071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 5083071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 509df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 510db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 511df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallPtrSet<BlockChain *, 4> UpdatedPreds; 512df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 513df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *BB = &*FI; 514df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain = *BlockToChain[BB]; 515df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!UpdatedPreds.insert(&Chain)) 516db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth continue; 517df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 518df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 519df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 520df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 521df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[*BCI] == &Chain); 522df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 523df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 524df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 525df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockToChain[*PI] == &Chain) 526df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 527df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 528df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 529db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 530df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 531df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 532df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockWorkList.push_back(BB); 533db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 534db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 535df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &FunctionChain = *BlockToChain[&F.front()]; 536df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth buildChain(&F.front(), FunctionChain, BlockWorkList); 537df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 538df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 539df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 540df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSetType FunctionBlockSet; 541df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 542df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSet.insert(FI); 543df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 544df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = FunctionChain.begin(), BCE = FunctionChain.end(); 545df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) 546df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!FunctionBlockSet.erase(*BCI)) 547df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function chain contains a block not in the function!\n" 548df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 549df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 550df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!FunctionBlockSet.empty()) 551df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (SmallPtrSet<MachineBasicBlock *, 16>::iterator FBI = FunctionBlockSet.begin(), 552df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FBE = FunctionBlockSet.end(); FBI != FBE; ++FBI) 553df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function contains blocks never placed into a chain!\n" 554df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*FBI) << "\n"; 555df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 556df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 557df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Splice the blocks into place. 558df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineFunction::iterator InsertPos = F.begin(); 559db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 560df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BI = FunctionChain.begin(), BE = FunctionChain.end(); 561df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BI != BE; ++BI) { 562df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 563df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : " ... ") 564df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << getBlockName(*BI) << "\n"); 565df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (InsertPos != MachineFunction::iterator(*BI)) 566df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.splice(InsertPos, *BI); 567df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth else 568df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++InsertPos; 569df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 570df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Update the terminator of the previous block. 571df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BI == FunctionChain.begin()) 572df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 573df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 574df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 575db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // FIXME: It would be awesome of updateTerminator would just return rather 576db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // than assert when the branch cannot be analyzed in order to remove this 577db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // boiler plate. 578db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth Cond.clear(); 579db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 580df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) 581df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PrevBB->updateTerminator(); 582db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 583df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 584df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Fixup the last block. 585df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth Cond.clear(); 586df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 587df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 588df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.back().updateTerminator(); 589db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 590db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 5914a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth/// \brief Recursive helper to align a loop and any nested loops. 5924a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruthstatic void AlignLoop(MachineFunction &F, MachineLoop *L, unsigned Align) { 5934a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth // Recurse through nested loops. 5944a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) 5954a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AlignLoop(F, *I, Align); 5964a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 5974a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth L->getTopBlock()->setAlignment(Align); 5984a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth} 5994a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 6004a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth/// \brief Align loop headers to target preferred alignments. 6014a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruthvoid MachineBlockPlacement::AlignLoops(MachineFunction &F) { 6024a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth if (F.getFunction()->hasFnAttr(Attribute::OptimizeForSize)) 6034a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; 6044a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 6054a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth unsigned Align = TLI->getPrefLoopAlignment(); 6064a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth if (!Align) 6074a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; // Don't care about loop alignment. 6084a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 6094a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I) 6104a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AlignLoop(F, *I, Align); 6114a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth} 6124a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 613db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthbool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 614db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // Check for single-block functions and skip them. 615db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth if (llvm::next(F.begin()) == F.end()) 616db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return false; 617db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 618db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 619db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 6204a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth MLI = &getAnalysis<MachineLoopInfo>(); 621db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth TII = F.getTarget().getInstrInfo(); 6224a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth TLI = F.getTarget().getTargetLowering(); 623db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BlockToChain.empty()); 624db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 6253071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildCFGChains(F); 6264a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AlignLoops(F); 627db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 628db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain.clear(); 629db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 630db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // We always return true as we have no way to track whether the final order 631db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // differs from the original order. 632db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return true; 633db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 63437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 63537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthnamespace { 63637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// \brief A pass to compute block placement statistics. 63737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// 63837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// A separate pass to compute interesting statistics for evaluating block 63937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// placement. This is separate from the actual placement pass so that they can 64037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// be computed in the absense of any placement transformations or when using 64137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// alternative placement strategies. 64237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthclass MachineBlockPlacementStats : public MachineFunctionPass { 64337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the branch probability pass. 64437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 64537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 64637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 64737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 64837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 64937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthpublic: 65037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth static char ID; // Pass identification, replacement for typeid 65137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineBlockPlacementStats() : MachineFunctionPass(ID) { 65237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 65337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 65437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 65537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth bool runOnMachineFunction(MachineFunction &F); 65637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 65737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth void getAnalysisUsage(AnalysisUsage &AU) const { 65837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 65937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 66037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.setPreservesAll(); 66137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 66237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 66337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 66437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const char *getPassName() const { return "Block Placement Stats"; } 66537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth}; 66637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 66737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 66837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthchar MachineBlockPlacementStats::ID = 0; 66937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 67037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 67137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 67237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 67337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 67437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 67537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 67637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthFunctionPass *llvm::createMachineBlockPlacementStatsPass() { 67737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return new MachineBlockPlacementStats(); 67837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 67937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 68037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthbool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 68137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Check for single-block functions and skip them. 68237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth if (llvm::next(F.begin()) == F.end()) 68337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 68437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 68537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 68637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 68737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 68837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 68937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 69037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 69137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : NumUncondBranches; 69237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 69337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : UncondBranchTakenFreq; 69437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 69537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SE = I->succ_end(); 69637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SI != SE; ++SI) { 69737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Skip if this successor is a fallthrough. 69837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth if (I->isLayoutSuccessor(*SI)) 69937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth continue; 70037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 70137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 70237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth ++NumBranches; 70337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BranchTakenFreq += EdgeFreq.getFrequency(); 70437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 70537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 70637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 70737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 70837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 70937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 710