From 766fc1db1640499c6affce80e7337d8c22dc8cb1 Mon Sep 17 00:00:00 2001 From: Anton Korobeynikov Date: Mon, 19 Oct 2009 18:21:09 +0000 Subject: Revert r84295, this unbreaks llvm-gcc bootstrap on x86-64/linux git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84516 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/CodePlacementOpt.cpp | 532 +++++++++++++-------------------------- 1 file changed, 177 insertions(+), 355 deletions(-) (limited to 'lib/CodeGen/CodePlacementOpt.cpp') diff --git a/lib/CodeGen/CodePlacementOpt.cpp b/lib/CodeGen/CodePlacementOpt.cpp index b5a7123..42b24a6 100644 --- a/lib/CodeGen/CodePlacementOpt.cpp +++ b/lib/CodeGen/CodePlacementOpt.cpp @@ -34,6 +34,14 @@ namespace { const TargetInstrInfo *TII; const TargetLowering *TLI; + /// ChangedMBBs - BBs which are modified by OptimizeIntraLoopEdges. + SmallPtrSet ChangedMBBs; + + /// UncondJmpMBBs - A list of BBs which are in loops and end with + /// unconditional branches. + SmallVector, 4> + UncondJmpMBBs; + public: static char ID; CodePlacementOpt() : MachineFunctionPass(&ID) {} @@ -50,15 +58,7 @@ namespace { } private: - bool HasFallthrough(MachineBasicBlock *MBB); - bool HasAnalyzableTerminator(MachineBasicBlock *MBB); - void Splice(MachineFunction &MF, - MachineFunction::iterator InsertPt, - MachineFunction::iterator Begin, - MachineFunction::iterator End); - void UpdateTerminator(MachineBasicBlock *MBB); - bool OptimizeIntraLoopEdges(MachineFunction &MF); - bool OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, MachineLoop *L); + bool OptimizeIntraLoopEdges(); bool AlignLoops(MachineFunction &MF); bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align); }; @@ -70,365 +70,168 @@ FunctionPass *llvm::createCodePlacementOptPass() { return new CodePlacementOpt(); } -/// HasFallthrough - Test whether the given branch has a fallthrough, either as -/// a plain fallthrough or as a fallthrough case of a conditional branch. +/// OptimizeBackEdges - Place loop back edges to move unconditional branches +/// out of the loop. /// -bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) { - MachineBasicBlock *TBB = 0, *FBB = 0; - SmallVector Cond; - if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) - return false; - // This conditional branch has no fallthrough. - if (FBB) - return false; - // An unconditional branch has no fallthrough. - if (Cond.empty() && TBB) - return false; - // It has a fallthrough. - return true; -} - -/// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB. -/// This is called before major changes are begun to test whether it will be -/// possible to complete the changes. +/// A: +/// ... +/// /// -/// Target-specific code is hereby encouraged to make AnalyzeBranch succeed -/// whenever possible. +/// B: --> loop header +/// ... +/// jcc C, [exit] /// -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. - if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond)) - return false; - // Make sure we have the option of reversing the condition. - if (!Cond.empty() && TII->ReverseBranchCondition(Cond)) - return false; - return true; -} - -/// Splice - Move the sequence of instructions [Begin,End) to just before -/// InsertPt. Update branch instructions as needed to account for broken -/// fallthrough edges and to take advantage of newly exposed fallthrough -/// opportunities. +/// C: +/// ... +/// jmp B /// -void CodePlacementOpt::Splice(MachineFunction &MF, - MachineFunction::iterator InsertPt, - MachineFunction::iterator Begin, - MachineFunction::iterator End) { - assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() && - "Splice can't change the entry block!"); - MachineFunction::iterator OldBeginPrior = prior(Begin); - MachineFunction::iterator OldEndPrior = prior(End); - - 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; - 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. +/// A: +/// ... +/// jmp B /// -bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) { - bool Changed = false; - +/// C: +/// ... +/// +/// +/// B: --> loop header +/// ... +/// jcc C, [exit] +/// +bool CodePlacementOpt::OptimizeIntraLoopEdges() { if (!TLI->shouldOptimizeCodePlacement()) - return Changed; - - for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); - I != E; ++I) - Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I); - - return Changed; -} + return false; -/// 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); - - if (TopMBB == MF.begin() || - HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) { - new_top: - for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(), - PE = TopMBB->pred_end(); PI != PE; ++PI) { - MachineBasicBlock *Pred = *PI; - if (Pred == TopMBB) continue; - if (HasFallthrough(Pred)) continue; - if (!L->contains(Pred)) continue; - - // Verify that we can analyze all the loop entry edges before beginning - // any changes which will require us to be able to analyze them. - if (Pred == MF.begin()) - continue; - if (!HasAnalyzableTerminator(Pred)) + for (unsigned i = 0, e = UncondJmpMBBs.size(); i != e; ++i) { + MachineBasicBlock *MBB = UncondJmpMBBs[i].first; + MachineBasicBlock *SuccMBB = UncondJmpMBBs[i].second; + MachineLoop *L = MLI->getLoopFor(MBB); + assert(L && "BB is expected to be in a loop!"); + + if (ChangedMBBs.count(MBB)) { + // BB has been modified, re-analyze. + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty()) continue; - if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred)))) + if (MLI->getLoopFor(TBB) != L || TBB->isLandingPad()) continue; + SuccMBB = TBB; + } else { + assert(MLI->getLoopFor(SuccMBB) == L && + "Successor is not in the same loop!"); + } - // Move the block. + if (MBB->isLayoutSuccessor(SuccMBB)) { + // Successor is right after MBB, just eliminate the unconditional jmp. + // Can this happen? + TII->RemoveBranch(*MBB); + ChangedMBBs.insert(MBB); + ++NumIntraElim; 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. - MachineFunction::iterator Begin = Pred; - MachineFunction::iterator End = next(Begin); - while (Begin != MF.begin()) { - MachineFunction::iterator Prior = prior(Begin); - if (Prior == MF.begin()) - break; - // Stop when a non-fallthrough edge is found. - if (!HasFallthrough(Prior)) - break; - // Stop if a block which could fall-through out of the loop is found. - if (Prior->isSuccessor(End)) - break; - // If we've reached the top, stop scanning. - if (Prior == MachineFunction::iterator(TopMBB)) { - // We know top currently has a fall through (because we just checked - // it) which would be lost if we do the transformation, so it isn't - // worthwhile to do the transformation unless it would expose a new - // fallthrough edge. - if (!Prior->isSuccessor(End)) - goto next_pred; - // Otherwise we can stop scanning and procede to move the blocks. + continue; + } + + // Now check if the predecessor is fallthrough from any BB. If there is, + // that BB should be from outside the loop since edge will become a jmp. + bool OkToMove = true; + MachineBasicBlock *FtMBB = 0, *FtTBB = 0, *FtFBB = 0; + SmallVector FtCond; + for (MachineBasicBlock::pred_iterator PI = SuccMBB->pred_begin(), + PE = SuccMBB->pred_end(); PI != PE; ++PI) { + MachineBasicBlock *PredMBB = *PI; + if (PredMBB->isLayoutSuccessor(SuccMBB)) { + if (TII->AnalyzeBranch(*PredMBB, FtTBB, FtFBB, FtCond)) { + OkToMove = false; break; } - // If we hit a switch or something complicated, don't move anything - // for this predecessor. - if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior)))) - break; - Begin = Prior; - ContiguousBlocks.insert(Begin); - ++NumIntraMoved; + if (!FtTBB) + FtTBB = SuccMBB; + else if (!FtFBB) { + assert(FtFBB != SuccMBB && "Unexpected control flow!"); + FtFBB = SuccMBB; + } + + // A fallthrough. + FtMBB = PredMBB; + MachineLoop *PL = MLI->getLoopFor(PredMBB); + if (PL && (PL == L || PL->getLoopDepth() >= L->getLoopDepth())) + OkToMove = false; + + break; } - - // 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; - - // 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. - goto new_top; - next_pred:; } - } - - // If the loop previously didn't exit with a fall-through and it now does, - // we eliminated a branch. - if (!BotHasFallthrough && HasFallthrough(BotMBB)) { - ++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. - - // 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)); - bool InsertAtTop = false; - if (TopMBB != MF.begin() && - !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) && - HasFallthrough(BotMBB)) { - InsertPt = TopMBB; - InsertAtTop = true; - } - - // 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(); - BI != BE; ++BI) { - MachineBasicBlock *BB = *BI; - - // Verify that we can analyze all the loop entry edges before beginning - // any changes which will require us to be able to analyze them. - if (!HasAnalyzableTerminator(BB)) - continue; - if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB)))) - continue; - - // If the layout predecessor is part of the loop, this block will be - // processed along with it. This keeps them in their relative order. - if (BB != MF.begin() && - L->contains(prior(MachineFunction::iterator(BB)))) - continue; - - // Check to see if this block is already contiguous with the main - // portion of the loop. - if (!ContiguousBlocks.insert(BB)) - continue; - - // Move the block. - 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)); - for (; End != MF.end(); ++End) { - if (!L->contains(End)) break; - if (!HasAnalyzableTerminator(End)) break; - ContiguousBlocks.insert(End); - ++NumIntraMoved; + if (!OkToMove) + continue; + + // Is it profitable? If SuccMBB can fallthrough itself, that can be changed + // into a jmp. + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + if (TII->AnalyzeBranch(*SuccMBB, TBB, FBB, Cond)) + continue; + if (!TBB && Cond.empty()) + TBB = next(MachineFunction::iterator(SuccMBB)); + else if (!FBB && !Cond.empty()) + FBB = next(MachineFunction::iterator(SuccMBB)); + + // This calculate the cost of the transformation. Also, it finds the *only* + // intra-loop edge if there is one. + int Cost = 0; + bool HasOneIntraSucc = true; + MachineBasicBlock *IntraSucc = 0; + for (MachineBasicBlock::succ_iterator SI = SuccMBB->succ_begin(), + SE = SuccMBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SSMBB = *SI; + if (MLI->getLoopFor(SSMBB) == L) { + if (!IntraSucc) + IntraSucc = SSMBB; + else + HasOneIntraSucc = false; } - // 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 (!InsertAtTop) - for (; End != MF.end(); ++End) { - if (L->contains(End)) break; - if (!HasAnalyzableTerminator(End)) break; - if (!HasFallthrough(prior(End))) break; + if (SuccMBB->isLayoutSuccessor(SSMBB)) + // This will become a jmp. + ++Cost; + else if (MBB->isLayoutSuccessor(SSMBB)) { + // One of the successor will become the new fallthrough. + if (SSMBB == FBB) { + FBB = 0; + --Cost; + } else if (!FBB && SSMBB == TBB && Cond.empty()) { + TBB = 0; + --Cost; + } else if (!Cond.empty() && !TII->ReverseBranchCondition(Cond)) { + assert(SSMBB == TBB); + TBB = FBB; + FBB = 0; + --Cost; } - - // Move the blocks. - Splice(MF, InsertPt, Begin, End); - - // Update TopMBB. - if (InsertAtTop) - TopMBB = Begin; + } } + if (Cost) + continue; + + // Now, let's move the successor to below the BB to eliminate the jmp. + SuccMBB->moveAfter(MBB); + TII->RemoveBranch(*MBB); + TII->RemoveBranch(*SuccMBB); + if (TBB) + TII->InsertBranch(*SuccMBB, TBB, FBB, Cond); + ChangedMBBs.insert(MBB); + ChangedMBBs.insert(SuccMBB); + if (FtMBB) { + TII->RemoveBranch(*FtMBB); + TII->InsertBranch(*FtMBB, FtTBB, FtFBB, FtCond); + ChangedMBBs.insert(FtMBB); + } + Changed = true; + } + ++NumIntraMoved; return Changed; } @@ -452,8 +255,6 @@ bool CodePlacementOpt::AlignLoops(MachineFunction &MF) { return Changed; } -/// AlignLoop - Align loop headers to target preferred alignments. -/// bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align) { bool Changed = false; @@ -463,13 +264,13 @@ bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L, 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)); - } + if (TopMBB == MF.begin()) return Changed; + + MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(TopMBB)); + while (MLI->getLoopFor(PredMBB) == L) { + TopMBB = PredMBB; + if (TopMBB == MF.begin()) return Changed; + PredMBB = prior(MachineFunction::iterator(TopMBB)); } TopMBB->setAlignment(Align); @@ -487,9 +288,30 @@ bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) { TLI = MF.getTarget().getTargetLowering(); TII = MF.getTarget().getInstrInfo(); - bool Changed = OptimizeIntraLoopEdges(MF); + // Analyze the BBs first and keep track of BBs that + // end with an unconditional jmp to another block in the same loop. + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { + MachineBasicBlock *MBB = I; + if (MBB->isLandingPad()) + continue; + MachineLoop *L = MLI->getLoopFor(MBB); + if (!L) + continue; + + MachineBasicBlock *TBB = 0, *FBB = 0; + SmallVector Cond; + if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty()) + continue; + if (MLI->getLoopFor(TBB) == L && !TBB->isLandingPad()) + UncondJmpMBBs.push_back(std::make_pair(MBB, TBB)); + } + + bool Changed = OptimizeIntraLoopEdges(); Changed |= AlignLoops(MF); + ChangedMBBs.clear(); + UncondJmpMBBs.clear(); + return Changed; } -- cgit v1.1