aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/CodeGen/InlineSpiller.cpp162
-rw-r--r--lib/CodeGen/LiveRangeEdit.cpp33
-rw-r--r--lib/CodeGen/LiveRangeEdit.h5
3 files changed, 129 insertions, 71 deletions
diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp
index c5994cb..f1b9aaf 100644
--- a/lib/CodeGen/InlineSpiller.cpp
+++ b/lib/CodeGen/InlineSpiller.cpp
@@ -120,13 +120,14 @@ private:
}
bool isSibling(unsigned Reg);
- void traceSiblingValue(unsigned, VNInfo*, VNInfo*);
+ MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
void analyzeSiblingValues();
bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
- bool reMaterializeFor(MachineBasicBlock::iterator MI);
+ void markValueUsed(LiveInterval*, VNInfo*);
+ bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI);
void reMaterializeAll();
bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
@@ -277,10 +278,10 @@ bool InlineSpiller::isSibling(unsigned Reg) {
/// Determine if the value is defined by all reloads, so spilling isn't
/// necessary - the value is already in the stack slot.
///
-/// Find a defining instruction that may be a candidate for rematerialization.
+/// Return a defining instruction that may be a candidate for rematerialization.
///
-void InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
- VNInfo *OrigVNI) {
+MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
+ VNInfo *OrigVNI) {
DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
<< UseVNI->id << '@' << UseVNI->def << '\n');
SmallPtrSet<VNInfo*, 8> Visited;
@@ -365,7 +366,7 @@ void InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
// We have an 'original' def. Don't record trivial cases.
if (VNI == UseVNI) {
DEBUG(dbgs() << "Not a sibling copy.\n");
- return;
+ return MI;
}
// Potential remat candidate.
@@ -385,10 +386,13 @@ void InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
<< SVI.SpillVNI->id << '@' << SVI.SpillVNI->def << '\n';
});
SibValues.insert(std::make_pair(UseVNI, SVI));
+ return SVI.DefMI;
}
/// analyzeSiblingValues - Trace values defined by sibling copies back to
/// something that isn't a sibling copy.
+///
+/// Keep track of values that may be rematerializable.
void InlineSpiller::analyzeSiblingValues() {
SibValues.clear();
@@ -403,11 +407,19 @@ void InlineSpiller::analyzeSiblingValues() {
for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
VE = LI.vni_end(); VI != VE; ++VI) {
VNInfo *VNI = *VI;
- if (VNI->isUnused() || !(VNI->isPHIDef() || VNI->getCopy()))
+ if (VNI->isUnused())
continue;
- VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
- if (OrigVNI->def != VNI->def)
- traceSiblingValue(Reg, VNI, OrigVNI);
+ MachineInstr *DefMI = 0;
+ // Check possible sibling copies.
+ if (VNI->isPHIDef() || VNI->getCopy()) {
+ VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
+ 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);
}
}
}
@@ -520,12 +532,51 @@ void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
} while (!WorkList.empty());
}
+
+//===----------------------------------------------------------------------===//
+// Rematerialization
+//===----------------------------------------------------------------------===//
+
+/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
+/// instruction cannot be eliminated. See through snippet copies
+void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
+ SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
+ WorkList.push_back(std::make_pair(LI, VNI));
+ do {
+ tie(LI, VNI) = WorkList.pop_back_val();
+ if (!UsedValues.insert(VNI))
+ 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());
+ if (PVNI)
+ WorkList.push_back(std::make_pair(LI, PVNI));
+ }
+ continue;
+ }
+
+ // Follow snippet copies.
+ MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
+ if (!SnippetCopies.count(MI))
+ continue;
+ LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
+ assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
+ VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getUseIndex());
+ 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(MachineBasicBlock::iterator MI) {
+bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg,
+ MachineBasicBlock::iterator MI) {
SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex();
- VNInfo *OrigVNI = Edit->getParent().getVNInfoAt(UseIdx);
+ VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx);
- if (!OrigVNI) {
+ if (!ParentVNI) {
DEBUG(dbgs() << "\tadding <undef> flags: ");
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
@@ -536,15 +587,16 @@ bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
return true;
}
- // FIXME: Properly remat for snippets as well.
- if (SnippetCopies.count(MI)) {
- UsedValues.insert(OrigVNI);
+ if (SnippetCopies.count(MI))
return false;
- }
- LiveRangeEdit::Remat RM(OrigVNI);
+ // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy.
+ LiveRangeEdit::Remat RM(ParentVNI);
+ SibValueMap::const_iterator SibI = SibValues.find(ParentVNI);
+ if (SibI != SibValues.end())
+ RM.OrigMI = SibI->second.DefMI;
if (!Edit->canRematerializeAt(RM, UseIdx, false, LIS)) {
- UsedValues.insert(OrigVNI);
+ markValueUsed(&VirtReg, ParentVNI);
DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
return false;
}
@@ -558,7 +610,7 @@ bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
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()) {
- UsedValues.insert(OrigVNI);
+ markValueUsed(&VirtReg, ParentVNI);
DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
return false;
}
@@ -606,58 +658,48 @@ bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
/// reMaterializeAll - Try to rematerialize as many uses as possible,
/// and trim the live ranges after.
void InlineSpiller::reMaterializeAll() {
- // Do a quick scan of the interval values to find if any are remattable.
+ // analyzeSiblingValues has already tested all relevant defining instructions.
if (!Edit->anyRematerializable(LIS, TII, AA))
return;
UsedValues.clear();
- // Try to remat before all uses of Edit->getReg().
+ // Try to remat before all uses of snippets.
bool anyRemat = false;
- for (MachineRegisterInfo::use_nodbg_iterator
- RI = MRI.use_nodbg_begin(Edit->getReg());
- MachineInstr *MI = RI.skipInstruction();)
- anyRemat |= reMaterializeFor(MI);
-
+ 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();)
+ anyRemat |= reMaterializeFor(LI, MI);
+ }
if (!anyRemat)
return;
// Remove any values that were completely rematted.
- bool anyRemoved = false;
- for (LiveInterval::vni_iterator I = Edit->getParent().vni_begin(),
- E = Edit->getParent().vni_end(); I != E; ++I) {
- VNInfo *VNI = *I;
- if (VNI->hasPHIKill() || !Edit->didRematerialize(VNI) ||
- UsedValues.count(VNI))
- continue;
- MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def);
- DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI);
- LIS.RemoveMachineInstrFromMaps(DefMI);
- VRM.RemoveMachineInstrFromMaps(DefMI);
- DefMI->eraseFromParent();
- VNI->def = SlotIndex();
- anyRemoved = true;
- }
-
- if (!anyRemoved)
- return;
-
- // Removing values may cause debug uses where parent is not live.
- for (MachineRegisterInfo::use_iterator RI = MRI.use_begin(Edit->getReg());
- MachineInstr *MI = RI.skipInstruction();) {
- if (!MI->isDebugValue())
- continue;
- // Try to preserve the debug value if parent is live immediately after it.
- MachineBasicBlock::iterator NextMI = MI;
- ++NextMI;
- if (NextMI != MI->getParent()->end() && !LIS.isNotInMIMap(NextMI)) {
- SlotIndex Idx = LIS.getInstructionIndex(NextMI);
- VNInfo *VNI = Edit->getParent().getVNInfoAt(Idx);
- if (VNI && (VNI->hasPHIKill() || UsedValues.count(VNI)))
+ for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
+ unsigned Reg = RegsToSpill[i];
+ LiveInterval &LI = LIS.getInterval(Reg);
+ for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
+ I != E; ++I) {
+ VNInfo *VNI = *I;
+ if (VNI->isUnused() || VNI->isPHIDef() || VNI->hasPHIKill() ||
+ UsedValues.count(VNI))
continue;
+ MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
+ MI->addRegisterDead(Reg, &TRI);
+ if (!MI->allDefsAreDead())
+ continue;
+ DEBUG(dbgs() << "All defs dead: " << *MI);
+ DeadDefs.push_back(MI);
+ // Remove all Reg references so we don't insert spill code around MI.
+ for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
+ MOE = MI->operands_end(); MOI != MOE ; ++MOI)
+ if (MOI->isReg() && MOI->getReg() == Reg)
+ MOI->setReg(0);
+ VNI->setIsUnused(true);
}
- DEBUG(dbgs() << "Removing debug info due to remat:" << "\t" << *MI);
- MI->eraseFromParent();
}
}
diff --git a/lib/CodeGen/LiveRangeEdit.cpp b/lib/CodeGen/LiveRangeEdit.cpp
index 6b419eb..d1a2faf 100644
--- a/lib/CodeGen/LiveRangeEdit.cpp
+++ b/lib/CodeGen/LiveRangeEdit.cpp
@@ -34,6 +34,16 @@ LiveInterval &LiveRangeEdit::createFrom(unsigned OldReg,
return LI;
}
+void LiveRangeEdit::checkRematerializable(VNInfo *VNI,
+ const MachineInstr *DefMI,
+ const TargetInstrInfo &tii,
+ AliasAnalysis *aa) {
+ assert(DefMI && "Missing instruction");
+ if (tii.isTriviallyReMaterializable(DefMI, aa))
+ remattable_.insert(VNI);
+ scannedRemattable_ = true;
+}
+
void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
const TargetInstrInfo &tii,
AliasAnalysis *aa) {
@@ -45,10 +55,8 @@ void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def);
if (!DefMI)
continue;
- if (tii.isTriviallyReMaterializable(DefMI, aa))
- remattable_.insert(VNI);
+ checkRematerializable(VNI, DefMI, tii, aa);
}
- scannedRemattable_ = true;
}
bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
@@ -69,14 +77,11 @@ bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
UseIdx = UseIdx.getUseIndex();
for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = OrigMI->getOperand(i);
- if (!MO.isReg() || !MO.getReg() || MO.getReg() == getReg())
+ if (!MO.isReg() || !MO.getReg() || MO.isDef())
continue;
// Reserved registers are OK.
if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
continue;
- // We don't want to move any defs.
- if (MO.isDef())
- return false;
// We cannot depend on virtual registers in uselessRegs_.
if (uselessRegs_)
for (unsigned ui = 0, ue = uselessRegs_->size(); ui != ue; ++ui)
@@ -103,16 +108,22 @@ bool LiveRangeEdit::canRematerializeAt(Remat &RM,
if (!remattable_.count(RM.ParentVNI))
return false;
- // No defining instruction.
- RM.OrigMI = lis.getInstructionFromIndex(RM.ParentVNI->def);
- assert(RM.OrigMI && "Defining instruction for remattable value disappeared");
+ // No defining instruction provided.
+ SlotIndex DefIdx;
+ if (RM.OrigMI)
+ DefIdx = lis.getInstructionIndex(RM.OrigMI);
+ else {
+ DefIdx = RM.ParentVNI->def;
+ RM.OrigMI = lis.getInstructionFromIndex(DefIdx);
+ assert(RM.OrigMI && "No defining instruction for remattable value");
+ }
// If only cheap remats were requested, bail out early.
if (cheapAsAMove && !RM.OrigMI->getDesc().isAsCheapAsAMove())
return false;
// Verify that all used registers are available with the same values.
- if (!allUsesAvailableAt(RM.OrigMI, RM.ParentVNI->def, UseIdx, lis))
+ if (!allUsesAvailableAt(RM.OrigMI, DefIdx, UseIdx, lis))
return false;
return true;
diff --git a/lib/CodeGen/LiveRangeEdit.h b/lib/CodeGen/LiveRangeEdit.h
index 0e03137..04eced6 100644
--- a/lib/CodeGen/LiveRangeEdit.h
+++ b/lib/CodeGen/LiveRangeEdit.h
@@ -125,6 +125,11 @@ public:
bool anyRematerializable(LiveIntervals&, const TargetInstrInfo&,
AliasAnalysis*);
+ /// checkRematerializable - Manually add VNI to the list of rematerializable
+ /// values if DefMI may be rematerializable.
+ void checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI,
+ const TargetInstrInfo&, AliasAnalysis*);
+
/// Remat - Information needed to rematerialize at a specific location.
struct Remat {
VNInfo *ParentVNI; // parent_'s value at the remat location.
generated by cgit v1.1 at 2024-12-26 17:44:37 +0000