X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FInlineSpiller.cpp;h=f0d407fccf9e180641d92d2ad58cb3836cc617e8;hb=9e065f52fcf0c77f7375f7f354069684de56e6d4;hp=64211c8d31b76237823697ea15748a709a1fc31c;hpb=76604af7748badc535017534f5f4c627516fdd7a;p=oota-llvm.git diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp index 64211c8d31b..f0d407fccf9 100644 --- a/lib/CodeGen/InlineSpiller.cpp +++ b/lib/CodeGen/InlineSpiller.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "Spiller.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" @@ -22,6 +21,7 @@ #include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" @@ -34,10 +34,11 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(NumSpilledRanges, "Number of spilled live ranges"); STATISTIC(NumSnippets, "Number of spilled snippets"); STATISTIC(NumSpills, "Number of spills inserted"); @@ -120,7 +121,7 @@ public: SibValueInfo(unsigned Reg, VNInfo *VNI) : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false), - SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {} + SpillReg(Reg), SpillVNI(VNI), SpillMBB(nullptr), DefMI(nullptr) {} // Returns true when a def has been found. bool hasDef() const { return DefByOrigPHI || DefMI; } @@ -137,21 +138,16 @@ private: ~InlineSpiller() {} public: - InlineSpiller(MachineFunctionPass &pass, - MachineFunction &mf, - VirtRegMap &vrm) - : MF(mf), - LIS(pass.getAnalysis()), - LSS(pass.getAnalysis()), - AA(&pass.getAnalysis()), - MDT(pass.getAnalysis()), - Loops(pass.getAnalysis()), - VRM(vrm), - MFI(*mf.getFrameInfo()), - MRI(mf.getRegInfo()), - TII(*mf.getTarget().getInstrInfo()), - TRI(*mf.getTarget().getRegisterInfo()), - MBFI(pass.getAnalysis()) {} + InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) + : MF(mf), LIS(pass.getAnalysis()), + LSS(pass.getAnalysis()), + AA(&pass.getAnalysis()), + MDT(pass.getAnalysis()), + Loops(pass.getAnalysis()), VRM(vrm), + MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()), + TII(*mf.getSubtarget().getInstrInfo()), + TRI(*mf.getSubtarget().getRegisterInfo()), + MBFI(pass.getAnalysis()) {} void spill(LiveRangeEdit &) override; @@ -166,7 +162,7 @@ private: bool isSibling(unsigned Reg); MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*); - void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = 0); + void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = nullptr); void analyzeSiblingValues(); bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI); @@ -178,7 +174,7 @@ private: bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); bool foldMemoryOperand(ArrayRef >, - MachineInstr *LoadMI = 0); + MachineInstr *LoadMI = nullptr); void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI); void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI); @@ -188,11 +184,16 @@ private: } namespace llvm { + +Spiller::~Spiller() { } +void Spiller::anchor() { } + Spiller *createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm) { return new InlineSpiller(pass, mf, vrm); } + } //===----------------------------------------------------------------------===// @@ -235,7 +236,7 @@ bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) { if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI)) return false; - MachineInstr *UseMI = 0; + MachineInstr *UseMI = nullptr; // Check that all uses satisfy our criteria. for (MachineRegisterInfo::reg_instr_nodbg_iterator @@ -366,7 +367,7 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVIIter, do { SVI = WorkList.pop_back_val(); TinyPtrVector *Deps = VNI ? &FirstDeps : &SVI->second.Deps; - VNI = 0; + VNI = nullptr; SibValueInfo &SV = SVI->second; if (!SV.SpillMBB) @@ -440,7 +441,20 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVIIter, // Also hoist spills to blocks with smaller loop depth, but make sure // that the new value dominates. Non-phi dependents are always // dominated, phis need checking. + + const BranchProbability MarginProb(4, 5); // 80% + // Hoist a spill to outer loop if there are multiple dependents (it + // can be beneficial if more than one dependents are hoisted) or + // if DepSV (the hoisting source) is hotter than SV (the hoisting + // destination) (we add a 80% margin to bias a little towards + // loop depth). + bool HoistCondition = + (MBFI.getBlockFreq(DepSV.SpillMBB) >= + (MBFI.getBlockFreq(SV.SpillMBB) * MarginProb)) || + Deps->size() > 1; + if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) && + HoistCondition && (!DepSVI->first->isPHIDef() || MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) { Changed = true; @@ -494,6 +508,7 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, SmallVector, 8> WorkList; WorkList.push_back(std::make_pair(UseReg, UseVNI)); + LiveInterval &OrigLI = LIS.getInterval(Original); do { unsigned Reg; VNInfo *VNI; @@ -507,8 +522,11 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, // Trace through PHI-defs created by live range splitting. if (VNI->isPHIDef()) { - // Stop at original PHIs. We don't know the value at the predecessors. - if (VNI->def == OrigVNI->def) { + // Stop at original PHIs. We don't know the value at the + // predecessors. Look up the VNInfo for the current definition + // in OrigLI, to properly determine whether or not this phi was + // added by splitting. + if (VNI->def == OrigLI.getVNInfoAt(VNI->def)->def) { DEBUG(dbgs() << "orig phi value\n"); SVI->second.DefByOrigPHI = true; SVI->second.AllDefsAreReloads = false; @@ -528,7 +546,6 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, // Separate all values dominated by OrigVNI into PHIs and non-PHIs. SmallVector PHIs, NonPHIs; LiveInterval &LI = LIS.getInterval(Reg); - LiveInterval &OrigLI = LIS.getInterval(Original); for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end(); VI != VE; ++VI) { @@ -559,8 +576,8 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, std::tie(SVI, Inserted) = SibValues.insert(std::make_pair(NonPHI, SibValueInfo(Reg, NonPHI))); // Add all the PHIs as dependents of NonPHI. - for (unsigned pi = 0, pe = PHIs.size(); pi != pe; ++pi) - SVI->second.Deps.push_back(PHIs[pi]); + SVI->second.Deps.insert(SVI->second.Deps.end(), PHIs.begin(), + PHIs.end()); // This is the first time we see NonPHI, add it to the worklist. if (Inserted) WorkList.push_back(std::make_pair(Reg, NonPHI)); @@ -645,7 +662,7 @@ void InlineSpiller::analyzeSiblingValues() { VNInfo *VNI = *VI; if (VNI->isUnused()) continue; - MachineInstr *DefMI = 0; + MachineInstr *DefMI = nullptr; if (!VNI->isPHIDef()) { DefMI = LIS.getInstructionFromIndex(VNI->def); assert(DefMI && "No defining instruction"); @@ -809,7 +826,7 @@ void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { WorkList.push_back(std::make_pair(LI, VNI)); do { std::tie(LI, VNI) = WorkList.pop_back_val(); - if (!UsedValues.insert(VNI)) + if (!UsedValues.insert(VNI).second) continue; if (VNI->isPHIDef()) { @@ -838,6 +855,15 @@ void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineBasicBlock::iterator MI) { + + // Analyze instruction + SmallVector, 8> Ops; + MIBundleOperands::VirtRegInfo RI = + MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); + + if (!RI.Reads) + return false; + SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true); VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex()); @@ -868,9 +894,6 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, // If the instruction also writes VirtReg.reg, it had better not require the // same register for uses and defs. - SmallVector, 8> Ops; - MIBundleOperands::VirtRegInfo RI = - MIBundleOperands(MI).analyzeVirtReg(VirtReg.reg, &Ops); if (RI.Tied) { markValueUsed(&VirtReg, ParentVNI); DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); @@ -924,10 +947,15 @@ void InlineSpiller::reMaterializeAll() { for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { unsigned Reg = RegsToSpill[i]; LiveInterval &LI = LIS.getInterval(Reg); - for (MachineRegisterInfo::use_bundle_nodbg_iterator - RI = MRI.use_bundle_nodbg_begin(Reg), E = MRI.use_bundle_nodbg_end(); - RI != E; ) { - MachineInstr *MI = &*(RI++); + for (MachineRegisterInfo::reg_bundle_iterator + RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end(); + RegI != E; ) { + MachineInstr *MI = &*(RegI++); + + // Debug values are not allowed to affect codegen. + if (MI->isDebugValue()) + continue; + anyRemat |= reMaterializeFor(LI, MI); } } @@ -1063,7 +1091,8 @@ foldMemoryOperand(ArrayRef > Ops, bool WasCopy = MI->isCopy(); unsigned ImpReg = 0; - bool SpillSubRegs = (MI->getOpcode() == TargetOpcode::PATCHPOINT || + bool SpillSubRegs = (MI->getOpcode() == TargetOpcode::STATEPOINT || + MI->getOpcode() == TargetOpcode::PATCHPOINT || MI->getOpcode() == TargetOpcode::STACKMAP); // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied @@ -1113,13 +1142,8 @@ foldMemoryOperand(ArrayRef > Ops, continue; // FoldMI does not define this physreg. Remove the LI segment. assert(MO->isDead() && "Cannot fold physreg def"); - for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units) { - if (LiveRange *LR = LIS.getCachedRegUnit(*Units)) { - SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); - if (VNInfo *VNI = LR->getVNInfoAt(Idx)) - LR->removeValNo(VNI); - } - } + SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); + LIS.removePhysRegDefAt(Reg, Idx); } LIS.ReplaceMachineInstrInMaps(MI, FoldMI); @@ -1203,12 +1227,16 @@ void InlineSpiller::spillAroundUses(unsigned Reg) { // Modify DBG_VALUE now that the value is in a spill slot. bool IsIndirect = MI->isIndirectDebugValue(); uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; - const MDNode *MDPtr = MI->getOperand(2).getMetadata(); + const MDNode *Var = MI->getDebugVariable(); + const MDNode *Expr = MI->getDebugExpression(); DebugLoc DL = MI->getDebugLoc(); DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); MachineBasicBlock *MBB = MI->getParent(); BuildMI(*MBB, MBB->erase(MI), DL, TII.get(TargetOpcode::DBG_VALUE)) - .addFrameIndex(StackSlot).addImm(Offset).addMetadata(MDPtr); + .addFrameIndex(StackSlot) + .addImm(Offset) + .addMetadata(Var) + .addMetadata(Expr); continue; } @@ -1345,10 +1373,10 @@ void InlineSpiller::spill(LiveRangeEdit &edit) { // Share a stack slot among all descendants of Original. Original = VRM.getOriginal(edit.getReg()); StackSlot = VRM.getStackSlot(Original); - StackInt = 0; + StackInt = nullptr; DEBUG(dbgs() << "Inline spilling " - << MRI.getRegClass(edit.getReg())->getName() + << TRI.getRegClassName(MRI.getRegClass(edit.getReg())) << ':' << edit.getParent() << "\nFrom original " << PrintReg(Original) << '\n'); assert(edit.getParent().isSpillable() &&