//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
#include "SplitKit.h"
-#include "VirtRegMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "regalloc"
+
STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple, "Number of splits that were simple");
STATISTIC(NumCopies, "Number of copies inserted for splitting");
// Split Analysis
//===----------------------------------------------------------------------===//
-SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
- const LiveIntervals &lis,
+SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
const MachineLoopInfo &mli)
- : MF(vrm.getMachineFunction()),
- VRM(vrm),
- LIS(lis),
- Loops(mli),
- TII(*MF.getTarget().getInstrInfo()),
- CurLI(0),
- LastSplitPoint(MF.getNumBlockIDs()) {}
+ : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
+ TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
+ LastSplitPoint(MF.getNumBlockIDs()) {}
void SplitAnalysis::clear() {
UseSlots.clear();
UseBlocks.clear();
ThroughBlocks.clear();
- CurLI = 0;
+ CurLI = nullptr;
DidRepairRange = false;
}
// First get all the defs from the interval values. This provides the correct
// slots for early clobbers.
- for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(),
- E = CurLI->vni_end(); I != E; ++I)
- if (!(*I)->isPHIDef() && !(*I)->isUnused())
- UseSlots.push_back((*I)->def);
+ for (const VNInfo *VNI : CurLI->valnos)
+ if (!VNI->isPHIDef() && !VNI->isUnused())
+ UseSlots.push_back(VNI->def);
// Get use slots form the use-def chain.
const MachineRegisterInfo &MRI = MF.getRegInfo();
- for (MachineRegisterInfo::use_nodbg_iterator
- I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E;
- ++I)
- if (!I.getOperand().isUndef())
- UseSlots.push_back(LIS.getInstructionIndex(&*I).getRegSlot());
+ for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
+ if (!MO.isUndef())
+ UseSlots.push_back(LIS.getInstructionIndex(MO.getParent()).getRegSlot());
array_pod_sort(UseSlots.begin(), UseSlots.end());
BlockInfo BI;
BI.MBB = MFI;
SlotIndex Start, Stop;
- tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
+ std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
// If the block contains no uses, the range must be live through. At one
// point, RegisterCoalescer could create dangling ranges that ended
// When not live in, the first use should be a def.
if (!BI.LiveIn) {
- assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
+ assert(LVI->start == LVI->valno->def && "Dangling Segment start");
assert(LVI->start == BI.FirstInstr && "First instr should be a def");
BI.FirstDef = BI.FirstInstr;
}
BI.FirstInstr = BI.FirstDef = LVI->start;
}
- // A LiveRange that starts in the middle of the block must be a def.
- assert(LVI->start == LVI->valno->def && "Dangling LiveRange start");
+ // A Segment that starts in the middle of the block must be a def.
+ assert(LVI->start == LVI->valno->def && "Dangling Segment start");
if (!BI.FirstDef)
BI.FirstDef = LVI->start;
}
//===----------------------------------------------------------------------===//
/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
-SplitEditor::SplitEditor(SplitAnalysis &sa,
- LiveIntervals &lis,
- VirtRegMap &vrm,
- MachineDominatorTree &mdt)
- : SA(sa), LIS(lis), VRM(vrm),
- MRI(vrm.getMachineFunction().getRegInfo()),
- MDT(mdt),
- TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
- TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
- Edit(0),
- OpenIdx(0),
- SpillMode(SM_Partition),
- RegAssign(Allocator)
-{}
+SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm,
+ MachineDominatorTree &mdt,
+ MachineBlockFrequencyInfo &mbfi)
+ : SA(sa), LIS(lis), VRM(vrm), MRI(vrm.getMachineFunction().getRegInfo()),
+ MDT(mdt), TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
+ TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
+ MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
+ RegAssign(Allocator) {}
void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
Edit = &LRE;
// We don't need an AliasAnalysis since we will only be performing
// cheap-as-a-copy remats anyway.
- Edit->anyRematerializable(0);
+ Edit->anyRematerializable(nullptr);
}
-#ifndef NDEBUG
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void SplitEditor::dump() const {
if (RegAssign.empty()) {
dbgs() << " empty\n";
assert(ParentVNI && "Mapping NULL value");
assert(Idx.isValid() && "Invalid SlotIndex");
assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
- LiveInterval *LI = Edit->get(RegIdx);
+ LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
// Create a new value.
VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());
// If the previous value was a simple mapping, add liveness for it now.
if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
SlotIndex Def = OldVNI->def;
- LI->addRange(LiveRange(Def, Def.getDeadSlot(), OldVNI));
+ LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI));
// No longer a simple mapping. Switch to a complex, non-forced mapping.
InsP.first->second = ValueForcePair();
}
// This is a complex mapping, add liveness for VNI
SlotIndex Def = VNI->def;
- LI->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
+ LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
return VNI;
}
// This was previously a single mapping. Make sure the old def is represented
// by a trivial live range.
SlotIndex Def = VNI->def;
- Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getDeadSlot(), VNI));
+ LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
+ LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI));
// Mark as complex mapped, forced.
- VFP = ValueForcePair(0, true);
+ VFP = ValueForcePair(nullptr, true);
}
VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
SlotIndex UseIdx,
MachineBasicBlock &MBB,
MachineBasicBlock::iterator I) {
- MachineInstr *CopyMI = 0;
+ MachineInstr *CopyMI = nullptr;
SlotIndex Def;
- LiveInterval *LI = Edit->get(RegIdx);
+ LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
// We may be trying to avoid interference that ends at a deleted instruction,
// so always begin RegIdx 0 early and all others late.
unsigned SplitEditor::openIntv() {
// Create the complement as index 0.
if (Edit->empty())
- Edit->create();
+ Edit->createEmptyInterval();
// Create the open interval.
OpenIdx = Edit->size();
- Edit->create();
+ Edit->createEmptyInterval();
return OpenIdx;
}
assert(MI && "enterIntvAfter called with invalid index");
VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(),
- llvm::next(MachineBasicBlock::iterator(MI)));
+ std::next(MachineBasicBlock::iterator(MI)));
return VNI->def;
}
}
VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(),
- llvm::next(MachineBasicBlock::iterator(MI)));
+ std::next(MachineBasicBlock::iterator(MI)));
return VNI->def;
}
//===----------------------------------------------------------------------===//
void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
- LiveInterval *LI = Edit->get(0);
+ LiveInterval *LI = &LIS.getInterval(Edit->get(0));
DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n");
RegAssignMap::iterator AssignI;
AssignI.setMap(RegAssign);
for (unsigned i = 0, e = Copies.size(); i != e; ++i) {
- VNInfo *VNI = Copies[i];
- SlotIndex Def = VNI->def;
+ SlotIndex Def = Copies[i]->def;
MachineInstr *MI = LIS.getInstructionFromIndex(Def);
assert(MI && "No instruction for back-copy");
while (!AtBegin && (--MBBI)->isDebugValue());
DEBUG(dbgs() << "Removing " << Def << '\t' << *MI);
- LI->removeValNo(VNI);
+ LIS.removeVRegDefAt(*LI, Def);
LIS.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
- // Adjust RegAssign if a register assignment is killed at VNI->def. We
- // want to avoid calculating the live range of the source register if
- // possible.
+ // Adjust RegAssign if a register assignment is killed at Def. We want to
+ // avoid calculating the live range of the source register if possible.
AssignI.find(Def.getPrevSlot());
if (!AssignI.valid() || AssignI.start() >= Def)
continue;
void SplitEditor::hoistCopiesForSize() {
// Get the complement interval, always RegIdx 0.
- LiveInterval *LI = Edit->get(0);
+ LiveInterval *LI = &LIS.getInterval(Edit->get(0));
LiveInterval *Parent = &Edit->getParent();
// Track the nearest common dominator for all back-copies for each ParentVNI,
// Find the nearest common dominator for parent values with multiple
// back-copies. If a single back-copy dominates, put it in DomPair.second.
- for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
- VI != VE; ++VI) {
- VNInfo *VNI = *VI;
+ for (VNInfo *VNI : LI->valnos) {
if (VNI->isUnused())
continue;
VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
// Remove redundant back-copies that are now known to be dominated by another
// def with the same value.
SmallVector<VNInfo*, 8> BackCopies;
- for (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end();
- VI != VE; ++VI) {
- VNInfo *VNI = *VI;
+ for (VNInfo *VNI : LI->valnos) {
if (VNI->isUnused())
continue;
VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def);
bool SplitEditor::transferValues() {
bool Skipped = false;
RegAssignMap::const_iterator AssignI = RegAssign.begin();
- for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(),
- ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) {
- DEBUG(dbgs() << " blit " << *ParentI << ':');
- VNInfo *ParentVNI = ParentI->valno;
+ for (const LiveRange::Segment &S : Edit->getParent()) {
+ DEBUG(dbgs() << " blit " << S << ':');
+ VNInfo *ParentVNI = S.valno;
// RegAssign has holes where RegIdx 0 should be used.
- SlotIndex Start = ParentI->start;
+ SlotIndex Start = S.start;
AssignI.advanceTo(Start);
do {
unsigned RegIdx;
- SlotIndex End = ParentI->end;
+ SlotIndex End = S.end;
if (!AssignI.valid()) {
RegIdx = 0;
} else if (AssignI.start() <= Start) {
// The interval [Start;End) is continuously mapped to RegIdx, ParentVNI.
DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx);
- LiveInterval *LI = Edit->get(RegIdx);
+ LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
// Check for a simply defined value that can be blitted directly.
ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
if (VNInfo *VNI = VFP.getPointer()) {
DEBUG(dbgs() << ':' << VNI->id);
- LI->addRange(LiveRange(Start, End, VNI));
+ LR.addSegment(LiveInterval::Segment(Start, End, VNI));
Start = End;
continue;
}
// LiveInBlocks.
MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
SlotIndex BlockStart, BlockEnd;
- tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
+ std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB);
// The first block may be live-in, or it may have its own def.
if (Start != BlockStart) {
- VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
+ VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
assert(VNI && "Missing def for complex mapped value");
DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber());
// MBB has its own def. Is it also live-out?
if (BlockStart == ParentVNI->def) {
// This block has the def of a parent PHI, so it isn't live-in.
assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?");
- VNInfo *VNI = LI->extendInBlock(BlockStart, std::min(BlockEnd, End));
+ VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End));
assert(VNI && "Missing def for complex mapped parent PHI");
if (End >= BlockEnd)
LRC.setLiveOutValue(MBB, VNI); // Live-out as well.
// This block needs a live-in value. The last block covered may not
// be live-out.
if (End < BlockEnd)
- LRC.addLiveInBlock(LI, MDT[MBB], End);
+ LRC.addLiveInBlock(LR, MDT[MBB], End);
else {
// Live-through, and we don't know the value.
- LRC.addLiveInBlock(LI, MDT[MBB]);
- LRC.setLiveOutValue(MBB, 0);
+ LRC.addLiveInBlock(LR, MDT[MBB]);
+ LRC.setLiveOutValue(MBB, nullptr);
}
}
BlockStart = BlockEnd;
++MBB;
}
Start = End;
- } while (Start != ParentI->end);
+ } while (Start != S.end);
DEBUG(dbgs() << '\n');
}
void SplitEditor::extendPHIKillRanges() {
// Extend live ranges to be live-out for successor PHI values.
- for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
- E = Edit->getParent().vni_end(); I != E; ++I) {
- const VNInfo *PHIVNI = *I;
+ for (const VNInfo *PHIVNI : Edit->getParent().valnos) {
if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
continue;
unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
- LiveInterval *LI = Edit->get(RegIdx);
+ LiveRange &LR = LIS.getInterval(Edit->get(RegIdx));
LiveRangeCalc &LRC = getLRCalc(RegIdx);
MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
if (Edit->getParent().liveAt(LastUse)) {
assert(RegAssign.lookup(LastUse) == RegIdx &&
"Different register assignment in phi predecessor");
- LRC.extend(LI, End);
+ LRC.extend(LR, End);
}
}
}
void SplitEditor::rewriteAssigned(bool ExtendRanges) {
for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()),
RE = MRI.reg_end(); RI != RE;) {
- MachineOperand &MO = RI.getOperand();
+ MachineOperand &MO = *RI;
MachineInstr *MI = MO.getParent();
++RI;
// LiveDebugVariables should have handled all DBG_VALUE instructions.
// Rewrite to the mapped register at Idx.
unsigned RegIdx = RegAssign.lookup(Idx);
- LiveInterval *LI = Edit->get(RegIdx);
+ LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));
MO.setReg(LI->reg);
DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
<< Idx << ':' << RegIdx << '\t' << *MI);
} else
Idx = Idx.getRegSlot(true);
- getLRCalc(RegIdx).extend(LI, Idx.getNextSlot());
+ getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot());
}
}
void SplitEditor::deleteRematVictims() {
SmallVector<MachineInstr*, 8> Dead;
for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){
- LiveInterval *LI = *I;
- for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end();
- LII != LIE; ++LII) {
+ LiveInterval *LI = &LIS.getInterval(*I);
+ for (const LiveRange::Segment &S : LI->segments) {
// Dead defs end at the dead slot.
- if (LII->end != LII->valno->def.getDeadSlot())
+ if (S.end != S.valno->def.getDeadSlot())
continue;
- MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def);
+ MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def);
assert(MI && "Missing instruction for dead def");
MI->addRegisterDead(LI->reg, &TRI);
// the inserted copies.
// Add the original defs from the parent interval.
- for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(),
- E = Edit->getParent().vni_end(); I != E; ++I) {
- const VNInfo *ParentVNI = *I;
+ for (const VNInfo *ParentVNI : Edit->getParent().valnos) {
if (ParentVNI->isUnused())
continue;
unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
deleteRematVictims();
// Get rid of unused values and set phi-kill flags.
- for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I)
- (*I)->RenumberValues(LIS);
+ for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) {
+ LiveInterval &LI = LIS.getInterval(*I);
+ LI.RenumberValues();
+ }
// Provide a reverse mapping from original indices to Edit ranges.
if (LRMap) {
ConnectedVNInfoEqClasses ConEQ(LIS);
for (unsigned i = 0, e = Edit->size(); i != e; ++i) {
// Don't use iterators, they are invalidated by create() below.
- LiveInterval *li = Edit->get(i);
+ LiveInterval *li = &LIS.getInterval(Edit->get(i));
unsigned NumComp = ConEQ.Classify(li);
if (NumComp <= 1)
continue;
SmallVector<LiveInterval*, 8> dups;
dups.push_back(li);
for (unsigned j = 1; j != NumComp; ++j)
- dups.push_back(&Edit->create());
+ dups.push_back(&Edit->createEmptyInterval());
ConEQ.Distribute(&dups[0], MRI);
// The new intervals all map back to i.
if (LRMap)
}
// Calculate spill weight and allocation hints for new intervals.
- Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops);
+ Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI);
assert(!LRMap || LRMap->size() == Edit->size());
}
unsigned IntvIn, SlotIndex LeaveBefore,
unsigned IntvOut, SlotIndex EnterAfter){
SlotIndex Start, Stop;
- tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
+ std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum);
DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop
<< ") intf " << LeaveBefore << '-' << EnterAfter
void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
unsigned IntvIn, SlotIndex LeaveBefore) {
SlotIndex Start, Stop;
- tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
+ std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
<< "), uses " << BI.FirstInstr << '-' << BI.LastInstr
void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
unsigned IntvOut, SlotIndex EnterAfter) {
SlotIndex Start, Stop;
- tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
+ std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop
<< "), uses " << BI.FirstInstr << '-' << BI.LastInstr
projects / oota-llvm.git / blobdiff