#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
STATISTIC(NumSpilledRanges, "Number of spilled live ranges");
-STATISTIC(NumSnippets, "Number of snippets included in spills");
+STATISTIC(NumSnippets, "Number of spilled snippets");
STATISTIC(NumSpills, "Number of spills inserted");
+STATISTIC(NumSpillsRemoved, "Number of spills removed");
STATISTIC(NumReloads, "Number of reloads inserted");
+STATISTIC(NumReloadsRemoved, "Number of reloads removed");
STATISTIC(NumFolded, "Number of folded stack accesses");
STATISTIC(NumFoldedLoads, "Number of folded loads");
STATISTIC(NumRemats, "Number of rematerialized defs for spilling");
-STATISTIC(NumOmitReloadSpill, "Number of omitted spills after reloads");
-STATISTIC(NumHoistLocal, "Number of locally hoisted spills");
-STATISTIC(NumHoistGlobal, "Number of globally hoisted spills");
-STATISTIC(NumRedundantSpills, "Number of redundant spills identified");
+STATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads");
+STATISTIC(NumHoists, "Number of hoisted spills");
+
+static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
+ cl::desc("Disable inline spill hoisting"));
namespace {
class InlineSpiller : public Spiller {
// True when value is defined by an original PHI not from splitting.
bool DefByOrigPHI;
+ // True when the COPY defining this value killed its source.
+ bool KillsSource;
+
// The preferred register to spill.
unsigned SpillReg;
TinyPtrVector<VNInfo*> Deps;
SibValueInfo(unsigned Reg, VNInfo *VNI)
- : AllDefsAreReloads(true), DefByOrigPHI(false),
+ : AllDefsAreReloads(true), DefByOrigPHI(false), KillsSource(false),
SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {}
// Returns true when a def has been found.
typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
SibValueMap SibValues;
- // Values live-out from basic blocks. This is the same as
- // LI.getVNInfoAt(LIS.getMBBEndIdx(MBB).getPrevSlot())
- typedef DenseMap<MachineBasicBlock*, VNInfo*> LiveOutMap;
- LiveOutMap LiveOutValues;
-
// Dead defs generated during spilling.
SmallVector<MachineInstr*, 8> DeadDefs;
OS << " all-reloads";
if (SVI.DefByOrigPHI)
OS << " orig-phi";
+ if (SVI.KillsSource)
+ OS << " kill";
OS << " deps[";
for (unsigned i = 0, e = SVI.Deps.size(); i != e; ++i)
OS << ' ' << SVI.Deps[i]->id << '@' << SVI.Deps[i]->def;
// Should this value be propagated as a preferred spill candidate? We don't
// propagate values of registers that are about to spill.
- bool PropSpill = !isRegToSpill(SV.SpillReg);
+ bool PropSpill = !DisableHoisting && !isRegToSpill(SV.SpillReg);
unsigned SpillDepth = ~0u;
for (TinyPtrVector<VNInfo*>::iterator DepI = Deps->begin(),
if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) {
if (SV.SpillMBB == DepSV.SpillMBB) {
// DepSV is in the same block. Hoist when dominated.
- if (SV.SpillVNI->def < DepSV.SpillVNI->def) {
+ if (DepSV.KillsSource && SV.SpillVNI->def < DepSV.SpillVNI->def) {
// This is an alternative def earlier in the same MBB.
// Hoist the spill as far as possible in SpillMBB. This can ease
// register pressure:
// spill x
// y = use x<kill>
//
+ // This hoist only helps when the DepSV copy kills its source.
Changed = true;
DepSV.SpillReg = SV.SpillReg;
DepSV.SpillVNI = SV.SpillVNI;
// 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) {
DEBUG(dbgs() << "orig phi value\n");
SVI->second.DefByOrigPHI = true;
propagateSiblingValue(SVI);
continue;
}
- // Get values live-out of predecessors.
+
+ // This is a PHI inserted by live range splitting. We could trace the
+ // live-out value from predecessor blocks, but that search can be very
+ // expensive if there are many predecessors and many more PHIs as
+ // generated by tail-dup when it sees an indirectbr. Instead, look at
+ // all the non-PHI defs that have the same value as OrigVNI. They must
+ // jointly dominate VNI->def. This is not optimal since VNI may actually
+ // be jointly dominated by a smaller subset of defs, so there is a change
+ // we will miss a AllDefsAreReloads optimization.
+
+ // Separate all values dominated by OrigVNI into PHIs and non-PHIs.
+ SmallVector<VNInfo*, 8> PHIs, NonPHIs;
LiveInterval &LI = LIS.getInterval(Reg);
- MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
- DEBUG(dbgs() << "split phi value, check " << MBB->pred_size()
- << " preds\n");
- for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
- PE = MBB->pred_end(); PI != PE; ++PI) {
- // Use a cache of block live-out values. This is faster than using
- // getVNInfoAt on complex intervals.
- VNInfo *&PVNI = LiveOutValues[*PI];
- if (!PVNI)
- PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot());
- if (!PVNI)
+ LiveInterval &OrigLI = LIS.getInterval(Original);
+
+ for (LiveInterval::vni_iterator VI = LI.vni_begin(), VE = LI.vni_end();
+ VI != VE; ++VI) {
+ VNInfo *VNI2 = *VI;
+ if (VNI2->isUnused())
+ continue;
+ if (!OrigLI.containsOneValue() &&
+ OrigLI.getVNInfoAt(VNI2->def) != OrigVNI)
continue;
- // Known predecessor value? Try an insertion.
+ if (VNI2->isPHIDef() && VNI2->def != OrigVNI->def)
+ PHIs.push_back(VNI2);
+ else
+ NonPHIs.push_back(VNI2);
+ }
+ DEBUG(dbgs() << "split phi value, checking " << PHIs.size()
+ << " phi-defs, and " << NonPHIs.size()
+ << " non-phi/orig defs\n");
+
+ // Create entries for all the PHIs. Don't add them to the worklist, we
+ // are processing all of them in one go here.
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+ SibValues.insert(std::make_pair(PHIs[i], SibValueInfo(Reg, PHIs[i])));
+
+ // Add every PHI as a dependent of all the non-PHIs.
+ for (unsigned i = 0, e = NonPHIs.size(); i != e; ++i) {
+ VNInfo *NonPHI = NonPHIs[i];
+ // Known value? Try an insertion.
tie(SVI, Inserted) =
- SibValues.insert(std::make_pair(PVNI, SibValueInfo(Reg, PVNI)));
- // This is the first time we see PVNI, add it to the worklist.
+ 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]);
+ // This is the first time we see NonPHI, add it to the worklist.
if (Inserted)
- WorkList.push_back(std::make_pair(Reg, PVNI));
- propagateSiblingValue(SVI, VNI);
+ WorkList.push_back(std::make_pair(Reg, NonPHI));
+ else
+ // Propagate to all inserted PHIs, not just VNI.
+ propagateSiblingValue(SVI);
}
+
// Next work list item.
continue;
}
if (unsigned SrcReg = isFullCopyOf(MI, Reg)) {
if (isSibling(SrcReg)) {
LiveInterval &SrcLI = LIS.getInterval(SrcReg);
- VNInfo *SrcVNI = SrcLI.getVNInfoAt(VNI->def.getUseIndex());
- assert(SrcVNI && "Copy from non-existing value");
+ LiveRange *SrcLR = SrcLI.getLiveRangeContaining(VNI->def.getRegSlot(true));
+ assert(SrcLR && "Copy from non-existing value");
+ // Check if this COPY kills its source.
+ SVI->second.KillsSource = (SrcLR->end == VNI->def);
+ VNInfo *SrcVNI = SrcLR->valno;
DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':'
- << SrcVNI->id << '@' << SrcVNI->def << '\n');
+ << 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)));
/// Keep track of values that may be rematerializable.
void InlineSpiller::analyzeSiblingValues() {
SibValues.clear();
- LiveOutValues.clear();
// No siblings at all?
if (Edit->getReg() == Original)
/// 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;
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);
- if (MBB == CopyMI->getParent())
- ++NumHoistLocal;
- else
- ++NumHoistGlobal;
+ ++NumSpills;
+ ++NumHoists;
return true;
}
// 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())
+ if (!MI->isCopy() && !MI->mayStore())
continue;
SlotIndex Idx = LIS.getInstructionIndex(MI);
if (LI->getVNInfoAt(Idx) != 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;
// eliminateDeadDefs won't normally remove stores, so switch opcode.
MI->setDesc(TII.get(TargetOpcode::KILL));
DeadDefs.push_back(MI);
- ++NumRedundantSpills;
+ ++NumSpillsRemoved;
+ --NumSpills;
}
}
} while (!WorkList.empty());
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));
}
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());
/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg,
MachineBasicBlock::iterator MI) {
- SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex();
+ SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
if (!ParentVNI) {
// 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() &&
+ if (RM.OrigMI->canFoldAsLoad() &&
foldMemoryOperand(MI, Ops, RM.OrigMI)) {
Edit->markRematerialized(RM.ParentVNI);
++NumFoldedLoads;
DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI);
VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator());
- NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
+ NewLI.addRange(LiveRange(DefIdx, UseIdx.getRegSlot(), DefVNI));
DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
++NumRemats;
return true;
/// If MI is a load or store of StackSlot, it can be removed.
bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
int FI = 0;
- unsigned InstrReg;
- if (!(InstrReg = TII.isLoadFromStackSlot(MI, FI)) &&
- !(InstrReg = TII.isStoreToStackSlot(MI, FI)))
- return false;
+ unsigned InstrReg = TII.isLoadFromStackSlot(MI, FI);
+ bool IsLoad = InstrReg;
+ if (!IsLoad)
+ InstrReg = TII.isStoreToStackSlot(MI, FI);
// We have a stack access. Is it the right register and slot?
if (InstrReg != Reg || FI != StackSlot)
DEBUG(dbgs() << "Coalescing stack access: " << *MI);
LIS.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
+
+ if (IsLoad) {
+ ++NumReloadsRemoved;
+ --NumReloads;
+ } else {
+ ++NumSpillsRemoved;
+ --NumSpills;
+ }
+
return true;
}
bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
const SmallVectorImpl<unsigned> &Ops,
MachineInstr *LoadMI) {
+ bool WasCopy = MI->isCopy();
+ unsigned ImpReg = 0;
+
// TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
// operands.
SmallVector<unsigned, 8> FoldOps;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
unsigned Idx = Ops[i];
MachineOperand &MO = MI->getOperand(Idx);
- if (MO.isImplicit())
+ if (MO.isImplicit()) {
+ ImpReg = MO.getReg();
continue;
+ }
// FIXME: Teach targets to deal with subregs.
if (MO.getSubReg())
return false;
if (!FoldMI)
return false;
LIS.ReplaceMachineInstrInMaps(MI, FoldMI);
- if (!LoadMI)
- VRM.addSpillSlotUse(StackSlot, FoldMI);
MI->eraseFromParent();
- DEBUG(dbgs() << "\tfolded: " << *FoldMI);
- ++NumFolded;
+
+ // TII.foldMemoryOperand may have left some implicit operands on the
+ // instruction. Strip them.
+ if (ImpReg)
+ for (unsigned i = FoldMI->getNumOperands(); i; --i) {
+ MachineOperand &MO = FoldMI->getOperand(i - 1);
+ if (!MO.isReg() || !MO.isImplicit())
+ break;
+ if (MO.getReg() == ImpReg)
+ FoldMI->RemoveOperand(i - 1);
+ }
+
+ DEBUG(dbgs() << "\tfolded: " << LIS.getInstructionIndex(FoldMI) << '\t'
+ << *FoldMI);
+ if (!WasCopy)
+ ++NumFolded;
+ else if (Ops.front() == 0)
+ ++NumSpills;
+ else
+ ++NumReloads;
return true;
}
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);
+ SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot();
DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI);
VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0,
LIS.getVNInfoAllocator());
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);
+ SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getRegSlot();
DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator());
NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
// 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;
DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI);
// FIXME: Use a second vreg if instruction has no tied ops.
- if (Writes && hasLiveDef)
+ 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.getDeadSlot(), VNI));
+ }
+ }
DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
}
MachineInstr *MI = RI.skipInstruction();) {
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();
}