X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FCodePlacementOpt.cpp;h=c13c05e26a20e6329c15a08ac8ec44c012b85ac4;hb=aba6559370c3d453588103fb667ffa3b11b76652;hp=b5a7123539a1c99349473185d1b40c41730663ac;hpb=c499e32b371faf02cbd17e03bad2a42b93ade82a;p=oota-llvm.git diff --git a/lib/CodeGen/CodePlacementOpt.cpp b/lib/CodeGen/CodePlacementOpt.cpp index b5a7123539a..c13c05e26a2 100644 --- a/lib/CodeGen/CodePlacementOpt.cpp +++ b/lib/CodeGen/CodePlacementOpt.cpp @@ -7,8 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file implements the pass that optimize code placement and align loop -// headers to target specific alignment boundary. +// This file implements the pass that optimizes code placement and aligns loop +// headers to target-specific alignment boundaries. // //===----------------------------------------------------------------------===// @@ -36,12 +36,9 @@ namespace { public: static char ID; - CodePlacementOpt() : MachineFunctionPass(&ID) {} + CodePlacementOpt() : MachineFunctionPass(ID) {} virtual bool runOnMachineFunction(MachineFunction &MF); - virtual const char *getPassName() const { - return "Code Placement Optimizater"; - } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); @@ -56,9 +53,12 @@ namespace { 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); }; @@ -66,9 +66,9 @@ namespace { char CodePlacementOpt::ID = 0; } // end anonymous namespace -FunctionPass *llvm::createCodePlacementOptPass() { - return new CodePlacementOpt(); -} +char &llvm::CodePlacementOptID = CodePlacementOpt::ID; +INITIALIZE_PASS(CodePlacementOpt, "code-placement", + "Code Placement Optimizer", false, false) /// HasFallthrough - Test whether the given branch has a fallthrough, either as /// a plain fallthrough or as a fallthrough case of a conditional branch. @@ -99,22 +99,23 @@ bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) { // 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 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; @@ -137,135 +138,22 @@ void CodePlacementOpt::Splice(MachineFunction &MF, MF.splice(InsertPt, Begin, End); - UpdateTerminator(prior(Begin)); - UpdateTerminator(OldBeginPrior); - UpdateTerminator(OldEndPrior); + prior(Begin)->updateTerminator(); + OldBeginPrior->updateTerminator(); + OldEndPrior->updateTerminator(); } -/// 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 Cond; - bool B = TII->AnalyzeBranch(*MBB, TBB, FBB, Cond); - (void) B; - assert(!B && "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) { +/// 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(); - if (!TLI->shouldOptimizeCodePlacement()) - return Changed; - - for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); - I != E; ++I) - Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I); - - return Changed; -} - -/// 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) { - bool Changed = false; - - // 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 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)))) { @@ -287,13 +175,14 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, 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()) @@ -319,22 +208,17 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, // 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. @@ -345,22 +229,33 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, // 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 + // to the top of the loop to avoid losing 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))) && @@ -369,6 +264,13 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, InsertAtTop = true; } + // Keep a record of which blocks are in the portion of the loop contiguous + // with the loop header. + SmallPtrSet 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(); @@ -394,12 +296,14 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, 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; @@ -407,10 +311,6 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, ++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. @@ -421,17 +321,54 @@ bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, 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) { @@ -462,17 +399,7 @@ bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L, 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;