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 28db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#define DEBUG_TYPE "block-placement2" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 344a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 35db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 36db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 37db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunction.h" 38db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/CodeGen/MachineFunctionPass.h" 394a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineLoopInfo.h" 404a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth#include "llvm/CodeGen/MachineModuleInfo.h" 41db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth#include "llvm/Support/Allocator.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 4837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumCondBranches, "Number of conditional branches"); 4937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(NumUncondBranches, "Number of uncondittional branches"); 5037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(CondBranchTakenFreq, 5137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking conditional branches"); 5237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthSTATISTIC(UncondBranchTakenFreq, 5337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Potential frequency of taking unconditional branches"); 5437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 55db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 563071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain; 57db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief Type for our function-wide basic block -> block chain mapping. 58db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthtypedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; 59db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 60db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 61db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 62db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// \brief A chain of blocks which will be laid out contiguously. 63db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 64db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// This is the datastructure representing a chain of consecutive blocks that 65db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// are profitable to layout together in order to maximize fallthrough 66c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// probabilities and code locality. We also can use a block chain to represent 67c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// a sequence of basic blocks which have some external (correctness) 68c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// requirement for sequential layout. 69db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth/// 70c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// Chains can be built around a single basic block and can be merged to grow 71c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// them. They participate in a block-to-chain mapping, which is updated 72c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth/// automatically as chains are merged together. 733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthclass BlockChain { 743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief The sequence of blocks belonging to this chain. 75db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 763071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// This is the sequence of blocks for a particular chain. These will be laid 773071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// out in-order within the function. 783071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth SmallVector<MachineBasicBlock *, 4> Blocks; 79db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 80db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide basic block to block chain mapping. 81db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 82db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This is retained in each block chain to simplify the computation of child 83db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// block chains for SCC-formation and iteration. We store the edges to child 84db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// basic blocks, and map them back to their associated chains using this 85db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// structure. 86db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChainMapType &BlockToChain; 87db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 883071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthpublic: 89db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Construct a new BlockChain. 90db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 91db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This builds a new block chain representing a single basic block in the 92db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// function. It also registers itself as the chain that block participates 93db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// in with the BlockToChain mapping. 94db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) 95df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { 96db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BB && "Cannot create a chain with a null basic block"); 97db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain[BB] = this; 98db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 99db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1003071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Iterator over blocks within the chain. 10170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator; 1023071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1033071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Beginning of blocks within the chain. 10470daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth iterator begin() { return Blocks.begin(); } 1053071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1063071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief End of blocks within the chain. 10770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth iterator end() { return Blocks.end(); } 1083071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1093071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief Merge a block chain into this one. 110db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 111db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This routine merges a block chain into this one. It takes care of forming 112db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// a contiguous sequence of basic blocks, updating the edge list, and 113db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// updating the block -> chain mapping. It does not free or tear down the 114db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// old chain, but the old chain's block list is no longer valid. 115d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void merge(MachineBasicBlock *BB, BlockChain *Chain) { 1163071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB); 1173071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!Blocks.empty()); 1183071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 1193071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Fast path in case we don't have a chain already. 1203071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth if (!Chain) { 1213071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(!BlockToChain[BB]); 1223071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(BB); 1233071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[BB] = this; 1243071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return; 125db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 126db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1273071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BB == *Chain->begin()); 1283071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(Chain->begin() != Chain->end()); 129db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1303071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // Update the incoming blocks to point to this chain, and add them to the 1313071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // chain structure. 1323071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); 1333071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 1343071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth Blocks.push_back(*BI); 1353071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain"); 1363071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BlockToChain[*BI] = this; 1373071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 138db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 139df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 1406313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth#ifndef NDEBUG 1416313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth /// \brief Dump the blocks in this chain. 1426313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth void dump() LLVM_ATTRIBUTE_USED { 1436313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth for (iterator I = begin(), E = end(); I != E; ++I) 1446313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth (*I)->dump(); 1456313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth } 1466313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth#endif // NDEBUG 1476313d941d29d77f62662c4bd13f12314e6b4b86eChandler Carruth 148df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// \brief Count of predecessors within the loop currently being processed. 149df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// 150df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// This count is updated at each loop we process to represent the number of 151df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth /// in-loop predecessors of this chain. 152df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth unsigned LoopPredecessors; 153db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 154db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 155db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 156db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthnamespace { 157db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthclass MachineBlockPlacement : public MachineFunctionPass { 1583071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth /// \brief A typedef for a block filter set. 1593071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet; 1603071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 161db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the branch probability pass. 162db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 163db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 164db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 165db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 166db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1674a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the loop info. 1684a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth const MachineLoopInfo *MLI; 1694a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 170db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief A handle to the target's instruction info. 171db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth const TargetInstrInfo *TII; 172db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1734a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth /// \brief A handle to the target's lowering info. 17469e42dbd006c0afb732067ece7327988b1e24c01Benjamin Kramer const TargetLoweringBase *TLI; 1754a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 176db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Allocator and owner of BlockChain structures. 177db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 178c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// We build BlockChains lazily while processing the loop structure of 179c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// a function. To reduce malloc traffic, we allocate them using this 180c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// slab-like allocator, and destroy them after the pass completes. An 181c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// important guarantee is that this allocator produces stable pointers to 182c04f816afd1ad9a1c3746f894556b6bea0cac8fcChandler Carruth /// the chains. 183db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth SpecificBumpPtrAllocator<BlockChain> ChainAllocator; 184db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 185db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// \brief Function wide BasicBlock to BlockChain mapping. 186db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// 187db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// This mapping allows efficiently moving from any given basic block to the 188db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// BlockChain it participates in, if any. We use it to, among other things, 189db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// allow implicitly defining edges between chains as the existing edges 190db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth /// between basic blocks. 191db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain; 192db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 193d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void markChainSuccessors(BlockChain &Chain, 194d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *LoopHeaderBB, 195b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 196d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter = 0); 197d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, 198d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, 199d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 200f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth MachineBasicBlock *selectBestCandidateBlock( 201d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 202d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 2033273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineBasicBlock *getFirstUnplacedBlock( 2043273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction &F, 2053273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth const BlockChain &PlacedChain, 2063273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth MachineFunction::iterator &PrevUnplacedBlockIt, 207d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter); 208df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth void buildChain(MachineBasicBlock *BB, BlockChain &Chain, 209b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 210d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter = 0); 211e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *findBestLoopTop(MachineLoop &L, 212e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth const BlockFilterSet &LoopBlockSet); 21370daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth MachineBasicBlock *findBestLoopExit(MachineFunction &F, 21470daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth MachineLoop &L, 21570daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth const BlockFilterSet &LoopBlockSet); 216d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak void buildLoopChains(MachineFunction &F, MachineLoop &L); 21716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, 21816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth const BlockFilterSet &LoopBlockSet); 2193071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth void buildCFGChains(MachineFunction &F); 220db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 221db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthpublic: 222db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth static char ID; // Pass identification, replacement for typeid 223db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBlockPlacement() : MachineFunctionPass(ID) { 224db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); 225db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 226db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 227db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth bool runOnMachineFunction(MachineFunction &F); 228db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 229db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth void getAnalysisUsage(AnalysisUsage &AU) const { 230db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 231db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 2324a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth AU.addRequired<MachineLoopInfo>(); 233db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 234db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 235db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth}; 236db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 237db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 238db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthchar MachineBlockPlacement::ID = 0; 2391dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; 240db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", 241db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 242db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 243db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 2444a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 245db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", 246db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth "Branch Probability Basic Block Placement", false, false) 247db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2483071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#ifndef NDEBUG 2493071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the name of a MBB. 2503071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2513071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 252d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszakstatic std::string getBlockName(MachineBasicBlock *BB) { 2533071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2543071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2553071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber() 2563071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth << " (derived from LLVM BB '" << BB->getName() << "')"; 2573071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2583071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 2593071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 260db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 2613071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Helper to print the number of a MBB. 2623071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 2633071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// Only used by debug logging. 264d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszakstatic std::string getBlockNum(MachineBasicBlock *BB) { 2653071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth std::string Result; 2663071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth raw_string_ostream OS(Result); 2673071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS << "BB#" << BB->getNumber(); 2683071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth OS.flush(); 2693071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth return Result; 270db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 2713071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth#endif 272db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 273729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// \brief Mark a chain's successors as having one fewer preds. 274729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// 275729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// When a chain is being merged into the "placed" chain, this routine will 276729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// quickly walk the successors of each block in the chain and mark them as 277729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// having one fewer active predecessor. It also adds any successors of this 278729bec89bd8c4368a741359fb882967ce01a6909Chandler Carruth/// chain which reach the zero-predecessor state to the worklist passed in. 279df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::markChainSuccessors( 280d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, 281d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *LoopHeaderBB, 282df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, 283d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 284df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Walk all the blocks in this chain, marking their successors as having 285df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // a predecessor placed. 286df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); 287df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth CBI != CBE; ++CBI) { 288df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Add any successors for which this is the only un-placed in-loop 289df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // predecessor to the worklist as a viable candidate for CFG-neutral 290df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // placement. No subsequent placement of this block will violate the CFG 291df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // shape, so we get to use heuristics to choose a favorable placement. 292df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), 293df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SE = (*CBI)->succ_end(); 294df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SI != SE; ++SI) { 295df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 296df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 297d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*SI]; 298df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Disregard edges within a fixed chain, or edges to the loop header. 299df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (&Chain == &SuccChain || *SI == LoopHeaderBB) 300df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 301df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 302df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // This is a cross-chain edge that is within the loop, so decrement the 303df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // loop predecessor count of the destination chain. 304df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) 305a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*SuccChain.begin()); 306df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 307df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 308db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 309db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 3109fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \brief Select the best successor for a block. 3119fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3129fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// This looks across all successors of a particular block and attempts to 3139fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// select the "best" one to be the layout successor. It only considers direct 3149fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// successors which also pass the block filter. It will attempt to avoid 3159fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// breaking CFG structure, but cave and break such structures in the case of 3169fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// very hot successor edges. 3179fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// 3189fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth/// \returns The best successor block found, or null if none are viable. 3199fd4e056e433b286f0e6576046ef2242365bfc38Chandler CarruthMachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( 320d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineBasicBlock *BB, BlockChain &Chain, 321d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 3229fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth const BranchProbability HotProb(4, 5); // 80% 3239fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3249fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth MachineBasicBlock *BestSucc = 0; 325340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // FIXME: Due to the performance of the probability and weight routines in 326340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // the MBPI analysis, we manually compute probabilities using the edge 327340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // weights. This is suboptimal as it means that the somewhat subtle 328340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // definition of edge weight semantics is encoded here as well. We should 329d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // improve the MBPI interface to efficiently support query patterns such as 330340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth // this. 331340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t BestWeight = 0; 332340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t WeightScale = 0; 333340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); 3349fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); 335d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 336d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SE = BB->succ_end(); 337d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SI != SE; ++SI) { 3389fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (BlockFilter && !BlockFilter->count(*SI)) 3399fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 340d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &SuccChain = *BlockToChain[*SI]; 3419fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth if (&SuccChain == &Chain) { 3429fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); 3439fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3449fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 34503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth if (*SI != *SuccChain.begin()) { 34603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n"); 34703300ecaee3ef853669582bcadec34170dbf515fChandler Carruth continue; 34803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 3499fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 350340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI); 351340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); 3529fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3539fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // Only consider successors which are either "hot", or wouldn't violate 3549fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth // any CFG constraints. 355b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (SuccChain.LoopPredecessors != 0) { 356b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (SuccProb < HotProb) { 357b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); 358b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 359b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 360b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth 361b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth // Make sure that a hot successor doesn't have a globally more important 362b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth // predecessor. 363b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BlockFrequency CandidateEdgeFreq 364b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth = MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl(); 365b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth bool BadCFGConflict = false; 366b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(), 367b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth PE = (*SI)->pred_end(); 368b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth PI != PE; ++PI) { 369b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) || 370d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockToChain[*PI] == &Chain) 371b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 372b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BlockFrequency PredEdgeFreq 373b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI); 374b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (PredEdgeFreq >= CandidateEdgeFreq) { 375b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth BadCFGConflict = true; 376b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth break; 377b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 378b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 379b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth if (BadCFGConflict) { 380b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) 381b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth << " -> non-cold CFG conflict\n"); 382b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth continue; 383b0dadb9dd52aed7a82e24542be8adf881d91c929Chandler Carruth } 3849fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 3859fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 3869fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb 3879fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << " (prob)" 3889fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") 3899fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth << "\n"); 390340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth if (BestSucc && BestWeight >= SuccWeight) 3919fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth continue; 3929fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth BestSucc = *SI; 393340d596509129de8c3fa9dbe4184a2b148b78757Chandler Carruth BestWeight = SuccWeight; 3949fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth } 3959fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth return BestSucc; 3969fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth} 3979fd4e056e433b286f0e6576046ef2242365bfc38Chandler Carruth 398fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruthnamespace { 399fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth/// \brief Predicate struct to detect blocks already placed. 400fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruthclass IsBlockPlaced { 401fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth const BlockChain &PlacedChain; 402fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth const BlockToChainMapType &BlockToChain; 403fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth 404fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruthpublic: 405fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth IsBlockPlaced(const BlockChain &PlacedChain, 406fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth const BlockToChainMapType &BlockToChain) 407fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth : PlacedChain(PlacedChain), BlockToChain(BlockToChain) {} 408fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth 409fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth bool operator()(MachineBasicBlock *BB) const { 410fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth return BlockToChain.lookup(BB) == &PlacedChain; 411fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth } 412fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth}; 413fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth} 414fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth 415f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// \brief Select the best block from a worklist. 416f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// 417f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// This looks through the provided worklist as a list of candidate basic 418f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// blocks and select the most profitable one to place. The definition of 419f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// profitable only really makes sense in the context of a loop. This returns 420f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// the most frequently visited block in the worklist, which in the case of 421f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// a loop, is the one most desirable to be physically close to the rest of the 422f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// loop body in order to improve icache behavior. 423f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// 424f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth/// \returns The best block found, or null if none are viable. 425f3fc0050abc1698504cbaede7766c4180c076928Chandler CarruthMachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( 426d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, 427d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak const BlockFilterSet *BlockFilter) { 428fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // Once we need to walk the worklist looking for a candidate, cleanup the 429fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // worklist of already placed entries. 430fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // FIXME: If this shows up on profiles, it could be folded (at the cost of 431fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth // some code complexity) into the loop below. 432fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(), 433fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth IsBlockPlaced(Chain, BlockToChain)), 434fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth WorkList.end()); 435fa97658b1c71f747cfe0f3e1f1bcbd86d7fa9f75Chandler Carruth 436f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth MachineBasicBlock *BestBlock = 0; 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); 450f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq 451f3fc0050abc1698504cbaede7766c4180c076928Chandler Carruth << " (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 } 483b5856c83ff4fd796c3eabccca2ed3b06173aeb51Chandler Carruth return 0; 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); 498df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BB = *llvm::prior(Chain.end()); 499df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (;;) { 500df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BB); 501d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak assert(BlockToChain[BB] == &Chain); 502df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(*llvm::prior(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); 533df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BB = *llvm::prior(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; 564e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *BestPred = 0; 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) << ", " 572e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth << Pred->succ_size() << " successors, " 573e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth << MBFI->getBlockFreq(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())) 62070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth return 0; 62145fb79bc54159330979bf24e4bfbdbb64bee1e2cChandler Carruth 622fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BlockFrequency BestExitEdgeFreq; 62370daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth unsigned BestExitLoopDepth = 0; 624fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth MachineBasicBlock *ExitingBB = 0; 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. 638fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (*I != *llvm::prior(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 68770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth << "] (" << ExitEdgeFreq << ")\n"); 688fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Note that we slightly bias this toward an existing layout successor to 689fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // retain incoming order in the absence of better information. 690fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // FIXME: Should we bias this more strongly? It's pretty weak. 69170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || 69270daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth ExitEdgeFreq > BestExitEdgeFreq || 693fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ((*I)->isLayoutSuccessor(*SI) && 694fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth !(ExitEdgeFreq < BestExitEdgeFreq))) { 695fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BestExitEdgeFreq = ExitEdgeFreq; 696fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ExitingBB = *I; 6972eb5a744b18d429928751b06e205cbb88f668ae7Chandler Carruth } 6982e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth } 699fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 700fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // Restore the old exiting state, no viable looping successor was found. 70170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth if (!HasLoopingSucc) { 702fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth ExitingBB = OldExitingBB; 703fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth BestExitEdgeFreq = OldBestExitEdgeFreq; 7042eb5a744b18d429928751b06e205cbb88f668ae7Chandler Carruth continue; 705fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth } 7062e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth } 70770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // Without a candidate exiting block or with only a single block in the 708fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth // loop, just use the loop header to layout the loop. 709fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (!ExitingBB || L.getNumBlocks() == 1) 71070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth return 0; 711fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 71251901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // Also, if we have exit blocks which lead to outer loops but didn't select 71351901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // one of them as the exiting block we are rotating toward, disable loop 71451901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth // rotation altogether. 71551901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth if (!BlocksExitingToOuterLoop.empty() && 71651901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth !BlocksExitingToOuterLoop.count(ExitingBB)) 71770daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth return 0; 71851901d85f718a7e293f52a7908eab9fe1c0c94a0Chandler Carruth 719fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); 72070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth return ExitingBB; 7212e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth} 7222e38cf961d6d80c88290ca6b8d867e021f80b763Chandler Carruth 72316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// \brief Attempt to rotate an exiting block to the bottom of the loop. 72416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// 72516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// Once we have built a chain, try to rotate it to line up the hot exit block 72616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// with fallthrough out of the loop if doing so doesn't introduce unnecessary 72716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// branches. For example, if the loop has fallthrough into its header and out 72816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth/// of its bottom already, don't rotate it. 72916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruthvoid MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, 73016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth MachineBasicBlock *ExitingBB, 73116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth const BlockFilterSet &LoopBlockSet) { 73216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!ExitingBB) 73316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 73416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 73516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth MachineBasicBlock *Top = *LoopChain.begin(); 73616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth bool ViableTopFallthrough = false; 73716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), 73816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth PE = Top->pred_end(); 73916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth PI != PE; ++PI) { 74016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain *PredChain = BlockToChain[*PI]; 74116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!LoopBlockSet.count(*PI) && 74216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth (!PredChain || *PI == *llvm::prior(PredChain->end()))) { 74316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth ViableTopFallthrough = true; 74416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth break; 74516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 74616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 74716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 74816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // If the header has viable fallthrough, check whether the current loop 74916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // bottom is a viable exiting block. If so, bail out as rotating will 75016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth // introduce an unnecessary branch. 75116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (ViableTopFallthrough) { 75216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth MachineBasicBlock *Bottom = *llvm::prior(LoopChain.end()); 75316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), 75416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth SE = Bottom->succ_end(); 75516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth SI != SE; ++SI) { 75616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain *SuccChain = BlockToChain[*SI]; 75716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (!LoopBlockSet.count(*SI) && 75816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth (!SuccChain || *SI == *SuccChain->begin())) 75916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 76016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 76116295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth } 76216295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 76316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth BlockChain::iterator ExitIt = std::find(LoopChain.begin(), LoopChain.end(), 76416295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth ExitingBB); 76516295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth if (ExitIt == LoopChain.end()) 76616295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth return; 76716295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 76816295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth std::rotate(LoopChain.begin(), llvm::next(ExitIt), LoopChain.end()); 76916295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth} 77016295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth 7713071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// \brief Forms basic block chains from the natural loop structures. 7723071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// 7733071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// These chains are designed to preserve the existing *structure* of the code 7743071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// as much as possible. We can then stitch the chains together in a way which 7753071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// both preserves the topological structure and minimizes taken conditional 7763071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth/// branches. 777df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruthvoid MachineBlockPlacement::buildLoopChains(MachineFunction &F, 778d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak MachineLoop &L) { 7793071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // First recurse through any nested loops, building chains for those inner 7803071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth // loops. 7813071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 7823071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 7833071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 784df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 785df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); 786fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth 787e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // First check to see if there is an obviously preferable top block for the 788e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // loop. This will default to the header, but may end up as one of the 789e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // predecessors to the header if there is one which will result in strictly 790e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // fewer branches in the loop body. 791e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); 792e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 793e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // If we selected just the header for the loop top, look for a potentially 794e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // profitable exit block in the event that rotating the loop can eliminate 795e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth // branches by placing an exit edge at the bottom. 796e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth MachineBasicBlock *ExitingBB = 0; 797e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth if (LoopTop == L.getHeader()) 798e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth ExitingBB = findBestLoopExit(F, L, LoopBlockSet); 799e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth 800e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth BlockChain &LoopChain = *BlockToChain[LoopTop]; 8013071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 802df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // FIXME: This is a really lame way of walking the chains in the loop: we 803df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // walk the blocks, and use a set to prevent visiting a particular chain 804df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // twice. 805d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak SmallPtrSet<BlockChain *, 4> UpdatedPreds; 806feb468ab24a9e85b4d27faa6badfb57a2414610cJakub Staszak assert(LoopChain.LoopPredecessors == 0); 807feb468ab24a9e85b4d27faa6badfb57a2414610cJakub Staszak UpdatedPreds.insert(&LoopChain); 808df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineLoop::block_iterator BI = L.block_begin(), 809df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BE = L.block_end(); 8103071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth BI != BE; ++BI) { 811d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak BlockChain &Chain = *BlockToChain[*BI]; 812fac1305da162259d17baa6700ecb5d148b86ef08Chandler Carruth if (!UpdatedPreds.insert(&Chain)) 813df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 814df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 815df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 816df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 817df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 818d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak assert(BlockToChain[*BCI] == &Chain); 819df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 820df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 821df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 822d4895ded27179c47ef7327e3322b6a11a905eb9fJakub Staszak if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) 823df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 824df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 825df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 826df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 827df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 828df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 829a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*Chain.begin()); 8303071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth } 831df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 832e773e8c3e53aadb6e861316e4db88d63a0226b2fChandler Carruth buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); 83316295fc20b68f9a9318cada4e4d96e964b1cdd7eChandler Carruth rotateLoop(LoopChain, ExitingBB, LoopBlockSet); 834df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 835df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 83610252db69bdddb445e53892b388fbe5921114b86Chandler Carruth // Crash at the end so we get all of the debugging output first. 83710252db69bdddb445e53892b388fbe5921114b86Chandler Carruth bool BadLoop = false; 83810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (LoopChain.LoopPredecessors) { 83910252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadLoop = true; 840df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block without its preds placed!\n" 841df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 842df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; 84310252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 844df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); 84570daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BCI != BCE; ++BCI) { 84670daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth dbgs() << " ... " << getBlockName(*BCI) << "\n"; 84710252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!LoopBlockSet.erase(*BCI)) { 848bc83fcd9bd95f8eff83cd5ad77b0aa5312d8a6a5Chandler Carruth // We don't mark the loop as bad here because there are real situations 849bc83fcd9bd95f8eff83cd5ad77b0aa5312d8a6a5Chandler Carruth // where this can occur. For example, with an unanalyzable fallthrough 850598894ff2547aaa0a32ded145063f3bfe042f620Chandler Carruth // from a loop block to a non-loop block or vice versa. 851df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop chain contains a block not contained by the loop!\n" 852df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 853df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 854df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 85510252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 85670daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth } 857df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 85810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!LoopBlockSet.empty()) { 85910252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadLoop = true; 860c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), 861c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth LBE = LoopBlockSet.end(); 862df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth LBI != LBE; ++LBI) 863df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Loop contains blocks never placed into a chain!\n" 864df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Loop header: " << getBlockName(*L.block_begin()) << "\n" 865df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" 866df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*LBI) << "\n"; 86710252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 86810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth assert(!BadLoop && "Detected problems with the placement of this loop."); 869df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 8703071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth} 871db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 8723071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruthvoid MachineBlockPlacement::buildCFGChains(MachineFunction &F) { 873df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Ensure that every BB in the function has an associated chain to simplify 874df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // the assumptions of the remaining algorithm. 87503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. 87603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 87703300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineBasicBlock *BB = FI; 8784aae4f90071f64854ec771496bd164149b0a1352Chandler Carruth BlockChain *Chain 8794aae4f90071f64854ec771496bd164149b0a1352Chandler Carruth = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); 88003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // Also, merge any blocks which we cannot reason about and must preserve 88103300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // the exact fallthrough behavior for. 88203300ecaee3ef853669582bcadec34170dbf515fChandler Carruth for (;;) { 88303300ecaee3ef853669582bcadec34170dbf515fChandler Carruth Cond.clear(); 88403300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 88503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) 88603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth break; 88703300ecaee3ef853669582bcadec34170dbf515fChandler Carruth 88803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineFunction::iterator NextFI(llvm::next(FI)); 88903300ecaee3ef853669582bcadec34170dbf515fChandler Carruth MachineBasicBlock *NextBB = NextFI; 89003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // Ensure that the layout successor is a viable block, as we know that 89103300ecaee3ef853669582bcadec34170dbf515fChandler Carruth // fallthrough is a possibility. 89203300ecaee3ef853669582bcadec34170dbf515fChandler Carruth assert(NextFI != FE && "Can't fallthrough past the last block."); 89303300ecaee3ef853669582bcadec34170dbf515fChandler Carruth DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " 89403300ecaee3ef853669582bcadec34170dbf515fChandler Carruth << getBlockName(BB) << " -> " << getBlockName(NextBB) 89503300ecaee3ef853669582bcadec34170dbf515fChandler Carruth << "\n"); 89603300ecaee3ef853669582bcadec34170dbf515fChandler Carruth Chain->merge(NextBB, 0); 89703300ecaee3ef853669582bcadec34170dbf515fChandler Carruth FI = NextFI; 89803300ecaee3ef853669582bcadec34170dbf515fChandler Carruth BB = NextBB; 89903300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 90003300ecaee3ef853669582bcadec34170dbf515fChandler Carruth } 901df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 902df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Build any loop-based chains. 9033071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; 9043071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth ++LI) 9053071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildLoopChains(F, **LI); 9063071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth 907df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallVector<MachineBasicBlock *, 16> BlockWorkList; 908db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 909df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth SmallPtrSet<BlockChain *, 4> UpdatedPreds; 910df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { 911df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *BB = &*FI; 912df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &Chain = *BlockToChain[BB]; 913df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!UpdatedPreds.insert(&Chain)) 914db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth continue; 915df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 916df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(Chain.LoopPredecessors == 0); 917df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); 918df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) { 919df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth assert(BlockToChain[*BCI] == &Chain); 920df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), 921df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PE = (*BCI)->pred_end(); 922df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PI != PE; ++PI) { 923df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BlockToChain[*PI] == &Chain) 924df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 925df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++Chain.LoopPredecessors; 926df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth } 927db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 928df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 929df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (Chain.LoopPredecessors == 0) 930a2deea1dcf8363f46bda8935283c5c701b5a278dChandler Carruth BlockWorkList.push_back(*Chain.begin()); 931db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 932db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 933df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BlockChain &FunctionChain = *BlockToChain[&F.front()]; 9343273c8937b8c3ebdd1cfc0c67054ce5571f0afc9Chandler Carruth buildChain(&F.front(), FunctionChain, BlockWorkList); 935df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 936df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; 937df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG({ 93810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth // Crash at the end so we get all of the debugging output first. 93910252db69bdddb445e53892b388fbe5921114b86Chandler Carruth bool BadFunc = false; 940df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSetType FunctionBlockSet; 941df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 942df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth FunctionBlockSet.insert(FI); 943df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 944c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockChain::iterator BCI = FunctionChain.begin(), 945c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth BCE = FunctionChain.end(); 946df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BCI != BCE; ++BCI) 94710252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!FunctionBlockSet.erase(*BCI)) { 94810252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadFunc = true; 949df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function chain contains a block not in the function!\n" 950df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*BCI) << "\n"; 95110252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 952df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 95310252db69bdddb445e53892b388fbe5921114b86Chandler Carruth if (!FunctionBlockSet.empty()) { 95410252db69bdddb445e53892b388fbe5921114b86Chandler Carruth BadFunc = true; 955c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), 956c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth FBE = FunctionBlockSet.end(); 957c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth FBI != FBE; ++FBI) 958df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth dbgs() << "Function contains blocks never placed into a chain!\n" 959df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << " Bad block: " << getBlockName(*FBI) << "\n"; 96010252db69bdddb445e53892b388fbe5921114b86Chandler Carruth } 96110252db69bdddb445e53892b388fbe5921114b86Chandler Carruth assert(!BadFunc && "Detected problems with the block placement."); 962df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth }); 963df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 964df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Splice the blocks into place. 965df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineFunction::iterator InsertPos = F.begin(); 966c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth for (BlockChain::iterator BI = FunctionChain.begin(), 967c0f05b3c3fe191b09e04a5f3d16be9f4f8cc036eChandler Carruth BE = FunctionChain.end(); 968df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth BI != BE; ++BI) { 969df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " 970df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth : " ... ") 971df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth << getBlockName(*BI) << "\n"); 972df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (InsertPos != MachineFunction::iterator(*BI)) 973df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.splice(InsertPos, *BI); 974df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth else 975df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth ++InsertPos; 976df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 977df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Update the terminator of the previous block. 978df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (BI == FunctionChain.begin()) 979df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth continue; 980df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); 981df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 982db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // FIXME: It would be awesome of updateTerminator would just return rather 983db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // than assert when the branch cannot be analyzed in order to remove this 984db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // boiler plate. 985db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth Cond.clear(); 986db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 98711236143173d1aedeace570ac1133d3d5dfb268eManman Ren if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { 98811236143173d1aedeace570ac1133d3d5dfb268eManman Ren // If PrevBB has a two-way branch, try to re-order the branches 98911236143173d1aedeace570ac1133d3d5dfb268eManman Ren // such that we branch to the successor with higher weight first. 99011236143173d1aedeace570ac1133d3d5dfb268eManman Ren if (TBB && !Cond.empty() && FBB && 99111236143173d1aedeace570ac1133d3d5dfb268eManman Ren MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && 99211236143173d1aedeace570ac1133d3d5dfb268eManman Ren !TII->ReverseBranchCondition(Cond)) { 99311236143173d1aedeace570ac1133d3d5dfb268eManman Ren DEBUG(dbgs() << "Reverse order of the two branches: " 99411236143173d1aedeace570ac1133d3d5dfb268eManman Ren << getBlockName(PrevBB) << "\n"); 99511236143173d1aedeace570ac1133d3d5dfb268eManman Ren DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) 99611236143173d1aedeace570ac1133d3d5dfb268eManman Ren << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); 99711236143173d1aedeace570ac1133d3d5dfb268eManman Ren DebugLoc dl; // FIXME: this is nowhere 99811236143173d1aedeace570ac1133d3d5dfb268eManman Ren TII->RemoveBranch(*PrevBB); 99911236143173d1aedeace570ac1133d3d5dfb268eManman Ren TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); 100011236143173d1aedeace570ac1133d3d5dfb268eManman Ren } 1001df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth PrevBB->updateTerminator(); 100211236143173d1aedeace570ac1133d3d5dfb268eManman Ren } 1003db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth } 1004df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth 1005df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth // Fixup the last block. 1006df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth Cond.clear(); 1007df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. 1008df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) 1009df234353fb396e84e7a3a1cdd94f73681e65bd88Chandler Carruth F.back().updateTerminator(); 10104a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 101170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // Walk through the backedges of the function now that we have fully laid out 101270daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth // the basic blocks and align the destination of each backedge. We don't rely 1013e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // exclusively on the loop info here so that we can align backedges in 1014e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // unnatural CFGs and backedges that were introduced purely because of the 1015e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // loop rotations done during this layout pass. 1016831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling if (F.getFunction()->getAttributes(). 1017831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize)) 10184a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; 10194a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth unsigned Align = TLI->getPrefLoopAlignment(); 10204a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth if (!Align) 10214a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth return; // Don't care about loop alignment. 1022e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (FunctionChain.begin() == FunctionChain.end()) 1023e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth return; // Empty chain. 10244a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 1025e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth const BranchProbability ColdProb(1, 5); // 20% 1026e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); 1027e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; 1028e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth for (BlockChain::iterator BI = llvm::next(FunctionChain.begin()), 102970daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BE = FunctionChain.end(); 103070daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth BI != BE; ++BI) { 1031e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Don't align non-looping basic blocks. These are unlikely to execute 1032e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // enough times to matter in practice. Note that we'll still handle 1033e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // unnatural CFGs inside of a natural outer loop (the common case) and 1034e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // rotated loops. 1035e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth MachineLoop *L = MLI->getLoopFor(*BI); 1036e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (!L) 1037e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1038e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1039e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // If the block is cold relative to the function entry don't waste space 1040e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // aligning it. 1041e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency Freq = MBFI->getBlockFreq(*BI); 1042e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (Freq < WeightedEntryFreq) 1043e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1044e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1045e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // If the block is cold relative to its loop header, don't align it 1046e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // regardless of what edges into the block exist. 1047e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth MachineBasicBlock *LoopHeader = L->getHeader(); 1048e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); 1049e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (Freq < (LoopHeaderFreq * ColdProb)) 1050e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1051e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1052e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Check for the existence of a non-layout predecessor which would benefit 1053e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // from aligning this block. 1054e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth MachineBasicBlock *LayoutPred = *llvm::prior(BI); 1055e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1056e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Force alignment if all the predecessors are jumps. We already checked 1057e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // that the block isn't cold above. 1058e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (!LayoutPred->isSuccessor(*BI)) { 1059e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth (*BI)->setAlignment(Align); 1060e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth continue; 1061e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth } 1062e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth 1063e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // Align this block if the layout predecessor's edge into this block is 1064e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // cold relative to the block. When this is true, othe predecessors make up 1065e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // all of the hot entries into the block and thus alignment is likely to be 1066e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth // important. 1067e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BranchProbability LayoutProb = MBPI->getEdgeProbability(LayoutPred, *BI); 1068e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; 1069e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth if (LayoutEdgeFreq <= (Freq * ColdProb)) 1070e6450dc2afc18531bf9b70180a9f67376d9f00c7Chandler Carruth (*BI)->setAlignment(Align); 107170daea90afc167a010a1851defda01d7e0eb45ebChandler Carruth } 10724a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth} 10734a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth 1074db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruthbool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { 1075db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // Check for single-block functions and skip them. 1076db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth if (llvm::next(F.begin()) == F.end()) 1077db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return false; 1078db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1079db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 1080db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 10814a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth MLI = &getAnalysis<MachineLoopInfo>(); 1082db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth TII = F.getTarget().getInstrInfo(); 10834a85cc982a977ddeb0249eb9304326deabe3a7a5Chandler Carruth TLI = F.getTarget().getTargetLowering(); 1084db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth assert(BlockToChain.empty()); 1085db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 10863071363bcdfd75e81326b4033970d8bee5b1b376Chandler Carruth buildCFGChains(F); 1087db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1088db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth BlockToChain.clear(); 1089f5e47ac596c698f1659c86bdad3a60056e68439cChandler Carruth ChainAllocator.DestroyAll(); 1090db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth 1091db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // We always return true as we have no way to track whether the final order 1092db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth // differs from the original order. 1093db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth return true; 1094db35087d21f09fdde81cab7e12fc0bcd8b7d00e9Chandler Carruth} 109537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 109637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthnamespace { 109737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// \brief A pass to compute block placement statistics. 109837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// 109937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// A separate pass to compute interesting statistics for evaluating block 110037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// placement. This is separate from the actual placement pass so that they can 1101d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer/// be computed in the absence of any placement transformations or when using 110237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth/// alternative placement strategies. 110337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthclass MachineBlockPlacementStats : public MachineFunctionPass { 110437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the branch probability pass. 110537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBranchProbabilityInfo *MBPI; 110637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 110737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth /// \brief A handle to the function-wide block frequency pass. 110837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth const MachineBlockFrequencyInfo *MBFI; 110937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 111037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthpublic: 111137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth static char ID; // Pass identification, replacement for typeid 111237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineBlockPlacementStats() : MachineFunctionPass(ID) { 111337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); 111437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 111537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 111637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth bool runOnMachineFunction(MachineFunction &F); 111737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 111837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth void getAnalysisUsage(AnalysisUsage &AU) const { 111937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBranchProbabilityInfo>(); 112037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.addRequired<MachineBlockFrequencyInfo>(); 112137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth AU.setPreservesAll(); 112237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MachineFunctionPass::getAnalysisUsage(AU); 112337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 112437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth}; 112537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 112637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 112737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthchar MachineBlockPlacementStats::ID = 0; 11281dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; 112937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", 113037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 113137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 113237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 113337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler CarruthINITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", 113437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth "Basic Block Placement Stats", false, false) 113537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 113637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruthbool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { 113737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Check for single-block functions and skip them. 113837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth if (llvm::next(F.begin()) == F.end()) 113937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 114037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 114137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 114237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 114337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 114437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { 114537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency BlockFreq = MBFI->getBlockFreq(I); 114637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches 114737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : NumUncondBranches; 114837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq 114937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth : UncondBranchTakenFreq; 115037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), 115137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SE = I->succ_end(); 115237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth SI != SE; ++SI) { 115337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth // Skip if this successor is a fallthrough. 115437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth if (I->isLayoutSuccessor(*SI)) 115537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth continue; 115637efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 115737efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); 115837efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth ++NumBranches; 115937efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth BranchTakenFreq += EdgeFreq.getFrequency(); 116037efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 116137efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth } 116237efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 116337efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth return false; 116437efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth} 116537efc9fe42a4867c81526cac7fca9fe0ea04a484Chandler Carruth 1166