#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");
AU.addRequired<LiveStacks>();
AU.addPreserved<LiveStacks>();
AU.addPreserved<RegisterCoalescer>();
+ AU.addPreserved<CalculateSpillWeights>();
if (StrongPHIElim)
AU.addPreservedID(StrongPHIEliminationID);
else
private:
- MachineBasicBlock::iterator
- findNextEmptySlot(MachineBasicBlock*, MachineInstr*,
- SlotIndex&);
MachineBasicBlock::iterator
findSpillPoint(MachineBasicBlock*, MachineInstr*, MachineInstr*,
- SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
+ SmallPtrSet<MachineInstr*, 4>&);
MachineBasicBlock::iterator
findRestorePoint(MachineBasicBlock*, MachineInstr*, SlotIndex,
- SmallPtrSet<MachineInstr*, 4>&, SlotIndex&);
+ SmallPtrSet<MachineInstr*, 4>&);
int CreateSpillStackSlot(unsigned, const TargetRegisterClass *);
bool Rematerialize(unsigned vreg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- SlotIndex 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,
- SlotIndex &SpotIndex) {
- MachineBasicBlock::iterator MII = MI;
- if (++MII != MBB->end()) {
- SlotIndex Index =
- LIs->findGapBeforeInstr(LIs->getInstructionIndex(MII));
- if (Index != SlotIndex()) {
- 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,
- SlotIndex &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)) {
- SlotIndex 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))
MachineBasicBlock::iterator
PreAllocSplitting::findRestorePoint(MachineBasicBlock *MBB, MachineInstr *MI,
SlotIndex LastIdx,
- SmallPtrSet<MachineInstr*, 4> &RefsInMBB,
- SlotIndex &RestoreIndex) {
+ 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();
SlotIndex Index = LIs->getInstructionIndex(MII);
if (Index > LastIdx)
break;
- SlotIndex 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 != SlotIndex()) {
+ } 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 (!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<SlotIndex, SlotIndex>::iterator
+ DenseMap<SlotIndex, SlotIndex>::const_iterator
II = Def2SpillMap.find(DefIndex);
if (II == Def2SpillMap.end())
return false;
SmallPtrSet<MachineBasicBlock*, 4> Processed;
SlotIndex EndIdx = LIs->getMBBEndIdx(MBB);
- LiveRange SLR(SpillIndex, EndIdx.getNextSlot(), CurrSValNo);
+ LiveRange SLR(SpillIndex, EndIdx, CurrSValNo);
CurrSLI->addRange(SLR);
Processed.insert(MBB);
SlotIndex EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = NewVNs[Walker];
- LI->addRange(LiveRange(DefIndex, EndIndex.getNextSlot(), RetVNI));
+ LI->addRange(LiveRange(DefIndex, EndIndex, RetVNI));
} else if (!ContainsDefs && ContainsUses) {
SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
// Search for the use in this block that precedes the instruction we care
// about, going to the fallback case if we don't find it.
- if (UseI == MBB->begin())
- return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs,
- Uses, NewVNs, LiveOut, Phis,
- IsTopLevel, IsIntraBlock);
-
MachineBasicBlock::iterator Walker = UseI;
- --Walker;
bool found = false;
while (Walker != MBB->begin()) {
+ --Walker;
if (BlockUses.count(Walker)) {
found = true;
break;
}
- --Walker;
- }
-
- // Must check begin() too.
- if (!found) {
- if (BlockUses.count(Walker))
- found = true;
- else
- return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs,
- Uses, NewVNs, LiveOut, Phis,
- IsTopLevel, IsIntraBlock);
}
+ if (!found)
+ return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs,
+ Uses, NewVNs, LiveOut, Phis,
+ IsTopLevel, IsIntraBlock);
+
SlotIndex UseIndex = LIs->getInstructionIndex(Walker);
UseIndex = UseIndex.getUseIndex();
SlotIndex EndIndex;
if (IsIntraBlock) {
- EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = EndIndex.getUseIndex();
+ EndIndex = LIs->getInstructionIndex(UseI).getDefIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
NewVNs, LiveOut, Phis, false, true);
- LI->addRange(LiveRange(UseIndex, EndIndex.getNextSlot(), RetVNI));
+ LI->addRange(LiveRange(UseIndex, EndIndex, RetVNI));
// FIXME: Need to set kills properly for inter-block stuff.
if (RetVNI->isKill(UseIndex)) RetVNI->removeKill(UseIndex);
// This case is basically a merging of the two preceding case, with the
// special note that checking for defs must take precedence over checking
// for uses, because of two-address instructions.
-
- if (UseI == MBB->begin())
- return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs, Uses,
- NewVNs, LiveOut, Phis,
- IsTopLevel, IsIntraBlock);
-
MachineBasicBlock::iterator Walker = UseI;
- --Walker;
bool foundDef = false;
bool foundUse = false;
while (Walker != MBB->begin()) {
+ --Walker;
if (BlockDefs.count(Walker)) {
foundDef = true;
break;
foundUse = true;
break;
}
- --Walker;
- }
-
- // Must check begin() too.
- if (!foundDef && !foundUse) {
- if (BlockDefs.count(Walker))
- foundDef = true;
- else if (BlockUses.count(Walker))
- foundUse = true;
- else
- return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs,
- Uses, NewVNs, LiveOut, Phis,
- IsTopLevel, IsIntraBlock);
}
+ if (!foundDef && !foundUse)
+ return PerformPHIConstructionFallBack(UseI, MBB, LI, Visited, Defs,
+ Uses, NewVNs, LiveOut, Phis,
+ IsTopLevel, IsIntraBlock);
+
SlotIndex StartIndex = LIs->getInstructionIndex(Walker);
StartIndex = foundDef ? StartIndex.getDefIndex() : StartIndex.getUseIndex();
SlotIndex EndIndex;
if (IsIntraBlock) {
- EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = EndIndex.getUseIndex();
+ EndIndex = LIs->getInstructionIndex(UseI).getDefIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
RetVNI = PerformPHIConstruction(Walker, MBB, LI, Visited, Defs, Uses,
NewVNs, LiveOut, Phis, false, true);
- LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
+ LI->addRange(LiveRange(StartIndex, EndIndex, RetVNI));
if (foundUse && RetVNI->isKill(StartIndex))
RetVNI->removeKill(StartIndex);
for (DenseMap<MachineBasicBlock*, VNInfo*>::iterator I =
IncomingVNs.begin(), E = IncomingVNs.end(); I != E; ++I) {
I->second->setHasPHIKill(true);
- SlotIndex KillIndex = LIs->getMBBEndIdx(I->first);
+ SlotIndex KillIndex(LIs->getMBBEndIdx(I->first), true);
if (!I->second->isKill(KillIndex))
I->second->addKill(KillIndex);
}
SlotIndex EndIndex;
if (IsIntraBlock) {
- EndIndex = LIs->getInstructionIndex(UseI);
- EndIndex = EndIndex.getUseIndex();
+ EndIndex = LIs->getInstructionIndex(UseI).getDefIndex();
} else
EndIndex = LIs->getMBBEndIdx(MBB);
- LI->addRange(LiveRange(StartIndex, EndIndex.getNextSlot(), RetVNI));
+ LI->addRange(LiveRange(StartIndex, EndIndex, RetVNI));
if (IsIntraBlock)
RetVNI->addKill(EndIndex);
/// ReconstructLiveInterval - Recompute a live interval from scratch.
void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) {
- BumpPtrAllocator& Alloc = LIs->getVNInfoAllocator();
+ VNInfo::Allocator& Alloc = LIs->getVNInfoAllocator();
// Clear the old ranges and valnos;
LI->clear();
SlotIndex DefIdx = LIs->getInstructionIndex(&*DI);
DefIdx = DefIdx.getDefIndex();
- assert(DI->getOpcode() != TargetInstrInfo::PHI &&
- "Following NewVN isPHIDef flag incorrect. Fix me!");
+ assert(!DI->isPHI() && "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.
bool PreAllocSplitting::Rematerialize(unsigned VReg, VNInfo* ValNo,
MachineInstr* DefMI,
MachineBasicBlock::iterator RestorePt,
- SlotIndex RestoreIdx,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
MachineBasicBlock& MBB = *RestorePt->getParent();
MachineBasicBlock::iterator KillPt = BarrierMBB->end();
- SlotIndex 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);
- SlotIndex RematIdx = LIs->getInstructionIndex(prior(RestorePt));
RematIdx = RematIdx.getDefIndex();
RenumberValno(CurrLI->findDefinedVNInfoForRegInt(RematIdx));
MachineBasicBlock* MBB,
int& SS,
SmallPtrSet<MachineInstr*, 4>& RefsInMBB) {
- MachineBasicBlock::iterator Pt = MBB->begin();
-
// Go top down if RefsInMBB is empty.
if (RefsInMBB.empty())
return 0;
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(),
/// so it would not cross the barrier that's being processed. Shrink wrap
/// (minimize) the live interval to the last uses.
bool PreAllocSplitting::SplitRegLiveInterval(LiveInterval *LI) {
- DEBUG(errs() << "Pre-alloc splitting " << LI->reg << " for " << *Barrier
+ DEBUG(dbgs() << "Pre-alloc splitting " << LI->reg << " for " << *Barrier
<< " result: ");
CurrLI = LI;
// If this would create a new join point, do not split.
if (DefMI && createsNewJoin(LR, DefMI->getParent(), Barrier->getParent())) {
- DEBUG(errs() << "FAILED (would create a new join point).\n");
+ DEBUG(dbgs() << "FAILED (would create a new join point).\n");
return false;
}
}
// Find a point to restore the value after the barrier.
- SlotIndex 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");
+ DEBUG(dbgs() << "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)) {
- DEBUG(errs() << "success (remat).\n");
+ if (Rematerialize(LI->reg, ValNo, DefMI, RestorePt, RefsInMBB)) {
+ DEBUG(dbgs() << "success (remat).\n");
return true;
}
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");
+ DEBUG(dbgs() << "FAILED (could not find a suitable spill point).\n");
return false; // No gap to insert spill.
}
// Add 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) {
- DEBUG(errs() << "FAILED (def is dead).\n");
+ DEBUG(dbgs() << "FAILED (def is dead).\n");
return false; // Def is dead. Do nothing.
}
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");
+ DEBUG(dbgs() << "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");
+ DEBUG(dbgs() << "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.
}
++NumSplits;
- DEBUG(errs() << "success.\n");
+ DEBUG(dbgs() << "success.\n");
return true;
}
// 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();
}
projects / oota-llvm.git / blobdiff