From 2e38cf961d6d80c88290ca6b8d867e021f80b763 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 27 Nov 2011 00:38:03 +0000 Subject: Introduce a loop block rotation optimization to the new block placement pass. This is designed to achieve one of the important optimizations that the old code placement pass did, but more simply. This is a somewhat rough and *very* conservative version of the transform. We could get a lot fancier here if there are profitable cases to do so. In particular, this only looks for a single pattern, it insists that the loop backedge being rotated away is the last backedge in the chain, and it doesn't provide any means of doing better in-loop placement due to the rotation. However, it appears that it will handle the important loops I am finding in the LLVM test suite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145158 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 95 +++++++++++++++++++++++++++++++++-- 1 file changed, 92 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 55d804b..f5be01b 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -121,13 +121,17 @@ public: } /// \brief Iterator over blocks within the chain. - typedef SmallVectorImpl::const_iterator iterator; + typedef SmallVectorImpl::iterator iterator; + typedef SmallVectorImpl::reverse_iterator + reverse_iterator; /// \brief Beginning of blocks within the chain. - iterator begin() const { return Blocks.begin(); } + iterator begin() { return Blocks.begin(); } + reverse_iterator rbegin() { return Blocks.rbegin(); } /// \brief End of blocks within the chain. - iterator end() const { return Blocks.end(); } + iterator end() { return Blocks.end(); } + reverse_iterator rend() { return Blocks.rend(); } /// \brief Merge a block chain into this one. /// @@ -222,6 +226,8 @@ class MachineBlockPlacement : public MachineFunctionPass { void buildChain(MachineBasicBlock *BB, BlockChain &Chain, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter = 0); + void rotateLoop(MachineLoop &L, BlockChain &LoopChain, + const BlockFilterSet &LoopBlockSet); void buildLoopChains(MachineFunction &F, MachineLoop &L); void buildCFGChains(MachineFunction &F); void AlignLoops(MachineFunction &F); @@ -552,6 +558,88 @@ void MachineBlockPlacement::buildChain( << getBlockNum(*Chain.begin()) << "\n"); } +/// \brief Attempt to rotate loop chains ending in an unconditional backedge. +/// +/// This is a very conservative attempt to rotate unconditional backedge jumps +/// into fallthrough opportunities. It only attempts to perform the rotation +/// when it is trivial to find a block within the loop which has a conditional +/// loop exit. This block is then made the bottom of the chain, and the in-loop +/// fallthrough block the top. That turns a conditional branch out of the loop +/// into a conditional branch to the top of the loop while completely +/// eliminitating an unconditional branch within the loop. +void MachineBlockPlacement::rotateLoop(MachineLoop &L, + BlockChain &LoopChain, + const BlockFilterSet &LoopBlockSet) { + MachineBasicBlock *Header = *L.block_begin(); + // Ensure that we have a chain of blocks which starts with the loop header. + // Otherwise, rotating the blocks might break an analyzable branch. + if (Header != *LoopChain.begin()) + return; + + // We only support rotating the loop chain as a unit, so look directly at the + // back of the chain and check that it has a backedge. + MachineBasicBlock *Latch = *llvm::prior(LoopChain.end()); + if (Latch == Header || + !Latch->isSuccessor(Header)) + return; + + // We need to analyze the branch and determine if rotating the loop will + // completely remove a branch. We bail if the analysis fails or we don't find + // an unconditional backedge. + SmallVector Cond; + MachineBasicBlock *TBB = 0, *FBB = 0; + if (TII->AnalyzeBranch(*Latch, TBB, FBB, Cond) || !TBB || FBB || !Cond.empty()) + return; + assert(TBB == Header && "Found backedge that doesn't go to the header!"); + + // Next we need to find a split point. This rotate algorithm is *very* + // narrow, and it only tries to do the rotate when it can find a split point + // which is an analyzable branch that exits the loop. Splitting there allows + // us to form a fallthrough out of the loop and a conditional jump to the top + // of the loop after rotation. + MachineBasicBlock *NewBottom = 0, *NewTop = 0; + BlockChain::iterator SplitIt = LoopChain.end(); + for (BlockChain::reverse_iterator I = llvm::next(LoopChain.rbegin()), + E = LoopChain.rend(); + I != E; ++I) { + Cond.clear(); + TBB = FBB = 0; + if (TII->AnalyzeBranch(**I, TBB, FBB, Cond) || !TBB || Cond.empty()) + continue; + // Swap things so that the in-loop successor is always in FBB or is an + // implicit fallthrough. + if (FBB && !LoopBlockSet.count(FBB)) + std::swap(TBB, FBB); + // Check that we actually have a loop exit branch. + // FIXME: We should probably just use the LoopInfo for this. + if (!LoopBlockSet.count(TBB) && (!FBB || !LoopBlockSet.count(FBB))) { + // This is a very arbitrary restriction, but it ensures we don't disrupt + // the existing chain layout. We insist that the in-loop successor is + // chained as a fallthrough successor (even if the branch hasn't been + // updated to reflect that yet). + if (FBB && FBB != *llvm::prior(I)) + continue; + + NewBottom = *I; + NewTop = *llvm::prior(I); + SplitIt = I.base(); + break; + } + } + if (!NewBottom || !NewTop || + SplitIt == LoopChain.end() || SplitIt == LoopChain.begin()) + return; + assert(BlockToChain[NewBottom] == &LoopChain); + assert(BlockToChain[NewTop] == &LoopChain); + assert(*SplitIt == NewTop); + + // Rotate the chain and we're done. + DEBUG(dbgs() << "Rotating loop headed by: " << getBlockName(Header) << "\n" + << " new top: " << getBlockName(NewTop) << "\n" + << " new bottom: " << getBlockName(NewBottom) << "\n"); + std::rotate(LoopChain.begin(), SplitIt, LoopChain.end()); +} + /// \brief Forms basic block chains from the natural loop structures. /// /// These chains are designed to preserve the existing *structure* of the code @@ -598,6 +686,7 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, } buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); + rotateLoop(L, LoopChain, LoopBlockSet); DEBUG({ // Crash at the end so we get all of the debugging output first. -- cgit v1.1 From 2eb5a744b18d429928751b06e205cbb88f668ae7 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 27 Nov 2011 09:22:53 +0000 Subject: Rework a bit of the implementation of loop block rotation to not rely so heavily on AnalyzeBranch. That routine doesn't behave as we want given that rotation occurs mid-way through re-ordering the function. Instead merely check that there are not unanalyzable branching constructs present, and then reason about the CFG via successor lists. This actually simplifies my mental model for all of this as well. The concrete result is that we now will rotate more loop chains. I've added a test case from Olden highlighting the effect. There is still a bit more to do here though in order to regain all of the performance in Olden. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145179 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 52 +++++++++++++++++++++-------------- 1 file changed, 31 insertions(+), 21 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index f5be01b..5de120e 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -585,12 +585,14 @@ void MachineBlockPlacement::rotateLoop(MachineLoop &L, // We need to analyze the branch and determine if rotating the loop will // completely remove a branch. We bail if the analysis fails or we don't find - // an unconditional backedge. + // an unconditional backedge. Note that this has to handle cases where the + // original order was rotated, and the chain has un-done it. As a result, + // there may not (yet) be the uncondiationl branch, but we can tell whether + // one will be added when updating the terminators. SmallVector Cond; MachineBasicBlock *TBB = 0, *FBB = 0; - if (TII->AnalyzeBranch(*Latch, TBB, FBB, Cond) || !TBB || FBB || !Cond.empty()) + if (TII->AnalyzeBranch(*Latch, TBB, FBB, Cond) || !Cond.empty()) return; - assert(TBB == Header && "Found backedge that doesn't go to the header!"); // Next we need to find a split point. This rotate algorithm is *very* // narrow, and it only tries to do the rotate when it can find a split point @@ -604,27 +606,35 @@ void MachineBlockPlacement::rotateLoop(MachineLoop &L, I != E; ++I) { Cond.clear(); TBB = FBB = 0; - if (TII->AnalyzeBranch(**I, TBB, FBB, Cond) || !TBB || Cond.empty()) + // Ensure that this is a block with a conditional branch which we can + // analyze and re-form after rotating the loop. While it might be tempting + // to use the TBB or FBB output parameters from this, they will often be + // lies as they are only correct after the terminators have been updated, + // and we are mid-chain formation. + if (TII->AnalyzeBranch(**I, TBB, FBB, Cond) || Cond.empty()) continue; - // Swap things so that the in-loop successor is always in FBB or is an - // implicit fallthrough. - if (FBB && !LoopBlockSet.count(FBB)) - std::swap(TBB, FBB); - // Check that we actually have a loop exit branch. - // FIXME: We should probably just use the LoopInfo for this. - if (!LoopBlockSet.count(TBB) && (!FBB || !LoopBlockSet.count(FBB))) { - // This is a very arbitrary restriction, but it ensures we don't disrupt - // the existing chain layout. We insist that the in-loop successor is - // chained as a fallthrough successor (even if the branch hasn't been - // updated to reflect that yet). - if (FBB && FBB != *llvm::prior(I)) - continue; - NewBottom = *I; - NewTop = *llvm::prior(I); - SplitIt = I.base(); - break; + // See if this block is an exiting block from the loop. LoopInfo provides + // a nice API for this, but it's actuall N*M runtime where N is the number + // of blocks in the loop and M is the number of successors. We can + // eliminate the N by doing this ourselves. + // FIXME: The LoopInfo datastructure should be improved for these types of + // queries. + MachineBasicBlock *ExitB = 0; + for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), SE = (*I)->succ_end(); + SI != SE; ++SI) { + if (!(*SI)->isLandingPad() && *SI != *I && !LoopBlockSet.count(*SI)) { + ExitB = *SI; + break; + } } + if (!ExitB) + continue; + + NewBottom = *I; + NewTop = *llvm::prior(I); + SplitIt = I.base(); + break; } if (!NewBottom || !NewTop || SplitIt == LoopChain.end() || SplitIt == LoopChain.begin()) -- cgit v1.1 From 7096692fd9ab5753f17500a27d400d1544b6d3d8 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 27 Nov 2011 10:32:16 +0000 Subject: Fix an impressive type-o / spell-o Duncan noticed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145181 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 5de120e..83c8231 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -587,7 +587,7 @@ void MachineBlockPlacement::rotateLoop(MachineLoop &L, // completely remove a branch. We bail if the analysis fails or we don't find // an unconditional backedge. Note that this has to handle cases where the // original order was rotated, and the chain has un-done it. As a result, - // there may not (yet) be the uncondiationl branch, but we can tell whether + // there may not (yet) be the unconditional branch, but we can tell whether // one will be added when updating the terminators. SmallVector Cond; MachineBasicBlock *TBB = 0, *FBB = 0; -- cgit v1.1 From fac1305da162259d17baa6700ecb5d148b86ef08 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 27 Nov 2011 13:34:33 +0000 Subject: Take two on rotating the block ordering of loops. My previous attempt was centered around the premise of laying out a loop in a chain, and then rotating that chain. This is good for preserving contiguous layout, but bad for actually making sane rotations. In order to keep it safe, I had to essentially make it impossible to rotate deeply nested loops. The information needed to correctly reason about a deeply nested loop is actually available -- *before* we layout the loop. We know the inner loops are already fused into chains, etc. We lose information the moment we actually lay out the loop. The solution was the other alternative for this algorithm I discussed with Benjamin and some others: rather than rotating the loop after-the-fact, try to pick a profitable starting block for the loop's layout, and then use our existing layout logic. I was worried about the complexity of this "pick" step, but it turns out such complexity is needed to handle all the important cases I keep teasing out of benchmarks. This is, I'm afraid, a bit of a work-in-progress. It is still misbehaving on some likely important cases I'm investigating in Olden. It also isn't really tested. I'm going to try to craft some interesting nested-loop test cases, but it's likely to be extremely time consuming and I don't want to go there until I'm sure I'm testing the correct behavior. Sadly I can't come up with a way of getting simple, fine grained test cases for this logic. We need complex loop structures to even trigger much of it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145183 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 188 +++++++++++++++++++--------------- 1 file changed, 103 insertions(+), 85 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 83c8231..56ad856 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -226,8 +226,9 @@ class MachineBlockPlacement : public MachineFunctionPass { void buildChain(MachineBasicBlock *BB, BlockChain &Chain, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter = 0); - void rotateLoop(MachineLoop &L, BlockChain &LoopChain, - const BlockFilterSet &LoopBlockSet); + MachineBasicBlock *findBestLoopTop(MachineFunction &F, + MachineLoop &L, + const BlockFilterSet &LoopBlockSet); void buildLoopChains(MachineFunction &F, MachineLoop &L); void buildCFGChains(MachineFunction &F); void AlignLoops(MachineFunction &F); @@ -558,96 +559,110 @@ void MachineBlockPlacement::buildChain( << getBlockNum(*Chain.begin()) << "\n"); } -/// \brief Attempt to rotate loop chains ending in an unconditional backedge. +/// \brief Find the best loop top block for layout. /// -/// This is a very conservative attempt to rotate unconditional backedge jumps -/// into fallthrough opportunities. It only attempts to perform the rotation -/// when it is trivial to find a block within the loop which has a conditional -/// loop exit. This block is then made the bottom of the chain, and the in-loop -/// fallthrough block the top. That turns a conditional branch out of the loop -/// into a conditional branch to the top of the loop while completely -/// eliminitating an unconditional branch within the loop. -void MachineBlockPlacement::rotateLoop(MachineLoop &L, - BlockChain &LoopChain, +/// This routine implements the logic to analyze the loop looking for the best +/// block to layout at the top of the loop. Typically this is done to maximize +/// fallthrough opportunities. +MachineBasicBlock * +MachineBlockPlacement::findBestLoopTop(MachineFunction &F, + MachineLoop &L, const BlockFilterSet &LoopBlockSet) { - MachineBasicBlock *Header = *L.block_begin(); - // Ensure that we have a chain of blocks which starts with the loop header. - // Otherwise, rotating the blocks might break an analyzable branch. - if (Header != *LoopChain.begin()) - return; - - // We only support rotating the loop chain as a unit, so look directly at the - // back of the chain and check that it has a backedge. - MachineBasicBlock *Latch = *llvm::prior(LoopChain.end()); - if (Latch == Header || - !Latch->isSuccessor(Header)) - return; - - // We need to analyze the branch and determine if rotating the loop will - // completely remove a branch. We bail if the analysis fails or we don't find - // an unconditional backedge. Note that this has to handle cases where the - // original order was rotated, and the chain has un-done it. As a result, - // there may not (yet) be the unconditional branch, but we can tell whether - // one will be added when updating the terminators. - SmallVector Cond; - MachineBasicBlock *TBB = 0, *FBB = 0; - if (TII->AnalyzeBranch(*Latch, TBB, FBB, Cond) || !Cond.empty()) - return; - - // Next we need to find a split point. This rotate algorithm is *very* - // narrow, and it only tries to do the rotate when it can find a split point - // which is an analyzable branch that exits the loop. Splitting there allows - // us to form a fallthrough out of the loop and a conditional jump to the top - // of the loop after rotation. - MachineBasicBlock *NewBottom = 0, *NewTop = 0; - BlockChain::iterator SplitIt = LoopChain.end(); - for (BlockChain::reverse_iterator I = llvm::next(LoopChain.rbegin()), - E = LoopChain.rend(); + BlockFrequency BestExitEdgeFreq; + MachineBasicBlock *ExitingBB = 0; + MachineBasicBlock *LoopingBB = 0; + DEBUG(dbgs() << "Finding best loop exit for: " + << getBlockName(L.getHeader()) << "\n"); + for (MachineLoop::block_iterator I = L.block_begin(), + E = L.block_end(); I != E; ++I) { - Cond.clear(); - TBB = FBB = 0; - // Ensure that this is a block with a conditional branch which we can - // analyze and re-form after rotating the loop. While it might be tempting - // to use the TBB or FBB output parameters from this, they will often be - // lies as they are only correct after the terminators have been updated, - // and we are mid-chain formation. - if (TII->AnalyzeBranch(**I, TBB, FBB, Cond) || Cond.empty()) + BlockChain &Chain = *BlockToChain[*I]; + // Ensure that this block is at the end of a chain; otherwise it could be + // mid-way through an inner loop or a successor of an analyzable branch. + if (*I != *llvm::prior(Chain.end())) continue; - // See if this block is an exiting block from the loop. LoopInfo provides - // a nice API for this, but it's actuall N*M runtime where N is the number - // of blocks in the loop and M is the number of successors. We can - // eliminate the N by doing this ourselves. - // FIXME: The LoopInfo datastructure should be improved for these types of - // queries. - MachineBasicBlock *ExitB = 0; - for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), SE = (*I)->succ_end(); + // Now walk the successors. We need to establish whether this has a viable + // exiting successor and whether it has a viable non-exiting successor. + // We store the old exiting state and restore it if a viable looping + // successor isn't found. + MachineBasicBlock *OldExitingBB = ExitingBB; + BlockFrequency OldBestExitEdgeFreq = BestExitEdgeFreq; + // We also compute and store the best looping successor for use in layout. + MachineBasicBlock *BestLoopSucc = 0; + // FIXME: Due to the performance of the probability and weight routines in + // the MBPI analysis, we use the internal weights. This is only valid + // because it is purely a ranking function, we don't care about anything + // but the relative values. + uint32_t BestLoopSuccWeight = 0; + // FIXME: We also manually compute the probabilities to avoid quadratic + // behavior. + uint32_t WeightScale = 0; + uint32_t SumWeight = MBPI->getSumForBlock(*I, WeightScale); + for (MachineBasicBlock::succ_iterator SI = (*I)->succ_begin(), + SE = (*I)->succ_end(); SI != SE; ++SI) { - if (!(*SI)->isLandingPad() && *SI != *I && !LoopBlockSet.count(*SI)) { - ExitB = *SI; - break; + if ((*SI)->isLandingPad()) + continue; + if (*SI == *I) + continue; + BlockChain &SuccChain = *BlockToChain[*SI]; + // Don't split chains, either this chain or the successor's chain. + if (&Chain == &SuccChain || *SI != *SuccChain.begin()) { + DEBUG(dbgs() << " " << (LoopBlockSet.count(*SI) ? "looping: " + : "exiting: ") + << getBlockName(*I) << " -> " + << getBlockName(*SI) << " (chain conflict)\n"); + continue; + } + + uint32_t SuccWeight = MBPI->getEdgeWeight(*I, *SI); + if (LoopBlockSet.count(*SI)) { + DEBUG(dbgs() << " looping: " << getBlockName(*I) << " -> " + << getBlockName(*SI) << " (" << SuccWeight << ")\n"); + if (BestLoopSucc && BestLoopSuccWeight >= SuccWeight) + continue; + + BestLoopSucc = *SI; + BestLoopSuccWeight = SuccWeight; + continue; + } + + BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight); + BlockFrequency ExitEdgeFreq = MBFI->getBlockFreq(*I) * SuccProb; + DEBUG(dbgs() << " exiting: " << getBlockName(*I) << " -> " + << getBlockName(*SI) << " (" << ExitEdgeFreq << ")\n"); + // Note that we slightly bias this toward an existing layout successor to + // retain incoming order in the absence of better information. + // FIXME: Should we bias this more strongly? It's pretty weak. + if (!ExitingBB || ExitEdgeFreq > BestExitEdgeFreq || + ((*I)->isLayoutSuccessor(*SI) && + !(ExitEdgeFreq < BestExitEdgeFreq))) { + BestExitEdgeFreq = ExitEdgeFreq; + ExitingBB = *I; } } - if (!ExitB) + + // Restore the old exiting state, no viable looping successor was found. + if (!BestLoopSucc) { + ExitingBB = OldExitingBB; + BestExitEdgeFreq = OldBestExitEdgeFreq; continue; + } - NewBottom = *I; - NewTop = *llvm::prior(I); - SplitIt = I.base(); - break; + // If this was best exiting block thus far, also record the looping block. + if (ExitingBB == *I) + LoopingBB = BestLoopSucc; } - if (!NewBottom || !NewTop || - SplitIt == LoopChain.end() || SplitIt == LoopChain.begin()) - return; - assert(BlockToChain[NewBottom] == &LoopChain); - assert(BlockToChain[NewTop] == &LoopChain); - assert(*SplitIt == NewTop); - - // Rotate the chain and we're done. - DEBUG(dbgs() << "Rotating loop headed by: " << getBlockName(Header) << "\n" - << " new top: " << getBlockName(NewTop) << "\n" - << " new bottom: " << getBlockName(NewBottom) << "\n"); - std::rotate(LoopChain.begin(), SplitIt, LoopChain.end()); + // Without a candidate exitting block or with only a single block in the + // loop, just use the loop header to layout the loop. + if (!ExitingBB || L.getNumBlocks() == 1) + return L.getHeader(); + + assert(LoopingBB && "All successors of a loop block are exit blocks!"); + DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); + DEBUG(dbgs() << " Best top block: " << getBlockName(LoopingBB) << "\n"); + return LoopingBB; } /// \brief Forms basic block chains from the natural loop structures. @@ -665,17 +680,21 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, SmallVector BlockWorkList; BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); - BlockChain &LoopChain = *BlockToChain[L.getHeader()]; + + MachineBasicBlock *LayoutTop = findBestLoopTop(F, L, LoopBlockSet); + BlockChain &LoopChain = *BlockToChain[LayoutTop]; // FIXME: This is a really lame way of walking the chains in the loop: we // walk the blocks, and use a set to prevent visiting a particular chain // twice. SmallPtrSet UpdatedPreds; + assert(BlockToChain[LayoutTop]->LoopPredecessors == 0); + UpdatedPreds.insert(BlockToChain[LayoutTop]); for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end(); BI != BE; ++BI) { BlockChain &Chain = *BlockToChain[*BI]; - if (!UpdatedPreds.insert(&Chain) || BI == L.block_begin()) + if (!UpdatedPreds.insert(&Chain)) continue; assert(Chain.LoopPredecessors == 0); @@ -695,8 +714,7 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, BlockWorkList.push_back(*Chain.begin()); } - buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); - rotateLoop(L, LoopChain, LoopBlockSet); + buildChain(LayoutTop, LoopChain, BlockWorkList, &LoopBlockSet); DEBUG({ // Crash at the end so we get all of the debugging output first. -- cgit v1.1 From 51901d85f718a7e293f52a7908eab9fe1c0c94a0 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 27 Nov 2011 20:18:00 +0000 Subject: Prevent rotating the blocks of a loop (and thus getting a backedge to be fallthrough) in cases where we might fail to rotate an exit to an outer loop onto the end of the loop chain. Having *some* rotation, but not performing this rotation, is the primary fix of thep performance regression with -enable-block-placement for Olden/em3d (a whopping 30% regression). Still working on reducing the test case that actually exercises this and the new rotation strategy out of this code, but I want to check if this regresses other test cases first as that may indicate it isn't the correct fix. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145195 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 56ad856..584290b 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -571,6 +571,11 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F, BlockFrequency BestExitEdgeFreq; MachineBasicBlock *ExitingBB = 0; MachineBasicBlock *LoopingBB = 0; + // If there are exits to outer loops, loop rotation can severely limit + // fallthrough opportunites unless it selects such an exit. Keep a set of + // blocks where rotating to exit with that block will reach an outer loop. + SmallPtrSet BlocksExitingToOuterLoop; + DEBUG(dbgs() << "Finding best loop exit for: " << getBlockName(L.getHeader()) << "\n"); for (MachineLoop::block_iterator I = L.block_begin(), @@ -641,6 +646,10 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F, BestExitEdgeFreq = ExitEdgeFreq; ExitingBB = *I; } + + if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI)) + if (ExitLoop->contains(&L)) + BlocksExitingToOuterLoop.insert(*I); } // Restore the old exiting state, no viable looping successor was found. @@ -659,6 +668,13 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F, if (!ExitingBB || L.getNumBlocks() == 1) return L.getHeader(); + // Also, if we have exit blocks which lead to outer loops but didn't select + // one of them as the exiting block we are rotating toward, disable loop + // rotation altogether. + if (!BlocksExitingToOuterLoop.empty() && + !BlocksExitingToOuterLoop.count(ExitingBB)) + return L.getHeader(); + assert(LoopingBB && "All successors of a loop block are exit blocks!"); DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n"); DEBUG(dbgs() << " Best top block: " << getBlockName(LoopingBB) << "\n"); -- cgit v1.1 From e6d81ad6a572f2492885f36fc5571225e963d39d Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Tue, 6 Dec 2011 23:59:33 +0000 Subject: - Remove unneeded #includes. - Remove unused types/fields. - Add some constantness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145993 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 29 ++++------------------------- 1 file changed, 4 insertions(+), 25 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 584290b..b07ce68 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -36,10 +36,7 @@ #include "llvm/CodeGen/Passes.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -56,22 +53,6 @@ STATISTIC(UncondBranchTakenFreq, "Potential frequency of taking unconditional branches"); namespace { -/// \brief A structure for storing a weighted edge. -/// -/// This stores an edge and its weight, computed as the product of the -/// frequency that the starting block is entered with the probability of -/// a particular exit block. -struct WeightedEdge { - BlockFrequency EdgeFrequency; - MachineBasicBlock *From, *To; - - bool operator<(const WeightedEdge &RHS) const { - return EdgeFrequency < RHS.EdgeFrequency; - } -}; -} - -namespace { class BlockChain; /// \brief Type for our function-wide basic block -> block chain mapping. typedef DenseMap BlockToChainMapType; @@ -121,17 +102,15 @@ public: } /// \brief Iterator over blocks within the chain. - typedef SmallVectorImpl::iterator iterator; - typedef SmallVectorImpl::reverse_iterator + typedef SmallVectorImpl::const_iterator iterator; + typedef SmallVectorImpl::const_reverse_iterator reverse_iterator; /// \brief Beginning of blocks within the chain. - iterator begin() { return Blocks.begin(); } - reverse_iterator rbegin() { return Blocks.rbegin(); } + iterator begin() const { return Blocks.begin(); } /// \brief End of blocks within the chain. - iterator end() { return Blocks.end(); } - reverse_iterator rend() { return Blocks.rend(); } + iterator end() const { return Blocks.end(); } /// \brief Merge a block chain into this one. /// -- cgit v1.1 From c9040b3b1308bf84a26522040ba9b4d2fff59634 Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Wed, 7 Dec 2011 00:08:00 +0000 Subject: Remove unneeded type. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145995 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 2 -- 1 file changed, 2 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index b07ce68..2287cc8 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -103,8 +103,6 @@ public: /// \brief Iterator over blocks within the chain. typedef SmallVectorImpl::const_iterator iterator; - typedef SmallVectorImpl::const_reverse_iterator - reverse_iterator; /// \brief Beginning of blocks within the chain. iterator begin() const { return Blocks.begin(); } -- cgit v1.1 From feb468ab24a9e85b4d27faa6badfb57a2414610c Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Wed, 7 Dec 2011 19:46:10 +0000 Subject: Remove unneeded semicolon. Skip two looking up at BlockChain. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146053 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 2287cc8..638d895 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -530,7 +530,7 @@ void MachineBlockPlacement::buildChain( markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter); Chain.merge(BestSucc, &SuccChain); BB = *llvm::prior(Chain.end()); - }; + } DEBUG(dbgs() << "Finished forming chain for header block " << getBlockNum(*Chain.begin()) << "\n"); @@ -681,8 +681,8 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, // walk the blocks, and use a set to prevent visiting a particular chain // twice. SmallPtrSet UpdatedPreds; - assert(BlockToChain[LayoutTop]->LoopPredecessors == 0); - UpdatedPreds.insert(BlockToChain[LayoutTop]); + assert(LoopChain.LoopPredecessors == 0); + UpdatedPreds.insert(&LoopChain); for (MachineLoop::block_iterator BI = L.block_begin(), BE = L.block_end(); BI != BE; ++BI) { -- cgit v1.1