From b5856c83ff4fd796c3eabccca2ed3b06173aeb51 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Mon, 14 Nov 2011 00:00:35 +0000 Subject: Teach machine block placement to cope with unnatural loops. These don't get loop info structures associated with them, and so we need some way to make forward progress selecting and placing basic blocks. The technique used here is pretty brutal -- it just scans the list of blocks looking for the first unplaced candidate. It keeps placing blocks like this until the CFG becomes tractable. The cost is somewhat unfortunate, it requires allocating a vector of all basic block pointers eagerly. I have some ideas about how to simplify and optimize this, but I'm trying to get the logic correct first. Thanks to Benjamin Kramer for the reduced test case out of GCC. Sadly there are other bugs that GCC is tickling that I'm reducing and working on now. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144516 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineBlockPlacement.cpp | 81 ++++++++++++++++++++++++++--------- 1 file changed, 60 insertions(+), 21 deletions(-) (limited to 'lib/CodeGen/MachineBlockPlacement.cpp') diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index de813a378e..ca17ad07e4 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -206,7 +206,7 @@ class MachineBlockPlacement : public MachineFunctionPass { void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB, - SmallVectorImpl &Blocks, + SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter = 0); MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB, BlockChain &Chain, @@ -214,8 +214,12 @@ class MachineBlockPlacement : public MachineFunctionPass { MachineBasicBlock *selectBestCandidateBlock( BlockChain &Chain, SmallVectorImpl &WorkList, const BlockFilterSet *BlockFilter); + MachineBasicBlock *getFirstUnplacedBlock(const BlockChain &PlacedChain, + ArrayRef Blocks, + unsigned &PrevUnplacedBlockIdx); void buildChain(MachineBasicBlock *BB, BlockChain &Chain, - SmallVectorImpl &Blocks, + ArrayRef Blocks, + SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter = 0); void buildLoopChains(MachineFunction &F, MachineLoop &L); void buildCFGChains(MachineFunction &F); @@ -403,17 +407,41 @@ MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock( return BestBlock; } +/// \brief Retrieve the first unplaced basic block. +/// +/// This routine is called when we are unable to use the CFG to walk through +/// all of the basic blocks and form a chain due to unnatural loops in the CFG. +/// We walk through the sequence of blocks, starting from the +/// LastUnplacedBlockIdx. We update this index to avoid re-scanning the entire +/// sequence on repeated calls to this routine. +MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock( + const BlockChain &PlacedChain, + ArrayRef Blocks, + unsigned &PrevUnplacedBlockIdx) { + for (unsigned i = PrevUnplacedBlockIdx, e = Blocks.size(); i != e; ++i) { + MachineBasicBlock *BB = Blocks[i]; + if (BlockToChain[BB] != &PlacedChain) { + PrevUnplacedBlockIdx = i; + return BB; + } + } + return 0; +} + void MachineBlockPlacement::buildChain( MachineBasicBlock *BB, BlockChain &Chain, + ArrayRef Blocks, SmallVectorImpl &BlockWorkList, const BlockFilterSet *BlockFilter) { assert(BB); assert(BlockToChain[BB] == &Chain); assert(*Chain.begin() == BB); + SmallVector Cond; // For AnalyzeBranch. + unsigned PrevUnplacedBlockIdx = 0; + MachineBasicBlock *LoopHeaderBB = BB; markChainSuccessors(Chain, LoopHeaderBB, BlockWorkList, BlockFilter); - SmallVector Cond; // For AnalyzeBranch. BB = *llvm::prior(Chain.end()); for (;;) { assert(BB); @@ -429,10 +457,12 @@ void MachineBlockPlacement::buildChain( Cond.clear(); MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch. if (TII->AnalyzeBranch(*BB, TBB, FBB, Cond) && BB->canFallThrough()) { - MachineFunction::iterator I(BB); - assert(llvm::next(I) != BB->getParent()->end() && - "The final block in the function can fallthrough!"); - BestSucc = llvm::next(I); + MachineFunction::iterator I(BB), NextI(llvm::next(I)); + // Ensure that the layout successor is a viable block, as we know that + // fallthrough is a possibility. + assert(NextI != BB->getParent()->end()); + assert(!BlockFilter || BlockFilter->count(NextI)); + BestSucc = NextI; } // Otherwise, look for the best viable successor if there is one to place @@ -440,13 +470,6 @@ void MachineBlockPlacement::buildChain( if (!BestSucc) BestSucc = selectBestSuccessor(BB, Chain, BlockFilter); - if (BestSucc) { - // Zero out LoopPredecessors for the successor we're about to merge. We - // do this here instead of during the merge to catch cases where we - // didn't *intend* to merge despite non-zero loop predecessors. - BlockToChain[BestSucc]->LoopPredecessors = 0; - } - // If an immediate successor isn't available, look for the best viable // block among those we've identified as not violating the loop's CFG at // this point. This won't be a fallthrough, but it will increase locality. @@ -454,19 +477,28 @@ void MachineBlockPlacement::buildChain( BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter); if (!BestSucc) { - DEBUG(dbgs() << "Finished forming chain for header block " - << getBlockNum(*Chain.begin()) << "\n"); - return; + BestSucc = getFirstUnplacedBlock(Chain, Blocks, PrevUnplacedBlockIdx); + if (!BestSucc) + break; + + DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the " + "layout successor until the CFG reduces\n"); } // Place this block, updating the datastructures to reflect its placement. BlockChain &SuccChain = *BlockToChain[BestSucc]; + // Zero out LoopPredecessors for the successor we're about to merge in case + // we selected a successor that didn't fit naturally into the CFG. + SuccChain.LoopPredecessors = 0; DEBUG(dbgs() << "Merging from " << getBlockNum(BB) << " to " << getBlockNum(BestSucc) << "\n"); 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 Forms basic block chains from the natural loop structures. @@ -484,6 +516,7 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, SmallVector BlockWorkList; BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end()); + BlockChain &LoopChain = *BlockToChain[L.getHeader()]; // 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 @@ -513,8 +546,8 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F, BlockWorkList.push_back(*BI); } - BlockChain &LoopChain = *BlockToChain[L.getHeader()]; - buildChain(*L.block_begin(), LoopChain, BlockWorkList, &LoopBlockSet); + buildChain(*L.block_begin(), LoopChain, L.getBlocks(), BlockWorkList, + &LoopBlockSet); DEBUG({ // Crash at the end so we get all of the debugging output first. @@ -561,11 +594,17 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { ++LI) buildLoopChains(F, **LI); + // We need a vector of blocks so that buildChain can handle unnatural CFG + // constructs by searching for unplaced blocks and just concatenating them. + SmallVector Blocks; + Blocks.reserve(F.size()); + SmallVector BlockWorkList; SmallPtrSet UpdatedPreds; for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { MachineBasicBlock *BB = &*FI; + Blocks.push_back(BB); BlockChain &Chain = *BlockToChain[BB]; if (!UpdatedPreds.insert(&Chain)) continue; @@ -588,7 +627,7 @@ void MachineBlockPlacement::buildCFGChains(MachineFunction &F) { } BlockChain &FunctionChain = *BlockToChain[&F.front()]; - buildChain(&F.front(), FunctionChain, BlockWorkList); + buildChain(&F.front(), FunctionChain, Blocks, BlockWorkList); typedef SmallPtrSet FunctionBlockSetType; DEBUG({ -- cgit v1.2.3-18-g5258