//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "LiveRangeCalc.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
#include <cmath>
#include <limits>
using namespace llvm;
+#define DEBUG_TYPE "regalloc"
+
char LiveIntervals::ID = 0;
char &llvm::LiveIntervalsID = LiveIntervals::ID;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
}
LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
- DomTree(0), LRCalc(0) {
+ DomTree(nullptr), LRCalc(nullptr) {
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
}
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
MF = &fn;
MRI = &MF->getRegInfo();
- TM = &fn.getTarget();
- TRI = TM->getRegisterInfo();
- TII = TM->getInstrInfo();
+ TRI = MF->getSubtarget().getRegisterInfo();
+ TII = MF->getSubtarget().getInstrInfo();
AA = &getAnalysis<AliasAnalysis>();
Indexes = &getAnalysis<SlotIndexes>();
DomTree = &getAnalysis<MachineDominatorTree>();
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
LRCalc->createDeadDefs(LI);
LRCalc->extendToUses(LI);
+ computeDeadValues(&LI, LI, nullptr, nullptr);
}
void LiveIntervals::computeVirtRegs() {
SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
// Visit all instructions reading li->reg.
- for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
- MachineInstr *UseMI = I.skipInstruction();) {
+ for (MachineRegisterInfo::reg_instr_iterator
+ I = MRI->reg_instr_begin(li->reg), E = MRI->reg_instr_end();
+ I != E; ) {
+ MachineInstr *UseMI = &*(I++);
if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
continue;
SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
(void)ExtVNI;
assert(ExtVNI == VNI && "Unexpected existing value number");
// Is this a PHIDef we haven't seen before?
- if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
+ if (!VNI->isPHIDef() || VNI->def != BlockStart ||
+ !UsedPHIs.insert(VNI).second)
continue;
// The PHI is live, make sure the predecessors are live-out.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
- if (!LiveOut.insert(*PI))
+ if (!LiveOut.insert(*PI).second)
continue;
SlotIndex Stop = getMBBEndIdx(*PI);
// A predecessor is not required to have a live-out value for a PHI.
// Make sure VNI is live-out from the predecessors.
for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
PE = MBB->pred_end(); PI != PE; ++PI) {
- if (!LiveOut.insert(*PI))
+ if (!LiveOut.insert(*PI).second)
continue;
SlotIndex Stop = getMBBEndIdx(*PI);
assert(li->getVNInfoBefore(Stop) == VNI &&
// Handle dead values.
bool CanSeparate = false;
+ computeDeadValues(li, NewLR, &CanSeparate, dead);
+
+ // Move the trimmed segments back.
+ li->segments.swap(NewLR.segments);
+ DEBUG(dbgs() << "Shrunk: " << *li << '\n');
+ return CanSeparate;
+}
+
+void LiveIntervals::computeDeadValues(LiveInterval *li,
+ LiveRange &LR,
+ bool *CanSeparate,
+ SmallVectorImpl<MachineInstr*> *dead) {
for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
I != E; ++I) {
VNInfo *VNI = *I;
if (VNI->isUnused())
continue;
- LiveRange::iterator LRI = NewLR.FindSegmentContaining(VNI->def);
- assert(LRI != NewLR.end() && "Missing segment for PHI");
+ LiveRange::iterator LRI = LR.FindSegmentContaining(VNI->def);
+ assert(LRI != LR.end() && "Missing segment for PHI");
if (LRI->end != VNI->def.getDeadSlot())
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
VNI->markUnused();
- NewLR.removeSegment(LRI->start, LRI->end);
+ LR.removeSegment(LRI->start, LRI->end);
DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
- CanSeparate = true;
+ if (CanSeparate)
+ *CanSeparate = true;
} else {
// This is a dead def. Make sure the instruction knows.
MachineInstr *MI = getInstructionFromIndex(VNI->def);
}
}
}
-
- // Move the trimmed segments back.
- li->segments.swap(NewLR.segments);
- DEBUG(dbgs() << "Shrunk: " << *li << '\n');
- return CanSeparate;
}
void LiveIntervals::extendToIndices(LiveRange &LR,
break;
}
if (CancelKill)
- MI->clearRegisterKills(Reg, NULL);
+ MI->clearRegisterKills(Reg, nullptr);
else
- MI->addRegisterKilled(Reg, NULL);
+ MI->addRegisterKilled(Reg, nullptr);
}
}
}
SlotIndex Start = LI.beginIndex();
if (Start.isBlock())
- return NULL;
+ return nullptr;
SlotIndex Stop = LI.endIndex();
if (Stop.isBlock())
- return NULL;
+ return nullptr;
// getMBBFromIndex doesn't need to search the MBB table when both indexes
// belong to proper instructions.
MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
- return MBB1 == MBB2 ? MBB1 : NULL;
+ return MBB1 == MBB2 ? MBB1 : nullptr;
}
bool
/// Update a single live range, assuming an instruction has been moved from
/// OldIdx to NewIdx.
void updateRange(LiveRange &LR, unsigned Reg) {
- if (!Updated.insert(&LR))
+ if (!Updated.insert(&LR).second)
return;
DEBUG({
dbgs() << " ";
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
SlotIndex LastUse = NewIdx;
- for (MachineRegisterInfo::use_nodbg_iterator
- UI = MRI.use_nodbg_begin(Reg),
- UE = MRI.use_nodbg_end();
- UI != UE; UI.skipInstruction()) {
+ for (MachineRegisterInfo::use_instr_nodbg_iterator
+ UI = MRI.use_instr_nodbg_begin(Reg),
+ UE = MRI.use_instr_nodbg_end();
+ UI != UE; ++UI) {
const MachineInstr* MI = &*UI;
SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
if (InstSlot > LastUse && InstSlot < OldIdx)