From 853d3fb8d24fab2258e9cd5dce3ec8ff4189eeda Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 22 Jun 2010 17:25:57 +0000 Subject: Move PHIElimination's SplitCriticalEdge for MachineBasicBlocks out into a utility routine, teach it how to update MachineLoopInfo, and make use of it in MachineLICM to split critical edges on demand. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106555 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineLICM.cpp | 73 +++++++++++++++++++++++++++++++-------------- 1 file changed, 50 insertions(+), 23 deletions(-) (limited to 'lib/CodeGen/MachineLICM.cpp') diff --git a/lib/CodeGen/MachineLICM.cpp b/lib/CodeGen/MachineLICM.cpp index d9623ab..9b24a9a 100644 --- a/lib/CodeGen/MachineLICM.cpp +++ b/lib/CodeGen/MachineLICM.cpp @@ -83,7 +83,6 @@ namespace { const char *getPassName() const { return "Machine Instruction LICM"; } - // FIXME: Loop preheaders? virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); @@ -182,6 +181,10 @@ namespace { /// current loop preheader that may become duplicates of instructions that /// are hoisted out of the loop. void InitCSEMap(MachineBasicBlock *BB); + + /// getCurPreheader - Get the preheader for the current loop, splitting + /// a critical edge if needed. + MachineBasicBlock *getCurPreheader(); }; } // end anonymous namespace @@ -193,11 +196,11 @@ FunctionPass *llvm::createMachineLICMPass(bool PreRegAlloc) { return new MachineLICM(PreRegAlloc); } -/// LoopIsOuterMostWithPreheader - Test if the given loop is the outer-most -/// loop that has a preheader. -static bool LoopIsOuterMostWithPreheader(MachineLoop *CurLoop) { +/// LoopIsOuterMostWithPredecessor - Test if the given loop is the outer-most +/// loop that has a unique predecessor. +static bool LoopIsOuterMostWithPredecessor(MachineLoop *CurLoop) { for (MachineLoop *L = CurLoop->getParentLoop(); L; L = L->getParentLoop()) - if (L->getLoopPreheader()) + if (L->getLoopPredecessor()) return false; return true; } @@ -223,20 +226,11 @@ bool MachineLICM::runOnMachineFunction(MachineFunction &MF) { for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; ++I){ CurLoop = *I; + CurPreheader = 0; // If this is done before regalloc, only visit outer-most preheader-sporting // loops. - if (PreRegAlloc && !LoopIsOuterMostWithPreheader(CurLoop)) - continue; - - // Determine the block to which to hoist instructions. If we can't find a - // suitable loop preheader, we can't do any hoisting. - // - // FIXME: We are only hoisting if the basic block coming into this loop - // has only one successor. This isn't the case in general because we haven't - // broken critical edges or added preheaders. - CurPreheader = CurLoop->getLoopPreheader(); - if (!CurPreheader) + if (PreRegAlloc && !LoopIsOuterMostWithPredecessor(CurLoop)) continue; if (!PreRegAlloc) @@ -438,13 +432,16 @@ void MachineLICM::AddToLiveIns(unsigned Reg) { /// operands that is safe to hoist, this instruction is called to do the /// dirty work. void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { + MachineBasicBlock *Preheader = getCurPreheader(); + if (!Preheader) return; + // Now move the instructions to the predecessor, inserting it before any // terminator instructions. DEBUG({ dbgs() << "Hoisting " << *MI; - if (CurPreheader->getBasicBlock()) + if (Preheader->getBasicBlock()) dbgs() << " to MachineBasicBlock " - << CurPreheader->getName(); + << Preheader->getName(); if (MI->getParent()->getBasicBlock()) dbgs() << " from MachineBasicBlock " << MI->getParent()->getName(); @@ -453,7 +450,7 @@ void MachineLICM::HoistPostRA(MachineInstr *MI, unsigned Def) { // Splice the instruction to the preheader. MachineBasicBlock *MBB = MI->getParent(); - CurPreheader->splice(CurPreheader->getFirstTerminator(), MBB, MI); + Preheader->splice(Preheader->getFirstTerminator(), MBB, MI); // Add register to livein list to all the BBs in the current loop since a // loop invariant must be kept live throughout the whole loop. This is @@ -756,6 +753,9 @@ bool MachineLICM::EliminateCSE(MachineInstr *MI, /// that are safe to hoist, this instruction is called to do the dirty work. /// void MachineLICM::Hoist(MachineInstr *MI) { + MachineBasicBlock *Preheader = getCurPreheader(); + if (!Preheader) return; + // First check whether we should hoist this instruction. if (!IsLoopInvariantInst(*MI) || !IsProfitableToHoist(*MI)) { // If not, try unfolding a hoistable load. @@ -767,9 +767,9 @@ void MachineLICM::Hoist(MachineInstr *MI) { // terminator instructions. DEBUG({ dbgs() << "Hoisting " << *MI; - if (CurPreheader->getBasicBlock()) + if (Preheader->getBasicBlock()) dbgs() << " to MachineBasicBlock " - << CurPreheader->getName(); + << Preheader->getName(); if (MI->getParent()->getBasicBlock()) dbgs() << " from MachineBasicBlock " << MI->getParent()->getName(); @@ -779,7 +779,7 @@ void MachineLICM::Hoist(MachineInstr *MI) { // If this is the first instruction being hoisted to the preheader, // initialize the CSE map with potential common expressions. if (FirstInLoop) { - InitCSEMap(CurPreheader); + InitCSEMap(Preheader); FirstInLoop = false; } @@ -789,7 +789,7 @@ void MachineLICM::Hoist(MachineInstr *MI) { CI = CSEMap.find(Opcode); if (!EliminateCSE(MI, CI)) { // Otherwise, splice the instruction to the preheader. - CurPreheader->splice(CurPreheader->getFirstTerminator(),MI->getParent(),MI); + Preheader->splice(Preheader->getFirstTerminator(),MI->getParent(),MI); // Clear the kill flags of any register this instruction defines, // since they may need to be live throughout the entire loop @@ -813,3 +813,30 @@ void MachineLICM::Hoist(MachineInstr *MI) { ++NumHoisted; Changed = true; } + +MachineBasicBlock *MachineLICM::getCurPreheader() { + // Determine the block to which to hoist instructions. If we can't find a + // suitable loop predecessor, we can't do any hoisting. + + // If we've tried to get a preheader and failed, don't try again. + if (CurPreheader == reinterpret_cast(-1)) + return 0; + + if (!CurPreheader) { + CurPreheader = CurLoop->getLoopPreheader(); + if (!CurPreheader) { + MachineBasicBlock *Pred = CurLoop->getLoopPredecessor(); + if (!Pred) { + CurPreheader = reinterpret_cast(-1); + return 0; + } + + CurPreheader = Pred->SplitCriticalEdge(CurLoop->getHeader(), this); + if (!CurPreheader) { + CurPreheader = reinterpret_cast(-1); + return 0; + } + } + } + return CurPreheader; +} -- cgit v1.1