#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"
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.
}
/// \brief Iterator over blocks within the chain.
- typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
- typedef SmallVectorImpl<MachineBasicBlock *>::reverse_iterator
- reverse_iterator;
+ typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator 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.
///
void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
SmallVectorImpl<MachineBasicBlock *> &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);
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");
}
-/// \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<MachineOperand, 4> 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;
+ // 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<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
+
+ 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 (MachineLoop *ExitLoop = MLI->getLoopFor(*SI))
+ if (ExitLoop->contains(&L))
+ BlocksExitingToOuterLoop.insert(*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();
+
+ // 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");
+ return LoopingBB;
}
/// \brief Forms basic block chains from the natural loop structures.
SmallVector<MachineBasicBlock *, 16> 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<BlockChain *, 4> UpdatedPreds;
+ assert(LoopChain.LoopPredecessors == 0);
+ UpdatedPreds.insert(&LoopChain);
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);
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.
projects / oota-llvm.git / blobdiff