X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=29cfb49953b9a227573daa61b6c172d5acfc202b;hb=23946fcaaefaf3c1a9d1ef86a3786f622c005f1a;hp=3d9f24e606712cc4be3e0cdd64beae2a1ffe4bdd;hpb=2399786b279b6db7077ac36020153714530365df;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 3d9f24e6067..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,19 +85,24 @@ namespace { MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *From, MachineBasicBlock *To, - bool AllPHIUse); + bool BreakPHIEdge); bool SinkInstruction(MachineInstr *MI, bool &SawStore); bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - bool &AllPHIUse, 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(); } @@ -138,7 +142,8 @@ bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, - bool &AllPHIUse, bool &LocalUse) const { + bool &BreakPHIEdge, + bool &LocalUse) const { assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); @@ -150,7 +155,10 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, // 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. + // 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 // ... @@ -162,9 +170,7 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, // 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; + BreakPHIEdge = true; for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); I != E; ++I) { @@ -172,11 +178,11 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *UseBlock = UseInst->getParent(); if (!(UseBlock == MBB && UseInst->isPHI() && UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { - AllPHIUse = false; + BreakPHIEdge = false; break; } } - if (AllPHIUse) + if (BreakPHIEdge) return true; for (MachineRegisterInfo::use_nodbg_iterator @@ -259,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; @@ -282,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. @@ -304,12 +313,12 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, - bool AllPHIUse) { + 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. @@ -356,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 (!AllPHIUse) { + if (!BreakPHIEdge) { for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), E = ToBB->pred_end(); PI != E; ++PI) { if (*PI == FromBB) @@ -369,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; @@ -392,7 +429,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // decide. MachineBasicBlock *SuccToSinkTo = 0; - bool AllPHIUse = 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. @@ -452,7 +489,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // must be sinkable to the same block. bool LocalUse = false; if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, - AllPHIUse, LocalUse)) + BreakPHIEdge, LocalUse)) return false; continue; @@ -464,7 +501,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { E = ParentBlock->succ_end(); SI != E; ++SI) { bool LocalUse = false; if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, - AllPHIUse, LocalUse)) { + BreakPHIEdge, LocalUse)) { SuccToSinkTo = *SI; break; } @@ -538,7 +575,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { DEBUG(dbgs() << "Sinking along critical edge.\n"); else { MachineBasicBlock *NewSucc = - SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, AllPHIUse); + SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); if (!NewSucc) { DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " "break critical edge\n"); @@ -550,15 +587,17 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); SuccToSinkTo = NewSucc; ++NumSplit; + BreakPHIEdge = false; } } } - if (AllPHIUse) { - if (NumSplit == SplitLimit) - return 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, AllPHIUse); + SuccToSinkTo, BreakPHIEdge); if (!NewSucc) { DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " "break critical edge\n"); @@ -578,10 +617,22 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) ++InsertPos; + // 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();