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 14d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer// a topological ordering of basic blocks) in the absence 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 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 334a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 34db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 35db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 36db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunction.h" 37db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 384a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 394a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineModuleInfo.h" 40db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Support/Allocator.h" 4107706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotem#include "llvm/Support/CommandLine.h" 423071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#include "llvm/Support/Debug.h" 43db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Target/TargetInstrInfo.h" 444a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/Target/TargetLowering.h" 45db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include <algorithm> 46db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthusing namespace llvm; 47db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "block-placement2" 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 5037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumCondBranches, "Number of conditional branches"); 5137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumUncondBranches, "Number of uncondittional branches"); 5237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(CondBranchTakenFreq, 5337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking conditional branches"); 5437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(UncondBranchTakenFreq, 5537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking unconditional branches"); 5637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 5707706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotemstatic cl::opt<unsigned> AlignAllBlock("align-all-blocks", 5807706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotem cl::desc("Force the alignment of all " 5907706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotem "blocks in the function."), 6007706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotem cl::init(0), cl::Hidden); 6107706e5506fb1bf494667e9fd16795b6c0b4d0fbNadav Rotem 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// FIXME: Find a good default for this flag and remove the flag. 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<unsigned> 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesExitBlockBias("block-placement-exit-block-bias", 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Block frequency percentage a loop exit block needs " 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "over the original exit to be considered the new exit."), 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::init(0), cl::Hidden); 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 69db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 703071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain; 71db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief Type for our function-wide basic block -> block chain mapping. 72db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthtypedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 73db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 74db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 75db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 76db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief A chain of blocks which will be laid out contiguously. 77db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 78db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// This is the datastructure representing a chain of consecutive blocks that 79db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// are profitable to layout together in order to maximize fallthrough 80c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// probabilities and code locality. We also can use a block chain to represent 81c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// a sequence of basic blocks which have some external (correctness) 82c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// requirement for sequential layout. 83db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 84c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// Chains can be built around a single basic block and can be merged to grow 85c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// them. They participate in a block-to-chain mapping, which is updated 86c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// automatically as chains are merged together. 873071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain { 883071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief The sequence of blocks belonging to this chain. 89db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 903071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// This is the sequence of blocks for a particular chain. These will be laid 913071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// out in-order within the function. 923071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth SmallVector<MachineBasicBlock *, 4> Blocks; 93db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 94db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide basic block to block chain mapping. 95db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 96db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This is retained in each block chain to simplify the computation of child 97db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// block chains for SCC-formation and iteration. We store the edges to child 98db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// basic blocks, and map them back to their associated chains using this 99db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// structure. 100db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChainMapType &BlockToChain; 101db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1023071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthpublic: 103db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Construct a new BlockChain. 104db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 105db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This builds a new block chain representing a single basic block in the 106db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// function. It also registers itself as the chain that block participates 107db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// in with the BlockToChain mapping. 108db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) 109df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { 110db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BB && "Cannot create a chain with a null basic block"); 111db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain[BB] = this; 112db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 113db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1143071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Iterator over blocks within the chain. 11570daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator; 1163071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1173071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Beginning of blocks within the chain. 11870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth iterator begin() { return Blocks.begin(); } 1193071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1203071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief End of blocks within the chain. 12170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth iterator end() { return Blocks.end(); } 1223071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1233071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Merge a block chain into this one. 124db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 125db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This routine merges a block chain into this one. It takes care of forming 126db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// a contiguous sequence of basic blocks, updating the edge list, and 127db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// updating the block -> chain mapping. It does not free or tear down the 128db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// old chain, but the old chain's block list is no longer valid. 129d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void merge(MachineBasicBlock *BB, BlockChain *Chain) { 1303071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB); 1313071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!Blocks.empty()); 1323071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1333071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Fast path in case we don't have a chain already. 1343071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth if (!Chain) { 1353071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!BlockToChain[BB]); 1363071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(BB); 1373071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[BB] = this; 1383071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return; 139db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 140db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1413071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB == *Chain->begin()); 1423071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(Chain->begin() != Chain->end()); 143db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1443071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Update the incoming blocks to point to this chain, and add them to the 1453071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // chain structure. 1463071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); 1473071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 1483071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(*BI); 1493071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain"); 1503071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[*BI] = this; 1513071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 152db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 153df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 1546313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth#ifndef NDEBUG 1556313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth /// \brief Dump the blocks in this chain. 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVM_DUMP_METHOD void dump() { 1576313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth for (iterator I = begin(), E = end(); I != E; ++I) 1586313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth (*I)->dump(); 1596313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth } 1606313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth#endif // NDEBUG 1616313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth 162df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// \brief Count of predecessors within the loop currently being processed. 163df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// 164df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// This count is updated at each loop we process to represent the number of 165df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// in-loop predecessors of this chain. 166df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth unsigned LoopPredecessors; 167db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 168db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 169db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 170db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 171db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthclass MachineBlockPlacement : public MachineFunctionPass { 1723071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief A typedef for a block filter set. 1733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet; 1743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 175db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the branch probability pass. 176db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 177db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 178db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 179db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 180db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1814a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the loop info. 1824a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth const MachineLoopInfo *MLI; 1834a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 184db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the target's instruction info. 185db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const TargetInstrInfo *TII; 186db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1874a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the target's lowering info. 18869e42dbd006c0afb732067ece7327988b1e24c01Benjamin Kramer const TargetLoweringBase *TLI; 1894a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 190db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Allocator and owner of BlockChain structures. 191db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 192c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// We build BlockChains lazily while processing the loop structure of 193c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// a function. To reduce malloc traffic, we allocate them using this 194c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// slab-like allocator, and destroy them after the pass completes. An 195c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// important guarantee is that this allocator produces stable pointers to 196c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// the chains. 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 207d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void markChainSuccessors(BlockChain &Chain, 208d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *LoopHeaderBB, 209b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockFilterSet *BlockFilter = nullptr); 211d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, 212d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, 213d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 214f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth MachineBasicBlock *selectBestCandidateBlock( 215d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 216d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 2173273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineBasicBlock *getFirstUnplacedBlock( 2183273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction &F, 2193273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth const BlockChain &PlacedChain, 2203273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction::iterator &PrevUnplacedBlockIt, 221d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 222df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 223b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockFilterSet *BlockFilter = nullptr); 225e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *findBestLoopTop(MachineLoop &L, 226e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth const BlockFilterSet &LoopBlockSet); 22770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth MachineBasicBlock *findBestLoopExit(MachineFunction &F, 22870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth MachineLoop &L, 22970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth const BlockFilterSet &LoopBlockSet); 230d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void buildLoopChains(MachineFunction &F, MachineLoop &L); 23116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, 23216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth const BlockFilterSet &LoopBlockSet); 2333071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth void buildCFGChains(MachineFunction &F); 234db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 235db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthpublic: 236db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth static char ID; // Pass identification, replacement for typeid 237db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBlockPlacement() : MachineFunctionPass(ID) { 238db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); 239db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 240db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &F) override; 242db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 244db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 245db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 2464a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AU.addRequired<MachineLoopInfo>(); 247db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 248db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 249db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 250db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 251db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 252db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthchar MachineBlockPlacement::ID = 0; 2531dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; 254db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 255db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 256db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 257db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 2584a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 259db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 260db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 261db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2623071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#ifndef NDEBUG 2633071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the name of a MBB. 2643071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2653071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 266d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszakstatic std::string getBlockName(MachineBasicBlock *BB) { 2673071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2683071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2693071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber() 2703071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth << " (derived from LLVM BB '" << BB->getName() << "')"; 2713071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2723071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 2733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 274db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the number of a MBB. 2763071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2773071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 278d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszakstatic std::string getBlockNum(MachineBasicBlock *BB) { 2793071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2803071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2813071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber(); 2823071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2833071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 284db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 2853071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#endif 286db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 287729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// \brief Mark a chain's successors as having one fewer preds. 288729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// 289729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// When a chain is being merged into the "placed" chain, this routine will 290729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// quickly walk the successors of each block in the chain and mark them as 291729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// having one fewer active predecessor. It also adds any successors of this 292729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// chain which reach the zero-predecessor state to the worklist passed in. 293df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::markChainSuccessors( 294d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, 295d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *LoopHeaderBB, 296df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 297d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 298df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Walk all the blocks in this chain, marking their successors as having 299df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // a predecessor placed. 300df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); 301df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth CBI != CBE; ++CBI) { 302df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Add any successors for which this is the only un-placed in-loop 303df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // predecessor to the worklist as a viable candidate for CFG-neutral 304df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // placement. No subsequent placement of this block will violate the CFG 305df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // shape, so we get to use heuristics to choose a favorable placement. 306df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), 307df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SE = (*CBI)->succ_end(); 308df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SI != SE; ++SI) { 309df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 310df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 311d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*SI]; 312df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Disregard edges within a fixed chain, or edges to the loop header. 313df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (&Chain == &SuccChain || *SI == LoopHeaderBB) 314df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 315df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 316df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // This is a cross-chain edge that is within the loop, so decrement the 317df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // loop predecessor count of the destination chain. 318df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) 319a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*SuccChain.begin()); 320df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 321df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 322db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 323db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 3249fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \brief Select the best successor for a block. 3259fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3269fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// This looks across all successors of a particular block and attempts to 3279fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// select the "best" one to be the layout successor. It only considers direct 3289fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// successors which also pass the block filter. It will attempt to avoid 3299fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// breaking CFG structure, but cave and break such structures in the case of 3309fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// very hot successor edges. 3319fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3329fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \returns The best successor block found, or null if none are viable. 3339fd4e056e433b286f0e6576046ef2242365bfc38Chandler CarruthMachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 334d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *BB, BlockChain &Chain, 335d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 3369fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth const BranchProbability HotProb(4, 5); // 80% 3379fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 338dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *BestSucc = nullptr; 339340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // FIXME: Due to the performance of the probability and weight routines in 340340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // the MBPI analysis, we manually compute probabilities using the edge 341340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // weights. This is suboptimal as it means that the somewhat subtle 342340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // definition of edge weight semantics is encoded here as well. We should 343d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // improve the MBPI interface to efficiently support query patterns such as 344340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // this. 345340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t BestWeight = 0; 346340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t WeightScale = 0; 347340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); 3489fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 349d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 350d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SE = BB->succ_end(); 351d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SI != SE; ++SI) { 3529fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 3539fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 354d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*SI]; 3559fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (&SuccChain == &Chain) { 3569fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); 3579fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3589fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 35903300ecaee3ef853669582bcadec34170dbf515fChandler Carruth if (*SI != *SuccChain.begin()) { 36003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n"); 36103300ecaee3ef853669582bcadec34170dbf515fChandler Carruth continue; 36203300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 3639fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 364340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI); 365340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 3669fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3679fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // Only consider successors which are either "hot", or wouldn't violate 3689fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // any CFG constraints. 369b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (SuccChain.LoopPredecessors != 0) { 370b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (SuccProb < HotProb) { 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " (prob) (CFG conflict)\n"); 373b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 374b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 375b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth 376b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth // Make sure that a hot successor doesn't have a globally more important 377b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth // predecessor. 378b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BlockFrequency CandidateEdgeFreq 379b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth = MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl(); 380b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth bool BadCFGConflict = false; 381b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(), 382b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth PE = (*SI)->pred_end(); 383b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth PI != PE; ++PI) { 384b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) || 385d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockToChain[*PI] == &Chain) 386b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 387b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BlockFrequency PredEdgeFreq 388b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI); 389b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (PredEdgeFreq >= CandidateEdgeFreq) { 390b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BadCFGConflict = true; 391b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth break; 392b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 393b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 394b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (BadCFGConflict) { 39536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 39636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << " (prob) (non-cold CFG conflict)\n"); 397b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 398b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 3999fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 4009fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 4019fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 4029fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << " (prob)" 4039fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") 4049fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << "\n"); 405340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth if (BestSucc && BestWeight >= SuccWeight) 4069fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 4079fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BestSucc = *SI; 408340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth BestWeight = SuccWeight; 4099fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 4109fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth return BestSucc; 4119fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth} 4129fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 413f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// \brief Select the best block from a worklist. 414f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// 415f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// This looks through the provided worklist as a list of candidate basic 416f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// blocks and select the most profitable one to place. The definition of 417f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// profitable only really makes sense in the context of a loop. This returns 418f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// the most frequently visited block in the worklist, which in the case of 419f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// a loop, is the one most desirable to be physically close to the rest of the 420f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// loop body in order to improve icache behavior. 421f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// 422f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// \returns The best block found, or null if none are viable. 423f3fc0050abc1698504cbaede7766c4180c076928Chandler CarruthMachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( 424d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 425d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 426fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // Once we need to walk the worklist looking for a candidate, cleanup the 427fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // worklist of already placed entries. 428fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // FIXME: If this shows up on profiles, it could be folded (at the cost of 429fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // some code complexity) into the loop below. 430fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(), 43136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines [&](MachineBasicBlock *BB) { 43236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return BlockToChain.lookup(BB) == &Chain; 43336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }), 434fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth WorkList.end()); 435fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *BestBlock = nullptr; 437f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth BlockFrequency BestFreq; 438f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = WorkList.begin(), 439f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth WBE = WorkList.end(); 440f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth WBI != WBE; ++WBI) { 441d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*WBI]; 442f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth if (&SuccChain == &Chain) { 443f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*WBI) 444f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth << " -> Already merged!\n"); 445f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth continue; 446f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth } 447f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); 448f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth 449f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); 45036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> "; 45136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MBFI->printBlockFreq(dbgs(), CandidateFreq) << " (freq)\n"); 452f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth if (BestBlock && BestFreq >= CandidateFreq) 453f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth continue; 454f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth BestBlock = *WBI; 455f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth BestFreq = CandidateFreq; 456f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth } 457f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth return BestBlock; 458f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth} 459f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth 460b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth/// \brief Retrieve the first unplaced basic block. 461b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth/// 462b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth/// This routine is called when we are unable to use the CFG to walk through 463b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth/// all of the basic blocks and form a chain due to unnatural loops in the CFG. 4643273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth/// We walk through the function's blocks in order, starting from the 4653273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth/// LastUnplacedBlockIt. We update this iterator on each call to avoid 4663273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth/// re-scanning the entire sequence on repeated calls to this routine. 467b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler CarruthMachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( 4683273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction &F, const BlockChain &PlacedChain, 4693273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction::iterator &PrevUnplacedBlockIt, 470d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 4713273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E; 4723273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth ++I) { 4733273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth if (BlockFilter && !BlockFilter->count(I)) 4743273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth continue; 475d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak if (BlockToChain[I] != &PlacedChain) { 4763273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth PrevUnplacedBlockIt = I; 47747fb954f7437250eda152ed4165af5ac1c0ec366Chandler Carruth // Now select the head of the chain to which the unplaced block belongs 47847fb954f7437250eda152ed4165af5ac1c0ec366Chandler Carruth // as the block to place. This will force the entire chain to be placed, 47947fb954f7437250eda152ed4165af5ac1c0ec366Chandler Carruth // and satisfies the requirements of merging chains. 480d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak return *BlockToChain[I]->begin(); 481b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth } 482b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth } 483dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 484b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth} 485b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth 486df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::buildChain( 487df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *BB, 488df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain, 489df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 490d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 4913071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB); 492d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak assert(BlockToChain[BB] == &Chain); 4933273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction &F = *BB->getParent(); 4943273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction::iterator PrevUnplacedBlockIt = F.begin(); 495b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth 496df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *LoopHeaderBB = BB; 497df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); 49836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BB = *std::prev(Chain.end()); 499df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (;;) { 500df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BB); 501d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak assert(BlockToChain[BB] == &Chain); 50236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(*std::prev(Chain.end()) == BB); 5036527ecc9189058b762c699521462956995f59dd8Chandler Carruth 50403300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // Look for the best viable successor if there is one to place immediately 50503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // after this block. 50674b4762234eaeff94058999758a83acc0b54cba6Duncan Sands MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); 5073071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 508df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // If an immediate successor isn't available, look for the best viable 509df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // block among those we've identified as not violating the loop's CFG at 510df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // this point. This won't be a fallthrough, but it will increase locality. 511f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth if (!BestSucc) 512f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); 513f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth 514df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!BestSucc) { 5153273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, 5163273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth BlockFilter); 517b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth if (!BestSucc) 518b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth break; 519b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth 520b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " 521b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth "layout successor until the CFG reduces\n"); 522df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 523db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 524df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Place this block, updating the datastructures to reflect its placement. 525d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[BestSucc]; 526b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth // Zero out LoopPredecessors for the successor we're about to merge in case 527b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth // we selected a successor that didn't fit naturally into the CFG. 528b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth SuccChain.LoopPredecessors = 0; 529df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << "Merging from " << getBlockNum(BB) 530df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " to " << getBlockNum(BestSucc) << "\n"); 531df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); 532df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth Chain.merge(BestSucc, &SuccChain); 53336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BB = *std::prev(Chain.end()); 534feb468ab24a9e85b4d27faa6badfb57a2414610cJakub Staszak } 535b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth 536b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth DEBUG(dbgs() << "Finished forming chain for header block " 537b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth << getBlockNum(*Chain.begin()) << "\n"); 5383071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 539db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 540fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth/// \brief Find the best loop top block for layout. 5412e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth/// 542e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// Look for a block which is strictly better than the loop header for laying 543e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// out at the top of the loop. This looks for one and only one pattern: 544e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// a latch block with no conditional exit. This block will cause a conditional 545e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// jump around it or will be the bottom of the loop if we lay it out in place, 546e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// but if it it doesn't end up at the bottom of the loop for any reason, 547e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// rotation alone won't fix it. Because such a block will always result in an 548e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// unconditional jump (for the backedge) rotating it in front of the loop 549e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// header is always profitable. 550e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler CarruthMachineBasicBlock * 551e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler CarruthMachineBlockPlacement::findBestLoopTop(MachineLoop &L, 552e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth const BlockFilterSet &LoopBlockSet) { 553e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // Check that the header hasn't been fused with a preheader block due to 554e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // crazy branches. If it has, we need to start with the header at the top to 555e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // prevent pulling the preheader into the loop body. 556e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 557e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (!LoopBlockSet.count(*HeaderChain.begin())) 558e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth return L.getHeader(); 559e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 560e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth DEBUG(dbgs() << "Finding best loop top for: " 561e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth << getBlockName(L.getHeader()) << "\n"); 562e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 563e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BlockFrequency BestPredFreq; 564dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *BestPred = nullptr; 565e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(), 566e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth PE = L.getHeader()->pred_end(); 567e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth PI != PE; ++PI) { 568e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *Pred = *PI; 569e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (!LoopBlockSet.count(Pred)) 570e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth continue; 571e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", " 57236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << Pred->succ_size() << " successors, "; 57336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MBFI->printBlockFreq(dbgs(), Pred) << " freq\n"); 574e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (Pred->succ_size() > 1) 575e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth continue; 576e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 577e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); 578e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (!BestPred || PredFreq > BestPredFreq || 579e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth (!(PredFreq < BestPredFreq) && 580e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth Pred->isLayoutSuccessor(L.getHeader()))) { 581e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BestPred = Pred; 582e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BestPredFreq = PredFreq; 583e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth } 584e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth } 585e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 586e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // If no direct predecessor is fine, just use the loop header. 587e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (!BestPred) 588e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth return L.getHeader(); 589e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 590e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // Walk backwards through any straight line of predecessors. 591e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth while (BestPred->pred_size() == 1 && 592e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth (*BestPred->pred_begin())->succ_size() == 1 && 593e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth *BestPred->pred_begin() != L.getHeader()) 594e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BestPred = *BestPred->pred_begin(); 595e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 596e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); 597e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth return BestPred; 598e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth} 599e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 600e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 601e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// \brief Find the best loop exiting block for layout. 602e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth/// 603fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth/// This routine implements the logic to analyze the loop looking for the best 604fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth/// block to layout at the top of the loop. Typically this is done to maximize 605fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth/// fallthrough opportunities. 606fac1305da162259d17baa6700ecb5d148b86ef08Chandler CarruthMachineBasicBlock * 60770daea90afc167a010a1851defda01d7e0eb45ebChandler CarruthMachineBlockPlacement::findBestLoopExit(MachineFunction &F, 60870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth MachineLoop &L, 60970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth const BlockFilterSet &LoopBlockSet) { 61045fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // We don't want to layout the loop linearly in all cases. If the loop header 61145fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // is just a normal basic block in the loop, we want to look for what block 61245fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // within the loop is the best one to layout at the top. However, if the loop 61345fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // header has be pre-merged into a chain due to predecessors not having 61445fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // analyzable branches, *and* the predecessor it is merged with is *not* part 61545fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // of the loop, rotating the header into the middle of the loop will create 61645fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // a non-contiguous range of blocks which is Very Bad. So start with the 61745fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth // header and only rotate if safe. 61845fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; 61945fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth if (!LoopBlockSet.count(*HeaderChain.begin())) 620dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 62145fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth 622fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BlockFrequency BestExitEdgeFreq; 62370daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth unsigned BestExitLoopDepth = 0; 624dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *ExitingBB = nullptr; 62551901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // If there are exits to outer loops, loop rotation can severely limit 62651901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // fallthrough opportunites unless it selects such an exit. Keep a set of 62751901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // blocks where rotating to exit with that block will reach an outer loop. 62851901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; 62951901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth 630fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth DEBUG(dbgs() << "Finding best loop exit for: " 631fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth << getBlockName(L.getHeader()) << "\n"); 632fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth for (MachineLoop::block_iterator I = L.block_begin(), 633fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth E = L.block_end(); 6342e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth I != E; ++I) { 635d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain = *BlockToChain[*I]; 636fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Ensure that this block is at the end of a chain; otherwise it could be 637fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // mid-way through an inner loop or a successor of an analyzable branch. 63836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (*I != *std::prev(Chain.end())) 6392e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth continue; 6402e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth 641fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Now walk the successors. We need to establish whether this has a viable 642fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // exiting successor and whether it has a viable non-exiting successor. 643fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // We store the old exiting state and restore it if a viable looping 644fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // successor isn't found. 645fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth MachineBasicBlock *OldExitingBB = ExitingBB; 646fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; 64770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth bool HasLoopingSucc = false; 648fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // FIXME: Due to the performance of the probability and weight routines in 64970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // the MBPI analysis, we use the internal weights and manually compute the 65070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // probabilities to avoid quadratic behavior. 651fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth uint32_t WeightScale = 0; 652fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); 653fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), 654fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth SE = (*I)->succ_end(); 6552eb5a744b18d429928751b06e205cbb88f668ae7Chandler Carruth SI != SE; ++SI) { 656fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if ((*SI)->isLandingPad()) 657fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth continue; 658fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (*SI == *I) 659fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth continue; 660d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*SI]; 661fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Don't split chains, either this chain or the successor's chain. 66270daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (&Chain == &SuccChain) { 66370daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 664fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth << getBlockName(*SI) << " (chain conflict)\n"); 665fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth continue; 666fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth } 667fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 668fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); 669fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (LoopBlockSet.count(*SI)) { 670fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " 671fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth << getBlockName(*SI) << " (" << SuccWeight << ")\n"); 67270daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth HasLoopingSucc = true; 673fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth continue; 674fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth } 675fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 67670daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth unsigned SuccLoopDepth = 0; 67770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) { 67870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth SuccLoopDepth = ExitLoop->getLoopDepth(); 67970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (ExitLoop->contains(&L)) 68070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BlocksExitingToOuterLoop.insert(*I); 68170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth } 68270daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth 683fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 684fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; 685fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " 68670daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth << getBlockName(*SI) << " [L:" << SuccLoopDepth 68736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << "] ("; 68836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MBFI->printBlockFreq(dbgs(), ExitEdgeFreq) << ")\n"); 68936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Note that we bias this toward an existing layout successor to retain 69036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // incoming order in the absence of better information. The exit must have 69136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // a frequency higher than the current exit before we consider breaking 69236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the layout. 69336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BranchProbability Bias(100 - ExitBlockBias, 100); 69470daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || 69570daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth ExitEdgeFreq > BestExitEdgeFreq || 696fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ((*I)->isLayoutSuccessor(*SI) && 69736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !(ExitEdgeFreq < BestExitEdgeFreq * Bias))) { 698fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BestExitEdgeFreq = ExitEdgeFreq; 699fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ExitingBB = *I; 7002eb5a744b18d429928751b06e205cbb88f668ae7Chandler Carruth } 7012e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth } 702fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 703fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Restore the old exiting state, no viable looping successor was found. 70470daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (!HasLoopingSucc) { 705fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ExitingBB = OldExitingBB; 706fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BestExitEdgeFreq = OldBestExitEdgeFreq; 7072eb5a744b18d429928751b06e205cbb88f668ae7Chandler Carruth continue; 708fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth } 7092e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth } 71070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // Without a candidate exiting block or with only a single block in the 711fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // loop, just use the loop header to layout the loop. 712fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (!ExitingBB || L.getNumBlocks() == 1) 713dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 714fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 71551901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // Also, if we have exit blocks which lead to outer loops but didn't select 71651901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // one of them as the exiting block we are rotating toward, disable loop 71751901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // rotation altogether. 71851901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth if (!BlocksExitingToOuterLoop.empty() && 71951901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth !BlocksExitingToOuterLoop.count(ExitingBB)) 720dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 72151901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth 722fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 72370daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth return ExitingBB; 7242e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth} 7252e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth 72616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// \brief Attempt to rotate an exiting block to the bottom of the loop. 72716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// 72816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// Once we have built a chain, try to rotate it to line up the hot exit block 72916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// with fallthrough out of the loop if doing so doesn't introduce unnecessary 73016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// branches. For example, if the loop has fallthrough into its header and out 73116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// of its bottom already, don't rotate it. 73216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruthvoid MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, 73316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth MachineBasicBlock *ExitingBB, 73416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth const BlockFilterSet &LoopBlockSet) { 73516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!ExitingBB) 73616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 73716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 73816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth MachineBasicBlock *Top = *LoopChain.begin(); 73916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth bool ViableTopFallthrough = false; 74016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), 74116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth PE = Top->pred_end(); 74216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth PI != PE; ++PI) { 74316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain *PredChain = BlockToChain[*PI]; 74416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!LoopBlockSet.count(*PI) && 74536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (!PredChain || *PI == *std::prev(PredChain->end()))) { 74616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth ViableTopFallthrough = true; 74716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth break; 74816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 74916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 75016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 75116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // If the header has viable fallthrough, check whether the current loop 75216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // bottom is a viable exiting block. If so, bail out as rotating will 75316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // introduce an unnecessary branch. 75416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (ViableTopFallthrough) { 75536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock *Bottom = *std::prev(LoopChain.end()); 75616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), 75716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth SE = Bottom->succ_end(); 75816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth SI != SE; ++SI) { 75916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain *SuccChain = BlockToChain[*SI]; 76016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!LoopBlockSet.count(*SI) && 76116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth (!SuccChain || *SI == *SuccChain->begin())) 76216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 76316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 76416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 76516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 76616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain::iterator ExitIt = std::find(LoopChain.begin(), LoopChain.end(), 76716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth ExitingBB); 76816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (ExitIt == LoopChain.end()) 76916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 77016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 77136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end()); 77216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth} 77316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 7743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Forms basic block chains from the natural loop structures. 7753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 7763071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// These chains are designed to preserve the existing *structure* of the code 7773071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// as much as possible. We can then stitch the chains together in a way which 7783071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// both preserves the topological structure and minimizes taken conditional 7793071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// branches. 780df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::buildLoopChains(MachineFunction &F, 781d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineLoop &L) { 7823071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // First recurse through any nested loops, building chains for those inner 7833071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // loops. 7843071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 7853071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 7863071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 787df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 788df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 789fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 790e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // First check to see if there is an obviously preferable top block for the 791e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // loop. This will default to the header, but may end up as one of the 792e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // predecessors to the header if there is one which will result in strictly 793e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // fewer branches in the loop body. 794e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); 795e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 796e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // If we selected just the header for the loop top, look for a potentially 797e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // profitable exit block in the event that rotating the loop can eliminate 798e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // branches by placing an exit edge at the bottom. 799dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *ExitingBB = nullptr; 800e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (LoopTop == L.getHeader()) 801e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth ExitingBB = findBestLoopExit(F, L, LoopBlockSet); 802e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 803e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BlockChain &LoopChain = *BlockToChain[LoopTop]; 8043071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 805df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // FIXME: This is a really lame way of walking the chains in the loop: we 806df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // walk the blocks, and use a set to prevent visiting a particular chain 807df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // twice. 808d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SmallPtrSet<BlockChain *, 4> UpdatedPreds; 809feb468ab24a9e85b4d27faa6badfb57a2414610cJakub Staszak assert(LoopChain.LoopPredecessors == 0); 810feb468ab24a9e85b4d27faa6badfb57a2414610cJakub Staszak UpdatedPreds.insert(&LoopChain); 811df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineLoop::block_iterator BI = L.block_begin(), 812df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BE = L.block_end(); 8133071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 814d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain = *BlockToChain[*BI]; 815fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (!UpdatedPreds.insert(&Chain)) 816df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 817df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 818df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 819df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 820df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 821d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak assert(BlockToChain[*BCI] == &Chain); 822df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 823df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 824df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 825d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 826df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 827df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 828df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 829df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 830df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 831df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 832a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*Chain.begin()); 8333071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 834df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 835e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); 83616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth rotateLoop(LoopChain, ExitingBB, LoopBlockSet); 837df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 838df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 83910252db69bdddb445e53892b388fbe5921114b86Chandler Carruth // Crash at the end so we get all of the debugging output first. 84010252db69bdddb445e53892b388fbe5921114b86Chandler Carruth bool BadLoop = false; 84110252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (LoopChain.LoopPredecessors) { 84210252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadLoop = true; 843df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block without its preds placed!\n" 844df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 845df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 84610252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 847df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 84870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BCI != BCE; ++BCI) { 84970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth dbgs() << " ... " << getBlockName(*BCI) << "\n"; 85010252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!LoopBlockSet.erase(*BCI)) { 851bc83fcd9bd95f8eff83cd5ad77b0aa5312d8a6a5Chandler Carruth // We don't mark the loop as bad here because there are real situations 852bc83fcd9bd95f8eff83cd5ad77b0aa5312d8a6a5Chandler Carruth // where this can occur. For example, with an unanalyzable fallthrough 853598894ff2547aaa0a32ded145063f3bfe042f620Chandler Carruth // from a loop block to a non-loop block or vice versa. 854df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block not contained by the loop!\n" 855df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 856df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 857df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 85810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 85970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth } 860df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 86110252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!LoopBlockSet.empty()) { 86210252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadLoop = true; 863c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), 864c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth LBE = LoopBlockSet.end(); 865df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth LBI != LBE; ++LBI) 866df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop contains blocks never placed into a chain!\n" 867df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 868df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 869df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*LBI) << "\n"; 87010252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 87110252db69bdddb445e53892b388fbe5921114b86Chandler Carruth assert(!BadLoop && "Detected problems with the placement of this loop."); 872df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 8733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 874db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 8753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthvoid MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 876df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Ensure that every BB in the function has an associated chain to simplify 877df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // the assumptions of the remaining algorithm. 87803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 87903300ecaee3ef853669582bcadec34170dbf515fChandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 88003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineBasicBlock *BB = FI; 8814aae4f90071f64854ec771496bd164149b0a1352Chandler Carruth BlockChain *Chain 8824aae4f90071f64854ec771496bd164149b0a1352Chandler Carruth = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 88303300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // Also, merge any blocks which we cannot reason about and must preserve 88403300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // the exact fallthrough behavior for. 88503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth for (;;) { 88603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth Cond.clear(); 887dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 88803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 88903300ecaee3ef853669582bcadec34170dbf515fChandler Carruth break; 89003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth 89136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineFunction::iterator NextFI(std::next(FI)); 89203300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineBasicBlock *NextBB = NextFI; 89303300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // Ensure that the layout successor is a viable block, as we know that 89403300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // fallthrough is a possibility. 89503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth assert(NextFI != FE && "Can't fallthrough past the last block."); 89603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 89703300ecaee3ef853669582bcadec34170dbf515fChandler Carruth << getBlockName(BB) << " -> " << getBlockName(NextBB) 89803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth << "\n"); 899dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Chain->merge(NextBB, nullptr); 90003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth FI = NextFI; 90103300ecaee3ef853669582bcadec34170dbf515fChandler Carruth BB = NextBB; 90203300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 90303300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 904df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 905df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Build any loop-based chains. 9063071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 9073071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth ++LI) 9083071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 9093071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 910df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 911db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 912df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallPtrSet<BlockChain *, 4> UpdatedPreds; 913df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 914df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *BB = &*FI; 915df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain = *BlockToChain[BB]; 916df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!UpdatedPreds.insert(&Chain)) 917db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth continue; 918df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 919df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 920df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 921df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 922df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[*BCI] == &Chain); 923df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 924df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 925df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 926df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockToChain[*PI] == &Chain) 927df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 928df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 929df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 930db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 931df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 932df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 933a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*Chain.begin()); 934db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 935db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 936df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &FunctionChain = *BlockToChain[&F.front()]; 9373273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth buildChain(&F.front(), FunctionChain, BlockWorkList); 938df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 93936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 940df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 94136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 942df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 94310252db69bdddb445e53892b388fbe5921114b86Chandler Carruth // Crash at the end so we get all of the debugging output first. 94410252db69bdddb445e53892b388fbe5921114b86Chandler Carruth bool BadFunc = false; 945df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSetType FunctionBlockSet; 946df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 947df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSet.insert(FI); 948df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 949c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockChain::iterator BCI = FunctionChain.begin(), 950c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth BCE = FunctionChain.end(); 951df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) 95210252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!FunctionBlockSet.erase(*BCI)) { 95310252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadFunc = true; 954df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function chain contains a block not in the function!\n" 955df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 95610252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 957df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 95810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!FunctionBlockSet.empty()) { 95910252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadFunc = true; 960c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), 961c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth FBE = FunctionBlockSet.end(); 962c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth FBI != FBE; ++FBI) 963df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function contains blocks never placed into a chain!\n" 964df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*FBI) << "\n"; 96510252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 96610252db69bdddb445e53892b388fbe5921114b86Chandler Carruth assert(!BadFunc && "Detected problems with the block placement."); 967df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 968df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 969df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Splice the blocks into place. 970df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineFunction::iterator InsertPos = F.begin(); 971c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockChain::iterator BI = FunctionChain.begin(), 972c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth BE = FunctionChain.end(); 973df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BI != BE; ++BI) { 974df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 975df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : " ... ") 976df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << getBlockName(*BI) << "\n"); 977df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (InsertPos != MachineFunction::iterator(*BI)) 978df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.splice(InsertPos, *BI); 979df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth else 980df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++InsertPos; 981df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 982df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Update the terminator of the previous block. 983df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BI == FunctionChain.begin()) 984df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 98536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock *PrevBB = std::prev(MachineFunction::iterator(*BI)); 986df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 987db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // FIXME: It would be awesome of updateTerminator would just return rather 988db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // than assert when the branch cannot be analyzed in order to remove this 989db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // boiler plate. 990db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth Cond.clear(); 991dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 99211236143173d1aedeace570ac1133d3d5dfb268eManman Ren if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { 99345c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // The "PrevBB" is not yet updated to reflect current code layout, so, 99445c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // o. it may fall-through to a block without explict "goto" instruction 99545c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // before layout, and no longer fall-through it after layout; or 99645c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // o. just opposite. 99745c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // 99845c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // AnalyzeBranch() may return erroneous value for FBB when these two 99945c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // situations take place. For the first scenario FBB is mistakenly set 100045c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // NULL; for the 2nd scenario, the FBB, which is expected to be NULL, 100145c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // is mistakenly pointing to "*BI". 100245c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // 100345c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang bool needUpdateBr = true; 100445c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang if (!Cond.empty() && (!FBB || FBB == *BI)) { 100545c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang PrevBB->updateTerminator(); 100645c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang needUpdateBr = false; 100745c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang Cond.clear(); 1008dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TBB = FBB = nullptr; 100945c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang if (TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { 101045c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang // FIXME: This should never take place. 1011dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines TBB = FBB = nullptr; 101245c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang } 101345c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang } 101445c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang 101511236143173d1aedeace570ac1133d3d5dfb268eManman Ren // If PrevBB has a two-way branch, try to re-order the branches 101611236143173d1aedeace570ac1133d3d5dfb268eManman Ren // such that we branch to the successor with higher weight first. 101711236143173d1aedeace570ac1133d3d5dfb268eManman Ren if (TBB && !Cond.empty() && FBB && 101811236143173d1aedeace570ac1133d3d5dfb268eManman Ren MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && 101911236143173d1aedeace570ac1133d3d5dfb268eManman Ren !TII->ReverseBranchCondition(Cond)) { 102011236143173d1aedeace570ac1133d3d5dfb268eManman Ren DEBUG(dbgs() << "Reverse order of the two branches: " 102111236143173d1aedeace570ac1133d3d5dfb268eManman Ren << getBlockName(PrevBB) << "\n"); 102211236143173d1aedeace570ac1133d3d5dfb268eManman Ren DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) 102311236143173d1aedeace570ac1133d3d5dfb268eManman Ren << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); 102411236143173d1aedeace570ac1133d3d5dfb268eManman Ren DebugLoc dl; // FIXME: this is nowhere 102511236143173d1aedeace570ac1133d3d5dfb268eManman Ren TII->RemoveBranch(*PrevBB); 102611236143173d1aedeace570ac1133d3d5dfb268eManman Ren TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); 102745c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang needUpdateBr = true; 102811236143173d1aedeace570ac1133d3d5dfb268eManman Ren } 102945c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang if (needUpdateBr) 103045c75443394b92a8ba8e2474a393039feb5b7d78Shuxin Yang PrevBB->updateTerminator(); 103111236143173d1aedeace570ac1133d3d5dfb268eManman Ren } 1032db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 1033df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 1034df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Fixup the last block. 1035df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth Cond.clear(); 1036dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch. 1037df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 1038df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.back().updateTerminator(); 10394a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 104070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // Walk through the backedges of the function now that we have fully laid out 104170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // the basic blocks and align the destination of each backedge. We don't rely 1042e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // exclusively on the loop info here so that we can align backedges in 1043e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // unnatural CFGs and backedges that were introduced purely because of the 1044e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // loop rotations done during this layout pass. 1045831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling if (F.getFunction()->getAttributes(). 1046831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize)) 10474a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; 10484a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth unsigned Align = TLI->getPrefLoopAlignment(); 10494a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth if (!Align) 10504a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; // Don't care about loop alignment. 1051e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (FunctionChain.begin() == FunctionChain.end()) 1052e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth return; // Empty chain. 10534a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 1054e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth const BranchProbability ColdProb(1, 5); // 20% 1055e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); 1056e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; 105736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (BlockChain::iterator BI = std::next(FunctionChain.begin()), 105870daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BE = FunctionChain.end(); 105970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BI != BE; ++BI) { 1060e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Don't align non-looping basic blocks. These are unlikely to execute 1061e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // enough times to matter in practice. Note that we'll still handle 1062e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // unnatural CFGs inside of a natural outer loop (the common case) and 1063e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // rotated loops. 1064e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth MachineLoop *L = MLI->getLoopFor(*BI); 1065e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (!L) 1066e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1067e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1068e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // If the block is cold relative to the function entry don't waste space 1069e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // aligning it. 1070e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency Freq = MBFI->getBlockFreq(*BI); 1071e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (Freq < WeightedEntryFreq) 1072e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1073e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1074e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // If the block is cold relative to its loop header, don't align it 1075e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // regardless of what edges into the block exist. 1076e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth MachineBasicBlock *LoopHeader = L->getHeader(); 1077e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); 1078e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (Freq < (LoopHeaderFreq * ColdProb)) 1079e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1080e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1081e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Check for the existence of a non-layout predecessor which would benefit 1082e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // from aligning this block. 108336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBasicBlock *LayoutPred = *std::prev(BI); 1084e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1085e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Force alignment if all the predecessors are jumps. We already checked 1086e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // that the block isn't cold above. 1087e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (!LayoutPred->isSuccessor(*BI)) { 1088e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth (*BI)->setAlignment(Align); 1089e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1090e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth } 1091e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1092e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Align this block if the layout predecessor's edge into this block is 1093975ee54731476ff6541fc42f6a8cd706f3d33f58Nadav Rotem // cold relative to the block. When this is true, other predecessors make up 1094e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // all of the hot entries into the block and thus alignment is likely to be 1095e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // important. 1096e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BranchProbability LayoutProb = MBPI->getEdgeProbability(LayoutPred, *BI); 1097e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; 1098e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (LayoutEdgeFreq <= (Freq * ColdProb)) 1099e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth (*BI)->setAlignment(Align); 110070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth } 11014a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth} 11024a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 1103db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthbool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 1104db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // Check for single-block functions and skip them. 110536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(F.begin()) == F.end()) 110636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 110736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 110836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(*F.getFunction())) 1109db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return false; 1110db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1111db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1112db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 11134a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth MLI = &getAnalysis<MachineLoopInfo>(); 1114db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth TII = F.getTarget().getInstrInfo(); 11154a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth TLI = F.getTarget().getTargetLowering(); 1116db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BlockToChain.empty()); 1117db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 11183071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildCFGChains(F); 1119db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1120db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain.clear(); 1121f5e47ac596c698f1659c86bdad3a60056e68439cChandler Carruth ChainAllocator.DestroyAll(); 1122db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 112333a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem if (AlignAllBlock) 112433a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem // Align all of the blocks in the function to a specific alignment. 112533a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem for (MachineFunction::iterator FI = F.begin(), FE = F.end(); 112633a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem FI != FE; ++FI) 112733a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem FI->setAlignment(AlignAllBlock); 112833a47d66e9f9126017d051bfba35cb9be6609b3eNadav Rotem 1129db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // We always return true as we have no way to track whether the final order 1130db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // differs from the original order. 1131db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return true; 1132db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 113337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 113437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthnamespace { 113537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// \brief A pass to compute block placement statistics. 113637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// 113737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// A separate pass to compute interesting statistics for evaluating block 113837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// placement. This is separate from the actual placement pass so that they can 1139d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer/// be computed in the absence of any placement transformations or when using 114037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// alternative placement strategies. 114137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthclass MachineBlockPlacementStats : public MachineFunctionPass { 114237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the branch probability pass. 114337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 114437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 114537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 114637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 114737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 114837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthpublic: 114937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth static char ID; // Pass identification, replacement for typeid 115037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineBlockPlacementStats() : MachineFunctionPass(ID) { 115137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 115237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 115337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 115436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &F) override; 115537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 115636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 115737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 115837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 115937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.setPreservesAll(); 116037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 116137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 116237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth}; 116337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 116437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 116537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthchar MachineBlockPlacementStats::ID = 0; 11661dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 116737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 116837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 116937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 117037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 117137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 117237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 117337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 117437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthbool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 117537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Check for single-block functions and skip them. 117636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(F.begin()) == F.end()) 117737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 117837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 117937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 118037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 118137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 118237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 118337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 118437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 118537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : NumUncondBranches; 118637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 118737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : UncondBranchTakenFreq; 118837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 118937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SE = I->succ_end(); 119037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SI != SE; ++SI) { 119137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Skip if this successor is a fallthrough. 119237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth if (I->isLayoutSuccessor(*SI)) 119337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth continue; 119437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 119537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 119637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth ++NumBranches; 119737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BranchTakenFreq += EdgeFreq.getFrequency(); 119837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 119937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 120037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 120137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 120237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 120337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 1204