X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=29cfb49953b9a227573daa61b6c172d5acfc202b;hb=70303688bc489a316cb0892499ac4024088fa58a;hp=330e675a2e6377bdb2daf7eda3080dc736dea9b7;hpb=6edb0eac87a6e46b89de3ad5d8e39c41969e2a54;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 330e675a2e6..29cfb49953b 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -35,10 +35,7 @@ using namespace llvm; static cl::opt SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), - cl::init(false), cl::Hidden); -static cl::opt -SplitLimit("split-limit", - cl::init(~0u), cl::Hidden); + cl::init(true), cl::Hidden); STATISTIC(NumSunk, "Number of machine instructions sunk"); STATISTIC(NumSplit, "Number of critical edges split"); @@ -60,7 +57,9 @@ namespace { public: static char ID; // Pass identification - MachineSinking() : MachineFunctionPass(ID) {} + MachineSinking() : MachineFunctionPass(ID) { + initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnMachineFunction(MachineFunction &MF); @@ -86,20 +85,24 @@ namespace { MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *From, MachineBasicBlock *To, - bool HasNonePHIUse); + bool BreakPHIEdge); bool SinkInstruction(MachineInstr *MI, bool &SawStore); bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - SmallPtrSet &PHIUses, - bool &NonPHIUse, bool &LocalUse) const; + bool &BreakPHIEdge, bool &LocalUse) const; bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); }; } // end anonymous namespace char MachineSinking::ID = 0; -INITIALIZE_PASS(MachineSinking, "machine-sink", - "Machine code sinking", false, false); +INITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", + "Machine code sinking", false, false) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(MachineSinking, "machine-sink", + "Machine code sinking", false, false) FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); } @@ -139,42 +142,56 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - SmallPtrSet &PHIUses, - bool &NonPHIUse, bool &LocalUse) const { + bool &BreakPHIEdge, + 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. + + // BreakPHIEdge is true if all the uses are in the successor MBB being sunken + // into and they are all PHI nodes. In this case, machine-sink must break + // the critical edge first. 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, + BreakPHIEdge = 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)) { + BreakPHIEdge = false; + break; + } + } + if (BreakPHIEdge) + 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(); @@ -248,8 +265,11 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { if (MI->isDebugValue()) continue; - if (PerformTrivialForwardCoalescing(MI, &MBB)) + bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); + if (Joined) { + MadeChange = true; continue; + } if (SinkInstruction(MI, SawStore)) ++NumSunk, MadeChange = true; @@ -271,7 +291,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, if (!CEBCandidates.insert(std::make_pair(From, To))) return true; - if (!(MI->isCopyLike() || MI->getDesc().isAsCheapAsAMove())) + if (!MI->isCopy() && !MI->getDesc().isAsCheapAsAMove()) return true; // MI is cheap, we probably don't want to break the critical edge for it. @@ -293,12 +313,12 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, - bool HasNonePHIUse) { + bool BreakPHIEdge) { if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) return 0; // Avoid breaking back edge. From == To means backedge for single BB loop. - if (!SplitEdges || NumSplit == SplitLimit || FromBB == ToBB) + if (!SplitEdges || FromBB == ToBB) return 0; // Check for backedges of more "complex" loops. @@ -345,7 +365,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 (!BreakPHIEdge) { for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), E = ToBB->pred_end(); PI != E; ++PI) { if (*PI == FromBB) @@ -358,9 +378,37 @@ MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, return FromBB->SplitCriticalEdge(ToBB, this); } +static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { + return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); +} + +/// collectDebgValues - Scan instructions following MI and collect any +/// matching DBG_VALUEs. +static void collectDebugValues(MachineInstr *MI, + SmallVector & DbgValues) { + DbgValues.clear(); + if (!MI->getOperand(0).isReg()) + return; + + MachineBasicBlock::iterator DI = MI; ++DI; + for (MachineBasicBlock::iterator DE = MI->getParent()->end(); + DI != DE; ++DI) { + if (!DI->isDebugValue()) + return; + if (DI->getOperand(0).isReg() && + DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) + DbgValues.push_back(DI); + } +} + /// SinkInstruction - Determine whether it is safe to sink the specified machine /// instruction out of its current block into a successor. bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { + // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to + // be close to the source to make it easier to coalesce. + if (AvoidsSinking(MI, MRI)) + return false; + // Check if it's safe to move the instruction. if (!MI->isSafeToMove(TII, AA, SawStore)) return false; @@ -381,9 +429,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // decide. MachineBasicBlock *SuccToSinkTo = 0; - SmallSet Defs; - SmallPtrSet PHIUses; - bool HasNonPHIUse = false; + bool BreakPHIEdge = 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 +464,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 +488,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, + BreakPHIEdge, LocalUse)) return false; continue; @@ -455,8 +500,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, + BreakPHIEdge, LocalUse)) { SuccToSinkTo = *SI; break; } @@ -530,7 +575,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, BreakPHIEdge); if (!NewSucc) { DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " "break critical edge\n"); @@ -542,51 +587,52 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); SuccToSinkTo = NewSucc; ++NumSplit; + BreakPHIEdge = false; } } } + if (BreakPHIEdge) { + // BreakPHIEdge is true if all the uses are in the successor MBB being + // sunken into and they are all PHI nodes. In this case, machine-sink must + // break the critical edge first. + MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, + SuccToSinkTo, BreakPHIEdge); + 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; - } - } - } - } + // collect matching debug values. + SmallVector DbgValuesToSink; + collectDebugValues(MI, DbgValuesToSink); // Move the instruction. SuccToSinkTo->splice(InsertPos, ParentBlock, MI, ++MachineBasicBlock::iterator(MI)); + // Move debug values. + for (SmallVector::iterator DBI = DbgValuesToSink.begin(), + DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { + MachineInstr *DbgMI = *DBI; + SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, + ++MachineBasicBlock::iterator(DbgMI)); + } + // Conservatively, clear any kill flags, since it's possible that they are no // longer correct. MI->clearKillInfo();