From 2399786b279b6db7077ac36020153714530365df Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Sat, 18 Sep 2010 06:42:17 +0000 Subject: Fix code that break critical edges for PHI uses. Watch out for multiple PHIs in different blocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@114270 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineSink.cpp | 137 +++++++++++++++++++++----------------------- 1 file changed, 66 insertions(+), 71 deletions(-) (limited to 'lib/CodeGen/MachineSink.cpp') diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 330e675a2e..3d9f24e606 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -86,12 +86,11 @@ namespace { MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *From, MachineBasicBlock *To, - bool HasNonePHIUse); + bool AllPHIUse); bool SinkInstruction(MachineInstr *MI, bool &SawStore); bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - SmallPtrSet &PHIUses, - bool &NonPHIUse, bool &LocalUse) const; + bool &AllPHIUse, bool &LocalUse) const; bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); }; @@ -139,42 +138,54 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - SmallPtrSet &PHIUses, - bool &NonPHIUse, bool &LocalUse) const { + bool &AllPHIUse, bool &LocalUse) const { assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); + + if (MRI->use_nodbg_empty(Reg)) + return true; + // Ignoring debug uses is necessary so debug info doesn't affect the code. // This may leave a referencing dbg_value in the original block, before // the definition of the vreg. Dwarf generator handles this although the // user might not get the right info at runtime. + + // PHI is in the successor BB. e.g. + // BB#1: derived from LLVM BB %bb4.preheader + // Predecessors according to CFG: BB#0 + // ... + // %reg16385 = DEC64_32r %reg16437, %EFLAGS + // ... + // JE_4 , %EFLAGS + // Successors according to CFG: BB#37 BB#2 + // + // BB#2: derived from LLVM BB %bb.nph + // Predecessors according to CFG: BB#0 BB#1 + // %reg16386 = PHI %reg16434, , %reg16385, + // + // Machine sink should break the critical edge first. + AllPHIUse = true; for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E; ++I) { - // Determine the block of the use. MachineInstr *UseInst = &*I; MachineBasicBlock *UseBlock = UseInst->getParent(); + if (!(UseBlock == MBB && UseInst->isPHI() && + UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { + AllPHIUse = false; + break; + } + } + if (AllPHIUse) + return true; - bool isPHI = UseInst->isPHI(); - if (isPHI) - PHIUses.insert(UseInst); - - if (isPHI) { - if (SplitEdges && UseBlock == MBB) - // PHI is in the successor BB. e.g. - // BB#1: derived from LLVM BB %bb4.preheader - // Predecessors according to CFG: BB#0 - // ... - // %reg16385 = DEC64_32r %reg16437, %EFLAGS - // ... - // JE_4 , %EFLAGS - // Successors according to CFG: BB#37 BB#2 - // - // BB#2: derived from LLVM BB %bb.nph - // Predecessors according to CFG: BB#0 BB#1 - // %reg16386 = PHI %reg16434, , %reg16385, - // - // Machine sink should break the critical edge first. - continue; + for (MachineRegisterInfo::use_nodbg_iterator + I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); + I != E; ++I) { + // Determine the block of the use. + MachineInstr *UseInst = &*I; + MachineBasicBlock *UseBlock = UseInst->getParent(); + if (UseInst->isPHI()) { // PHI nodes use the operand in the predecessor block, not the block with // the PHI. UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); @@ -293,7 +304,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, - bool HasNonePHIUse) { + bool AllPHIUse) { if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) return 0; @@ -345,7 +356,7 @@ MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, // // There is no need to do this check if all the uses are PHI nodes. PHI // sources are only defined on the specific predecessor edges. - if (HasNonePHIUse) { + if (!AllPHIUse) { for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), E = ToBB->pred_end(); PI != E; ++PI) { if (*PI == FromBB) @@ -381,9 +392,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // decide. MachineBasicBlock *SuccToSinkTo = 0; - SmallSet Defs; - SmallPtrSet PHIUses; - bool HasNonPHIUse = false; + bool AllPHIUse = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. @@ -418,7 +427,6 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { } else { // Virtual register uses are always safe to sink. if (MO.isUse()) continue; - Defs.insert(Reg); // If it's not safe to move defs of the register class, then abort. if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) @@ -443,8 +451,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If a previous operand picked a block to sink to, then this operand // must be sinkable to the same block. bool LocalUse = false; - if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, PHIUses, - HasNonPHIUse, LocalUse)) + if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, + AllPHIUse, LocalUse)) return false; continue; @@ -455,8 +463,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), E = ParentBlock->succ_end(); SI != E; ++SI) { bool LocalUse = false; - if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, PHIUses, - HasNonPHIUse, LocalUse)) { + if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, + AllPHIUse, LocalUse)) { SuccToSinkTo = *SI; break; } @@ -530,7 +538,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { DEBUG(dbgs() << "Sinking along critical edge.\n"); else { MachineBasicBlock *NewSucc = - SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, HasNonPHIUse); + SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, AllPHIUse); if (!NewSucc) { DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " "break critical edge\n"); @@ -546,43 +554,30 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { } } + if (AllPHIUse) { + if (NumSplit == SplitLimit) + return false; + MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, + SuccToSinkTo, AllPHIUse); + if (!NewSucc) { + DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " + "break critical edge\n"); + return false; + } + + DEBUG(dbgs() << " *** Splitting critical edge:" + " BB#" << ParentBlock->getNumber() + << " -- BB#" << NewSucc->getNumber() + << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); + SuccToSinkTo = NewSucc; + ++NumSplit; + } + // Determine where to insert into. Skip phi nodes. MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); - while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) { - MachineInstr *PHI = &*InsertPos; + while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) ++InsertPos; - if (SplitEdges && PHIUses.count(PHI)) { - if (NumSplit == SplitLimit) - return false; - - // A PHI use is in the destination successor so we can't sink the - // instruction here. Break the critical edge first! - for (unsigned i = 1, e = PHI->getNumOperands(); i != e; i += 2) { - unsigned SrcReg = PHI->getOperand(i).getReg(); - if (Defs.count(SrcReg)) { - MachineBasicBlock *SrcMBB = PHI->getOperand(i+1).getMBB(); - MachineBasicBlock *NewSucc = - SplitCriticalEdge(MI, SrcMBB, SuccToSinkTo, HasNonPHIUse); - if (!NewSucc) { - DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " - "break critical edge\n"); - return false; - } - - DEBUG(dbgs() << " *** Splitting critical edge:" - " BB#" << SrcMBB->getNumber() - << " -- BB#" << NewSucc->getNumber() - << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); - SuccToSinkTo = NewSucc; - InsertPos = NewSucc->begin(); - ++NumSplit; - break; - } - } - } - } - // Move the instruction. SuccToSinkTo->splice(InsertPos, ParentBlock, MI, ++MachineBasicBlock::iterator(MI)); -- cgit v1.2.3