X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FInlineSpiller.cpp;h=59a92890f5a686d2945dfa522b6d081e71099131;hb=e56023a059e5fafa97f0df32c65cf31cfc33ba17;hp=d1e3f1afbfa0083dfe788c1ea43c0cd5ab512847;hpb=17afb0664861507c9bd968f1678d8cca69b2851d;p=oota-llvm.git diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp index d1e3f1afbfa..59a92890f5a 100644 --- a/lib/CodeGen/InlineSpiller.cpp +++ b/lib/CodeGen/InlineSpiller.cpp @@ -12,28 +12,33 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "Spiller.h" -#include "LiveRangeEdit.h" -#include "VirtRegMap.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" +#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" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.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"); @@ -51,7 +56,6 @@ static cl::opt DisableHoisting("disable-spill-hoist", cl::Hidden, namespace { class InlineSpiller : public Spiller { - MachineFunctionPass &Pass; MachineFunction &MF; LiveIntervals &LIS; LiveStacks &LSS; @@ -63,6 +67,7 @@ class InlineSpiller : public Spiller { MachineRegisterInfo &MRI; const TargetInstrInfo &TII; const TargetRegisterInfo &TRI; + const MachineBlockFrequencyInfo &MBFI; // Variables that are valid during spill(), but used by multiple methods. LiveRangeEdit *Edit; @@ -116,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; } @@ -130,26 +135,21 @@ private: // Dead defs generated during spilling. SmallVector DeadDefs; - ~InlineSpiller() {} + ~InlineSpiller() override {} public: - InlineSpiller(MachineFunctionPass &pass, - MachineFunction &mf, - VirtRegMap &vrm) - : Pass(pass), - 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()) {} - - void spill(LiveRangeEdit &); + 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; private: bool isSnippet(const LiveInterval &SnipLI); @@ -162,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); @@ -173,13 +173,10 @@ private: void reMaterializeAll(); bool coalesceStackAccess(MachineInstr *MI, unsigned Reg); - bool foldMemoryOperand(MachineBasicBlock::iterator MI, - const SmallVectorImpl &Ops, - MachineInstr *LoadMI = 0); - void insertReload(LiveInterval &NewLI, SlotIndex, - MachineBasicBlock::iterator MI); - void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, - SlotIndex, MachineBasicBlock::iterator MI); + bool foldMemoryOperand(ArrayRef >, + MachineInstr *LoadMI = nullptr); + void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI); + void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI); void spillAroundUses(unsigned Reg); void spillAll(); @@ -187,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); } + } //===----------------------------------------------------------------------===// @@ -234,12 +236,13 @@ 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_nodbg_iterator - RI = MRI.reg_nodbg_begin(SnipLI.reg); - MachineInstr *MI = RI.skipInstruction();) { + for (MachineRegisterInfo::reg_instr_nodbg_iterator + RI = MRI.reg_instr_nodbg_begin(SnipLI.reg), + E = MRI.reg_instr_nodbg_end(); RI != E; ) { + MachineInstr *MI = &*(RI++); // Allow copies to/from Reg. if (isFullCopyOf(MI, Reg)) @@ -276,8 +279,9 @@ void InlineSpiller::collectRegsToSpill() { if (Original == Reg) return; - for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); - MachineInstr *MI = RI.skipInstruction();) { + for (MachineRegisterInfo::reg_instr_iterator + RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) { + MachineInstr *MI = &*(RI++); unsigned SnipReg = isFullCopyOf(MI, Reg); if (!isSibling(SnipReg)) continue; @@ -339,10 +343,12 @@ static raw_ostream &operator<<(raw_ostream &OS, /// propagateSiblingValue - Propagate the value in SVI to dependents if it is /// known. Otherwise remember the dependency for later. /// -/// @param SVI SibValues entry to propagate. +/// @param SVIIter SibValues entry to propagate. /// @param VNI Dependent value, or NULL to propagate to all saved dependents. -void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, +void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVIIter, VNInfo *VNI) { + SibValueMap::value_type *SVI = &*SVIIter; + // When VNI is non-NULL, add it to SVI's deps, and only propagate to that. TinyPtrVector FirstDeps; if (VNI) { @@ -354,16 +360,14 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, if (!SVI->second.hasDef()) return; - // Work list of values to propagate. It would be nice to use a SetVector - // here, but then we would be forced to use a SmallSet. - SmallVector WorkList(1, SVI); - SmallPtrSet WorkSet; + // Work list of values to propagate. + SmallSetVector WorkList; + WorkList.insert(SVI); do { SVI = WorkList.pop_back_val(); - WorkSet.erase(SVI->first); TinyPtrVector *Deps = VNI ? &FirstDeps : &SVI->second.Deps; - VNI = 0; + VNI = nullptr; SibValueInfo &SV = SVI->second; if (!SV.SpillMBB) @@ -437,7 +441,20 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, // 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; @@ -452,8 +469,7 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI, continue; // Something changed in DepSVI. Propagate to dependents. - if (WorkSet.insert(DepSVI->first)) - WorkList.push_back(DepSVI); + WorkList.insert(&*DepSVI); DEBUG(dbgs() << " update " << DepSVI->first->id << '@' << DepSVI->first->def << " to:\t" << DepSV); @@ -476,7 +492,7 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, // Check if a cached value already exists. SibValueMap::iterator SVI; bool Inserted; - tie(SVI, Inserted) = + std::tie(SVI, Inserted) = SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI))); if (!Inserted) { DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':' @@ -492,10 +508,11 @@ 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; - tie(Reg, VNI) = WorkList.pop_back_val(); + std::tie(Reg, VNI) = WorkList.pop_back_val(); DEBUG(dbgs() << " " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def << ":\t"); @@ -505,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; @@ -526,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) { @@ -554,11 +573,11 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) { VNInfo *NonPHI = NonPHIs[i]; // Known value? Try an insertion. - tie(SVI, Inserted) = + 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)); @@ -578,17 +597,17 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, if (unsigned SrcReg = isFullCopyOf(MI, Reg)) { if (isSibling(SrcReg)) { LiveInterval &SrcLI = LIS.getInterval(SrcReg); - LiveRange *SrcLR = SrcLI.getLiveRangeContaining(VNI->def.getUseIndex()); - assert(SrcLR && "Copy from non-existing value"); + LiveQueryResult SrcQ = SrcLI.Query(VNI->def); + assert(SrcQ.valueIn() && "Copy from non-existing value"); // Check if this COPY kills its source. - SVI->second.KillsSource = (SrcLR->end == VNI->def); - VNInfo *SrcVNI = SrcLR->valno; + SVI->second.KillsSource = SrcQ.isKill(); + VNInfo *SrcVNI = SrcQ.valueIn(); DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':' << SrcVNI->id << '@' << SrcVNI->def << " kill=" << unsigned(SVI->second.KillsSource) << '\n'); // Known sibling source value? Try an insertion. - tie(SVI, Inserted) = SibValues.insert(std::make_pair(SrcVNI, - SibValueInfo(SrcReg, SrcVNI))); + std::tie(SVI, Inserted) = SibValues.insert( + std::make_pair(SrcVNI, SibValueInfo(SrcReg, SrcVNI))); // This is the first time we see Src, add it to the worklist. if (Inserted) WorkList.push_back(std::make_pair(SrcReg, SrcVNI)); @@ -615,7 +634,7 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI, propagateSiblingValue(SVI); } while (!WorkList.empty()); - // Look up the value we were looking for. We already did this lokup at the + // Look up the value we were looking for. We already did this lookup at the // top of the function, but SibValues may have been invalidated. SVI = SibValues.find(UseVNI); assert(SVI != SibValues.end() && "Didn't compute requested info"); @@ -643,17 +662,19 @@ 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"); + } // Check possible sibling copies. - if (VNI->isPHIDef() || VNI->getCopy()) { + if (VNI->isPHIDef() || DefMI->isCopy()) { VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def); assert(OrigVNI && "Def outside original live range"); if (OrigVNI->def != VNI->def) DefMI = traceSiblingValue(Reg, VNI, OrigVNI); } - if (!DefMI && !VNI->isPHIDef()) - DefMI = LIS.getInstructionFromIndex(VNI->def); - if (DefMI && Edit->checkRematerializable(VNI, DefMI, TII, AA)) { + if (DefMI && Edit->checkRematerializable(VNI, DefMI, AA)) { DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def << " may remat from " << *DefMI); } @@ -665,8 +686,8 @@ void InlineSpiller::analyzeSiblingValues() { /// a spill at a better location. bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) { SlotIndex Idx = LIS.getInstructionIndex(CopyMI); - VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getDefIndex()); - assert(VNI && VNI->def == Idx.getDefIndex() && "Not defined by copy"); + VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot()); + assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy"); SibValueMap::iterator I = SibValues.find(VNI); if (I == SibValues.end()) return false; @@ -726,7 +747,6 @@ bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) { MRI.getRegClass(SVI.SpillReg), &TRI); --MII; // Point to store instruction. LIS.InsertMachineInstrInMaps(MII); - VRM.addSpillSlotUse(StackSlot, MII); DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII); ++NumSpills; @@ -744,7 +764,7 @@ void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { do { LiveInterval *LI; - tie(LI, VNI) = WorkList.pop_back_val(); + std::tie(LI, VNI) = WorkList.pop_back_val(); unsigned Reg = LI->reg; DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@' << VNI->def << " in " << *LI << '\n'); @@ -758,9 +778,11 @@ void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n'); // Find all spills and copies of VNI. - for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg); - MachineInstr *MI = UI.skipInstruction();) { - if (!MI->isCopy() && !MI->getDesc().mayStore()) + for (MachineRegisterInfo::use_instr_nodbg_iterator + UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end(); + UI != E; ) { + MachineInstr *MI = &*(UI++); + if (!MI->isCopy() && !MI->mayStore()) continue; SlotIndex Idx = LIS.getInstructionIndex(MI); if (LI->getVNInfoAt(Idx) != VNI) @@ -770,9 +792,9 @@ void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) { if (unsigned DstReg = isFullCopyOf(MI, Reg)) { if (isSibling(DstReg)) { LiveInterval &DstLI = LIS.getInterval(DstReg); - VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getDefIndex()); + VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot()); assert(DstVNI && "Missing defined value"); - assert(DstVNI->def == Idx.getDefIndex() && "Wrong copy def slot"); + assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot"); WorkList.push_back(std::make_pair(&DstLI, DstVNI)); } continue; @@ -803,15 +825,15 @@ void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { SmallVector, 8> WorkList; WorkList.push_back(std::make_pair(LI, VNI)); do { - tie(LI, VNI) = WorkList.pop_back_val(); - if (!UsedValues.insert(VNI)) + std::tie(LI, VNI) = WorkList.pop_back_val(); + if (!UsedValues.insert(VNI).second) continue; if (VNI->isPHIDef()) { MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), PE = MBB->pred_end(); PI != PE; ++PI) { - VNInfo *PVNI = LI->getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot()); + VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI)); if (PVNI) WorkList.push_back(std::make_pair(LI, PVNI)); } @@ -824,7 +846,7 @@ void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { continue; LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg()); assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy"); - VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getUseIndex()); + VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true)); assert(SnipVNI && "Snippet undefined before copy"); WorkList.push_back(std::make_pair(&SnipLI, SnipVNI)); } while (!WorkList.empty()); @@ -833,7 +855,16 @@ void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) { /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading. bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineBasicBlock::iterator MI) { - SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex(); + + // 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()); if (!ParentVNI) { @@ -855,7 +886,7 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, SibValueMap::const_iterator SibI = SibValues.find(ParentVNI); if (SibI != SibValues.end()) RM.OrigMI = SibI->second.DefMI; - if (!Edit->canRematerializeAt(RM, UseIdx, false, LIS)) { + if (!Edit->canRematerializeAt(RM, UseIdx, false)) { markValueUsed(&VirtReg, ParentVNI); DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI); return false; @@ -863,52 +894,41 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, // If the instruction also writes VirtReg.reg, it had better not require the // same register for uses and defs. - bool Reads, Writes; - SmallVector Ops; - tie(Reads, Writes) = MI->readsWritesVirtualRegister(VirtReg.reg, &Ops); - if (Writes) { - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(Ops[i]); - if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) { - markValueUsed(&VirtReg, ParentVNI); - DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); - return false; - } - } + if (RI.Tied) { + markValueUsed(&VirtReg, ParentVNI); + DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI); + return false; } // Before rematerializing into a register for a single instruction, try to // fold a load into the instruction. That avoids allocating a new register. - if (RM.OrigMI->getDesc().canFoldAsLoad() && - foldMemoryOperand(MI, Ops, RM.OrigMI)) { + if (RM.OrigMI->canFoldAsLoad() && + foldMemoryOperand(Ops, RM.OrigMI)) { Edit->markRematerialized(RM.ParentVNI); ++NumFoldedLoads; return true; } // Alocate a new register for the remat. - LiveInterval &NewLI = Edit->createFrom(Original, LIS, VRM); - NewLI.markNotSpillable(); + unsigned NewVReg = Edit->createFrom(Original); // Finally we can rematerialize OrigMI before MI. - SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM, - LIS, TII, TRI); + SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewVReg, RM, + TRI); + (void)DefIdx; DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' << *LIS.getInstructionFromIndex(DefIdx)); // Replace operands for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(Ops[i]); + MachineOperand &MO = MI->getOperand(Ops[i].second); if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) { - MO.setReg(NewLI.reg); + MO.setReg(NewVReg); MO.setIsKill(); } } - DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI); + DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI << '\n'); - VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator()); - NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI)); - DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); ++NumRemats; return true; } @@ -917,7 +937,7 @@ bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, /// and trim the live ranges after. void InlineSpiller::reMaterializeAll() { // analyzeSiblingValues has already tested all relevant defining instructions. - if (!Edit->anyRematerializable(LIS, TII, AA)) + if (!Edit->anyRematerializable(AA)) return; UsedValues.clear(); @@ -927,10 +947,17 @@ 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_nodbg_iterator - RI = MRI.use_nodbg_begin(Reg); - MachineInstr *MI = RI.skipInstruction();) + 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); + } } if (!anyRemat) return; @@ -958,21 +985,24 @@ void InlineSpiller::reMaterializeAll() { if (DeadDefs.empty()) return; DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n"); - Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII); + Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); // Get rid of deleted and empty intervals. - for (unsigned i = RegsToSpill.size(); i != 0; --i) { - unsigned Reg = RegsToSpill[i-1]; - if (!LIS.hasInterval(Reg)) { - RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); + unsigned ResultPos = 0; + for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { + unsigned Reg = RegsToSpill[i]; + if (!LIS.hasInterval(Reg)) continue; - } + LiveInterval &LI = LIS.getInterval(Reg); - if (!LI.empty()) + if (LI.empty()) { + Edit->eraseVirtReg(Reg); continue; - Edit->eraseVirtReg(Reg, LIS); - RegsToSpill.erase(RegsToSpill.begin() + (i - 1)); + } + + RegsToSpill[ResultPos++] = Reg; } + RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end()); DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n"); } @@ -1008,29 +1038,75 @@ bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) { return true; } -/// foldMemoryOperand - Try folding stack slot references in Ops into MI. -/// @param MI Instruction using or defining the current register. -/// @param Ops Operand indices from readsWritesVirtualRegister(). +#if !defined(NDEBUG) +// Dump the range of instructions from B to E with their slot indexes. +static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E, + LiveIntervals const &LIS, + const char *const header, + unsigned VReg =0) { + char NextLine = '\n'; + char SlotIndent = '\t'; + + if (std::next(B) == E) { + NextLine = ' '; + SlotIndent = ' '; + } + + dbgs() << '\t' << header << ": " << NextLine; + + for (MachineBasicBlock::iterator I = B; I != E; ++I) { + SlotIndex Idx = LIS.getInstructionIndex(I).getRegSlot(); + + // If a register was passed in and this instruction has it as a + // destination that is marked as an early clobber, print the + // early-clobber slot index. + if (VReg) { + MachineOperand *MO = I->findRegisterDefOperand(VReg); + if (MO && MO->isEarlyClobber()) + Idx = Idx.getRegSlot(true); + } + + dbgs() << SlotIndent << Idx << '\t' << *I; + } +} +#endif + +/// foldMemoryOperand - Try folding stack slot references in Ops into their +/// instructions. +/// +/// @param Ops Operand indices from analyzeVirtReg(). /// @param LoadMI Load instruction to use instead of stack slot when non-null. -/// @return True on success, and MI will be erased. -bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI, - const SmallVectorImpl &Ops, - MachineInstr *LoadMI) { +/// @return True on success. +bool InlineSpiller:: +foldMemoryOperand(ArrayRef > Ops, + MachineInstr *LoadMI) { + if (Ops.empty()) + return false; + // Don't attempt folding in bundles. + MachineInstr *MI = Ops.front().first; + if (Ops.back().first != MI || MI->isBundled()) + return false; + bool WasCopy = MI->isCopy(); unsigned ImpReg = 0; + bool SpillSubRegs = (MI->getOpcode() == TargetOpcode::STATEPOINT || + MI->getOpcode() == TargetOpcode::PATCHPOINT || + MI->getOpcode() == TargetOpcode::STACKMAP); + // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied // operands. SmallVector FoldOps; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - unsigned Idx = Ops[i]; + unsigned Idx = Ops[i].second; MachineOperand &MO = MI->getOperand(Idx); if (MO.isImplicit()) { ImpReg = MO.getReg(); continue; } // FIXME: Teach targets to deal with subregs. - if (MO.getSubReg()) + if (!SpillSubRegs && MO.getSubReg()) return false; // We cannot fold a load instruction into a def. if (LoadMI && MO.isDef()) @@ -1040,16 +1116,46 @@ bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI, FoldOps.push_back(Idx); } + MachineInstrSpan MIS(MI); + MachineInstr *FoldMI = LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI) : TII.foldMemoryOperand(MI, FoldOps, StackSlot); if (!FoldMI) return false; + + // Remove LIS for any dead defs in the original MI not in FoldMI. + for (MIBundleOperands MO(MI); MO.isValid(); ++MO) { + if (!MO->isReg()) + continue; + unsigned Reg = MO->getReg(); + if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) || + MRI.isReserved(Reg)) { + continue; + } + // Skip non-Defs, including undef uses and internal reads. + if (MO->isUse()) + continue; + MIBundleOperands::PhysRegInfo RI = + MIBundleOperands(FoldMI).analyzePhysReg(Reg, &TRI); + if (RI.Defines) + continue; + // FoldMI does not define this physreg. Remove the LI segment. + assert(MO->isDead() && "Cannot fold physreg def"); + SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); + LIS.removePhysRegDefAt(Reg, Idx); + } + LIS.ReplaceMachineInstrInMaps(MI, FoldMI); - if (!LoadMI) - VRM.addSpillSlotUse(StackSlot, FoldMI); MI->eraseFromParent(); + // Insert any new instructions other than FoldMI into the LIS maps. + assert(!MIS.empty() && "Unexpected empty span of instructions!"); + for (MachineBasicBlock::iterator MII = MIS.begin(), End = MIS.end(); + MII != End; ++MII) + if (&*MII != FoldMI) + LIS.InsertMachineInstrInMaps(&*MII); + // TII.foldMemoryOperand may have left some implicit operands on the // instruction. Strip them. if (ImpReg) @@ -1061,46 +1167,47 @@ bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI, FoldMI->RemoveOperand(i - 1); } - DEBUG(dbgs() << "\tfolded: " << LIS.getInstructionIndex(FoldMI) << '\t' - << *FoldMI); + DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS, + "folded")); + if (!WasCopy) ++NumFolded; - else if (Ops.front() == 0) + else if (Ops.front().second == 0) ++NumSpills; else ++NumReloads; return true; } -/// insertReload - Insert a reload of NewLI.reg before MI. -void InlineSpiller::insertReload(LiveInterval &NewLI, +void InlineSpiller::insertReload(unsigned NewVReg, SlotIndex Idx, MachineBasicBlock::iterator MI) { MachineBasicBlock &MBB = *MI->getParent(); - TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot, - MRI.getRegClass(NewLI.reg), &TRI); - --MI; // Point to load instruction. - SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex(); - VRM.addSpillSlotUse(StackSlot, MI); - DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI); - VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0, - LIS.getVNInfoAllocator()); - NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI)); + + MachineInstrSpan MIS(MI); + TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot, + MRI.getRegClass(NewVReg), &TRI); + + LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI); + + DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload", + NewVReg)); ++NumReloads; } -/// insertSpill - Insert a spill of NewLI.reg after MI. -void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI, - SlotIndex Idx, MachineBasicBlock::iterator MI) { +/// insertSpill - Insert a spill of NewVReg after MI. +void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill, + MachineBasicBlock::iterator MI) { MachineBasicBlock &MBB = *MI->getParent(); - TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot, - MRI.getRegClass(NewLI.reg), &TRI); - --MI; // Point to store instruction. - SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex(); - VRM.addSpillSlotUse(StackSlot, MI); - DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI); - VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator()); - NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI)); + + MachineInstrSpan MIS(MI); + TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot, + MRI.getRegClass(NewVReg), &TRI); + + LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end()); + + DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS, + "spill")); ++NumSpills; } @@ -1110,24 +1217,28 @@ void InlineSpiller::spillAroundUses(unsigned Reg) { LiveInterval &OldLI = LIS.getInterval(Reg); // Iterate over instructions using Reg. - for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg); - MachineInstr *MI = RI.skipInstruction();) { + 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()) { // Modify DBG_VALUE now that the value is in a spill slot. - uint64_t Offset = MI->getOperand(1).getImm(); - const MDNode *MDPtr = MI->getOperand(2).getMetadata(); + bool IsIndirect = MI->isIndirectDebugValue(); + uint64_t Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; + const MDNode *Var = MI->getDebugVariable(); + const MDNode *Expr = MI->getDebugExpression(); DebugLoc DL = MI->getDebugLoc(); - if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot, - Offset, MDPtr, DL)) { - DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); - MachineBasicBlock *MBB = MI->getParent(); - MBB->insert(MBB->erase(MI), NewDV); - } else { - DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); - MI->eraseFromParent(); - } + DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); + MachineBasicBlock *MBB = MI->getParent(); + assert(cast(Var)->isValidLocationForIntrinsic(DL) && + "Expected inlined-at fields to agree"); + BuildMI(*MBB, MBB->erase(MI), DL, TII.get(TargetOpcode::DBG_VALUE)) + .addFrameIndex(StackSlot) + .addImm(Offset) + .addMetadata(Var) + .addMetadata(Expr); continue; } @@ -1140,14 +1251,14 @@ void InlineSpiller::spillAroundUses(unsigned Reg) { continue; // Analyze instruction. - bool Reads, Writes; - SmallVector Ops; - tie(Reads, Writes) = MI->readsWritesVirtualRegister(Reg, &Ops); + SmallVector, 8> Ops; + MIBundleOperands::VirtRegInfo RI = + MIBundleOperands(MI).analyzeVirtReg(Reg, &Ops); // Find the slot index where this instruction reads and writes OldLI. // This is usually the def slot, except for tied early clobbers. - SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex(); - if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getUseIndex())) + SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot(); + if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true))) if (SlotIndex::isSameInstr(Idx, VNI->def)) Idx = VNI->def; @@ -1160,7 +1271,7 @@ void InlineSpiller::spillAroundUses(unsigned Reg) { SnippetCopies.insert(MI); continue; } - if (Writes) { + if (RI.Writes) { // Hoist the spill of a sib-reg copy. if (hoistSpill(OldLI, MI)) { // This COPY is now dead, the value is already in the stack slot. @@ -1177,45 +1288,35 @@ void InlineSpiller::spillAroundUses(unsigned Reg) { } // Attempt to fold memory ops. - if (foldMemoryOperand(MI, Ops)) + if (foldMemoryOperand(Ops)) continue; - // Allocate interval around instruction. + // Create a new virtual register for spill/fill. // FIXME: Infer regclass from instruction alone. - LiveInterval &NewLI = Edit->createFrom(Reg, LIS, VRM); - NewLI.markNotSpillable(); + unsigned NewVReg = Edit->createFrom(Reg); - if (Reads) - insertReload(NewLI, Idx, MI); + if (RI.Reads) + insertReload(NewVReg, Idx, MI); // Rewrite instruction operands. bool hasLiveDef = false; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(Ops[i]); - MO.setReg(NewLI.reg); + MachineOperand &MO = Ops[i].first->getOperand(Ops[i].second); + MO.setReg(NewVReg); if (MO.isUse()) { - if (!MI->isRegTiedToDefOperand(Ops[i])) + if (!Ops[i].first->isRegTiedToDefOperand(Ops[i].second)) MO.setIsKill(); } else { if (!MO.isDead()) hasLiveDef = true; } } - DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI); + DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n'); // FIXME: Use a second vreg if instruction has no tied ops. - if (Writes) { - if (hasLiveDef) - insertSpill(NewLI, OldLI, Idx, MI); - else { - // This instruction defines a dead value. We don't need to spill it, - // but do create a live range for the dead value. - VNInfo *VNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator()); - NewLI.addRange(LiveRange(Idx, Idx.getNextSlot(), VNI)); - } - } - - DEBUG(dbgs() << "\tinterval: " << NewLI << '\n'); + if (RI.Writes) + if (hasLiveDef) + insertSpill(NewVReg, true, MI); } } @@ -1225,7 +1326,7 @@ void InlineSpiller::spillAll() { if (StackSlot == VirtRegMap::NO_STACK_SLOT) { StackSlot = VRM.assignVirt2StackSlot(Original); StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original)); - StackInt->getNextValue(SlotIndex(), 0, LSS.getVNInfoAllocator()); + StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator()); } else StackInt = &LSS.getInterval(StackSlot); @@ -1234,8 +1335,8 @@ void InlineSpiller::spillAll() { assert(StackInt->getNumValNums() == 1 && "Bad stack interval values"); for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) - StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]), - StackInt->getValNumInfo(0)); + StackInt->MergeSegmentsInAsValue(LIS.getInterval(RegsToSpill[i]), + StackInt->getValNumInfo(0)); DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n'); // Spill around uses of all RegsToSpill. @@ -1245,16 +1346,17 @@ void InlineSpiller::spillAll() { // Hoisted spills may cause dead code. if (!DeadDefs.empty()) { DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n"); - Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII); + Edit->eliminateDeadDefs(DeadDefs, RegsToSpill); } // Finally delete the SnippetCopies. for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) { - for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(RegsToSpill[i]); - MachineInstr *MI = RI.skipInstruction();) { + for (MachineRegisterInfo::reg_instr_iterator + RI = MRI.reg_instr_begin(RegsToSpill[i]), E = MRI.reg_instr_end(); + RI != E; ) { + MachineInstr *MI = &*(RI++); assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy"); // FIXME: Do this with a LiveRangeEdit callback. - VRM.RemoveMachineInstrFromMaps(MI); LIS.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); } @@ -1262,7 +1364,7 @@ void InlineSpiller::spillAll() { // Delete all spilled registers. for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) - Edit->eraseVirtReg(RegsToSpill[i], LIS); + Edit->eraseVirtReg(RegsToSpill[i]); } void InlineSpiller::spill(LiveRangeEdit &edit) { @@ -1273,12 +1375,12 @@ 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() - << ':' << edit.getParent() << "\nFrom original " - << LIS.getInterval(Original) << '\n'); + << TRI.getRegClassName(MRI.getRegClass(edit.getReg())) + << ':' << edit.getParent() + << "\nFrom original " << PrintReg(Original) << '\n'); assert(edit.getParent().isSpillable() && "Attempting to spill already spilled value."); assert(DeadDefs.empty() && "Previous spill didn't remove dead defs"); @@ -1291,5 +1393,5 @@ void InlineSpiller::spill(LiveRangeEdit &edit) { if (!RegsToSpill.empty()) spillAll(); - Edit->calculateRegClassAndHint(MF, LIS, Loops); + Edit->calculateRegClassAndHint(MF, Loops, MBFI); }