#define DEBUG_TYPE "regalloc"
#include "LiveRangeCalc.h"
#include "llvm/CodeGen/MachineDominators.h"
using namespace llvm;
void LiveRangeCalc::reset(const MachineFunction *MF) {
unsigned N = MF->getNumBlockIDs();
Seen.clear();
Seen.resize(N);
LiveOut.resize(N);
LiveIn.clear();
}
void LiveRangeCalc::updateLiveIns(VNInfo *OverrideVNI, SlotIndexes *Indexes) {
for (SmallVectorImpl<LiveInBlock>::iterator I = LiveIn.begin(),
E = LiveIn.end(); I != E; ++I) {
if (!I->DomNode)
continue;
MachineBasicBlock *MBB = I->DomNode->getBlock();
VNInfo *VNI = OverrideVNI ? OverrideVNI : I->Value;
assert(VNI && "No live-in value found");
SlotIndex Start, End;
tie(Start, End) = Indexes->getMBBRange(MBB);
if (I->Kill.isValid())
I->LI->addRange(LiveRange(Start, I->Kill, VNI));
else {
I->LI->addRange(LiveRange(Start, End, VNI));
assert(Seen.test(MBB->getNumber()));
LiveOut[MBB] = LiveOutPair(VNI, (MachineDomTreeNode *)0);
}
}
LiveIn.clear();
}
void LiveRangeCalc::extend(LiveInterval *LI,
SlotIndex Kill,
SlotIndexes *Indexes,
MachineDominatorTree *DomTree,
VNInfo::Allocator *Alloc) {
assert(LI && "Missing live range");
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 (LI->extendInBlock(Indexes->getMBBStartIdx(KillMBB), Kill))
return;
VNInfo *VNI = findReachingDefs(LI, KillMBB, Kill, Indexes, DomTree);
if (!VNI)
updateSSA(Indexes, DomTree, Alloc);
updateLiveIns(VNI, Indexes);
}
void LiveRangeCalc::calculateValues(SlotIndexes *Indexes,
MachineDominatorTree *DomTree,
VNInfo::Allocator *Alloc) {
assert(Indexes && "Missing SlotIndexes");
assert(DomTree && "Missing dominator tree");
updateSSA(Indexes, DomTree, Alloc);
updateLiveIns(0, Indexes);
}
VNInfo *LiveRangeCalc::findReachingDefs(LiveInterval *LI,
MachineBasicBlock *KillMBB,
SlotIndex Kill,
SlotIndexes *Indexes,
MachineDominatorTree *DomTree) {
SmallVector<MachineBasicBlock*, 16> WorkList(1, KillMBB);
bool UniqueVNI = true;
VNInfo *TheVNI = 0;
for (unsigned i = 0; i != WorkList.size(); ++i) {
MachineBasicBlock *MBB = WorkList[i];
assert(!MBB->pred_empty() && "Value live-in to entry block?");
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 = LI->extendInBlock(Start, End);
setLiveOutValue(Pred, VNI);
if (VNI) {
if (TheVNI && TheVNI != VNI)
UniqueVNI = false;
TheVNI = VNI;
continue;
}
if (Pred != KillMBB)
WorkList.push_back(Pred);
else
Kill = SlotIndex();
}
}
LiveIn.clear();
LiveIn.reserve(WorkList.size());
while(!WorkList.empty())
addLiveInBlock(LI, DomTree->getNode(WorkList.pop_back_val()));
assert(LiveIn.back().DomNode->getBlock() == KillMBB);
LiveIn.back().Kill = Kill;
return UniqueVNI ? TheVNI : 0;
}
void LiveRangeCalc::updateSSA(SlotIndexes *Indexes,
MachineDominatorTree *DomTree,
VNInfo::Allocator *Alloc) {
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);
VNInfo *VNI = I->LI->getNextValue(Start, *Alloc);
VNI->setIsPHIDef(true);
I->Value = VNI;
I->DomNode = 0;
if (I->Kill.isValid())
I->LI->addRange(LiveRange(Start, I->Kill, VNI));
else {
I->LI->addRange(LiveRange(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);
}