public:
static char ID;
- CodePlacementOpt() : MachineFunctionPass(&ID) {}
+ CodePlacementOpt() : MachineFunctionPass(ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const {
MachineFunction::iterator InsertPt,
MachineFunction::iterator Begin,
MachineFunction::iterator End);
- void UpdateTerminator(MachineBasicBlock *MBB);
+ bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
+ MachineLoop *L);
+ bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
+ MachineLoop *L);
+ bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
bool OptimizeIntraLoopEdges(MachineFunction &MF);
- bool OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, MachineLoop *L);
bool AlignLoops(MachineFunction &MF);
bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
};
// Conservatively ignore EH landing pads.
if (MBB->isLandingPad()) return false;
- // Ignore blocks which look like they might have EH-related control flow.
- // At the time of this writing, there are blocks which AnalyzeBranch
- // thinks end in single uncoditional branches, yet which have two CFG
- // successors. Code in this file is not prepared to reason about such things.
- if (!MBB->empty() && MBB->back().getOpcode() == TargetInstrInfo::EH_LABEL)
- return false;
-
// Aggressively handle return blocks and similar constructs.
if (MBB->succ_empty()) return true;
// Ask the target's AnalyzeBranch if it can handle this block.
MachineBasicBlock *TBB = 0, *FBB = 0;
SmallVector<MachineOperand, 4> Cond;
- // Make the the terminator is understood.
+ // Make sure the terminator is understood.
if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
return false;
+ // Ignore blocks which look like they might have EH-related control flow.
+ // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't
+ // recognize the possibility of a control transfer through an unwind.
+ // Such blocks contain EH_LABEL instructions, however they may be in the
+ // middle of the block. Instead of searching for them, just check to see
+ // if the CFG disagrees with AnalyzeBranch.
+ if (1u + !Cond.empty() != MBB->succ_size())
+ return false;
// Make sure we have the option of reversing the condition.
if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
return false;
MF.splice(InsertPt, Begin, End);
- UpdateTerminator(prior(Begin));
- UpdateTerminator(OldBeginPrior);
- UpdateTerminator(OldEndPrior);
-}
-
-/// UpdateTerminator - Update the terminator instructions in MBB to account
-/// for changes to the layout. If the block previously used a fallthrough,
-/// it may now need a branch, and if it previously used branching it may now
-/// be able to use a fallthrough.
-///
-void CodePlacementOpt::UpdateTerminator(MachineBasicBlock *MBB) {
- // A block with no successors has no concerns with fall-through edges.
- if (MBB->succ_empty()) return;
-
- MachineBasicBlock *TBB = 0, *FBB = 0;
- SmallVector<MachineOperand, 4> Cond;
- assert(!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) &&
- "UpdateTerminators requires analyzable predecessors!");
- if (Cond.empty()) {
- if (TBB) {
- // The block has an unconditional branch. If its successor is now
- // its layout successor, delete the branch.
- if (MBB->isLayoutSuccessor(TBB))
- TII->RemoveBranch(*MBB);
- } else {
- // The block has an unconditional fallthrough. If its successor is not
- // its layout successor, insert a branch.
- TBB = *MBB->succ_begin();
- if (!MBB->isLayoutSuccessor(TBB))
- TII->InsertBranch(*MBB, TBB, 0, Cond);
- }
- } else {
- if (FBB) {
- // The block has a non-fallthrough conditional branch. If one of its
- // successors is its layout successor, rewrite it to a fallthrough
- // conditional branch.
- if (MBB->isLayoutSuccessor(TBB)) {
- TII->RemoveBranch(*MBB);
- TII->ReverseBranchCondition(Cond);
- TII->InsertBranch(*MBB, FBB, 0, Cond);
- } else if (MBB->isLayoutSuccessor(FBB)) {
- TII->RemoveBranch(*MBB);
- TII->InsertBranch(*MBB, TBB, 0, Cond);
- }
- } else {
- // The block has a fallthrough conditional branch.
- MachineBasicBlock *MBBA = *MBB->succ_begin();
- MachineBasicBlock *MBBB = *next(MBB->succ_begin());
- if (MBBA == TBB) std::swap(MBBB, MBBA);
- if (MBB->isLayoutSuccessor(TBB)) {
- TII->RemoveBranch(*MBB);
- TII->ReverseBranchCondition(Cond);
- TII->InsertBranch(*MBB, MBBA, 0, Cond);
- } else if (!MBB->isLayoutSuccessor(MBBA)) {
- TII->RemoveBranch(*MBB);
- TII->InsertBranch(*MBB, TBB, MBBA, Cond);
- }
- }
- }
-}
-
-/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
-/// intra-loop branching and to form contiguous loops.
-///
-bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
- bool Changed = false;
-
- if (!TLI->shouldOptimizeCodePlacement())
- return Changed;
-
- for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
- I != E; ++I)
- Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
-
- return Changed;
+ prior(Begin)->updateTerminator();
+ OldBeginPrior->updateTerminator();
+ OldEndPrior->updateTerminator();
}
-/// OptimizeIntraLoopEdgesInLoop - Reposition loop blocks to minimize
-/// intra-loop branching and to form contiguous loops.
-///
-/// This code takes the approach of making minor changes to the existing
-/// layout to fix specific loop-oriented problems. Also, it depends on
-/// AnalyzeBranch, which can't understand complex control instructions.
-///
-bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF,
- MachineLoop *L) {
+/// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
+/// to the loop top to the top of the loop so that they have a fall through.
+/// This can introduce a branch on entry to the loop, but it can eliminate a
+/// branch within the loop. See the @simple case in
+/// test/CodeGen/X86/loop_blocks.ll for an example of this.
+bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
+ MachineLoop *L) {
bool Changed = false;
+ MachineBasicBlock *TopMBB = L->getTopBlock();
- // Do optimization for nested loops.
- for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
- Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
-
- // Keep a record of which blocks are in the portion of the loop contiguous
- // with the loop header.
- SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
- ContiguousBlocks.insert(L->getHeader());
-
- // Find the loop "top", ignoring any discontiguous parts.
- MachineBasicBlock *TopMBB = L->getHeader();
- if (TopMBB != MF.begin()) {
- MachineBasicBlock *PriorMBB = prior(MachineFunction::iterator(TopMBB));
- while (L->contains(PriorMBB)) {
- ContiguousBlocks.insert(PriorMBB);
- TopMBB = PriorMBB;
- if (TopMBB == MF.begin()) break;
- PriorMBB = prior(MachineFunction::iterator(TopMBB));
- }
- }
-
- // Find the loop "bottom", ignoring any discontiguous parts.
- MachineBasicBlock *BotMBB = L->getHeader();
- if (BotMBB != prior(MF.end())) {
- MachineBasicBlock *NextMBB = next(MachineFunction::iterator(BotMBB));
- while (L->contains(NextMBB)) {
- ContiguousBlocks.insert(NextMBB);
- BotMBB = NextMBB;
- if (BotMBB == next(MachineFunction::iterator(BotMBB))) break;
- NextMBB = next(MachineFunction::iterator(BotMBB));
- }
- }
-
- // First, move blocks which unconditionally jump to the loop top to the
- // top of the loop so that they have a fall through. This can introduce a
- // branch on entry to the loop, but it can eliminate a branch within the
- // loop. See the @simple case in test/CodeGen/X86/loop_blocks.ll for an
- // example of this.
-
- bool BotHasFallthrough = HasFallthrough(BotMBB);
+ bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
if (TopMBB == MF.begin() ||
HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
continue;
// Move the block.
+ DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber()
+ << " to top of loop.\n");
Changed = true;
- ContiguousBlocks.insert(Pred);
// Move it and all the blocks that can reach it via fallthrough edges
- // exclusively, to keep existing fallthrough-edges intact.
+ // exclusively, to keep existing fallthrough edges intact.
MachineFunction::iterator Begin = Pred;
- MachineFunction::iterator End = next(Begin);
+ MachineFunction::iterator End = llvm::next(Begin);
while (Begin != MF.begin()) {
MachineFunction::iterator Prior = prior(Begin);
if (Prior == MF.begin())
// for this predecessor.
if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
break;
+ // Ok, the block prior to Begin will be moved along with the rest.
+ // Extend the range to include it.
Begin = Prior;
- ContiguousBlocks.insert(Begin);
++NumIntraMoved;
}
- // Update BotMBB, before moving Begin/End around and forgetting where
- // the new bottom is.
- if (BotMBB == prior(End))
- BotMBB = prior(Begin);
-
// Move the blocks.
Splice(MF, TopMBB, Begin, End);
- // Update TopMBB, now that all the updates requiring the old top are
- // complete.
- TopMBB = Begin;
+ // Update TopMBB.
+ TopMBB = L->getTopBlock();
// We have a new loop top. Iterate on it. We shouldn't have to do this
// too many times if BranchFolding has done a reasonable job.
// If the loop previously didn't exit with a fall-through and it now does,
// we eliminated a branch.
- if (!BotHasFallthrough && HasFallthrough(BotMBB)) {
+ if (Changed &&
+ !BotHasFallthrough &&
+ HasFallthrough(L->getBottomBlock())) {
++NumIntraElim;
- BotHasFallthrough = true;
}
- // Next, move any loop blocks that are not in the portion of the loop
- // contiguous with the header. This makes the loop contiguous, provided that
- // AnalyzeBranch can handle all the relevant branching. See the @cfg_islands
- // case in test/CodeGen/X86/loop_blocks.ll for an example of this.
+ return Changed;
+}
+
+/// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
+/// portion of the loop contiguous with the header. This usually makes the loop
+/// contiguous, provided that AnalyzeBranch can handle all the relevant
+/// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
+/// for an example of this.
+bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
+ MachineLoop *L) {
+ bool Changed = false;
+ MachineBasicBlock *TopMBB = L->getTopBlock();
+ MachineBasicBlock *BotMBB = L->getBottomBlock();
// Determine a position to move orphaned loop blocks to. If TopMBB is not
// entered via fallthrough and BotMBB is exited via fallthrough, prepend them
// to the top of the loop to avoid loosing that fallthrough. Otherwise append
// them to the bottom, even if it previously had a fallthrough, on the theory
// that it's worth an extra branch to keep the loop contiguous.
- MachineFunction::iterator InsertPt = next(MachineFunction::iterator(BotMBB));
+ MachineFunction::iterator InsertPt =
+ llvm::next(MachineFunction::iterator(BotMBB));
bool InsertAtTop = false;
if (TopMBB != MF.begin() &&
!HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
InsertAtTop = true;
}
+ // Keep a record of which blocks are in the portion of the loop contiguous
+ // with the loop header.
+ SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
+ for (MachineFunction::iterator I = TopMBB,
+ E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
+ ContiguousBlocks.insert(I);
+
// Find non-contigous blocks and fix them.
if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
continue;
// Move the block.
+ DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber()
+ << " to be contiguous with loop.\n");
Changed = true;
// Process this block and all loop blocks contiguous with it, to keep
// them in their relative order.
MachineFunction::iterator Begin = BB;
- MachineFunction::iterator End = next(MachineFunction::iterator(BB));
+ MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
for (; End != MF.end(); ++End) {
if (!L->contains(End)) break;
if (!HasAnalyzableTerminator(End)) break;
++NumIntraMoved;
}
- // Update BotMBB.
- if (!InsertAtTop)
- BotMBB = prior(End);
-
// If we're inserting at the bottom of the loop, and the code we're
// moving originally had fall-through successors, bring the sucessors
// up with the loop blocks to preserve the fall-through edges.
if (!HasFallthrough(prior(End))) break;
}
- // Move the blocks.
+ // Move the blocks. This may invalidate TopMBB and/or BotMBB, but
+ // we don't need them anymore at this point.
Splice(MF, InsertPt, Begin, End);
-
- // Update TopMBB.
- if (InsertAtTop)
- TopMBB = Begin;
}
return Changed;
}
+/// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
+/// intra-loop branching and to form contiguous loops.
+///
+/// This code takes the approach of making minor changes to the existing
+/// layout to fix specific loop-oriented problems. Also, it depends on
+/// AnalyzeBranch, which can't understand complex control instructions.
+///
+bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
+ MachineLoop *L) {
+ bool Changed = false;
+
+ // Do optimization for nested loops.
+ for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
+ Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
+
+ // Do optimization for this loop.
+ Changed |= EliminateUnconditionalJumpsToTop(MF, L);
+ Changed |= MoveDiscontiguousLoopBlocks(MF, L);
+
+ return Changed;
+}
+
+/// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
+/// intra-loop branching and to form contiguous loops.
+///
+bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
+ bool Changed = false;
+
+ if (!TLI->shouldOptimizeCodePlacement())
+ return Changed;
+
+ // Do optimization for each loop in the function.
+ for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
+ I != E; ++I)
+ if (!(*I)->getParentLoop())
+ Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
+
+ return Changed;
+}
+
/// AlignLoops - Align loop headers to target preferred alignments.
///
bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= AlignLoop(MF, *I, Align);
- MachineBasicBlock *TopMBB = L->getHeader();
- if (TopMBB != MF.begin()) {
- MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(TopMBB));
- while (L->contains(PredMBB)) {
- TopMBB = PredMBB;
- if (TopMBB == MF.begin()) break;
- PredMBB = prior(MachineFunction::iterator(TopMBB));
- }
- }
-
- TopMBB->setAlignment(Align);
+ L->getTopBlock()->setAlignment(Align);
Changed = true;
++NumLoopsAligned;
projects / oota-llvm.git / blobdiff