X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=8a93a24287b60f676b5152898d583cd44253f8b7;hb=1de4aa904e9672abfc2e755d798c926d324e2d36;hp=4a9ea72b05a24ff91e7f81ea1a4c5a0a8b3edd95;hpb=6ee358b4eb92298357687cb460dde8e26678aca2;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 4a9ea72b05a..8a93a24287b 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -27,25 +27,39 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; -STATISTIC(NumSunk, "Number of machine instructions sunk"); +static cl::opt +SplitEdges("machine-sink-split", + cl::desc("Split critical edges during machine sinking"), + cl::init(true), cl::Hidden); + +STATISTIC(NumSunk, "Number of machine instructions sunk"); +STATISTIC(NumSplit, "Number of critical edges split"); +STATISTIC(NumCoalesces, "Number of copies coalesced"); namespace { class MachineSinking : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - MachineRegisterInfo *RegInfo; // Machine register information + MachineRegisterInfo *MRI; // Machine register information MachineDominatorTree *DT; // Machine dominator tree MachineLoopInfo *LI; AliasAnalysis *AA; BitVector AllocatableSet; // Which physregs are allocatable? + // Remember which edges have been considered for breaking. + SmallSet, 8> + CEBCandidates; + public: static char ID; // Pass identification - MachineSinking() : MachineFunctionPass(&ID) {} + MachineSinking() : MachineFunctionPass(ID) { + initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnMachineFunction(MachineFunction &MF); @@ -58,41 +72,132 @@ namespace { AU.addPreserved(); AU.addPreserved(); } + + virtual void releaseMemory() { + CEBCandidates.clear(); + } + private: bool ProcessBlock(MachineBasicBlock &MBB); + bool isWorthBreakingCriticalEdge(MachineInstr *MI, + MachineBasicBlock *From, + MachineBasicBlock *To); + MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, + MachineBasicBlock *From, + MachineBasicBlock *To, + bool BreakPHIEdge); bool SinkInstruction(MachineInstr *MI, bool &SawStore); - bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB) const; - bool LiveOutOfBasicBlock(const MachineInstr *MI, unsigned Reg) const; + bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, + MachineBasicBlock *DefMBB, + bool &BreakPHIEdge, bool &LocalUse) const; + bool PerformTrivialForwardCoalescing(MachineInstr *MI, + MachineBasicBlock *MBB); }; } // end anonymous namespace char MachineSinking::ID = 0; -static RegisterPass -X("machine-sink", "Machine code sinking"); +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(); } +bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, + MachineBasicBlock *MBB) { + if (!MI->isCopy()) + return false; + + unsigned SrcReg = MI->getOperand(1).getReg(); + unsigned DstReg = MI->getOperand(0).getReg(); + if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || + !TargetRegisterInfo::isVirtualRegister(DstReg) || + !MRI->hasOneNonDBGUse(SrcReg)) + return false; + + const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); + const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); + if (SRC != DRC) + return false; + + MachineInstr *DefMI = MRI->getVRegDef(SrcReg); + if (DefMI->isCopyLike()) + return false; + DEBUG(dbgs() << "Coalescing: " << *DefMI); + DEBUG(dbgs() << "*** to: " << *MI); + MRI->replaceRegWith(DstReg, SrcReg); + MI->eraseFromParent(); + ++NumCoalesces; + return true; +} + /// AllUsesDominatedByBlock - Return true if all uses of the specified register -/// occur in blocks dominated by the specified block. -bool MachineSinking::AllUsesDominatedByBlock(unsigned Reg, - MachineBasicBlock *MBB) const { +/// occur in blocks dominated by the specified block. If any use is in the +/// definition block, then return false since it is never legal to move def +/// after uses. +bool +MachineSinking::AllUsesDominatedByBlock(unsigned Reg, + MachineBasicBlock *MBB, + MachineBasicBlock *DefMBB, + 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 = RegInfo->use_nodbg_begin(Reg), E = RegInfo->use_nodbg_end(); + 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; + 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(); + } else if (UseBlock == DefMBB) { + LocalUse = true; + return false; } // Check that it dominates. @@ -109,7 +214,7 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { const TargetMachine &TM = MF.getTarget(); TII = TM.getInstrInfo(); TRI = TM.getRegisterInfo(); - RegInfo = &MF.getRegInfo(); + MRI = &MF.getRegInfo(); DT = &getAnalysis(); LI = &getAnalysis(); AA = &getAnalysis(); @@ -121,6 +226,7 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { bool MadeChange = false; // Process all basic blocks. + CEBCandidates.clear(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) MadeChange |= ProcessBlock(*I); @@ -159,6 +265,9 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { if (MI->isDebugValue()) continue; + if (PerformTrivialForwardCoalescing(MI, &MBB)) + continue; + if (SinkInstruction(MI, SawStore)) ++NumSunk, MadeChange = true; @@ -168,47 +277,116 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { return MadeChange; } -/// LiveOutOfBasicBlock - Determine if the physical register, defined and dead -/// in MI, is live on exit from the basic block. -bool MachineSinking::LiveOutOfBasicBlock(const MachineInstr *MI, - unsigned Reg) const { - assert(TargetRegisterInfo::isPhysicalRegister(Reg) && - "Only want to determine if a physical register is live out of a BB!"); - - const MachineBasicBlock *MBB = MI->getParent(); - SmallSet KilledRegs; - MachineBasicBlock::const_iterator I = MBB->end(); - MachineBasicBlock::const_iterator E = MBB->begin(); - assert(I != E && "How can there be an empty block at this point?!"); - - // Loop through the instructions bottom-up. If we see a kill of the preg - // first, then it's not live out of the BB. If we see a use or def first, then - // we assume that it is live out of the BB. - do { - const MachineInstr &CurMI = *--I; +bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, + MachineBasicBlock *From, + MachineBasicBlock *To) { + // FIXME: Need much better heuristics. - for (unsigned i = 0, e = CurMI.getNumOperands(); i != e; ++i) { - const MachineOperand &MO = CurMI.getOperand(i); - if (!MO.isReg()) continue; // Ignore non-register operands. + // If the pass has already considered breaking this edge (during this pass + // through the function), then let's go ahead and break it. This means + // sinking multiple "cheap" instructions into the same block. + if (!CEBCandidates.insert(std::make_pair(From, To))) + return true; - unsigned MOReg = MO.getReg(); - if (MOReg == 0) continue; + if (!MI->isCopy() && !MI->getDesc().isAsCheapAsAMove()) + return true; - if (MOReg == Reg) { - if (MO.isKill()) - return false; - if (MO.isUse() || MO.isDef()) - return true; - } - } - } while (I != E); + // MI is cheap, we probably don't want to break the critical edge for it. + // However, if this would allow some definitions of its source operands + // to be sunk then it's probably worth it. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + if (MRI->hasOneNonDBGUse(Reg)) + return true; + } return false; } +MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, + MachineBasicBlock *FromBB, + MachineBasicBlock *ToBB, + bool BreakPHIEdge) { + if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) + return 0; + + // Avoid breaking back edge. From == To means backedge for single BB loop. + if (!SplitEdges || FromBB == ToBB) + return 0; + + // Check for backedges of more "complex" loops. + if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && + LI->isLoopHeader(ToBB)) + return 0; + + // It's not always legal to break critical edges and sink the computation + // to the edge. + // + // BB#1: + // v1024 + // Beq BB#3 + // + // BB#2: + // ... no uses of v1024 + // + // BB#3: + // ... + // = v1024 + // + // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: + // + // BB#1: + // ... + // Bne BB#2 + // BB#4: + // v1024 = + // B BB#3 + // BB#2: + // ... no uses of v1024 + // + // BB#3: + // ... + // = v1024 + // + // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 + // flow. We need to ensure the new basic block where the computation is + // sunk to dominates all the uses. + // It's only legal to break critical edge and sink the computation to the + // new block if all the predecessors of "To", except for "From", are + // not dominated by "From". Given SSA property, this means these + // predecessors are dominated by "To". + // + // 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 (!BreakPHIEdge) { + for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), + E = ToBB->pred_end(); PI != E; ++PI) { + if (*PI == FromBB) + continue; + if (!DT->dominates(ToBB, *PI)) + return 0; + } + } + + return FromBB->SplitCriticalEdge(ToBB, this); +} + +static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { + return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); +} + /// 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; @@ -228,8 +406,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. MachineBasicBlock *SuccToSinkTo = 0; - SmallVector PhysRegs; + 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. @@ -242,7 +420,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If the physreg has no defs anywhere, it's just an ambient register // and we can freely move its uses. Alternatively, if it's allocatable, // it could get allocated to something with a def during allocation. - if (!RegInfo->def_empty(Reg)) + if (!MRI->def_empty(Reg)) return false; if (AllocatableSet.test(Reg)) @@ -251,25 +429,22 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // Check for a def among the register's aliases too. for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { unsigned AliasReg = *Alias; - if (!RegInfo->def_empty(AliasReg)) + if (!MRI->def_empty(AliasReg)) return false; if (AllocatableSet.test(AliasReg)) return false; } - } else { - if (!MO.isDead()) - // A def that isn't dead. We can't move it. - return false; - else - PhysRegs.push_back(Reg); + } else if (!MO.isDead()) { + // A def that isn't dead. We can't move it. + return false; } } else { // Virtual register uses are always safe to sink. if (MO.isUse()) continue; // If it's not safe to move defs of the register class, then abort. - if (!TII->isSafeToMoveRegClassDefs(RegInfo->getRegClass(Reg))) + if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) return false; // FIXME: This picks a successor to sink into based on having one @@ -290,7 +465,9 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { if (SuccToSinkTo) { // If a previous operand picked a block to sink to, then this operand // must be sinkable to the same block. - if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo)) + bool LocalUse = false; + if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, + BreakPHIEdge, LocalUse)) return false; continue; @@ -300,10 +477,15 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // we should sink to. for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), E = ParentBlock->succ_end(); SI != E; ++SI) { - if (AllUsesDominatedByBlock(Reg, *SI)) { + bool LocalUse = false; + if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, + BreakPHIEdge, LocalUse)) { SuccToSinkTo = *SI; break; } + if (LocalUse) + // Def is used locally, it's never safe to move this def. + return false; } // If we couldn't find a block to sink to, ignore this instruction. @@ -329,41 +511,83 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If the instruction to move defines a dead physical register which is live // when leaving the basic block, don't move it because it could turn into a // "zombie" define of that preg. E.g., EFLAGS. () - for (SmallVectorImpl::const_iterator - I = PhysRegs.begin(), E = PhysRegs.end(); I != E; ++I) - if (LiveOutOfBasicBlock(MI, *I)) + for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { + const MachineOperand &MO = MI->getOperand(I); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; + if (SuccToSinkTo->isLiveIn(Reg)) return false; + } DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); // If the block has multiple predecessors, this would introduce computation on // a path that it doesn't already exist. We could split the critical edge, // but for now we just punt. - // FIXME: Split critical edges if not backedges. if (SuccToSinkTo->pred_size() > 1) { // We cannot sink a load across a critical edge - there may be stores in // other code paths. + bool TryBreak = false; bool store = true; if (!MI->isSafeToMove(TII, AA, store)) { - DEBUG(dbgs() << " *** PUNTING: Wont sink load along critical edge.\n"); - return false; + DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); + TryBreak = true; } // We don't want to sink across a critical edge if we don't dominate the // successor. We could be introducing calculations to new code paths. - if (!DT->dominates(ParentBlock, SuccToSinkTo)) { - DEBUG(dbgs() << " *** PUNTING: Critical edge found\n"); - return false; + if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { + DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); + TryBreak = true; } // Don't sink instructions into a loop. - if (LI->isLoopHeader(SuccToSinkTo)) { - DEBUG(dbgs() << " *** PUNTING: Loop header found\n"); - return false; + if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { + DEBUG(dbgs() << " *** NOTE: Loop header found\n"); + TryBreak = true; } // Otherwise we are OK with sinking along a critical edge. - DEBUG(dbgs() << "Sinking along critical edge.\n"); + if (!TryBreak) + DEBUG(dbgs() << "Sinking along critical edge.\n"); + else { + MachineBasicBlock *NewSucc = + SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); + if (!NewSucc) { + DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " + "break critical edge\n"); + return false; + } else { + DEBUG(dbgs() << " *** Splitting critical edge:" + " BB#" << ParentBlock->getNumber() + << " -- BB#" << NewSucc->getNumber() + << " -- 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.