X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FCodePlacementOpt.cpp;h=91a9536e7757c250634194021496e691f4937fb5;hb=90c579de5a383cee278acc3f7e7b9d0a656e6a35;hp=85cbc78b5148cc07ad466d5fc969e82c6b096a32;hpb=afc158780089a3d9c1bfe78de77855dfdd901bd0;p=oota-llvm.git diff --git a/lib/CodeGen/CodePlacementOpt.cpp b/lib/CodeGen/CodePlacementOpt.cpp index 85cbc78b514..91a9536e775 100644 --- a/lib/CodeGen/CodePlacementOpt.cpp +++ b/lib/CodeGen/CodePlacementOpt.cpp @@ -36,7 +36,7 @@ namespace { public: static char ID; - CodePlacementOpt() : MachineFunctionPass(&ID) {} + CodePlacementOpt() : MachineFunctionPass(ID) {} virtual bool runOnMachineFunction(MachineFunction &MF); virtual const char *getPassName() const { @@ -56,9 +56,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); }; @@ -99,22 +102,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,134 +141,22 @@ void CodePlacementOpt::Splice(MachineFunction &MF, 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 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 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)))) { @@ -286,13 +178,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()) @@ -318,22 +211,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. @@ -344,22 +232,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 // 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))) && @@ -368,6 +267,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(); @@ -393,12 +299,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; @@ -406,10 +314,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. @@ -420,17 +324,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) { @@ -461,17 +402,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;