#define DEBUG_TYPE "regalloc"
#include "Spiller.h"
#include "LiveRangeEdit.h"
#include "VirtRegMap.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace {
class InlineSpiller : public Spiller {
MachineFunctionPass &Pass;
MachineFunction &MF;
LiveIntervals &LIS;
LiveStacks &LSS;
AliasAnalysis *AA;
MachineDominatorTree &MDT;
MachineLoopInfo &Loops;
VirtRegMap &VRM;
MachineFrameInfo &MFI;
MachineRegisterInfo &MRI;
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
LiveRangeEdit *Edit;
LiveInterval *StackInt;
int StackSlot;
unsigned Original;
SmallVector<unsigned, 8> RegsToSpill;
SmallPtrSet<MachineInstr*, 8> SnippetCopies;
SmallPtrSet<VNInfo*, 8> UsedValues;
struct SibValueInfo {
bool AllDefsAreReloads;
unsigned SpillReg;
VNInfo *SpillVNI;
MachineInstr *DefMI;
SibValueInfo(unsigned Reg, VNInfo *VNI)
: AllDefsAreReloads(false), SpillReg(Reg), SpillVNI(VNI), DefMI(0) {}
};
typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
SibValueMap SibValues;
SmallVector<MachineInstr*, 8> DeadDefs;
~InlineSpiller() {}
public:
InlineSpiller(MachineFunctionPass &pass,
MachineFunction &mf,
VirtRegMap &vrm)
: Pass(pass),
MF(mf),
LIS(pass.getAnalysis<LiveIntervals>()),
LSS(pass.getAnalysis<LiveStacks>()),
AA(&pass.getAnalysis<AliasAnalysis>()),
MDT(pass.getAnalysis<MachineDominatorTree>()),
Loops(pass.getAnalysis<MachineLoopInfo>()),
VRM(vrm),
MFI(*mf.getFrameInfo()),
MRI(mf.getRegInfo()),
TII(*mf.getTarget().getInstrInfo()),
TRI(*mf.getTarget().getRegisterInfo()) {}
void spill(LiveRangeEdit &);
private:
bool isSnippet(const LiveInterval &SnipLI);
void collectRegsToSpill();
bool isRegToSpill(unsigned Reg) {
return std::find(RegsToSpill.begin(),
RegsToSpill.end(), Reg) != RegsToSpill.end();
}
bool isSibling(unsigned Reg);
MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
void analyzeSiblingValues();
bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
void markValueUsed(LiveInterval*, VNInfo*);
bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI);
void reMaterializeAll();
bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
bool foldMemoryOperand(MachineBasicBlock::iterator MI,
const SmallVectorImpl<unsigned> &Ops,
MachineInstr *LoadMI = 0);
void insertReload(LiveInterval &NewLI, SlotIndex,
MachineBasicBlock::iterator MI);
void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
SlotIndex, MachineBasicBlock::iterator MI);
void spillAroundUses(unsigned Reg);
void spillAll();
};
}
namespace llvm {
Spiller *createInlineSpiller(MachineFunctionPass &pass,
MachineFunction &mf,
VirtRegMap &vrm) {
return new InlineSpiller(pass, mf, vrm);
}
}
static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) {
if (!MI->isCopy())
return 0;
if (MI->getOperand(0).getSubReg() != 0)
return 0;
if (MI->getOperand(1).getSubReg() != 0)
return 0;
if (MI->getOperand(0).getReg() == Reg)
return MI->getOperand(1).getReg();
if (MI->getOperand(1).getReg() == Reg)
return MI->getOperand(0).getReg();
return 0;
}
bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
unsigned Reg = Edit->getReg();
if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
return false;
MachineInstr *UseMI = 0;
for (MachineRegisterInfo::reg_nodbg_iterator
RI = MRI.reg_nodbg_begin(SnipLI.reg);
MachineInstr *MI = RI.skipInstruction();) {
if (isFullCopyOf(MI, Reg))
continue;
int FI;
if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
continue;
if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
continue;
if (UseMI && MI != UseMI)
return false;
UseMI = MI;
}
return true;
}
void InlineSpiller::collectRegsToSpill() {
unsigned Reg = Edit->getReg();
RegsToSpill.assign(1, Reg);
SnippetCopies.clear();
if (Original == Reg)
return;
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
MachineInstr *MI = RI.skipInstruction();) {
unsigned SnipReg = isFullCopyOf(MI, Reg);
if (!isSibling(SnipReg))
continue;
LiveInterval &SnipLI = LIS.getInterval(SnipReg);
if (!isSnippet(SnipLI))
continue;
SnippetCopies.insert(MI);
if (!isRegToSpill(SnipReg))
RegsToSpill.push_back(SnipReg);
DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
}
}
bool InlineSpiller::isSibling(unsigned Reg) {
return TargetRegisterInfo::isVirtualRegister(Reg) &&
VRM.getOriginal(Reg) == Original;
}
MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
VNInfo *OrigVNI) {
DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
<< UseVNI->id << '@' << UseVNI->def << '\n');
SmallPtrSet<VNInfo*, 8> Visited;
SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList;
WorkList.push_back(std::make_pair(UseReg, UseVNI));
SibValueInfo SVI(UseReg, UseVNI);
MachineBasicBlock *UseMBB = LIS.getMBBFromIndex(UseVNI->def);
unsigned SpillDepth = Loops.getLoopDepth(UseMBB);
bool SeenOrigPHI = false;
do {
unsigned Reg;
VNInfo *VNI;
tie(Reg, VNI) = WorkList.pop_back_val();
if (!Visited.insert(VNI))
continue;
if (!isRegToSpill(Reg)) {
MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
if (MBB != UseMBB && MDT.dominates(MBB, UseMBB)) {
unsigned Depth = Loops.getLoopDepth(MBB);
if (Depth < SpillDepth) {
DEBUG(dbgs() << " spill depth " << Depth << ": " << PrintReg(Reg)
<< ':' << VNI->id << '@' << VNI->def << '\n');
SVI.SpillReg = Reg;
SVI.SpillVNI = VNI;
SpillDepth = Depth;
}
}
}
if (VNI->isPHIDef()) {
if (VNI->def == OrigVNI->def) {
DEBUG(dbgs() << " orig phi value " << PrintReg(Reg) << ':'
<< VNI->id << '@' << VNI->def << '\n');
SeenOrigPHI = true;
continue;
}
LiveInterval &LI = LIS.getInterval(Reg);
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(Reg, PVNI));
}
continue;
}
MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
assert(MI && "Missing def");
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");
DEBUG(dbgs() << " copy of " << PrintReg(SrcReg) << ':'
<< SrcVNI->id << '@' << SrcVNI->def << '\n');
WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
continue;
}
}
int FI;
if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) {
DEBUG(dbgs() << " reload " << PrintReg(Reg) << ':'
<< VNI->id << "@" << VNI->def << '\n');
SVI.AllDefsAreReloads = true;
continue;
}
if (VNI == UseVNI) {
DEBUG(dbgs() << "Not a sibling copy.\n");
return MI;
}
DEBUG(dbgs() << " def " << PrintReg(Reg) << ':'
<< VNI->id << '@' << VNI->def << '\t' << *MI);
SVI.DefMI = MI;
} while (!WorkList.empty());
if (SeenOrigPHI || SVI.DefMI)
SVI.AllDefsAreReloads = false;
DEBUG({
if (SVI.AllDefsAreReloads)
dbgs() << "All defs are reloads.\n";
else
dbgs() << "Prefer to spill " << PrintReg(SVI.SpillReg) << ':'
<< SVI.SpillVNI->id << '@' << SVI.SpillVNI->def << '\n';
});
SibValues.insert(std::make_pair(UseVNI, SVI));
return SVI.DefMI;
}
void InlineSpiller::analyzeSiblingValues() {
SibValues.clear();
if (Edit->getReg() == Original)
return;
LiveInterval &OrigLI = LIS.getInterval(Original);
for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
unsigned Reg = RegsToSpill[i];
LiveInterval &LI = LIS.getInterval(Reg);
for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
VE = LI.vni_end(); VI != VE; ++VI) {
VNInfo *VNI = *VI;
if (VNI->isUnused())
continue;
MachineInstr *DefMI = 0;
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)) {
DEBUG(dbgs() << "Value " << PrintReg(Reg) << ':' << VNI->id << '@'
<< VNI->def << " may remat from " << *DefMI);
}
}
}
}
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");
SibValueMap::iterator I = SibValues.find(VNI);
if (I == SibValues.end())
return false;
const SibValueInfo &SVI = I->second;
if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI)
return false;
if (!LIS.hasInterval(SVI.SpillReg)) {
DEBUG(dbgs() << "Stale interval: " << PrintReg(SVI.SpillReg) << '\n');
SibValues.erase(I);
return false;
}
LiveInterval &SibLI = LIS.getInterval(SVI.SpillReg);
if (!SibLI.containsValue(SVI.SpillVNI)) {
DEBUG(dbgs() << "Stale value: " << PrintReg(SVI.SpillReg) << '\n');
SibValues.erase(I);
return false;
}
assert(StackInt && "No stack slot assigned yet.");
LiveInterval &OrigLI = LIS.getInterval(Original);
VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
<< *StackInt << '\n');
if (SVI.AllDefsAreReloads)
return true;
eliminateRedundantSpills(SibLI, SVI.SpillVNI);
MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def);
MachineBasicBlock::iterator MII;
if (SVI.SpillVNI->isPHIDef())
MII = MBB->SkipPHIsAndLabels(MBB->begin());
else {
MachineInstr *DefMI = LIS.getInstructionFromIndex(SVI.SpillVNI->def);
assert(DefMI && "Defining instruction disappeared");
MII = DefMI;
++MII;
}
TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot,
MRI.getRegClass(SVI.SpillReg), &TRI);
--MII; LIS.InsertMachineInstrInMaps(MII);
VRM.addSpillSlotUse(StackSlot, MII);
DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII);
return true;
}
void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
assert(VNI && "Missing value");
SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
WorkList.push_back(std::make_pair(&SLI, VNI));
assert(StackInt && "No stack slot assigned yet.");
do {
LiveInterval *LI;
tie(LI, VNI) = WorkList.pop_back_val();
unsigned Reg = LI->reg;
DEBUG(dbgs() << "Checking redundant spills for "
<< VNI->id << '@' << VNI->def << " in " << *LI << '\n');
if (isRegToSpill(Reg))
continue;
StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg);
MachineInstr *MI = UI.skipInstruction();) {
if (!MI->isCopy() && !MI->getDesc().mayStore())
continue;
SlotIndex Idx = LIS.getInstructionIndex(MI);
if (LI->getVNInfoAt(Idx) != VNI)
continue;
if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
if (isSibling(DstReg)) {
LiveInterval &DstLI = LIS.getInterval(DstReg);
VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getDefIndex());
assert(DstVNI && "Missing defined value");
assert(DstVNI->def == Idx.getDefIndex() && "Wrong copy def slot");
WorkList.push_back(std::make_pair(&DstLI, DstVNI));
}
continue;
}
int FI;
if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI);
MI->setDesc(TII.get(TargetOpcode::KILL));
DeadDefs.push_back(MI);
}
}
} while (!WorkList.empty());
}
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;
}
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());
}
bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg,
MachineBasicBlock::iterator MI) {
SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex();
VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx);
if (!ParentVNI) {
DEBUG(dbgs() << "\tadding <undef> flags: ");
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg)
MO.setIsUndef();
}
DEBUG(dbgs() << UseIdx << '\t' << *MI);
return true;
}
if (SnippetCopies.count(MI))
return false;
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)) {
markValueUsed(&VirtReg, ParentVNI);
DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
return false;
}
bool Reads, Writes;
SmallVector<unsigned, 8> 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 (RM.OrigMI->getDesc().canFoldAsLoad() &&
foldMemoryOperand(MI, Ops, RM.OrigMI)) {
Edit->markRematerialized(RM.ParentVNI);
return true;
}
LiveInterval &NewLI = Edit->createFrom(Original, LIS, VRM);
NewLI.markNotSpillable();
SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM,
LIS, TII, TRI);
DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
<< *LIS.getInstructionFromIndex(DefIdx));
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(Ops[i]);
if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) {
MO.setReg(NewLI.reg);
MO.setIsKill();
}
}
DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI);
VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator());
NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
return true;
}
void InlineSpiller::reMaterializeAll() {
if (!Edit->anyRematerializable(LIS, TII, AA))
return;
UsedValues.clear();
bool anyRemat = false;
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;
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() || 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);
}
}
if (DeadDefs.empty())
return;
DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII);
for (unsigned i = RegsToSpill.size(); i != 0; --i) {
unsigned Reg = RegsToSpill[i-1];
if (!LIS.hasInterval(Reg)) {
RegsToSpill.erase(RegsToSpill.begin() + (i - 1));
continue;
}
LiveInterval &LI = LIS.getInterval(Reg);
if (!LI.empty())
continue;
Edit->eraseVirtReg(Reg, LIS);
RegsToSpill.erase(RegsToSpill.begin() + (i - 1));
}
DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n");
}
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;
if (InstrReg != Reg || FI != StackSlot)
return false;
DEBUG(dbgs() << "Coalescing stack access: " << *MI);
LIS.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
return true;
}
bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
const SmallVectorImpl<unsigned> &Ops,
MachineInstr *LoadMI) {
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())
continue;
if (MO.getSubReg())
return false;
if (LoadMI && MO.isDef())
return false;
if (!MI->isRegTiedToDefOperand(Idx))
FoldOps.push_back(Idx);
}
MachineInstr *FoldMI =
LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI)
: TII.foldMemoryOperand(MI, FoldOps, StackSlot);
if (!FoldMI)
return false;
LIS.ReplaceMachineInstrInMaps(MI, FoldMI);
if (!LoadMI)
VRM.addSpillSlotUse(StackSlot, FoldMI);
MI->eraseFromParent();
DEBUG(dbgs() << "\tfolded: " << *FoldMI);
return true;
}
void InlineSpiller::insertReload(LiveInterval &NewLI,
SlotIndex Idx,
MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();
TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot,
MRI.getRegClass(NewLI.reg), &TRI);
--MI; 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));
}
void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
SlotIndex Idx, MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();
TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot,
MRI.getRegClass(NewLI.reg), &TRI);
--MI; 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));
}
void InlineSpiller::spillAroundUses(unsigned Reg) {
LiveInterval &OldLI = LIS.getInterval(Reg);
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
MachineInstr *MI = RI.skipInstruction();) {
if (MI->isDebugValue()) {
uint64_t Offset = MI->getOperand(1).getImm();
const MDNode *MDPtr = MI->getOperand(2).getMetadata();
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();
}
continue;
}
if (SnippetCopies.count(MI))
continue;
if (coalesceStackAccess(MI, Reg))
continue;
bool Reads, Writes;
SmallVector<unsigned, 8> Ops;
tie(Reads, Writes) = MI->readsWritesVirtualRegister(Reg, &Ops);
SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getUseIndex()))
if (SlotIndex::isSameInstr(Idx, VNI->def))
Idx = VNI->def;
unsigned SibReg = isFullCopyOf(MI, Reg);
if (SibReg && isSibling(SibReg)) {
if (Writes) {
if (hoistSpill(OldLI, MI)) {
MI->getOperand(0).setIsDead();
DeadDefs.push_back(MI);
continue;
}
} else {
LiveInterval &SibLI = LIS.getInterval(SibReg);
eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
}
}
if (foldMemoryOperand(MI, Ops))
continue;
LiveInterval &NewLI = Edit->createFrom(Reg, LIS, VRM);
NewLI.markNotSpillable();
if (Reads)
insertReload(NewLI, Idx, MI);
bool hasLiveDef = false;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(Ops[i]);
MO.setReg(NewLI.reg);
if (MO.isUse()) {
if (!MI->isRegTiedToDefOperand(Ops[i]))
MO.setIsKill();
} else {
if (!MO.isDead())
hasLiveDef = true;
}
}
DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI);
if (Writes && hasLiveDef)
insertSpill(NewLI, OldLI, Idx, MI);
DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
}
}
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());
} else
StackInt = &LSS.getInterval(StackSlot);
if (Original != Edit->getReg())
VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
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));
DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
spillAroundUses(RegsToSpill[i]);
if (!DeadDefs.empty()) {
DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII);
}
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg());
MachineInstr *MI = RI.skipInstruction();) {
assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy");
VRM.RemoveMachineInstrFromMaps(MI);
LIS.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
}
for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
Edit->eraseVirtReg(RegsToSpill[i], LIS);
}
void InlineSpiller::spill(LiveRangeEdit &edit) {
Edit = &edit;
assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
&& "Trying to spill a stack slot.");
Original = VRM.getOriginal(edit.getReg());
StackSlot = VRM.getStackSlot(Original);
StackInt = 0;
DEBUG(dbgs() << "Inline spilling "
<< MRI.getRegClass(edit.getReg())->getName()
<< ':' << edit.getParent() << "\nFrom original "
<< LIS.getInterval(Original) << '\n');
assert(edit.getParent().isSpillable() &&
"Attempting to spill already spilled value.");
assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
collectRegsToSpill();
analyzeSiblingValues();
reMaterializeAll();
if (!RegsToSpill.empty())
spillAll();
Edit->calculateRegClassAndHint(MF, LIS, Loops);
}