#define DEBUG_TYPE "pre-alloc-split"
#include "VirtRegMap.h"
+#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
using namespace llvm;
static cl::opt<int> PreSplitLimit("pre-split-limit", cl::init(-1), cl::Hidden);
-static cl::opt<int> DeadSplitLimit("dead-split-limit", cl::init(-1), cl::Hidden);
-static cl::opt<int> RestoreFoldLimit("restore-fold-limit", cl::init(-1), cl::Hidden);
+static cl::opt<int> DeadSplitLimit("dead-split-limit", cl::init(-1),
+ cl::Hidden);
+static cl::opt<int> RestoreFoldLimit("restore-fold-limit", cl::init(-1),
+ cl::Hidden);
STATISTIC(NumSplits, "Number of intervals split");
STATISTIC(NumRemats, "Number of intervals split by rematerialization");
STATISTIC(NumDeadSpills, "Number of dead spills removed");
namespace {
- class VISIBILITY_HIDDEN PreAllocSplitting : public MachineFunctionPass {
+ class PreAllocSplitting : public MachineFunctionPass {
MachineFunction *CurrMF;
const TargetMachine *TM;
const TargetInstrInfo *TII;
const TargetRegisterInfo* TRI;
MachineFrameInfo *MFI;
MachineRegisterInfo *MRI;
+ SlotIndexes *SIs;
LiveIntervals *LIs;
LiveStacks *LSs;
VirtRegMap *VRM;
MachineBasicBlock *BarrierMBB;
// Barrier - Current barrier index.
- LiveIndex BarrierIdx;
+ SlotIndex BarrierIdx;
// CurrLI - Current live interval being split.
LiveInterval *CurrLI;
DenseMap<unsigned, int> IntervalSSMap;
// Def2SpillMap - A map from a def instruction index to spill index.
- DenseMap<LiveIndex, LiveIndex> Def2SpillMap;
+ DenseMap<SlotIndex, SlotIndex> Def2SpillMap;
public:
static char ID;
- PreAllocSplitting() : MachineFunctionPass(&ID) {}
+ PreAllocSplitting()
+ : MachineFunctionPass(&ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- AU.addRequired<LiveIndexes>();
- AU.addPreserved<LiveIndexes>();
+ AU.addRequired<SlotIndexes>();
+ AU.addPreserved<SlotIndexes>();
AU.addRequired<LiveIntervals>();
AU.addPreserved<LiveIntervals>();
AU.addRequired<LiveStacks>();
AU.addPreserved<LiveStacks>();
AU.addPreserved<RegisterCoalescer>();
+ AU.addPreserved<CalculateSpillWeights>();
if (StrongPHIElim)
AU.addPreservedID(StrongPHIEliminationID);
else
private:
- MachineBasicBlock::iterator
- findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
- LiveIndex&);
MachineBasicBlock::iterator
findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
- SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+ SmallPtrSet<MachineInstr*, 4>&);
MachineBasicBlock::iterator
- findRestorePoint(MachineBasicBlock*, MachineInstr*, LiveIndex,
- SmallPtrSet<MachineInstr*, 4>&, LiveIndex&);
+ findRestorePoint(MachineBasicBlock*, MachineInstr*, SlotIndex,
+ SmallPtrSet<MachineInstr*, 4>&);
int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
bool IsAvailableInStack(MachineBasicBlock*, unsigned,
- LiveIndex, LiveIndex,
- LiveIndex&, int&) const;
+ SlotIndex, SlotIndex,
+ SlotIndex&, int&) const;
- void UpdateSpillSlotInterval(VNInfo*, LiveIndex, LiveIndex);
+ void UpdateSpillSlotInterval(VNInfo*, SlotIndex, SlotIndex);
bool SplitRegLiveInterval(LiveInterval*);
bool Rematerialize(unsigned vreg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- LiveIndex RestoreIdx,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB);
MachineInstr* FoldSpill(unsigned vreg, const TargetRegisterClass* RC,
MachineInstr* DefMI,
const PassInfo *const llvm::PreAllocSplittingID = &X;
-
-/// findNextEmptySlot - Find a gap after the given machine instruction in the
-/// instruction index map. If there isn't one, return end().
-MachineBasicBlock::iterator
-PreAllocSplitting::findNextEmptySlot(MachineBasicBlock *MBB, MachineInstr *MI,
- LiveIndex &SpotIndex) {
- MachineBasicBlock::iterator MII = MI;
- if (++MII != MBB->end()) {
- LiveIndex Index =
- LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
- if (Index != LiveIndex()) {
- SpotIndex = Index;
- return MII;
- }
- }
- return MBB->end();
-}
-
/// findSpillPoint - Find a gap as far away from the given MI that's suitable
/// for spilling the current live interval. The index must be before any
/// defs and uses of the live interval register in the mbb. Return begin() if
MachineBasicBlock::iterator
PreAllocSplitting::findSpillPoint(MachineBasicBlock *MBB, MachineInstr *MI,
MachineInstr *DefMI,
- SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
- LiveIndex &SpillIndex) {
+ SmallPtrSet<MachineInstr*, 4> &RefsInMBB) {
MachineBasicBlock::iterator Pt = MBB->begin();
MachineBasicBlock::iterator MII = MI;
if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
while (MII != EndPt && !RefsInMBB.count(MII)) {
- LiveIndex Index = LIs->getInstructionIndex(MII);
-
// We can't insert the spill between the barrier (a call), and its
// corresponding call frame setup.
if (MII->getOpcode() == TRI->getCallFrameDestroyOpcode()) {
}
}
continue;
- } else if (LIs->hasGapBeforeInstr(Index)) {
+ } else {
Pt = MII;
- SpillIndex = LIs->findGapBeforeInstr(Index, true);
}
if (RefsInMBB.count(MII))
/// found.
MachineBasicBlock::iterator
PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
- LiveIndex LastIdx,
- SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
- LiveIndex &RestoreIndex) {
+ SlotIndex LastIdx,
+ SmallPtrSet<MachineInstr*, 4> &RefsInMBB) {
// FIXME: Allow spill to be inserted to the beginning of the mbb. Update mbb
// begin index accordingly.
MachineBasicBlock::iterator Pt = MBB->end();
// FIXME: Limit the number of instructions to examine to reduce
// compile time?
while (MII != EndPt) {
- LiveIndex Index = LIs->getInstructionIndex(MII);
+ SlotIndex Index = LIs->getInstructionIndex(MII);
if (Index > LastIdx)
break;
- LiveIndex Gap = LIs->findGapBeforeInstr(Index);
// We can't insert a restore between the barrier (a call) and its
// corresponding call frame teardown.
if (MII == EndPt || RefsInMBB.count(MII)) return Pt;
++MII;
} while (MII->getOpcode() != TRI->getCallFrameDestroyOpcode());
- } else if (Gap != LiveIndex()) {
+ } else {
Pt = MII;
- RestoreIndex = Gap;
}
if (RefsInMBB.count(MII))
if (I != IntervalSSMap.end()) {
SS = I->second;
} else {
- SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
+ SS = MFI->CreateSpillStackObject(RC->getSize(), RC->getAlignment());
IntervalSSMap[Reg] = SS;
}
if (CurrSLI->hasAtLeastOneValue())
CurrSValNo = CurrSLI->getValNumInfo(0);
else
- CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+ CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
LSs->getVNInfoAllocator());
return SS;
}
/// slot at the specified index.
bool
PreAllocSplitting::IsAvailableInStack(MachineBasicBlock *DefMBB,
- unsigned Reg, LiveIndex DefIndex,
- LiveIndex RestoreIndex,
- LiveIndex &SpillIndex,
+ unsigned Reg, SlotIndex DefIndex,
+ SlotIndex RestoreIndex,
+ SlotIndex &SpillIndex,
int& SS) const {
if (!DefMBB)
return false;
- DenseMap<unsigned, int>::iterator I = IntervalSSMap.find(Reg);
+ DenseMap<unsigned, int>::const_iterator I = IntervalSSMap.find(Reg);
if (I == IntervalSSMap.end())
return false;
- DenseMap<LiveIndex, LiveIndex>::iterator
+ DenseMap<SlotIndex, SlotIndex>::const_iterator
II = Def2SpillMap.find(DefIndex);
if (II == Def2SpillMap.end())
return false;
/// interval being split, and the spill and restore indicies, update the live
/// interval of the spill stack slot.
void
-PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, LiveIndex SpillIndex,
- LiveIndex RestoreIndex) {
+PreAllocSplitting::UpdateSpillSlotInterval(VNInfo *ValNo, SlotIndex SpillIndex,
+ SlotIndex RestoreIndex) {
assert(LIs->getMBBFromIndex(RestoreIndex) == BarrierMBB &&
"Expect restore in the barrier mbb");
}
SmallPtrSet<MachineBasicBlock*, 4> Processed;
- LiveIndex EndIdx = LIs->getMBBEndIdx(MBB);
+ SlotIndex EndIdx = LIs->getMBBEndIdx(MBB);
LiveRange SLR(SpillIndex, EndIdx.getNextSlot(), CurrSValNo);
CurrSLI->addRange(SLR);
Processed.insert(MBB);
WorkList.pop_back();
if (Processed.count(MBB))
continue;
- LiveIndex Idx = LIs->getMBBStartIdx(MBB);
+ SlotIndex Idx = LIs->getMBBStartIdx(MBB);
LR = CurrLI->getLiveRangeContaining(Idx);
if (LR && LR->valno == ValNo) {
EndIdx = LIs->getMBBEndIdx(MBB);
}
// Once we've found it, extend its VNInfo to our instruction.
- LiveIndex DefIndex = LIs->getInstructionIndex(Walker);
+ SlotIndex DefIndex = LIs->getInstructionIndex(Walker);
DefIndex = DefIndex.getDefIndex();
- LiveIndex EndIndex = LIs->getMBBEndIdx(MBB);
+ SlotIndex EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = NewVNs[Walker];
LI->addRange(LiveRange(DefIndex, EndIndex.getNextSlot(), RetVNI));
IsTopLevel, IsIntraBlock);
}
- LiveIndex UseIndex = LIs->getInstructionIndex(Walker);
+ SlotIndex UseIndex = LIs->getInstructionIndex(Walker);
UseIndex = UseIndex.getUseIndex();
- LiveIndex EndIndex;
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
EndIndex = EndIndex.getUseIndex();
IsTopLevel, IsIntraBlock);
}
- LiveIndex StartIndex = LIs->getInstructionIndex(Walker);
+ SlotIndex StartIndex = LIs->getInstructionIndex(Walker);
StartIndex = foundDef ? StartIndex.getDefIndex() : StartIndex.getUseIndex();
- LiveIndex EndIndex;
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
EndIndex = EndIndex.getUseIndex();
// assume that we are not intrablock here.
if (Phis.count(MBB)) return Phis[MBB];
- LiveIndex StartIndex = LIs->getMBBStartIdx(MBB);
+ SlotIndex StartIndex = LIs->getMBBStartIdx(MBB);
VNInfo *RetVNI = Phis[MBB] =
- LI->getNextValue(LiveIndex(), /*FIXME*/ 0, false,
+ LI->getNextValue(SlotIndex(), /*FIXME*/ 0, false,
LIs->getVNInfoAllocator());
if (!IsIntraBlock) LiveOut[MBB] = RetVNI;
for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I =
IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) {
I->second->setHasPHIKill(true);
- LiveIndex KillIndex = LIs->getMBBEndIdx(I->first);
+ SlotIndex KillIndex = LIs->getMBBEndIdx(I->first);
if (!I->second->isKill(KillIndex))
I->second->addKill(KillIndex);
}
}
- LiveIndex EndIndex;
+ SlotIndex EndIndex;
if (IsIntraBlock) {
EndIndex = LIs->getInstructionIndex(UseI);
EndIndex = EndIndex.getUseIndex();
DE = MRI->def_end(); DI != DE; ++DI) {
Defs[(*DI).getParent()].insert(&*DI);
- LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
+ SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
DefIdx = DefIdx.getDefIndex();
assert(DI->getOpcode() != TargetInstrInfo::PHI &&
- "Following NewVN isPHIDef flag incorrect. Fix me!");
+ "PHI instr in code during pre-alloc splitting.");
VNInfo* NewVN = LI->getNextValue(DefIdx, 0, true, Alloc);
// If the def is a move, set the copy field.
// Add ranges for dead defs
for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(LI->reg),
DE = MRI->def_end(); DI != DE; ++DI) {
- LiveIndex DefIdx = LIs->getInstructionIndex(&*DI);
+ SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
DefIdx = DefIdx.getDefIndex();
if (LI->liveAt(DefIdx)) continue;
VI != VE; ++VI) {
VNInfo* VNI = *VI;
for (unsigned i = 0, e = VNI->kills.size(); i != e; ++i) {
- LiveIndex KillIdx = VNI->kills[i];
+ SlotIndex KillIdx = VNI->kills[i];
if (KillIdx.isPHI())
continue;
MachineInstr *KillMI = LIs->getInstructionFromIndex(KillIdx);
for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(CurrLI->reg),
E = MRI->reg_end(); I != E; ++I) {
MachineOperand& MO = I.getOperand();
- LiveIndex InstrIdx = LIs->getInstructionIndex(&*I);
+ SlotIndex InstrIdx = LIs->getInstructionIndex(&*I);
if ((MO.isUse() && NewLI.liveAt(InstrIdx.getUseIndex())) ||
(MO.isDef() && NewLI.liveAt(InstrIdx.getDefIndex())))
bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- LiveIndex RestoreIdx,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
MachineBasicBlock& MBB = *RestorePt->getParent();
MachineBasicBlock::iterator KillPt = BarrierMBB->end();
- LiveIndex KillIdx;
if (!ValNo->isDefAccurate() || DefMI->getParent() == BarrierMBB)
- KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, KillIdx);
+ KillPt = findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB);
else
- KillPt = findNextEmptySlot(DefMI->getParent(), DefMI, KillIdx);
+ KillPt = llvm::next(MachineBasicBlock::iterator(DefMI));
if (KillPt == DefMI->getParent()->end())
return false;
- TII->reMaterialize(MBB, RestorePt, VReg, 0, DefMI);
- LIs->InsertMachineInstrInMaps(prior(RestorePt), RestoreIdx);
+ TII->reMaterialize(MBB, RestorePt, VReg, 0, DefMI, TRI);
+ SlotIndex RematIdx = LIs->InsertMachineInstrInMaps(prior(RestorePt));
ReconstructLiveInterval(CurrLI);
- LiveIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
RematIdx = RematIdx.getDefIndex();
RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx));
if (I != IntervalSSMap.end()) {
SS = I->second;
} else {
- SS = MFI->CreateStackObject(RC->getSize(), RC->getAlignment());
+ SS = MFI->CreateSpillStackObject(RC->getSize(), RC->getAlignment());
}
MachineInstr* FMI = TII->foldMemoryOperand(*MBB->getParent(),
if (CurrSLI->hasAtLeastOneValue())
CurrSValNo = CurrSLI->getValNumInfo(0);
else
- CurrSValNo = CurrSLI->getNextValue(LiveIndex(), 0, false,
+ CurrSValNo = CurrSLI->getNextValue(SlotIndex(), 0, false,
LSs->getVNInfoAllocator());
}
}
// Find a point to restore the value after the barrier.
- LiveIndex RestoreIndex;
MachineBasicBlock::iterator RestorePt =
- findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB, RestoreIndex);
+ findRestorePoint(BarrierMBB, Barrier, LR->end, RefsInMBB);
if (RestorePt == BarrierMBB->end()) {
DEBUG(errs() << "FAILED (could not find a suitable restore point).\n");
return false;
}
if (DefMI && LIs->isReMaterializable(*LI, ValNo, DefMI))
- if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt,
- RestoreIndex, RefsInMBB)) {
+ if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt, RefsInMBB)) {
DEBUG(errs() << "success (remat).\n");
return true;
}
// Add a spill either before the barrier or after the definition.
MachineBasicBlock *DefMBB = DefMI ? DefMI->getParent() : NULL;
const TargetRegisterClass *RC = MRI->getRegClass(CurrLI->reg);
- LiveIndex SpillIndex;
+ SlotIndex SpillIndex;
MachineInstr *SpillMI = NULL;
int SS = -1;
if (!ValNo->isDefAccurate()) {
SpillIndex = LIs->getInstructionIndex(SpillMI);
} else {
MachineBasicBlock::iterator SpillPt =
- findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB, SpillIndex);
+ findSpillPoint(BarrierMBB, Barrier, NULL, RefsInMBB);
if (SpillPt == BarrierMBB->begin()) {
DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
SS = CreateSpillStackSlot(CurrLI->reg, RC);
TII->storeRegToStackSlot(*BarrierMBB, SpillPt, CurrLI->reg, true, SS, RC);
SpillMI = prior(SpillPt);
- LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
+ SpillIndex = LIs->InsertMachineInstrInMaps(SpillMI);
}
} else if (!IsAvailableInStack(DefMBB, CurrLI->reg, ValNo->def,
- RestoreIndex, SpillIndex, SS)) {
+ LIs->getZeroIndex(), SpillIndex, SS)) {
// If it's already split, just restore the value. There is no need to spill
// the def again.
if (!DefMI) {
if (DefMBB == BarrierMBB) {
// Add spill after the def and the last use before the barrier.
SpillPt = findSpillPoint(BarrierMBB, Barrier, DefMI,
- RefsInMBB, SpillIndex);
+ RefsInMBB);
if (SpillPt == DefMBB->begin()) {
DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
}
} else {
- SpillPt = findNextEmptySlot(DefMBB, DefMI, SpillIndex);
+ SpillPt = llvm::next(MachineBasicBlock::iterator(DefMI));
if (SpillPt == DefMBB->end()) {
DEBUG(errs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
SS = CreateSpillStackSlot(CurrLI->reg, RC);
TII->storeRegToStackSlot(*DefMBB, SpillPt, CurrLI->reg, false, SS, RC);
SpillMI = prior(SpillPt);
- LIs->InsertMachineInstrInMaps(SpillMI, SpillIndex);
+ SpillIndex = LIs->InsertMachineInstrInMaps(SpillMI);
}
}
// Add restore.
bool FoldedRestore = false;
+ SlotIndex RestoreIndex;
if (MachineInstr* LMI = FoldRestore(CurrLI->reg, RC, Barrier,
BarrierMBB, SS, RefsInMBB)) {
RestorePt = LMI;
} else {
TII->loadRegFromStackSlot(*BarrierMBB, RestorePt, CurrLI->reg, SS, RC);
MachineInstr *LoadMI = prior(RestorePt);
- LIs->InsertMachineInstrInMaps(LoadMI, RestoreIndex);
+ RestoreIndex = LIs->InsertMachineInstrInMaps(LoadMI);
}
// Update spill stack slot live interval.
ReconstructLiveInterval(CurrLI);
if (!FoldedRestore) {
- LiveIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
+ SlotIndex RestoreIdx = LIs->getInstructionIndex(prior(RestorePt));
RestoreIdx = RestoreIdx.getDefIndex();
RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RestoreIdx));
}
// reaching definition (VNInfo).
for (MachineRegisterInfo::use_iterator UI = MRI->use_begin((*LI)->reg),
UE = MRI->use_end(); UI != UE; ++UI) {
- LiveIndex index = LIs->getInstructionIndex(&*UI);
+ SlotIndex index = LIs->getInstructionIndex(&*UI);
index = index.getUseIndex();
const LiveRange* LR = (*LI)->getLiveRangeContaining(index);
// Otherwise, this is a load-store case, so DCE them.
for (SmallPtrSet<MachineInstr*, 4>::iterator UI =
VNUseCount[CurrVN].begin(), UE = VNUseCount[CurrVN].end();
- UI != UI; ++UI) {
+ UI != UE; ++UI) {
LIs->RemoveMachineInstrFromMaps(*UI);
(*UI)->eraseFromParent();
}
if (LR->valno->hasPHIKill())
return false;
- LiveIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
+ SlotIndex MBBEnd = LIs->getMBBEndIdx(BarrierMBB);
if (LR->end < MBBEnd)
return false;
TII = TM->getInstrInfo();
MFI = MF.getFrameInfo();
MRI = &MF.getRegInfo();
+ SIs = &getAnalysis<SlotIndexes>();
LIs = &getAnalysis<LiveIntervals>();
LSs = &getAnalysis<LiveStacks>();
VRM = &getAnalysis<VirtRegMap>();
projects / oota-llvm.git / blobdiff