Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1 | //===-- MachineBlockPlacement.cpp - Basic Block Code Layout optimization --===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 10 | // This file implements basic block placement transformations using the CFG |
| 11 | // structure and branch probability estimates. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 12 | // |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 13 | // The pass strives to preserve the structure of the CFG (that is, retain |
Benjamin Kramer | d9b0b02 | 2012-06-02 10:20:22 +0000 | [diff] [blame] | 14 | // a topological ordering of basic blocks) in the absence of a *strong* signal |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 15 | // to the contrary from probabilities. However, within the CFG structure, it |
| 16 | // attempts to choose an ordering which favors placing more likely sequences of |
| 17 | // blocks adjacent to each other. |
| 18 | // |
| 19 | // The algorithm works from the inner-most loop within a function outward, and |
| 20 | // at each stage walks through the basic blocks, trying to coalesce them into |
| 21 | // sequential chains where allowed by the CFG (or demanded by heavy |
| 22 | // probabilities). Finally, it walks the blocks in topological order, and the |
| 23 | // first time it reaches a chain of basic blocks, it schedules them in the |
| 24 | // function in-order. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 25 | // |
| 26 | //===----------------------------------------------------------------------===// |
| 27 | |
| 28 | #define DEBUG_TYPE "block-placement2" |
Chandler Carruth | d04a8d4 | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 29 | #include "llvm/CodeGen/Passes.h" |
| 30 | #include "llvm/ADT/DenseMap.h" |
| 31 | #include "llvm/ADT/SmallPtrSet.h" |
| 32 | #include "llvm/ADT/SmallVector.h" |
| 33 | #include "llvm/ADT/Statistic.h" |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 34 | #include "llvm/CodeGen/MachineBasicBlock.h" |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 35 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
| 36 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
| 37 | #include "llvm/CodeGen/MachineFunction.h" |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 38 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 39 | #include "llvm/CodeGen/MachineLoopInfo.h" |
| 40 | #include "llvm/CodeGen/MachineModuleInfo.h" |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 41 | #include "llvm/Support/Allocator.h" |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 42 | #include "llvm/Support/Debug.h" |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 43 | #include "llvm/Target/TargetInstrInfo.h" |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 44 | #include "llvm/Target/TargetLowering.h" |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 45 | #include <algorithm> |
| 46 | using namespace llvm; |
| 47 | |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 48 | STATISTIC(NumCondBranches, "Number of conditional branches"); |
| 49 | STATISTIC(NumUncondBranches, "Number of uncondittional branches"); |
| 50 | STATISTIC(CondBranchTakenFreq, |
| 51 | "Potential frequency of taking conditional branches"); |
| 52 | STATISTIC(UncondBranchTakenFreq, |
| 53 | "Potential frequency of taking unconditional branches"); |
| 54 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 55 | namespace { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 56 | class BlockChain; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 57 | /// \brief Type for our function-wide basic block -> block chain mapping. |
| 58 | typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType; |
| 59 | } |
| 60 | |
| 61 | namespace { |
| 62 | /// \brief A chain of blocks which will be laid out contiguously. |
| 63 | /// |
| 64 | /// This is the datastructure representing a chain of consecutive blocks that |
| 65 | /// are profitable to layout together in order to maximize fallthrough |
Chandler Carruth | c04f816 | 2012-06-26 05:16:37 +0000 | [diff] [blame] | 66 | /// probabilities and code locality. We also can use a block chain to represent |
| 67 | /// a sequence of basic blocks which have some external (correctness) |
| 68 | /// requirement for sequential layout. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 69 | /// |
Chandler Carruth | c04f816 | 2012-06-26 05:16:37 +0000 | [diff] [blame] | 70 | /// Chains can be built around a single basic block and can be merged to grow |
| 71 | /// them. They participate in a block-to-chain mapping, which is updated |
| 72 | /// automatically as chains are merged together. |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 73 | class BlockChain { |
| 74 | /// \brief The sequence of blocks belonging to this chain. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 75 | /// |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 76 | /// This is the sequence of blocks for a particular chain. These will be laid |
| 77 | /// out in-order within the function. |
| 78 | SmallVector<MachineBasicBlock *, 4> Blocks; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 79 | |
| 80 | /// \brief A handle to the function-wide basic block to block chain mapping. |
| 81 | /// |
| 82 | /// This is retained in each block chain to simplify the computation of child |
| 83 | /// block chains for SCC-formation and iteration. We store the edges to child |
| 84 | /// basic blocks, and map them back to their associated chains using this |
| 85 | /// structure. |
| 86 | BlockToChainMapType &BlockToChain; |
| 87 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 88 | public: |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 89 | /// \brief Construct a new BlockChain. |
| 90 | /// |
| 91 | /// This builds a new block chain representing a single basic block in the |
| 92 | /// function. It also registers itself as the chain that block participates |
| 93 | /// in with the BlockToChain mapping. |
| 94 | BlockChain(BlockToChainMapType &BlockToChain, MachineBasicBlock *BB) |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 95 | : Blocks(1, BB), BlockToChain(BlockToChain), LoopPredecessors(0) { |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 96 | assert(BB && "Cannot create a chain with a null basic block"); |
| 97 | BlockToChain[BB] = this; |
| 98 | } |
| 99 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 100 | /// \brief Iterator over blocks within the chain. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 101 | typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator; |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 102 | |
| 103 | /// \brief Beginning of blocks within the chain. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 104 | iterator begin() { return Blocks.begin(); } |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 105 | |
| 106 | /// \brief End of blocks within the chain. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 107 | iterator end() { return Blocks.end(); } |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 108 | |
| 109 | /// \brief Merge a block chain into this one. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 110 | /// |
| 111 | /// This routine merges a block chain into this one. It takes care of forming |
| 112 | /// a contiguous sequence of basic blocks, updating the edge list, and |
| 113 | /// updating the block -> chain mapping. It does not free or tear down the |
| 114 | /// old chain, but the old chain's block list is no longer valid. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 115 | void merge(MachineBasicBlock *BB, BlockChain *Chain) { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 116 | assert(BB); |
| 117 | assert(!Blocks.empty()); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 118 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 119 | // Fast path in case we don't have a chain already. |
| 120 | if (!Chain) { |
| 121 | assert(!BlockToChain[BB]); |
| 122 | Blocks.push_back(BB); |
| 123 | BlockToChain[BB] = this; |
| 124 | return; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 125 | } |
| 126 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 127 | assert(BB == *Chain->begin()); |
| 128 | assert(Chain->begin() != Chain->end()); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 129 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 130 | // Update the incoming blocks to point to this chain, and add them to the |
| 131 | // chain structure. |
| 132 | for (BlockChain::iterator BI = Chain->begin(), BE = Chain->end(); |
| 133 | BI != BE; ++BI) { |
| 134 | Blocks.push_back(*BI); |
| 135 | assert(BlockToChain[*BI] == Chain && "Incoming blocks not in chain"); |
| 136 | BlockToChain[*BI] = this; |
| 137 | } |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 138 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 139 | |
Chandler Carruth | 6313d94 | 2012-04-08 14:37:01 +0000 | [diff] [blame] | 140 | #ifndef NDEBUG |
| 141 | /// \brief Dump the blocks in this chain. |
| 142 | void dump() LLVM_ATTRIBUTE_USED { |
| 143 | for (iterator I = begin(), E = end(); I != E; ++I) |
| 144 | (*I)->dump(); |
| 145 | } |
| 146 | #endif // NDEBUG |
| 147 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 148 | /// \brief Count of predecessors within the loop currently being processed. |
| 149 | /// |
| 150 | /// This count is updated at each loop we process to represent the number of |
| 151 | /// in-loop predecessors of this chain. |
| 152 | unsigned LoopPredecessors; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 153 | }; |
| 154 | } |
| 155 | |
| 156 | namespace { |
| 157 | class MachineBlockPlacement : public MachineFunctionPass { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 158 | /// \brief A typedef for a block filter set. |
| 159 | typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet; |
| 160 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 161 | /// \brief A handle to the branch probability pass. |
| 162 | const MachineBranchProbabilityInfo *MBPI; |
| 163 | |
| 164 | /// \brief A handle to the function-wide block frequency pass. |
| 165 | const MachineBlockFrequencyInfo *MBFI; |
| 166 | |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 167 | /// \brief A handle to the loop info. |
| 168 | const MachineLoopInfo *MLI; |
| 169 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 170 | /// \brief A handle to the target's instruction info. |
| 171 | const TargetInstrInfo *TII; |
| 172 | |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 173 | /// \brief A handle to the target's lowering info. |
| 174 | const TargetLowering *TLI; |
| 175 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 176 | /// \brief Allocator and owner of BlockChain structures. |
| 177 | /// |
Chandler Carruth | c04f816 | 2012-06-26 05:16:37 +0000 | [diff] [blame] | 178 | /// We build BlockChains lazily while processing the loop structure of |
| 179 | /// a function. To reduce malloc traffic, we allocate them using this |
| 180 | /// slab-like allocator, and destroy them after the pass completes. An |
| 181 | /// important guarantee is that this allocator produces stable pointers to |
| 182 | /// the chains. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 183 | SpecificBumpPtrAllocator<BlockChain> ChainAllocator; |
| 184 | |
| 185 | /// \brief Function wide BasicBlock to BlockChain mapping. |
| 186 | /// |
| 187 | /// This mapping allows efficiently moving from any given basic block to the |
| 188 | /// BlockChain it participates in, if any. We use it to, among other things, |
| 189 | /// allow implicitly defining edges between chains as the existing edges |
| 190 | /// between basic blocks. |
| 191 | DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain; |
| 192 | |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 193 | void markChainSuccessors(BlockChain &Chain, |
| 194 | MachineBasicBlock *LoopHeaderBB, |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 195 | SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 196 | const BlockFilterSet *BlockFilter = 0); |
| 197 | MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, |
| 198 | BlockChain &Chain, |
| 199 | const BlockFilterSet *BlockFilter); |
Chandler Carruth | f3fc005 | 2011-11-13 11:42:26 +0000 | [diff] [blame] | 200 | MachineBasicBlock *selectBestCandidateBlock( |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 201 | BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, |
| 202 | const BlockFilterSet *BlockFilter); |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 203 | MachineBasicBlock *getFirstUnplacedBlock( |
| 204 | MachineFunction &F, |
| 205 | const BlockChain &PlacedChain, |
| 206 | MachineFunction::iterator &PrevUnplacedBlockIt, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 207 | const BlockFilterSet *BlockFilter); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 208 | void buildChain(MachineBasicBlock *BB, BlockChain &Chain, |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 209 | SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 210 | const BlockFilterSet *BlockFilter = 0); |
Chandler Carruth | e773e8c | 2012-04-16 13:33:36 +0000 | [diff] [blame] | 211 | MachineBasicBlock *findBestLoopTop(MachineLoop &L, |
| 212 | const BlockFilterSet &LoopBlockSet); |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 213 | MachineBasicBlock *findBestLoopExit(MachineFunction &F, |
| 214 | MachineLoop &L, |
| 215 | const BlockFilterSet &LoopBlockSet); |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 216 | void buildLoopChains(MachineFunction &F, MachineLoop &L); |
Chandler Carruth | 16295fc | 2012-04-16 09:31:23 +0000 | [diff] [blame] | 217 | void rotateLoop(BlockChain &LoopChain, MachineBasicBlock *ExitingBB, |
| 218 | const BlockFilterSet &LoopBlockSet); |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 219 | void buildCFGChains(MachineFunction &F); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 220 | |
| 221 | public: |
| 222 | static char ID; // Pass identification, replacement for typeid |
| 223 | MachineBlockPlacement() : MachineFunctionPass(ID) { |
| 224 | initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry()); |
| 225 | } |
| 226 | |
| 227 | bool runOnMachineFunction(MachineFunction &F); |
| 228 | |
| 229 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 230 | AU.addRequired<MachineBranchProbabilityInfo>(); |
| 231 | AU.addRequired<MachineBlockFrequencyInfo>(); |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 232 | AU.addRequired<MachineLoopInfo>(); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 233 | MachineFunctionPass::getAnalysisUsage(AU); |
| 234 | } |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 235 | }; |
| 236 | } |
| 237 | |
| 238 | char MachineBlockPlacement::ID = 0; |
Andrew Trick | 1dd8c85 | 2012-02-08 21:23:13 +0000 | [diff] [blame] | 239 | char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 240 | INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2", |
| 241 | "Branch Probability Basic Block Placement", false, false) |
| 242 | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) |
| 243 | INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 244 | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 245 | INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2", |
| 246 | "Branch Probability Basic Block Placement", false, false) |
| 247 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 248 | #ifndef NDEBUG |
| 249 | /// \brief Helper to print the name of a MBB. |
| 250 | /// |
| 251 | /// Only used by debug logging. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 252 | static std::string getBlockName(MachineBasicBlock *BB) { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 253 | std::string Result; |
| 254 | raw_string_ostream OS(Result); |
| 255 | OS << "BB#" << BB->getNumber() |
| 256 | << " (derived from LLVM BB '" << BB->getName() << "')"; |
| 257 | OS.flush(); |
| 258 | return Result; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 259 | } |
| 260 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 261 | /// \brief Helper to print the number of a MBB. |
| 262 | /// |
| 263 | /// Only used by debug logging. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 264 | static std::string getBlockNum(MachineBasicBlock *BB) { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 265 | std::string Result; |
| 266 | raw_string_ostream OS(Result); |
| 267 | OS << "BB#" << BB->getNumber(); |
| 268 | OS.flush(); |
| 269 | return Result; |
| 270 | } |
| 271 | #endif |
| 272 | |
Chandler Carruth | 729bec8 | 2011-11-13 11:34:55 +0000 | [diff] [blame] | 273 | /// \brief Mark a chain's successors as having one fewer preds. |
| 274 | /// |
| 275 | /// When a chain is being merged into the "placed" chain, this routine will |
| 276 | /// quickly walk the successors of each block in the chain and mark them as |
| 277 | /// having one fewer active predecessor. It also adds any successors of this |
| 278 | /// chain which reach the zero-predecessor state to the worklist passed in. |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 279 | void MachineBlockPlacement::markChainSuccessors( |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 280 | BlockChain &Chain, |
| 281 | MachineBasicBlock *LoopHeaderBB, |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 282 | SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 283 | const BlockFilterSet *BlockFilter) { |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 284 | // Walk all the blocks in this chain, marking their successors as having |
| 285 | // a predecessor placed. |
| 286 | for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end(); |
| 287 | CBI != CBE; ++CBI) { |
| 288 | // Add any successors for which this is the only un-placed in-loop |
| 289 | // predecessor to the worklist as a viable candidate for CFG-neutral |
| 290 | // placement. No subsequent placement of this block will violate the CFG |
| 291 | // shape, so we get to use heuristics to choose a favorable placement. |
| 292 | for (MachineBasicBlock::succ_iterator SI = (*CBI)->succ_begin(), |
| 293 | SE = (*CBI)->succ_end(); |
| 294 | SI != SE; ++SI) { |
| 295 | if (BlockFilter && !BlockFilter->count(*SI)) |
| 296 | continue; |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 297 | BlockChain &SuccChain = *BlockToChain[*SI]; |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 298 | // Disregard edges within a fixed chain, or edges to the loop header. |
| 299 | if (&Chain == &SuccChain || *SI == LoopHeaderBB) |
| 300 | continue; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 301 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 302 | // This is a cross-chain edge that is within the loop, so decrement the |
| 303 | // loop predecessor count of the destination chain. |
| 304 | if (SuccChain.LoopPredecessors > 0 && --SuccChain.LoopPredecessors == 0) |
Chandler Carruth | a2deea1 | 2011-11-24 08:46:04 +0000 | [diff] [blame] | 305 | BlockWorkList.push_back(*SuccChain.begin()); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 306 | } |
| 307 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 308 | } |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 309 | |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 310 | /// \brief Select the best successor for a block. |
| 311 | /// |
| 312 | /// This looks across all successors of a particular block and attempts to |
| 313 | /// select the "best" one to be the layout successor. It only considers direct |
| 314 | /// successors which also pass the block filter. It will attempt to avoid |
| 315 | /// breaking CFG structure, but cave and break such structures in the case of |
| 316 | /// very hot successor edges. |
| 317 | /// |
| 318 | /// \returns The best successor block found, or null if none are viable. |
| 319 | MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor( |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 320 | MachineBasicBlock *BB, BlockChain &Chain, |
| 321 | const BlockFilterSet *BlockFilter) { |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 322 | const BranchProbability HotProb(4, 5); // 80% |
| 323 | |
| 324 | MachineBasicBlock *BestSucc = 0; |
Chandler Carruth | 340d596 | 2011-11-14 09:12:57 +0000 | [diff] [blame] | 325 | // FIXME: Due to the performance of the probability and weight routines in |
| 326 | // the MBPI analysis, we manually compute probabilities using the edge |
| 327 | // weights. This is suboptimal as it means that the somewhat subtle |
| 328 | // definition of edge weight semantics is encoded here as well. We should |
Benjamin Kramer | d9b0b02 | 2012-06-02 10:20:22 +0000 | [diff] [blame] | 329 | // improve the MBPI interface to efficiently support query patterns such as |
Chandler Carruth | 340d596 | 2011-11-14 09:12:57 +0000 | [diff] [blame] | 330 | // this. |
| 331 | uint32_t BestWeight = 0; |
| 332 | uint32_t WeightScale = 0; |
| 333 | uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale); |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 334 | DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n"); |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 335 | for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), |
| 336 | SE = BB->succ_end(); |
| 337 | SI != SE; ++SI) { |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 338 | if (BlockFilter && !BlockFilter->count(*SI)) |
| 339 | continue; |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 340 | BlockChain &SuccChain = *BlockToChain[*SI]; |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 341 | if (&SuccChain == &Chain) { |
| 342 | DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Already merged!\n"); |
| 343 | continue; |
| 344 | } |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 345 | if (*SI != *SuccChain.begin()) { |
| 346 | DEBUG(dbgs() << " " << getBlockName(*SI) << " -> Mid chain!\n"); |
| 347 | continue; |
| 348 | } |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 349 | |
Chandler Carruth | 340d596 | 2011-11-14 09:12:57 +0000 | [diff] [blame] | 350 | uint32_t SuccWeight = MBPI->getEdgeWeight(BB, *SI); |
| 351 | BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 352 | |
| 353 | // Only consider successors which are either "hot", or wouldn't violate |
| 354 | // any CFG constraints. |
Chandler Carruth | b0dadb9 | 2011-11-20 11:22:06 +0000 | [diff] [blame] | 355 | if (SuccChain.LoopPredecessors != 0) { |
| 356 | if (SuccProb < HotProb) { |
| 357 | DEBUG(dbgs() << " " << getBlockName(*SI) << " -> CFG conflict\n"); |
| 358 | continue; |
| 359 | } |
| 360 | |
| 361 | // Make sure that a hot successor doesn't have a globally more important |
| 362 | // predecessor. |
| 363 | BlockFrequency CandidateEdgeFreq |
| 364 | = MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl(); |
| 365 | bool BadCFGConflict = false; |
| 366 | for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(), |
| 367 | PE = (*SI)->pred_end(); |
| 368 | PI != PE; ++PI) { |
| 369 | if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) || |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 370 | BlockToChain[*PI] == &Chain) |
Chandler Carruth | b0dadb9 | 2011-11-20 11:22:06 +0000 | [diff] [blame] | 371 | continue; |
| 372 | BlockFrequency PredEdgeFreq |
| 373 | = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI); |
| 374 | if (PredEdgeFreq >= CandidateEdgeFreq) { |
| 375 | BadCFGConflict = true; |
| 376 | break; |
| 377 | } |
| 378 | } |
| 379 | if (BadCFGConflict) { |
| 380 | DEBUG(dbgs() << " " << getBlockName(*SI) |
| 381 | << " -> non-cold CFG conflict\n"); |
| 382 | continue; |
| 383 | } |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 384 | } |
| 385 | |
| 386 | DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb |
| 387 | << " (prob)" |
| 388 | << (SuccChain.LoopPredecessors != 0 ? " (CFG break)" : "") |
| 389 | << "\n"); |
Chandler Carruth | 340d596 | 2011-11-14 09:12:57 +0000 | [diff] [blame] | 390 | if (BestSucc && BestWeight >= SuccWeight) |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 391 | continue; |
| 392 | BestSucc = *SI; |
Chandler Carruth | 340d596 | 2011-11-14 09:12:57 +0000 | [diff] [blame] | 393 | BestWeight = SuccWeight; |
Chandler Carruth | 9fd4e05 | 2011-11-13 11:34:53 +0000 | [diff] [blame] | 394 | } |
| 395 | return BestSucc; |
| 396 | } |
| 397 | |
Chandler Carruth | fa97658 | 2011-11-14 09:46:33 +0000 | [diff] [blame] | 398 | namespace { |
| 399 | /// \brief Predicate struct to detect blocks already placed. |
| 400 | class IsBlockPlaced { |
| 401 | const BlockChain &PlacedChain; |
| 402 | const BlockToChainMapType &BlockToChain; |
| 403 | |
| 404 | public: |
| 405 | IsBlockPlaced(const BlockChain &PlacedChain, |
| 406 | const BlockToChainMapType &BlockToChain) |
| 407 | : PlacedChain(PlacedChain), BlockToChain(BlockToChain) {} |
| 408 | |
| 409 | bool operator()(MachineBasicBlock *BB) const { |
| 410 | return BlockToChain.lookup(BB) == &PlacedChain; |
| 411 | } |
| 412 | }; |
| 413 | } |
| 414 | |
Chandler Carruth | f3fc005 | 2011-11-13 11:42:26 +0000 | [diff] [blame] | 415 | /// \brief Select the best block from a worklist. |
| 416 | /// |
| 417 | /// This looks through the provided worklist as a list of candidate basic |
| 418 | /// blocks and select the most profitable one to place. The definition of |
| 419 | /// profitable only really makes sense in the context of a loop. This returns |
| 420 | /// the most frequently visited block in the worklist, which in the case of |
| 421 | /// a loop, is the one most desirable to be physically close to the rest of the |
| 422 | /// loop body in order to improve icache behavior. |
| 423 | /// |
| 424 | /// \returns The best block found, or null if none are viable. |
| 425 | MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 426 | BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList, |
| 427 | const BlockFilterSet *BlockFilter) { |
Chandler Carruth | fa97658 | 2011-11-14 09:46:33 +0000 | [diff] [blame] | 428 | // Once we need to walk the worklist looking for a candidate, cleanup the |
| 429 | // worklist of already placed entries. |
| 430 | // FIXME: If this shows up on profiles, it could be folded (at the cost of |
| 431 | // some code complexity) into the loop below. |
| 432 | WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(), |
| 433 | IsBlockPlaced(Chain, BlockToChain)), |
| 434 | WorkList.end()); |
| 435 | |
Chandler Carruth | f3fc005 | 2011-11-13 11:42:26 +0000 | [diff] [blame] | 436 | MachineBasicBlock *BestBlock = 0; |
| 437 | BlockFrequency BestFreq; |
| 438 | for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = WorkList.begin(), |
| 439 | WBE = WorkList.end(); |
| 440 | WBI != WBE; ++WBI) { |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 441 | BlockChain &SuccChain = *BlockToChain[*WBI]; |
Chandler Carruth | f3fc005 | 2011-11-13 11:42:26 +0000 | [diff] [blame] | 442 | if (&SuccChain == &Chain) { |
| 443 | DEBUG(dbgs() << " " << getBlockName(*WBI) |
| 444 | << " -> Already merged!\n"); |
| 445 | continue; |
| 446 | } |
| 447 | assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block"); |
| 448 | |
| 449 | BlockFrequency CandidateFreq = MBFI->getBlockFreq(*WBI); |
| 450 | DEBUG(dbgs() << " " << getBlockName(*WBI) << " -> " << CandidateFreq |
| 451 | << " (freq)\n"); |
| 452 | if (BestBlock && BestFreq >= CandidateFreq) |
| 453 | continue; |
| 454 | BestBlock = *WBI; |
| 455 | BestFreq = CandidateFreq; |
| 456 | } |
| 457 | return BestBlock; |
| 458 | } |
| 459 | |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 460 | /// \brief Retrieve the first unplaced basic block. |
| 461 | /// |
| 462 | /// This routine is called when we are unable to use the CFG to walk through |
| 463 | /// all of the basic blocks and form a chain due to unnatural loops in the CFG. |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 464 | /// We walk through the function's blocks in order, starting from the |
| 465 | /// LastUnplacedBlockIt. We update this iterator on each call to avoid |
| 466 | /// re-scanning the entire sequence on repeated calls to this routine. |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 467 | MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 468 | MachineFunction &F, const BlockChain &PlacedChain, |
| 469 | MachineFunction::iterator &PrevUnplacedBlockIt, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 470 | const BlockFilterSet *BlockFilter) { |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 471 | for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E; |
| 472 | ++I) { |
| 473 | if (BlockFilter && !BlockFilter->count(I)) |
| 474 | continue; |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 475 | if (BlockToChain[I] != &PlacedChain) { |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 476 | PrevUnplacedBlockIt = I; |
Chandler Carruth | 47fb954 | 2011-11-23 03:03:21 +0000 | [diff] [blame] | 477 | // Now select the head of the chain to which the unplaced block belongs |
| 478 | // as the block to place. This will force the entire chain to be placed, |
| 479 | // and satisfies the requirements of merging chains. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 480 | return *BlockToChain[I]->begin(); |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 481 | } |
| 482 | } |
| 483 | return 0; |
| 484 | } |
| 485 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 486 | void MachineBlockPlacement::buildChain( |
| 487 | MachineBasicBlock *BB, |
| 488 | BlockChain &Chain, |
| 489 | SmallVectorImpl<MachineBasicBlock *> &BlockWorkList, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 490 | const BlockFilterSet *BlockFilter) { |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 491 | assert(BB); |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 492 | assert(BlockToChain[BB] == &Chain); |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 493 | MachineFunction &F = *BB->getParent(); |
| 494 | MachineFunction::iterator PrevUnplacedBlockIt = F.begin(); |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 495 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 496 | MachineBasicBlock *LoopHeaderBB = BB; |
| 497 | markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); |
| 498 | BB = *llvm::prior(Chain.end()); |
| 499 | for (;;) { |
| 500 | assert(BB); |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 501 | assert(BlockToChain[BB] == &Chain); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 502 | assert(*llvm::prior(Chain.end()) == BB); |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 503 | |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 504 | // Look for the best viable successor if there is one to place immediately |
| 505 | // after this block. |
Duncan Sands | 74b4762 | 2012-09-14 09:00:11 +0000 | [diff] [blame] | 506 | MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 507 | |
| 508 | // If an immediate successor isn't available, look for the best viable |
| 509 | // block among those we've identified as not violating the loop's CFG at |
| 510 | // this point. This won't be a fallthrough, but it will increase locality. |
Chandler Carruth | f3fc005 | 2011-11-13 11:42:26 +0000 | [diff] [blame] | 511 | if (!BestSucc) |
| 512 | BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 513 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 514 | if (!BestSucc) { |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 515 | BestSucc = getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, |
| 516 | BlockFilter); |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 517 | if (!BestSucc) |
| 518 | break; |
| 519 | |
| 520 | DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " |
| 521 | "layout successor until the CFG reduces\n"); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 522 | } |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 523 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 524 | // Place this block, updating the datastructures to reflect its placement. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 525 | BlockChain &SuccChain = *BlockToChain[BestSucc]; |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 526 | // Zero out LoopPredecessors for the successor we're about to merge in case |
| 527 | // we selected a successor that didn't fit naturally into the CFG. |
| 528 | SuccChain.LoopPredecessors = 0; |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 529 | DEBUG(dbgs() << "Merging from " << getBlockNum(BB) |
| 530 | << " to " << getBlockNum(BestSucc) << "\n"); |
| 531 | markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); |
| 532 | Chain.merge(BestSucc, &SuccChain); |
| 533 | BB = *llvm::prior(Chain.end()); |
Jakub Staszak | feb468a | 2011-12-07 19:46:10 +0000 | [diff] [blame] | 534 | } |
Chandler Carruth | b5856c8 | 2011-11-14 00:00:35 +0000 | [diff] [blame] | 535 | |
| 536 | DEBUG(dbgs() << "Finished forming chain for header block " |
| 537 | << getBlockNum(*Chain.begin()) << "\n"); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 538 | } |
| 539 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 540 | /// \brief Find the best loop top block for layout. |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 541 | /// |
Chandler Carruth | e773e8c | 2012-04-16 13:33:36 +0000 | [diff] [blame] | 542 | /// Look for a block which is strictly better than the loop header for laying |
| 543 | /// out at the top of the loop. This looks for one and only one pattern: |
| 544 | /// a latch block with no conditional exit. This block will cause a conditional |
| 545 | /// jump around it or will be the bottom of the loop if we lay it out in place, |
| 546 | /// but if it it doesn't end up at the bottom of the loop for any reason, |
| 547 | /// rotation alone won't fix it. Because such a block will always result in an |
| 548 | /// unconditional jump (for the backedge) rotating it in front of the loop |
| 549 | /// header is always profitable. |
| 550 | MachineBasicBlock * |
| 551 | MachineBlockPlacement::findBestLoopTop(MachineLoop &L, |
| 552 | const BlockFilterSet &LoopBlockSet) { |
| 553 | // Check that the header hasn't been fused with a preheader block due to |
| 554 | // crazy branches. If it has, we need to start with the header at the top to |
| 555 | // prevent pulling the preheader into the loop body. |
| 556 | BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; |
| 557 | if (!LoopBlockSet.count(*HeaderChain.begin())) |
| 558 | return L.getHeader(); |
| 559 | |
| 560 | DEBUG(dbgs() << "Finding best loop top for: " |
| 561 | << getBlockName(L.getHeader()) << "\n"); |
| 562 | |
| 563 | BlockFrequency BestPredFreq; |
| 564 | MachineBasicBlock *BestPred = 0; |
| 565 | for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(), |
| 566 | PE = L.getHeader()->pred_end(); |
| 567 | PI != PE; ++PI) { |
| 568 | MachineBasicBlock *Pred = *PI; |
| 569 | if (!LoopBlockSet.count(Pred)) |
| 570 | continue; |
| 571 | DEBUG(dbgs() << " header pred: " << getBlockName(Pred) << ", " |
| 572 | << Pred->succ_size() << " successors, " |
| 573 | << MBFI->getBlockFreq(Pred) << " freq\n"); |
| 574 | if (Pred->succ_size() > 1) |
| 575 | continue; |
| 576 | |
| 577 | BlockFrequency PredFreq = MBFI->getBlockFreq(Pred); |
| 578 | if (!BestPred || PredFreq > BestPredFreq || |
| 579 | (!(PredFreq < BestPredFreq) && |
| 580 | Pred->isLayoutSuccessor(L.getHeader()))) { |
| 581 | BestPred = Pred; |
| 582 | BestPredFreq = PredFreq; |
| 583 | } |
| 584 | } |
| 585 | |
| 586 | // If no direct predecessor is fine, just use the loop header. |
| 587 | if (!BestPred) |
| 588 | return L.getHeader(); |
| 589 | |
| 590 | // Walk backwards through any straight line of predecessors. |
| 591 | while (BestPred->pred_size() == 1 && |
| 592 | (*BestPred->pred_begin())->succ_size() == 1 && |
| 593 | *BestPred->pred_begin() != L.getHeader()) |
| 594 | BestPred = *BestPred->pred_begin(); |
| 595 | |
| 596 | DEBUG(dbgs() << " final top: " << getBlockName(BestPred) << "\n"); |
| 597 | return BestPred; |
| 598 | } |
| 599 | |
| 600 | |
| 601 | /// \brief Find the best loop exiting block for layout. |
| 602 | /// |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 603 | /// This routine implements the logic to analyze the loop looking for the best |
| 604 | /// block to layout at the top of the loop. Typically this is done to maximize |
| 605 | /// fallthrough opportunities. |
| 606 | MachineBasicBlock * |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 607 | MachineBlockPlacement::findBestLoopExit(MachineFunction &F, |
| 608 | MachineLoop &L, |
| 609 | const BlockFilterSet &LoopBlockSet) { |
Chandler Carruth | 45fb79b | 2012-04-10 13:35:57 +0000 | [diff] [blame] | 610 | // We don't want to layout the loop linearly in all cases. If the loop header |
| 611 | // is just a normal basic block in the loop, we want to look for what block |
| 612 | // within the loop is the best one to layout at the top. However, if the loop |
| 613 | // header has be pre-merged into a chain due to predecessors not having |
| 614 | // analyzable branches, *and* the predecessor it is merged with is *not* part |
| 615 | // of the loop, rotating the header into the middle of the loop will create |
| 616 | // a non-contiguous range of blocks which is Very Bad. So start with the |
| 617 | // header and only rotate if safe. |
| 618 | BlockChain &HeaderChain = *BlockToChain[L.getHeader()]; |
| 619 | if (!LoopBlockSet.count(*HeaderChain.begin())) |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 620 | return 0; |
Chandler Carruth | 45fb79b | 2012-04-10 13:35:57 +0000 | [diff] [blame] | 621 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 622 | BlockFrequency BestExitEdgeFreq; |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 623 | unsigned BestExitLoopDepth = 0; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 624 | MachineBasicBlock *ExitingBB = 0; |
Chandler Carruth | 51901d8 | 2011-11-27 20:18:00 +0000 | [diff] [blame] | 625 | // If there are exits to outer loops, loop rotation can severely limit |
| 626 | // fallthrough opportunites unless it selects such an exit. Keep a set of |
| 627 | // blocks where rotating to exit with that block will reach an outer loop. |
| 628 | SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop; |
| 629 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 630 | DEBUG(dbgs() << "Finding best loop exit for: " |
| 631 | << getBlockName(L.getHeader()) << "\n"); |
| 632 | for (MachineLoop::block_iterator I = L.block_begin(), |
| 633 | E = L.block_end(); |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 634 | I != E; ++I) { |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 635 | BlockChain &Chain = *BlockToChain[*I]; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 636 | // Ensure that this block is at the end of a chain; otherwise it could be |
| 637 | // mid-way through an inner loop or a successor of an analyzable branch. |
| 638 | if (*I != *llvm::prior(Chain.end())) |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 639 | continue; |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 640 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 641 | // Now walk the successors. We need to establish whether this has a viable |
| 642 | // exiting successor and whether it has a viable non-exiting successor. |
| 643 | // We store the old exiting state and restore it if a viable looping |
| 644 | // successor isn't found. |
| 645 | MachineBasicBlock *OldExitingBB = ExitingBB; |
| 646 | BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 647 | bool HasLoopingSucc = false; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 648 | // FIXME: Due to the performance of the probability and weight routines in |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 649 | // the MBPI analysis, we use the internal weights and manually compute the |
| 650 | // probabilities to avoid quadratic behavior. |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 651 | uint32_t WeightScale = 0; |
| 652 | uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); |
| 653 | for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), |
| 654 | SE = (*I)->succ_end(); |
Chandler Carruth | 2eb5a74 | 2011-11-27 09:22:53 +0000 | [diff] [blame] | 655 | SI != SE; ++SI) { |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 656 | if ((*SI)->isLandingPad()) |
| 657 | continue; |
| 658 | if (*SI == *I) |
| 659 | continue; |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 660 | BlockChain &SuccChain = *BlockToChain[*SI]; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 661 | // Don't split chains, either this chain or the successor's chain. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 662 | if (&Chain == &SuccChain) { |
| 663 | DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 664 | << getBlockName(*SI) << " (chain conflict)\n"); |
| 665 | continue; |
| 666 | } |
| 667 | |
| 668 | uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); |
| 669 | if (LoopBlockSet.count(*SI)) { |
| 670 | DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " |
| 671 | << getBlockName(*SI) << " (" << SuccWeight << ")\n"); |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 672 | HasLoopingSucc = true; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 673 | continue; |
| 674 | } |
| 675 | |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 676 | unsigned SuccLoopDepth = 0; |
| 677 | if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) { |
| 678 | SuccLoopDepth = ExitLoop->getLoopDepth(); |
| 679 | if (ExitLoop->contains(&L)) |
| 680 | BlocksExitingToOuterLoop.insert(*I); |
| 681 | } |
| 682 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 683 | BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); |
| 684 | BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; |
| 685 | DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 686 | << getBlockName(*SI) << " [L:" << SuccLoopDepth |
| 687 | << "] (" << ExitEdgeFreq << ")\n"); |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 688 | // Note that we slightly bias this toward an existing layout successor to |
| 689 | // retain incoming order in the absence of better information. |
| 690 | // FIXME: Should we bias this more strongly? It's pretty weak. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 691 | if (!ExitingBB || BestExitLoopDepth < SuccLoopDepth || |
| 692 | ExitEdgeFreq > BestExitEdgeFreq || |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 693 | ((*I)->isLayoutSuccessor(*SI) && |
| 694 | !(ExitEdgeFreq < BestExitEdgeFreq))) { |
| 695 | BestExitEdgeFreq = ExitEdgeFreq; |
| 696 | ExitingBB = *I; |
Chandler Carruth | 2eb5a74 | 2011-11-27 09:22:53 +0000 | [diff] [blame] | 697 | } |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 698 | } |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 699 | |
| 700 | // Restore the old exiting state, no viable looping successor was found. |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 701 | if (!HasLoopingSucc) { |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 702 | ExitingBB = OldExitingBB; |
| 703 | BestExitEdgeFreq = OldBestExitEdgeFreq; |
Chandler Carruth | 2eb5a74 | 2011-11-27 09:22:53 +0000 | [diff] [blame] | 704 | continue; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 705 | } |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 706 | } |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 707 | // Without a candidate exiting block or with only a single block in the |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 708 | // loop, just use the loop header to layout the loop. |
| 709 | if (!ExitingBB || L.getNumBlocks() == 1) |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 710 | return 0; |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 711 | |
Chandler Carruth | 51901d8 | 2011-11-27 20:18:00 +0000 | [diff] [blame] | 712 | // Also, if we have exit blocks which lead to outer loops but didn't select |
| 713 | // one of them as the exiting block we are rotating toward, disable loop |
| 714 | // rotation altogether. |
| 715 | if (!BlocksExitingToOuterLoop.empty() && |
| 716 | !BlocksExitingToOuterLoop.count(ExitingBB)) |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 717 | return 0; |
Chandler Carruth | 51901d8 | 2011-11-27 20:18:00 +0000 | [diff] [blame] | 718 | |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 719 | DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 720 | return ExitingBB; |
Chandler Carruth | 2e38cf9 | 2011-11-27 00:38:03 +0000 | [diff] [blame] | 721 | } |
| 722 | |
Chandler Carruth | 16295fc | 2012-04-16 09:31:23 +0000 | [diff] [blame] | 723 | /// \brief Attempt to rotate an exiting block to the bottom of the loop. |
| 724 | /// |
| 725 | /// Once we have built a chain, try to rotate it to line up the hot exit block |
| 726 | /// with fallthrough out of the loop if doing so doesn't introduce unnecessary |
| 727 | /// branches. For example, if the loop has fallthrough into its header and out |
| 728 | /// of its bottom already, don't rotate it. |
| 729 | void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain, |
| 730 | MachineBasicBlock *ExitingBB, |
| 731 | const BlockFilterSet &LoopBlockSet) { |
| 732 | if (!ExitingBB) |
| 733 | return; |
| 734 | |
| 735 | MachineBasicBlock *Top = *LoopChain.begin(); |
| 736 | bool ViableTopFallthrough = false; |
| 737 | for (MachineBasicBlock::pred_iterator PI = Top->pred_begin(), |
| 738 | PE = Top->pred_end(); |
| 739 | PI != PE; ++PI) { |
| 740 | BlockChain *PredChain = BlockToChain[*PI]; |
| 741 | if (!LoopBlockSet.count(*PI) && |
| 742 | (!PredChain || *PI == *llvm::prior(PredChain->end()))) { |
| 743 | ViableTopFallthrough = true; |
| 744 | break; |
| 745 | } |
| 746 | } |
| 747 | |
| 748 | // If the header has viable fallthrough, check whether the current loop |
| 749 | // bottom is a viable exiting block. If so, bail out as rotating will |
| 750 | // introduce an unnecessary branch. |
| 751 | if (ViableTopFallthrough) { |
| 752 | MachineBasicBlock *Bottom = *llvm::prior(LoopChain.end()); |
| 753 | for (MachineBasicBlock::succ_iterator SI = Bottom->succ_begin(), |
| 754 | SE = Bottom->succ_end(); |
| 755 | SI != SE; ++SI) { |
| 756 | BlockChain *SuccChain = BlockToChain[*SI]; |
| 757 | if (!LoopBlockSet.count(*SI) && |
| 758 | (!SuccChain || *SI == *SuccChain->begin())) |
| 759 | return; |
| 760 | } |
| 761 | } |
| 762 | |
| 763 | BlockChain::iterator ExitIt = std::find(LoopChain.begin(), LoopChain.end(), |
| 764 | ExitingBB); |
| 765 | if (ExitIt == LoopChain.end()) |
| 766 | return; |
| 767 | |
| 768 | std::rotate(LoopChain.begin(), llvm::next(ExitIt), LoopChain.end()); |
| 769 | } |
| 770 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 771 | /// \brief Forms basic block chains from the natural loop structures. |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 772 | /// |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 773 | /// These chains are designed to preserve the existing *structure* of the code |
| 774 | /// as much as possible. We can then stitch the chains together in a way which |
| 775 | /// both preserves the topological structure and minimizes taken conditional |
| 776 | /// branches. |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 777 | void MachineBlockPlacement::buildLoopChains(MachineFunction &F, |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 778 | MachineLoop &L) { |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 779 | // First recurse through any nested loops, building chains for those inner |
| 780 | // loops. |
| 781 | for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) |
| 782 | buildLoopChains(F, **LI); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 783 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 784 | SmallVector<MachineBasicBlock *, 16> BlockWorkList; |
| 785 | BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 786 | |
Chandler Carruth | e773e8c | 2012-04-16 13:33:36 +0000 | [diff] [blame] | 787 | // First check to see if there is an obviously preferable top block for the |
| 788 | // loop. This will default to the header, but may end up as one of the |
| 789 | // predecessors to the header if there is one which will result in strictly |
| 790 | // fewer branches in the loop body. |
| 791 | MachineBasicBlock *LoopTop = findBestLoopTop(L, LoopBlockSet); |
| 792 | |
| 793 | // If we selected just the header for the loop top, look for a potentially |
| 794 | // profitable exit block in the event that rotating the loop can eliminate |
| 795 | // branches by placing an exit edge at the bottom. |
| 796 | MachineBasicBlock *ExitingBB = 0; |
| 797 | if (LoopTop == L.getHeader()) |
| 798 | ExitingBB = findBestLoopExit(F, L, LoopBlockSet); |
| 799 | |
| 800 | BlockChain &LoopChain = *BlockToChain[LoopTop]; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 801 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 802 | // FIXME: This is a really lame way of walking the chains in the loop: we |
| 803 | // walk the blocks, and use a set to prevent visiting a particular chain |
| 804 | // twice. |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 805 | SmallPtrSet<BlockChain *, 4> UpdatedPreds; |
Jakub Staszak | feb468a | 2011-12-07 19:46:10 +0000 | [diff] [blame] | 806 | assert(LoopChain.LoopPredecessors == 0); |
| 807 | UpdatedPreds.insert(&LoopChain); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 808 | for (MachineLoop::block_iterator BI = L.block_begin(), |
| 809 | BE = L.block_end(); |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 810 | BI != BE; ++BI) { |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 811 | BlockChain &Chain = *BlockToChain[*BI]; |
Chandler Carruth | fac1305 | 2011-11-27 13:34:33 +0000 | [diff] [blame] | 812 | if (!UpdatedPreds.insert(&Chain)) |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 813 | continue; |
| 814 | |
| 815 | assert(Chain.LoopPredecessors == 0); |
| 816 | for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); |
| 817 | BCI != BCE; ++BCI) { |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 818 | assert(BlockToChain[*BCI] == &Chain); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 819 | for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), |
| 820 | PE = (*BCI)->pred_end(); |
| 821 | PI != PE; ++PI) { |
Jakub Staszak | d4895de | 2011-12-21 23:02:08 +0000 | [diff] [blame] | 822 | if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI)) |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 823 | continue; |
| 824 | ++Chain.LoopPredecessors; |
| 825 | } |
| 826 | } |
| 827 | |
| 828 | if (Chain.LoopPredecessors == 0) |
Chandler Carruth | a2deea1 | 2011-11-24 08:46:04 +0000 | [diff] [blame] | 829 | BlockWorkList.push_back(*Chain.begin()); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 830 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 831 | |
Chandler Carruth | e773e8c | 2012-04-16 13:33:36 +0000 | [diff] [blame] | 832 | buildChain(LoopTop, LoopChain, BlockWorkList, &LoopBlockSet); |
Chandler Carruth | 16295fc | 2012-04-16 09:31:23 +0000 | [diff] [blame] | 833 | rotateLoop(LoopChain, ExitingBB, LoopBlockSet); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 834 | |
| 835 | DEBUG({ |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 836 | // Crash at the end so we get all of the debugging output first. |
| 837 | bool BadLoop = false; |
| 838 | if (LoopChain.LoopPredecessors) { |
| 839 | BadLoop = true; |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 840 | dbgs() << "Loop chain contains a block without its preds placed!\n" |
| 841 | << " Loop header: " << getBlockName(*L.block_begin()) << "\n" |
| 842 | << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 843 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 844 | for (BlockChain::iterator BCI = LoopChain.begin(), BCE = LoopChain.end(); |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 845 | BCI != BCE; ++BCI) { |
| 846 | dbgs() << " ... " << getBlockName(*BCI) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 847 | if (!LoopBlockSet.erase(*BCI)) { |
Chandler Carruth | bc83fcd | 2011-11-14 10:55:53 +0000 | [diff] [blame] | 848 | // We don't mark the loop as bad here because there are real situations |
| 849 | // where this can occur. For example, with an unanalyzable fallthrough |
Chandler Carruth | 598894f | 2011-11-23 10:35:36 +0000 | [diff] [blame] | 850 | // from a loop block to a non-loop block or vice versa. |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 851 | dbgs() << "Loop chain contains a block not contained by the loop!\n" |
| 852 | << " Loop header: " << getBlockName(*L.block_begin()) << "\n" |
| 853 | << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" |
| 854 | << " Bad block: " << getBlockName(*BCI) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 855 | } |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 856 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 857 | |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 858 | if (!LoopBlockSet.empty()) { |
| 859 | BadLoop = true; |
Chandler Carruth | c0f05b3 | 2011-11-13 22:50:09 +0000 | [diff] [blame] | 860 | for (BlockFilterSet::iterator LBI = LoopBlockSet.begin(), |
| 861 | LBE = LoopBlockSet.end(); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 862 | LBI != LBE; ++LBI) |
| 863 | dbgs() << "Loop contains blocks never placed into a chain!\n" |
| 864 | << " Loop header: " << getBlockName(*L.block_begin()) << "\n" |
| 865 | << " Chain header: " << getBlockName(*LoopChain.begin()) << "\n" |
| 866 | << " Bad block: " << getBlockName(*LBI) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 867 | } |
| 868 | assert(!BadLoop && "Detected problems with the placement of this loop."); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 869 | }); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 870 | } |
| 871 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 872 | void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 873 | // Ensure that every BB in the function has an associated chain to simplify |
| 874 | // the assumptions of the remaining algorithm. |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 875 | SmallVector<MachineOperand, 4> Cond; // For AnalyzeBranch. |
| 876 | for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
| 877 | MachineBasicBlock *BB = FI; |
Chandler Carruth | 4aae4f9 | 2011-11-24 11:23:15 +0000 | [diff] [blame] | 878 | BlockChain *Chain |
| 879 | = new (ChainAllocator.Allocate()) BlockChain(BlockToChain, BB); |
Chandler Carruth | 03300ec | 2011-11-19 10:26:02 +0000 | [diff] [blame] | 880 | // Also, merge any blocks which we cannot reason about and must preserve |
| 881 | // the exact fallthrough behavior for. |
| 882 | for (;;) { |
| 883 | Cond.clear(); |
| 884 | MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. |
| 885 | if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough()) |
| 886 | break; |
| 887 | |
| 888 | MachineFunction::iterator NextFI(llvm::next(FI)); |
| 889 | MachineBasicBlock *NextBB = NextFI; |
| 890 | // Ensure that the layout successor is a viable block, as we know that |
| 891 | // fallthrough is a possibility. |
| 892 | assert(NextFI != FE && "Can't fallthrough past the last block."); |
| 893 | DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: " |
| 894 | << getBlockName(BB) << " -> " << getBlockName(NextBB) |
| 895 | << "\n"); |
| 896 | Chain->merge(NextBB, 0); |
| 897 | FI = NextFI; |
| 898 | BB = NextBB; |
| 899 | } |
| 900 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 901 | |
| 902 | // Build any loop-based chains. |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 903 | for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE; |
| 904 | ++LI) |
| 905 | buildLoopChains(F, **LI); |
| 906 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 907 | SmallVector<MachineBasicBlock *, 16> BlockWorkList; |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 908 | |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 909 | SmallPtrSet<BlockChain *, 4> UpdatedPreds; |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 910 | for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 911 | MachineBasicBlock *BB = &*FI; |
| 912 | BlockChain &Chain = *BlockToChain[BB]; |
| 913 | if (!UpdatedPreds.insert(&Chain)) |
| 914 | continue; |
| 915 | |
| 916 | assert(Chain.LoopPredecessors == 0); |
| 917 | for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end(); |
| 918 | BCI != BCE; ++BCI) { |
| 919 | assert(BlockToChain[*BCI] == &Chain); |
| 920 | for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(), |
| 921 | PE = (*BCI)->pred_end(); |
| 922 | PI != PE; ++PI) { |
| 923 | if (BlockToChain[*PI] == &Chain) |
| 924 | continue; |
| 925 | ++Chain.LoopPredecessors; |
| 926 | } |
| 927 | } |
| 928 | |
| 929 | if (Chain.LoopPredecessors == 0) |
Chandler Carruth | a2deea1 | 2011-11-24 08:46:04 +0000 | [diff] [blame] | 930 | BlockWorkList.push_back(*Chain.begin()); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 931 | } |
| 932 | |
| 933 | BlockChain &FunctionChain = *BlockToChain[&F.front()]; |
Chandler Carruth | 3273c89 | 2011-11-15 06:26:43 +0000 | [diff] [blame] | 934 | buildChain(&F.front(), FunctionChain, BlockWorkList); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 935 | |
| 936 | typedef SmallPtrSet<MachineBasicBlock *, 16> FunctionBlockSetType; |
| 937 | DEBUG({ |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 938 | // Crash at the end so we get all of the debugging output first. |
| 939 | bool BadFunc = false; |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 940 | FunctionBlockSetType FunctionBlockSet; |
| 941 | for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) |
| 942 | FunctionBlockSet.insert(FI); |
| 943 | |
Chandler Carruth | c0f05b3 | 2011-11-13 22:50:09 +0000 | [diff] [blame] | 944 | for (BlockChain::iterator BCI = FunctionChain.begin(), |
| 945 | BCE = FunctionChain.end(); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 946 | BCI != BCE; ++BCI) |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 947 | if (!FunctionBlockSet.erase(*BCI)) { |
| 948 | BadFunc = true; |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 949 | dbgs() << "Function chain contains a block not in the function!\n" |
| 950 | << " Bad block: " << getBlockName(*BCI) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 951 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 952 | |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 953 | if (!FunctionBlockSet.empty()) { |
| 954 | BadFunc = true; |
Chandler Carruth | c0f05b3 | 2011-11-13 22:50:09 +0000 | [diff] [blame] | 955 | for (FunctionBlockSetType::iterator FBI = FunctionBlockSet.begin(), |
| 956 | FBE = FunctionBlockSet.end(); |
| 957 | FBI != FBE; ++FBI) |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 958 | dbgs() << "Function contains blocks never placed into a chain!\n" |
| 959 | << " Bad block: " << getBlockName(*FBI) << "\n"; |
Chandler Carruth | 10252db | 2011-11-13 21:39:51 +0000 | [diff] [blame] | 960 | } |
| 961 | assert(!BadFunc && "Detected problems with the block placement."); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 962 | }); |
| 963 | |
| 964 | // Splice the blocks into place. |
| 965 | MachineFunction::iterator InsertPos = F.begin(); |
Chandler Carruth | c0f05b3 | 2011-11-13 22:50:09 +0000 | [diff] [blame] | 966 | for (BlockChain::iterator BI = FunctionChain.begin(), |
| 967 | BE = FunctionChain.end(); |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 968 | BI != BE; ++BI) { |
| 969 | DEBUG(dbgs() << (BI == FunctionChain.begin() ? "Placing chain " |
| 970 | : " ... ") |
| 971 | << getBlockName(*BI) << "\n"); |
| 972 | if (InsertPos != MachineFunction::iterator(*BI)) |
| 973 | F.splice(InsertPos, *BI); |
| 974 | else |
| 975 | ++InsertPos; |
| 976 | |
| 977 | // Update the terminator of the previous block. |
| 978 | if (BI == FunctionChain.begin()) |
| 979 | continue; |
| 980 | MachineBasicBlock *PrevBB = llvm::prior(MachineFunction::iterator(*BI)); |
| 981 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 982 | // FIXME: It would be awesome of updateTerminator would just return rather |
| 983 | // than assert when the branch cannot be analyzed in order to remove this |
| 984 | // boiler plate. |
| 985 | Cond.clear(); |
| 986 | MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. |
Manman Ren | 1123614 | 2012-07-31 01:11:07 +0000 | [diff] [blame] | 987 | if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) { |
| 988 | // If PrevBB has a two-way branch, try to re-order the branches |
| 989 | // such that we branch to the successor with higher weight first. |
| 990 | if (TBB && !Cond.empty() && FBB && |
| 991 | MBPI->getEdgeWeight(PrevBB, FBB) > MBPI->getEdgeWeight(PrevBB, TBB) && |
| 992 | !TII->ReverseBranchCondition(Cond)) { |
| 993 | DEBUG(dbgs() << "Reverse order of the two branches: " |
| 994 | << getBlockName(PrevBB) << "\n"); |
| 995 | DEBUG(dbgs() << " Edge weight: " << MBPI->getEdgeWeight(PrevBB, FBB) |
| 996 | << " vs " << MBPI->getEdgeWeight(PrevBB, TBB) << "\n"); |
| 997 | DebugLoc dl; // FIXME: this is nowhere |
| 998 | TII->RemoveBranch(*PrevBB); |
| 999 | TII->InsertBranch(*PrevBB, FBB, TBB, Cond, dl); |
| 1000 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 1001 | PrevBB->updateTerminator(); |
Manman Ren | 1123614 | 2012-07-31 01:11:07 +0000 | [diff] [blame] | 1002 | } |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1003 | } |
Chandler Carruth | df23435 | 2011-11-13 11:20:44 +0000 | [diff] [blame] | 1004 | |
| 1005 | // Fixup the last block. |
| 1006 | Cond.clear(); |
| 1007 | MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. |
| 1008 | if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond)) |
| 1009 | F.back().updateTerminator(); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1010 | |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 1011 | // Walk through the backedges of the function now that we have fully laid out |
| 1012 | // the basic blocks and align the destination of each backedge. We don't rely |
Chandler Carruth | e6450dc | 2012-08-07 09:45:24 +0000 | [diff] [blame] | 1013 | // exclusively on the loop info here so that we can align backedges in |
| 1014 | // unnatural CFGs and backedges that were introduced purely because of the |
| 1015 | // loop rotations done during this layout pass. |
Bill Wendling | 6765834 | 2012-10-09 07:45:08 +0000 | [diff] [blame] | 1016 | if (F.getFunction()->getFnAttributes(). |
Bill Wendling | 034b94b | 2012-12-19 07:18:57 +0000 | [diff] [blame^] | 1017 | hasAttribute(Attribute::OptimizeForSize)) |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1018 | return; |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1019 | unsigned Align = TLI->getPrefLoopAlignment(); |
| 1020 | if (!Align) |
| 1021 | return; // Don't care about loop alignment. |
Chandler Carruth | e6450dc | 2012-08-07 09:45:24 +0000 | [diff] [blame] | 1022 | if (FunctionChain.begin() == FunctionChain.end()) |
| 1023 | return; // Empty chain. |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1024 | |
Chandler Carruth | e6450dc | 2012-08-07 09:45:24 +0000 | [diff] [blame] | 1025 | const BranchProbability ColdProb(1, 5); // 20% |
| 1026 | BlockFrequency EntryFreq = MBFI->getBlockFreq(F.begin()); |
| 1027 | BlockFrequency WeightedEntryFreq = EntryFreq * ColdProb; |
| 1028 | for (BlockChain::iterator BI = llvm::next(FunctionChain.begin()), |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 1029 | BE = FunctionChain.end(); |
| 1030 | BI != BE; ++BI) { |
Chandler Carruth | e6450dc | 2012-08-07 09:45:24 +0000 | [diff] [blame] | 1031 | // Don't align non-looping basic blocks. These are unlikely to execute |
| 1032 | // enough times to matter in practice. Note that we'll still handle |
| 1033 | // unnatural CFGs inside of a natural outer loop (the common case) and |
| 1034 | // rotated loops. |
| 1035 | MachineLoop *L = MLI->getLoopFor(*BI); |
| 1036 | if (!L) |
| 1037 | continue; |
| 1038 | |
| 1039 | // If the block is cold relative to the function entry don't waste space |
| 1040 | // aligning it. |
| 1041 | BlockFrequency Freq = MBFI->getBlockFreq(*BI); |
| 1042 | if (Freq < WeightedEntryFreq) |
| 1043 | continue; |
| 1044 | |
| 1045 | // If the block is cold relative to its loop header, don't align it |
| 1046 | // regardless of what edges into the block exist. |
| 1047 | MachineBasicBlock *LoopHeader = L->getHeader(); |
| 1048 | BlockFrequency LoopHeaderFreq = MBFI->getBlockFreq(LoopHeader); |
| 1049 | if (Freq < (LoopHeaderFreq * ColdProb)) |
| 1050 | continue; |
| 1051 | |
| 1052 | // Check for the existence of a non-layout predecessor which would benefit |
| 1053 | // from aligning this block. |
| 1054 | MachineBasicBlock *LayoutPred = *llvm::prior(BI); |
| 1055 | |
| 1056 | // Force alignment if all the predecessors are jumps. We already checked |
| 1057 | // that the block isn't cold above. |
| 1058 | if (!LayoutPred->isSuccessor(*BI)) { |
| 1059 | (*BI)->setAlignment(Align); |
| 1060 | continue; |
| 1061 | } |
| 1062 | |
| 1063 | // Align this block if the layout predecessor's edge into this block is |
| 1064 | // cold relative to the block. When this is true, othe predecessors make up |
| 1065 | // all of the hot entries into the block and thus alignment is likely to be |
| 1066 | // important. |
| 1067 | BranchProbability LayoutProb = MBPI->getEdgeProbability(LayoutPred, *BI); |
| 1068 | BlockFrequency LayoutEdgeFreq = MBFI->getBlockFreq(LayoutPred) * LayoutProb; |
| 1069 | if (LayoutEdgeFreq <= (Freq * ColdProb)) |
| 1070 | (*BI)->setAlignment(Align); |
Chandler Carruth | 70daea9 | 2012-04-16 01:12:56 +0000 | [diff] [blame] | 1071 | } |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1072 | } |
| 1073 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1074 | bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { |
| 1075 | // Check for single-block functions and skip them. |
| 1076 | if (llvm::next(F.begin()) == F.end()) |
| 1077 | return false; |
| 1078 | |
| 1079 | MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); |
| 1080 | MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1081 | MLI = &getAnalysis<MachineLoopInfo>(); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1082 | TII = F.getTarget().getInstrInfo(); |
Chandler Carruth | 4a85cc9 | 2011-10-21 08:57:37 +0000 | [diff] [blame] | 1083 | TLI = F.getTarget().getTargetLowering(); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1084 | assert(BlockToChain.empty()); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1085 | |
Chandler Carruth | 3071363 | 2011-10-23 09:18:45 +0000 | [diff] [blame] | 1086 | buildCFGChains(F); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1087 | |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1088 | BlockToChain.clear(); |
Chandler Carruth | f5e47ac | 2011-11-14 10:57:23 +0000 | [diff] [blame] | 1089 | ChainAllocator.DestroyAll(); |
Chandler Carruth | db35087 | 2011-10-21 06:46:38 +0000 | [diff] [blame] | 1090 | |
| 1091 | // We always return true as we have no way to track whether the final order |
| 1092 | // differs from the original order. |
| 1093 | return true; |
| 1094 | } |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 1095 | |
| 1096 | namespace { |
| 1097 | /// \brief A pass to compute block placement statistics. |
| 1098 | /// |
| 1099 | /// A separate pass to compute interesting statistics for evaluating block |
| 1100 | /// placement. This is separate from the actual placement pass so that they can |
Benjamin Kramer | d9b0b02 | 2012-06-02 10:20:22 +0000 | [diff] [blame] | 1101 | /// be computed in the absence of any placement transformations or when using |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 1102 | /// alternative placement strategies. |
| 1103 | class MachineBlockPlacementStats : public MachineFunctionPass { |
| 1104 | /// \brief A handle to the branch probability pass. |
| 1105 | const MachineBranchProbabilityInfo *MBPI; |
| 1106 | |
| 1107 | /// \brief A handle to the function-wide block frequency pass. |
| 1108 | const MachineBlockFrequencyInfo *MBFI; |
| 1109 | |
| 1110 | public: |
| 1111 | static char ID; // Pass identification, replacement for typeid |
| 1112 | MachineBlockPlacementStats() : MachineFunctionPass(ID) { |
| 1113 | initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); |
| 1114 | } |
| 1115 | |
| 1116 | bool runOnMachineFunction(MachineFunction &F); |
| 1117 | |
| 1118 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 1119 | AU.addRequired<MachineBranchProbabilityInfo>(); |
| 1120 | AU.addRequired<MachineBlockFrequencyInfo>(); |
| 1121 | AU.setPreservesAll(); |
| 1122 | MachineFunctionPass::getAnalysisUsage(AU); |
| 1123 | } |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 1124 | }; |
| 1125 | } |
| 1126 | |
| 1127 | char MachineBlockPlacementStats::ID = 0; |
Andrew Trick | 1dd8c85 | 2012-02-08 21:23:13 +0000 | [diff] [blame] | 1128 | char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID; |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 1129 | INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", |
| 1130 | "Basic Block Placement Stats", false, false) |
| 1131 | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) |
| 1132 | INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) |
| 1133 | INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", |
| 1134 | "Basic Block Placement Stats", false, false) |
| 1135 | |
Chandler Carruth | 37efc9f | 2011-11-02 07:17:12 +0000 | [diff] [blame] | 1136 | bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { |
| 1137 | // Check for single-block functions and skip them. |
| 1138 | if (llvm::next(F.begin()) == F.end()) |
| 1139 | return false; |
| 1140 | |
| 1141 | MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); |
| 1142 | MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); |
| 1143 | |
| 1144 | for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { |
| 1145 | BlockFrequency BlockFreq = MBFI->getBlockFreq(I); |
| 1146 | Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches |
| 1147 | : NumUncondBranches; |
| 1148 | Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq |
| 1149 | : UncondBranchTakenFreq; |
| 1150 | for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), |
| 1151 | SE = I->succ_end(); |
| 1152 | SI != SE; ++SI) { |
| 1153 | // Skip if this successor is a fallthrough. |
| 1154 | if (I->isLayoutSuccessor(*SI)) |
| 1155 | continue; |
| 1156 | |
| 1157 | BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); |
| 1158 | ++NumBranches; |
| 1159 | BranchTakenFreq += EdgeFreq.getFrequency(); |
| 1160 | } |
| 1161 | } |
| 1162 | |
| 1163 | return false; |
| 1164 | } |
| 1165 | |