X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=f44e4d1eaabddbcfbe2e6600636e797b8b25f9b5;hb=d8e141c0c19fd55834b2a10ec4909effb39e0703;hp=5969c0b3455d257547cdb7b30ce34fe43679e5b3;hpb=44be1a8d661cfab0cc3d11b0dd158271b2d2ca04;p=oota-llvm.git diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index 5969c0b3455..f44e4d1eaab 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -16,23 +16,24 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "machine-sink" #include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineLoopInfo.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" using namespace llvm; -static cl::opt +#define DEBUG_TYPE "machine-sink" + +static cl::opt SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), cl::init(true), cl::Hidden); @@ -49,7 +50,6 @@ namespace { 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> @@ -57,11 +57,13 @@ namespace { public: static char ID; // Pass identification - MachineSinking() : MachineFunctionPass(ID) {} + MachineSinking() : MachineFunctionPass(ID) { + initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); + } - virtual bool runOnMachineFunction(MachineFunction &MF); + bool runOnMachineFunction(MachineFunction &MF) override; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); AU.addRequired(); @@ -71,7 +73,7 @@ namespace { AU.addPreserved(); } - virtual void releaseMemory() { + void releaseMemory() override { CEBCandidates.clear(); } @@ -88,16 +90,26 @@ namespace { bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, bool &BreakPHIEdge, bool &LocalUse) const; + MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, + bool &BreakPHIEdge); + bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, + MachineBasicBlock *MBB, + MachineBasicBlock *SuccToSinkTo); + bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); }; } // end anonymous namespace char MachineSinking::ID = 0; -INITIALIZE_PASS(MachineSinking, "machine-sink", - "Machine code sinking", false, false); - -FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); } +char &llvm::MachineSinkingID = MachineSinking::ID; +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) bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB) { @@ -140,14 +152,10 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Only makes sense for vregs"); + // Ignore debug uses because debug info doesn't affect the code. 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. @@ -164,13 +172,12 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, // 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) { - MachineInstr *UseInst = &*I; + for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { + MachineInstr *UseInst = MO.getParent(); + unsigned OpNo = &MO - &UseInst->getOperand(0); MachineBasicBlock *UseBlock = UseInst->getParent(); if (!(UseBlock == MBB && UseInst->isPHI() && - UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { + UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) { BreakPHIEdge = false; break; } @@ -178,16 +185,15 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, if (BreakPHIEdge) return true; - for (MachineRegisterInfo::use_nodbg_iterator - I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); - I != E; ++I) { + for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { // Determine the block of the use. - MachineInstr *UseInst = &*I; + MachineInstr *UseInst = MO.getParent(); + unsigned OpNo = &MO - &UseInst->getOperand(0); 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(); + UseBlock = UseInst->getOperand(OpNo+1).getMBB(); } else if (UseBlock == DefMBB) { LocalUse = true; return false; @@ -202,6 +208,9 @@ MachineSinking::AllUsesDominatedByBlock(unsigned Reg, } bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { + if (skipOptnoneFunction(*MF.getFunction())) + return false; + DEBUG(dbgs() << "******** Machine Sinking ********\n"); const TargetMachine &TM = MF.getTarget(); @@ -211,7 +220,6 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { DT = &getAnalysis(); LI = &getAnalysis(); AA = &getAnalysis(); - AllocatableSet = TRI->getAllocatableSet(MF); bool EverMadeChange = false; @@ -258,8 +266,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; @@ -281,7 +292,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->isAsCheapAsAMove()) return true; // MI is cheap, we probably don't want to break the critical edge for it. @@ -289,12 +300,29 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, // 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; + if (!MO.isReg() || !MO.isUse()) + continue; unsigned Reg = MO.getReg(); - if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) + if (Reg == 0) continue; - if (MRI->hasOneNonDBGUse(Reg)) - return true; + + // We don't move live definitions of physical registers, + // so sinking their uses won't enable any opportunities. + if (TargetRegisterInfo::isPhysicalRegister(Reg)) + continue; + + // If this instruction is the only user of a virtual register, + // check if breaking the edge will enable sinking + // both this instruction and the defining instruction. + if (MRI->hasOneNonDBGUse(Reg)) { + // If the definition resides in same MBB, + // claim it's likely we can sink these together. + // If definition resides elsewhere, we aren't + // blocking it from being sunk so don't break the edge. + MachineInstr *DefMI = MRI->getVRegDef(Reg); + if (DefMI->getParent() == MI->getParent()) + return true; + } } return false; @@ -305,16 +333,16 @@ MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, MachineBasicBlock *ToBB, bool BreakPHIEdge) { if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) - return 0; + return nullptr; // Avoid breaking back edge. From == To means backedge for single BB loop. if (!SplitEdges || FromBB == ToBB) - return 0; + return nullptr; // Check for backedges of more "complex" loops. if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && LI->isLoopHeader(ToBB)) - return 0; + return nullptr; // It's not always legal to break critical edges and sink the computation // to the edge. @@ -361,37 +389,103 @@ MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, if (*PI == FromBB) continue; if (!DT->dominates(ToBB, *PI)) - return 0; + return nullptr; } } return FromBB->SplitCriticalEdge(ToBB, this); } -/// 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) { - // Check if it's safe to move the instruction. - if (!MI->isSafeToMove(TII, AA, SawStore)) +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, + SmallVectorImpl &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); + } +} + +/// isPostDominatedBy - Return true if A is post dominated by B. +static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { + + // FIXME - Use real post dominator. + if (A->succ_size() != 2) + return false; + MachineBasicBlock::succ_iterator I = A->succ_begin(); + if (B == *I) + ++I; + MachineBasicBlock *OtherSuccBlock = *I; + if (OtherSuccBlock->succ_size() != 1 || + *(OtherSuccBlock->succ_begin()) != B) return false; - // FIXME: This should include support for sinking instructions within the - // block they are currently in to shorten the live ranges. We often get - // instructions sunk into the top of a large block, but it would be better to - // also sink them down before their first use in the block. This xform has to - // be careful not to *increase* register pressure though, e.g. sinking - // "x = y + z" down if it kills y and z would increase the live ranges of y - // and z and only shrink the live range of x. + return true; +} + +/// isProfitableToSinkTo - Return true if it is profitable to sink MI. +bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, + MachineBasicBlock *MBB, + MachineBasicBlock *SuccToSinkTo) { + assert (MI && "Invalid MachineInstr!"); + assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); + + if (MBB == SuccToSinkTo) + return false; + + // It is profitable if SuccToSinkTo does not post dominate current block. + if (!isPostDominatedBy(MBB, SuccToSinkTo)) + return true; + + // Check if only use in post dominated block is PHI instruction. + bool NonPHIUse = false; + for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { + MachineBasicBlock *UseBlock = UseInst.getParent(); + if (UseBlock == SuccToSinkTo && !UseInst.isPHI()) + NonPHIUse = true; + } + if (!NonPHIUse) + return true; + + // If SuccToSinkTo post dominates then also it may be profitable if MI + // can further profitably sinked into another block in next round. + bool BreakPHIEdge = false; + // FIXME - If finding successor is compile time expensive then catch results. + if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) + return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); + + // If SuccToSinkTo is final destination and it is a post dominator of current + // block then it is not profitable to sink MI into SuccToSinkTo block. + return false; +} + +/// FindSuccToSinkTo - Find a successor to sink this instruction to. +MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, + MachineBasicBlock *MBB, + bool &BreakPHIEdge) { + + assert (MI && "Invalid MachineInstr!"); + assert (MBB && "Invalid MachineBasicBlock!"); // Loop over all the operands of the specified instruction. If there is // anything we can't handle, bail out. - MachineBasicBlock *ParentBlock = MI->getParent(); // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. - MachineBasicBlock *SuccToSinkTo = 0; - - bool BreakPHIEdge = false; + MachineBasicBlock *SuccToSinkTo = nullptr; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { const MachineOperand &MO = MI->getOperand(i); if (!MO.isReg()) continue; // Ignore non-register operands. @@ -404,24 +498,11 @@ 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 (!MRI->def_empty(Reg)) - return false; - - if (AllocatableSet.test(Reg)) - return false; - - // Check for a def among the register's aliases too. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - if (!MRI->def_empty(AliasReg)) - return false; - - if (AllocatableSet.test(AliasReg)) - return false; - } + if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) + return nullptr; } else if (!MO.isDead()) { // A def that isn't dead. We can't move it. - return false; + return nullptr; } } else { // Virtual register uses are always safe to sink. @@ -429,7 +510,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // If it's not safe to move defs of the register class, then abort. if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) - return false; + return nullptr; // FIXME: This picks a successor to sink into based on having one // successor that dominates all the uses. However, there are cases where @@ -450,48 +531,87 @@ 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, + if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge, LocalUse)) - return false; + return nullptr; continue; } // Otherwise, we should look at all the successors and decide which one // we should sink to. - for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), - E = ParentBlock->succ_end(); SI != E; ++SI) { + // We give successors with smaller loop depth higher priority. + SmallVector Succs(MBB->succ_begin(), MBB->succ_end()); + // Sort Successors according to their loop depth. + std::stable_sort( + Succs.begin(), Succs.end(), + [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) { + return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); + }); + for (SmallVectorImpl::iterator SI = Succs.begin(), + E = Succs.end(); SI != E; ++SI) { + MachineBasicBlock *SuccBlock = *SI; bool LocalUse = false; - if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, + if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, BreakPHIEdge, LocalUse)) { - SuccToSinkTo = *SI; + SuccToSinkTo = SuccBlock; break; } if (LocalUse) // Def is used locally, it's never safe to move this def. - return false; + return nullptr; } // If we couldn't find a block to sink to, ignore this instruction. - if (SuccToSinkTo == 0) - return false; + if (!SuccToSinkTo) + return nullptr; + if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) + return nullptr; } } - // If there are no outputs, it must have side-effects. - if (SuccToSinkTo == 0) - return false; + // It is not possible to sink an instruction into its own block. This can + // happen with loops. + if (MBB == SuccToSinkTo) + return nullptr; // It's not safe to sink instructions to EH landing pad. Control flow into // landing pad is implicitly defined. - if (SuccToSinkTo->isLandingPad()) + if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) + return nullptr; + + return SuccToSinkTo; +} + +/// 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; - // It is not possible to sink an instruction into its own block. This can - // happen with loops. - if (MI->getParent() == SuccToSinkTo) + // Check if it's safe to move the instruction. + if (!MI->isSafeToMove(TII, AA, SawStore)) return false; + // FIXME: This should include support for sinking instructions within the + // block they are currently in to shorten the live ranges. We often get + // instructions sunk into the top of a large block, but it would be better to + // also sink them down before their first use in the block. This xform has to + // be careful not to *increase* register pressure though, e.g. sinking + // "x = y + z" down if it kills y and z would increase the live ranges of y + // and z and only shrink the live range of x. + + bool BreakPHIEdge = false; + MachineBasicBlock *ParentBlock = MI->getParent(); + MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); + + // If there are no outputs, it must have side-effects. + if (!SuccToSinkTo) + return false; + + // 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. () @@ -506,9 +626,8 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 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. + // If the block has multiple predecessors, this is a critical edge. + // Decide if we can sink along it or need to break the edge. if (SuccToSinkTo->pred_size() > 1) { // We cannot sink a load across a critical edge - there may be stores in // other code paths. @@ -579,10 +698,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 (SmallVectorImpl::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();