#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;
- // Known predecessor value? Try an insertion.
+ if (!OrigLI.containsOneValue() &&
+ OrigLI.getVNInfoAt(VNI2->def) != OrigVNI)
+ continue;
+ 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.getUseIndex());
+ 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)
VRM.addSpillSlotUse(StackSlot, MII);
DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII);
- if (MBB == CopyMI->getParent())
- ++NumHoistLocal;
- else
- ++NumHoistGlobal;
+ ++NumSpills;
+ ++NumHoists;
return true;
}
// 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());
/// 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();
// TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
// operands.
SmallVector<unsigned, 8> FoldOps;
VRM.addSpillSlotUse(StackSlot, FoldMI);
MI->eraseFromParent();
DEBUG(dbgs() << "\tfolded: " << *FoldMI);
- ++NumFolded;
+ if (!WasCopy)
+ ++NumFolded;
+ else if (Ops.front() == 0)
+ ++NumSpills;
+ else
+ ++NumReloads;
return true;
}
projects / oota-llvm.git / blobdiff