#define DEBUG_TYPE "regalloc"
#include "LiveRangeCalc.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
using namespace llvm;
void LiveRangeCalc::reset(const MachineFunction *mf,
SlotIndexes *SI,
MachineDominatorTree *MDT,
VNInfo::Allocator *VNIA) {
MF = mf;
MRI = &MF->getRegInfo();
Indexes = SI;
DomTree = MDT;
Alloc = VNIA;
unsigned N = MF->getNumBlockIDs();
Seen.clear();
Seen.resize(N);
LiveOut.resize(N);
LiveIn.clear();
}
void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) {
assert(MRI && Indexes && "call reset() first");
for (MachineRegisterInfo::def_iterator
I = MRI->def_begin(Reg), E = MRI->def_end(); I != E; ++I) {
const MachineInstr *MI = &*I;
SlotIndex Idx;
if (MI->isPHI())
Idx = Indexes->getMBBStartIdx(MI->getParent());
else
Idx = Indexes->getInstructionIndex(MI)
.getRegSlot(I.getOperand().isEarlyClobber());
LR.createDeadDef(Idx, *Alloc);
}
}
void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg) {
assert(MRI && Indexes && "call reset() first");
for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
E = MRI->reg_nodbg_end(); I != E; ++I) {
MachineOperand &MO = I.getOperand();
if (MO.isUse())
MO.setIsKill(false);
if (!MO.readsReg())
continue;
const MachineInstr *MI = &*I;
SlotIndex Idx;
if (MI->isPHI()) {
assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
Idx = Indexes->getMBBEndIdx(MI->getOperand(I.getOperandNo()+1).getMBB());
} else {
Idx = Indexes->getInstructionIndex(MI).getRegSlot();
unsigned DefIdx;
if (MO.isDef()) {
if (MO.isEarlyClobber())
Idx = Idx.getRegSlot(true);
} else if (MI->isRegTiedToDefOperand(I.getOperandNo(), &DefIdx)) {
if (MI->getOperand(DefIdx).isEarlyClobber())
Idx = Idx.getRegSlot(true);
}
}
extend(LR, Idx, Reg);
}
}
void LiveRangeCalc::updateLiveIns() {
LiveRangeUpdater Updater;
for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
E = LiveIn.end(); I != E; ++I) {
if (!I->DomNode)
continue;
MachineBasicBlock *MBB = I->DomNode->getBlock();
assert(I->Value && "No live-in value found");
SlotIndex Start, End;
tie(Start, End) = Indexes->getMBBRange(MBB);
if (I->Kill.isValid())
End = I->Kill;
else {
assert(Seen.test(MBB->getNumber()));
LiveOut[MBB] = LiveOutPair(I->Value, (MachineDomTreeNode *)0);
}
Updater.setDest(&I->LR);
Updater.add(Start, End, I->Value);
}
LiveIn.clear();
}
void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg) {
assert(Kill.isValid() && "Invalid SlotIndex");
assert(Indexes && "Missing SlotIndexes");
assert(DomTree && "Missing dominator tree");
MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill.getPrevSlot());
assert(KillMBB && "No MBB at Kill");
if (LR.extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
return;
if (findReachingDefs(LR, *KillMBB, Kill, PhysReg))
return;
calculateValues();
}
void LiveRangeCalc::calculateValues() {
assert(Indexes && "Missing SlotIndexes");
assert(DomTree && "Missing dominator tree");
updateSSA();
updateLiveIns();
}
bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
SlotIndex Kill, unsigned PhysReg) {
unsigned KillMBBNum = KillMBB.getNumber();
SmallVector<unsigned, 16> WorkList(1, KillMBBNum);
bool UniqueVNI = true;
VNInfo *TheVNI = 0;
for (unsigned i = 0; i != WorkList.size(); ++i) {
MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
#ifndef NDEBUG
if (MBB->pred_empty()) {
MBB->getParent()->verify();
llvm_unreachable("Use not jointly dominated by defs.");
}
if (TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
!MBB->isLiveIn(PhysReg)) {
MBB->getParent()->verify();
errs() << "The register needs to be live in to BB#" << MBB->getNumber()
<< ", but is missing from the live-in list.\n";
llvm_unreachable("Invalid global physical register");
}
#endif
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
MachineBasicBlock *Pred = *PI;
if (Seen.test(Pred->getNumber())) {
if (VNInfo *VNI = LiveOut[Pred].first) {
if (TheVNI && TheVNI != VNI)
UniqueVNI = false;
TheVNI = VNI;
}
continue;
}
SlotIndex Start, End;
tie(Start, End) = Indexes->getMBBRange(Pred);
VNInfo *VNI = LR.extendInBlock(Start, End);
setLiveOutValue(Pred, VNI);
if (VNI) {
if (TheVNI && TheVNI != VNI)
UniqueVNI = false;
TheVNI = VNI;
continue;
}
if (Pred != &KillMBB)
WorkList.push_back(Pred->getNumber());
else
Kill = SlotIndex();
}
}
LiveIn.clear();
if (WorkList.size() > 4)
array_pod_sort(WorkList.begin(), WorkList.end());
if (UniqueVNI) {
LiveRangeUpdater Updater(&LR);
for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(),
E = WorkList.end(); I != E; ++I) {
SlotIndex Start, End;
tie(Start, End) = Indexes->getMBBRange(*I);
if (*I == KillMBBNum && Kill.isValid())
End = Kill;
else
LiveOut[MF->getBlockNumbered(*I)] =
LiveOutPair(TheVNI, (MachineDomTreeNode *)0);
Updater.add(Start, End, TheVNI);
}
return true;
}
LiveIn.reserve(WorkList.size());
for (SmallVectorImpl<unsigned>::const_iterator
I = WorkList.begin(), E = WorkList.end(); I != E; ++I) {
MachineBasicBlock *MBB = MF->getBlockNumbered(*I);
addLiveInBlock(LR, DomTree->getNode(MBB));
if (MBB == &KillMBB)
LiveIn.back().Kill = Kill;
}
return false;
}
void LiveRangeCalc::updateSSA() {
assert(Indexes && "Missing SlotIndexes");
assert(DomTree && "Missing dominator tree");
unsigned Changes;
do {
Changes = 0;
for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
E = LiveIn.end(); I != E; ++I) {
MachineDomTreeNode *Node = I->DomNode;
if (!Node)
continue;
MachineBasicBlock *MBB = Node->getBlock();
MachineDomTreeNode *IDom = Node->getIDom();
LiveOutPair IDomValue;
bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
if (!needPHI) {
IDomValue = LiveOut[IDom->getBlock()];
if (IDomValue.first && !IDomValue.second)
LiveOut[IDom->getBlock()].second = IDomValue.second =
DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
LiveOutPair &Value = LiveOut[*PI];
if (!Value.first || Value.first == IDomValue.first)
continue;
if (!Value.second)
Value.second =
DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
if (DomTree->dominates(IDom, Value.second)) {
needPHI = true;
break;
}
}
}
LiveOutPair &LOP = LiveOut[MBB];
if (needPHI) {
++Changes;
assert(Alloc && "Need VNInfo allocator to create PHI-defs");
SlotIndex Start, End;
tie(Start, End) = Indexes->getMBBRange(MBB);
LiveRange &LR = I->LR;
VNInfo *VNI = LR.getNextValue(Start, *Alloc);
I->Value = VNI;
I->DomNode = 0;
if (I->Kill.isValid())
LR.addSegment(LiveInterval::Segment(Start, I->Kill, VNI));
else {
LR.addSegment(LiveInterval::Segment(Start, End, VNI));
LOP = LiveOutPair(VNI, Node);
}
} else if (IDomValue.first) {
I->Value = IDomValue.first;
if (I->Kill.isValid())
continue;
if (LOP.first == IDomValue.first)
continue;
++Changes;
LOP = IDomValue;
}
}
} while (Changes);
}