X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FMachineSink.cpp;h=edf8fc0645bf6105d450b617ba9719ff941cda20;hp=dacdbddfa26aac059a7896c8b30e2a32f2271ef3;hb=d43e6df10b85ee4a4dfd8dc164eff1177d4eb8d2;hpb=a0ec3f9b7b826b9b40b80199923b664bad808cce diff --git a/lib/CodeGen/MachineSink.cpp b/lib/CodeGen/MachineSink.cpp index dacdbddfa26..edf8fc0645b 100644 --- a/lib/CodeGen/MachineSink.cpp +++ b/lib/CodeGen/MachineSink.cpp @@ -16,13 +16,14 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "machine-sink" #include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/SetVector.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/MachinePostDominators.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -30,8 +31,11 @@ #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "machine-sink" + static cl::opt SplitEdges("machine-sink-split", cl::desc("Split critical edges during machine sinking"), @@ -45,14 +49,19 @@ namespace { class MachineSinking : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - MachineRegisterInfo *MRI; // Machine register information - MachineDominatorTree *DT; // Machine dominator tree + MachineRegisterInfo *MRI; // Machine register information + MachineDominatorTree *DT; // Machine dominator tree + MachinePostDominatorTree *PDT; // Machine post dominator tree MachineLoopInfo *LI; AliasAnalysis *AA; // Remember which edges have been considered for breaking. SmallSet, 8> CEBCandidates; + // Remember which edges we are about to split. + // This is different from CEBCandidates since those edges + // will be split. + SetVector > ToSplit; public: static char ID; // Pass identification @@ -60,19 +69,21 @@ namespace { 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(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); } - virtual void releaseMemory() { + void releaseMemory() override { CEBCandidates.clear(); } @@ -81,10 +92,22 @@ namespace { bool isWorthBreakingCriticalEdge(MachineInstr *MI, MachineBasicBlock *From, MachineBasicBlock *To); - MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, - MachineBasicBlock *From, - MachineBasicBlock *To, - bool BreakPHIEdge); + /// \brief Postpone the splitting of the given critical + /// edge (\p From, \p To). + /// + /// We do not split the edges on the fly. Indeed, this invalidates + /// the dominance information and thus triggers a lot of updates + /// of that information underneath. + /// Instead, we postpone all the splits after each iteration of + /// the main loop. That way, the information is at least valid + /// for the lifetime of an iteration. + /// + /// \return True if the edge is marked as toSplit, false otherwise. + /// False can be retruned if, for instance, this is not profitable. + bool PostponeSplitCriticalEdge(MachineInstr *MI, + MachineBasicBlock *From, + MachineBasicBlock *To, + bool BreakPHIEdge); bool SinkInstruction(MachineInstr *MI, bool &SawStore); bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, MachineBasicBlock *DefMBB, @@ -98,16 +121,6 @@ namespace { bool PerformTrivialForwardCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); }; - - // SuccessorSorter - Sort Successors according to their loop depth. - struct SuccessorSorter { - SuccessorSorter(MachineLoopInfo *LoopInfo) : LI(LoopInfo) {} - bool operator()(const MachineBasicBlock *LHS, - const MachineBasicBlock *RHS) const { - return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); - } - MachineLoopInfo *LI; - }; } // end anonymous namespace char MachineSinking::ID = 0; @@ -181,13 +194,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; } @@ -195,16 +207,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; @@ -219,13 +230,17 @@ 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(); - TII = TM.getInstrInfo(); - TRI = TM.getRegisterInfo(); + TII = TM.getSubtargetImpl()->getInstrInfo(); + TRI = TM.getSubtargetImpl()->getRegisterInfo(); MRI = &MF.getRegInfo(); DT = &getAnalysis(); + PDT = &getAnalysis(); LI = &getAnalysis(); AA = &getAnalysis(); @@ -236,10 +251,24 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { // Process all basic blocks. CEBCandidates.clear(); + ToSplit.clear(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) MadeChange |= ProcessBlock(*I); + // If we have anything we marked as toSplit, split it now. + for (auto &Pair : ToSplit) { + auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this); + if (NewSucc != nullptr) { + DEBUG(dbgs() << " *** Splitting critical edge:" + " BB#" << Pair.first->getNumber() + << " -- BB#" << NewSucc->getNumber() + << " -- BB#" << Pair.second->getNumber() << '\n'); + MadeChange = true; + ++NumSplit; + } else + DEBUG(dbgs() << " *** Not legal to break critical edge\n"); + } // If this iteration over the code changed anything, keep iterating. if (!MadeChange) break; EverMadeChange = true; @@ -300,7 +329,7 @@ bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, if (!CEBCandidates.insert(std::make_pair(From, To))) return true; - if (!MI->isCopy() && !MI->isAsCheapAsAMove()) + if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI)) return true; // MI is cheap, we probably don't want to break the critical edge for it. @@ -308,32 +337,49 @@ 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; + + // We don't move live definitions of physical registers, + // so sinking their uses won't enable any opportunities. + if (TargetRegisterInfo::isPhysicalRegister(Reg)) continue; - if (MRI->hasOneNonDBGUse(Reg)) - return true; + + // 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; } -MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, - MachineBasicBlock *FromBB, - MachineBasicBlock *ToBB, - bool BreakPHIEdge) { +bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr *MI, + MachineBasicBlock *FromBB, + MachineBasicBlock *ToBB, + bool BreakPHIEdge) { if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) - return 0; + return false; // Avoid breaking back edge. From == To means backedge for single BB loop. if (!SplitEdges || FromBB == ToBB) - return 0; + return false; // Check for backedges of more "complex" loops. if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && LI->isLoopHeader(ToBB)) - return 0; + return false; // It's not always legal to break critical edges and sink the computation // to the edge. @@ -380,11 +426,13 @@ MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, if (*PI == FromBB) continue; if (!DT->dominates(ToBB, *PI)) - return 0; + return false; } } - return FromBB->SplitCriticalEdge(ToBB, this); + ToSplit.insert(std::make_pair(FromBB, ToBB)); + + return true; } static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { @@ -410,23 +458,6 @@ static void collectDebugValues(MachineInstr *MI, } } -/// 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; - - return true; -} - /// isProfitableToSinkTo - Return true if it is profitable to sink MI. bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, MachineBasicBlock *MBB, @@ -438,17 +469,14 @@ bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, return false; // It is profitable if SuccToSinkTo does not post dominate current block. - if (!isPostDominatedBy(MBB, SuccToSinkTo)) - return true; + if (!PDT->dominates(SuccToSinkTo, MBB)) + return true; // Check if only use in post dominated block is PHI instruction. bool NonPHIUse = false; - for (MachineRegisterInfo::use_nodbg_iterator - I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); - I != E; ++I) { - MachineInstr *UseInst = &*I; - MachineBasicBlock *UseBlock = UseInst->getParent(); - if (UseBlock == SuccToSinkTo && !UseInst->isPHI()) + for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { + MachineBasicBlock *UseBlock = UseInst.getParent(); + if (UseBlock == SuccToSinkTo && !UseInst.isPHI()) NonPHIUse = true; } if (!NonPHIUse) @@ -479,7 +507,7 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // SuccToSinkTo - This is the successor to sink this instruction to, once we // decide. - MachineBasicBlock *SuccToSinkTo = 0; + 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. @@ -493,10 +521,10 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // 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->isConstantPhysReg(Reg, *MBB->getParent())) - return NULL; + return nullptr; } else if (!MO.isDead()) { // A def that isn't dead. We can't move it. - return NULL; + return nullptr; } } else { // Virtual register uses are always safe to sink. @@ -504,7 +532,7 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // If it's not safe to move defs of the register class, then abort. if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) - return NULL; + 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 @@ -527,7 +555,7 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, bool LocalUse = false; if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, BreakPHIEdge, LocalUse)) - return NULL; + return nullptr; continue; } @@ -536,7 +564,12 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, // we should sink to. // We give successors with smaller loop depth higher priority. SmallVector Succs(MBB->succ_begin(), MBB->succ_end()); - std::stable_sort(Succs.begin(), Succs.end(), SuccessorSorter(LI)); + // 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; @@ -548,26 +581,26 @@ MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, } if (LocalUse) // Def is used locally, it's never safe to move this def. - return NULL; + return nullptr; } // If we couldn't find a block to sink to, ignore this instruction. - if (SuccToSinkTo == 0) - return NULL; - else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) - return NULL; + if (!SuccToSinkTo) + return nullptr; + if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) + return nullptr; } } // It is not possible to sink an instruction into its own block. This can // happen with loops. if (MBB == SuccToSinkTo) - return NULL; + return nullptr; // It's not safe to sink instructions to EH landing pad. Control flow into // landing pad is implicitly defined. if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) - return NULL; + return nullptr; return SuccToSinkTo; } @@ -597,7 +630,7 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); // If there are no outputs, it must have side-effects. - if (SuccToSinkTo == 0) + if (!SuccToSinkTo) return false; @@ -615,9 +648,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. @@ -645,21 +677,16 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { if (!TryBreak) DEBUG(dbgs() << "Sinking along critical edge.\n"); else { - MachineBasicBlock *NewSucc = - SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); - if (!NewSucc) { + // Mark this edge as to be split. + // If the edge can actually be split, the next iteration of the main loop + // will sink MI in the newly created block. + bool Status = + PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); + if (!Status) 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; - } + "break critical edge\n"); + // The instruction will not be sunk this time. + return false; } } @@ -667,20 +694,13 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { // 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) { + bool Status = PostponeSplitCriticalEdge(MI, ParentBlock, + SuccToSinkTo, BreakPHIEdge); + if (!Status) 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; + // The instruction will not be sunk this time. + return false; } // Determine where to insert into. Skip phi nodes. @@ -704,9 +724,19 @@ bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { ++MachineBasicBlock::iterator(DbgMI)); } - // Conservatively, clear any kill flags, since it's possible that they are no - // longer correct. - MI->clearKillInfo(); + // When sinking the instruction the live time of its operands can be extended + // bejond their original last use (marked with a kill flag). Conservatively + // clear the kill flag in all instructions that use the same operand + // registers. + for (auto &MO : MI->uses()) + if (MO.isReg() && MO.isUse()) { + // Preserve the kill flag for this instruction. + bool IsKill = MO.isKill(); + // Clear the kill flag in all instruction that use this operand. + MRI->clearKillFlags(MO.getReg()); + // Restore the kill flag for only this instruction. + MO.setIsKill(IsKill); + } return true; }