#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <cmath>
using namespace llvm;
+namespace {
+ // Hidden options for help debugging.
+ cl::opt<bool> DisableReMat("disable-rematerialization",
+ cl::init(false), cl::Hidden);
+}
+
STATISTIC(numIntervals, "Number of original intervals");
STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
STATISTIC(numFolded , "Number of loads/stores folded into instructions");
mi2iMap_.clear();
i2miMap_.clear();
r2iMap_.clear();
+ // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
+ VNInfoAllocator.Reset();
+ for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
+ delete ClonedMIs[i];
}
/// runOnMachineFunction - Register allocate the whole function
// Number MachineInstrs and MachineBasicBlocks.
// Initialize MBB indexes to a sentinal.
- MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U);
+ MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
unsigned MIIndex = 0;
for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
MBB != E; ++MBB) {
- // Set the MBB2IdxMap entry for this MBB.
- MBB2IdxMap[MBB->getNumber()] = MIIndex;
+ unsigned StartIdx = MIIndex;
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
i2miMap_.push_back(I);
MIIndex += InstrSlots::NUM;
}
+
+ // Set the MBB2IdxMap entry for this MBB.
+ MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
}
computeIntervals();
}
}
-// Not called?
-/// CreateNewLiveInterval - Create a new live interval with the given live
-/// ranges. The new live interval will have an infinite spill weight.
-LiveInterval&
-LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI,
- const std::vector<LiveRange> &LRs) {
- const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg);
-
- // Create a new virtual register for the spill interval.
- unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC);
-
- // Replace the old virtual registers in the machine operands with the shiny
- // new one.
- for (std::vector<LiveRange>::const_iterator
- I = LRs.begin(), E = LRs.end(); I != E; ++I) {
- unsigned Index = getBaseIndex(I->start);
- unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM;
-
- for (; Index != End; Index += InstrSlots::NUM) {
- // Skip deleted instructions
- while (Index != End && !getInstructionFromIndex(Index))
- Index += InstrSlots::NUM;
-
- if (Index == End) break;
-
- MachineInstr *MI = getInstructionFromIndex(Index);
-
- for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) {
- MachineOperand &MOp = MI->getOperand(J);
- if (MOp.isRegister() && MOp.getReg() == LI->reg)
- MOp.setReg(NewVReg);
- }
- }
+/// isReMaterializable - Returns true if the definition MI of the specified
+/// val# of the specified interval is re-materializable.
+bool LiveIntervals::isReMaterializable(const LiveInterval &li,
+ const VNInfo *ValNo, MachineInstr *MI) {
+ if (DisableReMat)
+ return false;
+
+ if (tii_->isTriviallyReMaterializable(MI))
+ return true;
+
+ int FrameIdx = 0;
+ if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
+ !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
+ return false;
+
+ // This is a load from fixed stack slot. It can be rematerialized unless it's
+ // re-defined by a two-address instruction.
+ for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
+ i != e; ++i) {
+ const VNInfo *VNI = *i;
+ if (VNI == ValNo)
+ continue;
+ unsigned DefIdx = VNI->def;
+ if (DefIdx == ~1U)
+ continue; // Dead val#.
+ MachineInstr *DefMI = (DefIdx == ~0u)
+ ? NULL : getInstructionFromIndex(DefIdx);
+ if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
+ return false;
}
+ return true;
+}
- LiveInterval &NewLI = getOrCreateInterval(NewVReg);
-
- // The spill weight is now infinity as it cannot be spilled again
- NewLI.weight = float(HUGE_VAL);
-
- for (std::vector<LiveRange>::const_iterator
- I = LRs.begin(), E = LRs.end(); I != E; ++I) {
- DOUT << " Adding live range " << *I << " to new interval\n";
- NewLI.addRange(*I);
+/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
+/// slot / to reg or any rematerialized load into ith operand of specified
+/// MI. If it is successul, MI is updated with the newly created MI and
+/// returns true.
+bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
+ MachineInstr *DefMI,
+ unsigned index, unsigned i,
+ bool isSS, int slot, unsigned reg) {
+ MachineInstr *fmi = isSS
+ ? mri_->foldMemoryOperand(MI, i, slot)
+ : mri_->foldMemoryOperand(MI, i, DefMI);
+ if (fmi) {
+ // Attempt to fold the memory reference into the instruction. If
+ // we can do this, we don't need to insert spill code.
+ if (lv_)
+ lv_->instructionChanged(MI, fmi);
+ MachineBasicBlock &MBB = *MI->getParent();
+ vrm.virtFolded(reg, MI, i, fmi);
+ mi2iMap_.erase(MI);
+ i2miMap_[index/InstrSlots::NUM] = fmi;
+ mi2iMap_[fmi] = index;
+ MI = MBB.insert(MBB.erase(MI), fmi);
+ ++numFolded;
+ return true;
}
-
- DOUT << "Created new live interval " << NewLI << "\n";
- return NewLI;
+ return false;
}
std::vector<LiveInterval*> LiveIntervals::
-addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
+addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
// since this is called after the analysis is done we don't know if
// LiveVariables is available
lv_ = getAnalysisToUpdate<LiveVariables>();
li.print(DOUT, mri_);
DOUT << '\n';
- const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
+ SSARegMap *RegMap = mf_->getSSARegMap();
+ const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
+
+ unsigned NumValNums = li.getNumValNums();
+ SmallVector<MachineInstr*, 4> ReMatDefs;
+ ReMatDefs.resize(NumValNums, NULL);
+ SmallVector<MachineInstr*, 4> ReMatOrigDefs;
+ ReMatOrigDefs.resize(NumValNums, NULL);
+ SmallVector<int, 4> ReMatIds;
+ ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
+ BitVector ReMatDelete(NumValNums);
+ unsigned slot = VirtRegMap::MAX_STACK_SLOT;
+
+ bool NeedStackSlot = false;
+ for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
+ i != e; ++i) {
+ const VNInfo *VNI = *i;
+ unsigned VN = VNI->id;
+ unsigned DefIdx = VNI->def;
+ if (DefIdx == ~1U)
+ continue; // Dead val#.
+ // Is the def for the val# rematerializable?
+ MachineInstr *DefMI = (DefIdx == ~0u)
+ ? NULL : getInstructionFromIndex(DefIdx);
+ if (DefMI && isReMaterializable(li, VNI, DefMI)) {
+ // Remember how to remat the def of this val#.
+ ReMatOrigDefs[VN] = DefMI;
+ // Original def may be modified so we have to make a copy here. vrm must
+ // delete these!
+ ReMatDefs[VN] = DefMI = DefMI->clone();
+ vrm.setVirtIsReMaterialized(reg, DefMI);
+
+ bool CanDelete = true;
+ for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
+ unsigned KillIdx = VNI->kills[j];
+ MachineInstr *KillMI = (KillIdx & 1)
+ ? NULL : getInstructionFromIndex(KillIdx);
+ // Kill is a phi node, not all of its uses can be rematerialized.
+ // It must not be deleted.
+ if (!KillMI) {
+ CanDelete = false;
+ // Need a stack slot if there is any live range where uses cannot be
+ // rematerialized.
+ NeedStackSlot = true;
+ break;
+ }
+ }
+
+ if (CanDelete)
+ ReMatDelete.set(VN);
+ } else {
+ // Need a stack slot if there is any live range where uses cannot be
+ // rematerialized.
+ NeedStackSlot = true;
+ }
+ }
+
+ // One stack slot per live interval.
+ if (NeedStackSlot)
+ slot = vrm.assignVirt2StackSlot(reg);
for (LiveInterval::Ranges::const_iterator
- i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
- unsigned index = getBaseIndex(i->start);
- unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM;
+ I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
+ MachineInstr *DefMI = ReMatDefs[I->valno->id];
+ MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id];
+ bool DefIsReMat = DefMI != NULL;
+ bool CanDelete = ReMatDelete[I->valno->id];
+ int LdSlot = 0;
+ bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot);
+ bool isLoad = isLoadSS ||
+ (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
+ unsigned index = getBaseIndex(I->start);
+ unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
for (; index != end; index += InstrSlots::NUM) {
// skip deleted instructions
while (index != end && !getInstructionFromIndex(index))
RestartInstruction:
for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
MachineOperand& mop = MI->getOperand(i);
- if (mop.isRegister() && mop.getReg() == li.reg) {
- MachineInstr *fmi = li.remat ? NULL
- : mri_->foldMemoryOperand(MI, i, slot);
- if (fmi) {
- // Attempt to fold the memory reference into the instruction. If we
- // can do this, we don't need to insert spill code.
- if (lv_)
- lv_->instructionChanged(MI, fmi);
- MachineBasicBlock &MBB = *MI->getParent();
- vrm.virtFolded(li.reg, MI, i, fmi);
- mi2iMap_.erase(MI);
- i2miMap_[index/InstrSlots::NUM] = fmi;
- mi2iMap_[fmi] = index;
- MI = MBB.insert(MBB.erase(MI), fmi);
- ++numFolded;
- // Folding the load/store can completely change the instruction in
- // unpredictable ways, rescan it from the beginning.
- goto RestartInstruction;
- } else {
- // Create a new virtual register for the spill interval.
- unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc);
+ if (!mop.isRegister())
+ continue;
+ unsigned Reg = mop.getReg();
+ if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
+ continue;
+ bool isSubReg = RegMap->isSubRegister(Reg);
+ unsigned SubIdx = 0;
+ if (isSubReg) {
+ SubIdx = RegMap->getSubRegisterIndex(Reg);
+ Reg = RegMap->getSuperRegister(Reg);
+ }
+ if (Reg != li.reg)
+ continue;
+
+ bool TryFold = !DefIsReMat;
+ bool FoldSS = true;
+ int FoldSlot = slot;
+ if (DefIsReMat) {
+ // If this is the rematerializable definition MI itself and
+ // all of its uses are rematerialized, simply delete it.
+ if (MI == OrigDefMI && CanDelete) {
+ RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ break;
+ }
+
+ // If def for this use can't be rematerialized, then try folding.
+ TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad));
+ if (isLoad) {
+ // Try fold loads (from stack slot, constant pool, etc.) into uses.
+ FoldSS = isLoadSS;
+ FoldSlot = LdSlot;
+ }
+ }
+
+ // FIXME: fold subreg use
+ if (!isSubReg && TryFold &&
+ tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg))
+ // Folding the load/store can completely change the instruction in
+ // unpredictable ways, rescan it from the beginning.
+ goto RestartInstruction;
+
+ // Create a new virtual register for the spill interval.
+ unsigned NewVReg = RegMap->createVirtualRegister(rc);
+ if (isSubReg)
+ RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx);
- // Scan all of the operands of this instruction rewriting operands
- // to use NewVReg instead of li.reg as appropriate. We do this for
- // two reasons:
- //
- // 1. If the instr reads the same spilled vreg multiple times, we
- // want to reuse the NewVReg.
- // 2. If the instr is a two-addr instruction, we are required to
- // keep the src/dst regs pinned.
- //
- // Keep track of whether we replace a use and/or def so that we can
- // create the spill interval with the appropriate range.
- mop.setReg(NewVReg);
+ // Scan all of the operands of this instruction rewriting operands
+ // to use NewVReg instead of li.reg as appropriate. We do this for
+ // two reasons:
+ //
+ // 1. If the instr reads the same spilled vreg multiple times, we
+ // want to reuse the NewVReg.
+ // 2. If the instr is a two-addr instruction, we are required to
+ // keep the src/dst regs pinned.
+ //
+ // Keep track of whether we replace a use and/or def so that we can
+ // create the spill interval with the appropriate range.
+ mop.setReg(NewVReg);
- bool HasUse = mop.isUse();
- bool HasDef = mop.isDef();
- for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
- if (MI->getOperand(j).isReg() &&
- MI->getOperand(j).getReg() == li.reg) {
- MI->getOperand(j).setReg(NewVReg);
- HasUse |= MI->getOperand(j).isUse();
- HasDef |= MI->getOperand(j).isDef();
- }
- }
-
- // create a new register for this spill
- vrm.grow();
- if (li.remat)
- vrm.setVirtIsReMaterialized(NewVReg, li.remat);
+ bool HasUse = mop.isUse();
+ bool HasDef = mop.isDef();
+ for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
+ if (MI->getOperand(j).isRegister() &&
+ MI->getOperand(j).getReg() == li.reg) {
+ MI->getOperand(j).setReg(NewVReg);
+ HasUse |= MI->getOperand(j).isUse();
+ HasDef |= MI->getOperand(j).isDef();
+ }
+ }
+
+ vrm.grow();
+ if (DefIsReMat) {
+ vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
+ if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
+ // Each valnum may have its own remat id.
+ ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
+ } else {
+ vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]);
+ }
+ if (!CanDelete || (HasUse && HasDef)) {
+ // If this is a two-addr instruction then its use operands are
+ // rematerializable but its def is not. It should be assigned a
+ // stack slot.
vrm.assignVirt2StackSlot(NewVReg, slot);
- LiveInterval &nI = getOrCreateInterval(NewVReg);
- nI.remat = li.remat;
- assert(nI.empty());
-
- // the spill weight is now infinity as it
- // cannot be spilled again
- nI.weight = HUGE_VALF;
-
- if (HasUse) {
- LiveRange LR(getLoadIndex(index), getUseIndex(index),
- nI.getNextValue(~0U, 0));
- DOUT << " +" << LR;
- nI.addRange(LR);
- }
- if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(~0U, 0));
- DOUT << " +" << LR;
- nI.addRange(LR);
- }
+ }
+ } else {
+ vrm.assignVirt2StackSlot(NewVReg, slot);
+ }
+
+ // create a new register interval for this spill / remat.
+ LiveInterval &nI = getOrCreateInterval(NewVReg);
+ assert(nI.empty());
+
+ // the spill weight is now infinity as it
+ // cannot be spilled again
+ nI.weight = HUGE_VALF;
+
+ if (HasUse) {
+ LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
+ DOUT << " +" << LR;
+ nI.addRange(LR);
+ }
+ if (HasDef) {
+ LiveRange LR(getDefIndex(index), getStoreIndex(index),
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
+ DOUT << " +" << LR;
+ nI.addRange(LR);
+ }
- added.push_back(&nI);
+ added.push_back(&nI);
- // update live variables if it is available
- if (lv_)
- lv_->addVirtualRegisterKilled(NewVReg, MI);
+ // update live variables if it is available
+ if (lv_)
+ lv_->addVirtualRegisterKilled(NewVReg, MI);
- DOUT << "\t\t\t\tadded new interval: ";
- nI.print(DOUT, mri_);
- DOUT << '\n';
- }
- }
+ DOUT << "\t\t\t\tadded new interval: ";
+ nI.print(DOUT, mri_);
+ DOUT << '\n';
}
}
}
cerr << "%reg" << reg;
}
-/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to
-/// two addr elimination.
-static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg,
- const TargetInstrInfo *TII) {
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO1 = MI->getOperand(i);
- if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
- for (unsigned j = i+1; j < e; ++j) {
- MachineOperand &MO2 = MI->getOperand(j);
- if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
- MI->getInstrDescriptor()->
- getOperandConstraint(j, TOI::TIED_TO) == (int)i)
- return true;
- }
- }
- }
- return false;
-}
-
void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
MachineBasicBlock::iterator mi,
unsigned MIIdx,
// done once for the vreg. We use an empty interval to detect the first
// time we see a vreg.
if (interval.empty()) {
- // Remember if the definition can be rematerialized. All load's from fixed
- // stack slots are re-materializable.
- int FrameIdx = 0;
- if (vi.DefInst &&
- (tii_->isReMaterializable(vi.DefInst->getOpcode()) ||
- (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) &&
- mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))))
- interval.remat = vi.DefInst;
-
// Get the Idx of the defining instructions.
unsigned defIndex = getDefIndex(MIIdx);
-
- unsigned ValNum;
+ VNInfo *ValNo;
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNum = interval.getNextValue(~0U, 0);
+ if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
+ ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
+ else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+ ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
+ VNInfoAllocator);
else
- ValNum = interval.getNextValue(defIndex, SrcReg);
-
- assert(ValNum == 0 && "First value in interval is not 0?");
- ValNum = 0; // Clue in the optimizer.
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
+
+ assert(ValNo->id == 0 && "First value in interval is not 0?");
// Loop over all of the blocks that the vreg is defined in. There are
// two cases we have to handle here. The most common case is a vreg
if (killIdx > defIndex) {
assert(vi.AliveBlocks.none() &&
"Shouldn't be alive across any blocks!");
- LiveRange LR(defIndex, killIdx, ValNum);
+ LiveRange LR(defIndex, killIdx, ValNo);
interval.addRange(LR);
DOUT << " +" << LR << "\n";
+ interval.addKill(ValNo, killIdx);
return;
}
}
// range that goes from this definition to the end of the defining block.
LiveRange NewLR(defIndex,
getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
- ValNum);
+ ValNo);
DOUT << " +" << NewLR;
interval.addRange(NewLR);
if (!MBB->empty()) {
LiveRange LR(getMBBStartIdx(i),
getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
- ValNum);
+ ValNo);
interval.addRange(LR);
DOUT << " +" << LR;
}
// block to the 'use' slot of the killing instruction.
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
+ unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
LiveRange LR(getMBBStartIdx(Kill->getParent()),
- getUseIndex(getInstructionIndex(Kill))+1,
- ValNum);
+ killIdx, ValNo);
interval.addRange(LR);
+ interval.addKill(ValNo, killIdx);
DOUT << " +" << LR;
}
} else {
- // Can no longer safely assume definition is rematerializable.
- interval.remat = NULL;
-
// If this is the second time we see a virtual register definition, it
// must be due to phi elimination or two addr elimination. If this is
// the result of two address elimination, then the vreg is one of the
// def-and-use register operand.
- if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) {
+ if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
// If this is a two-address definition, then we have already processed
// the live range. The only problem is that we didn't realize there
// are actually two values in the live interval. Because of this we
unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
unsigned RedefIndex = getDefIndex(MIIdx);
+ const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
+ VNInfo *OldValNo = OldLR->valno;
+ unsigned OldEnd = OldLR->end;
+
// Delete the initial value, which should be short and continuous,
// because the 2-addr copy must be in the same MBB as the redef.
interval.removeRange(DefIndex, RedefIndex);
// The new value number (#1) is defined by the instruction we claimed
// defined value #0.
- unsigned ValNo = interval.getNextValue(0, 0);
- interval.setValueNumberInfo(1, interval.getValNumInfo(0));
+ VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
+ interval.copyValNumInfo(ValNo, OldValNo);
// Value#0 is now defined by the 2-addr instruction.
- interval.setValueNumberInfo(0, std::make_pair(~0U, 0U));
+ OldValNo->def = RedefIndex;
+ OldValNo->reg = 0;
// Add the new live interval which replaces the range for the input copy.
LiveRange LR(DefIndex, RedefIndex, ValNo);
DOUT << " replace range with " << LR;
interval.addRange(LR);
+ interval.addKill(ValNo, RedefIndex);
+ interval.removeKills(ValNo, RedefIndex, OldEnd);
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
if (lv_->RegisterDefIsDead(mi, interval.reg))
- interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
+ interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
DOUT << " RESULT: ";
interval.print(DOUT, mri_);
"PHI elimination vreg should have one kill, the PHI itself!");
// Remove the old range that we now know has an incorrect number.
+ VNInfo *VNI = interval.getValNumInfo(0);
MachineInstr *Killer = vi.Kills[0];
unsigned Start = getMBBStartIdx(Killer->getParent());
unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
DOUT << " Removing [" << Start << "," << End << "] from: ";
interval.print(DOUT, mri_); DOUT << "\n";
interval.removeRange(Start, End);
+ interval.addKill(VNI, Start+1); // odd # means phi node
DOUT << " RESULT: "; interval.print(DOUT, mri_);
// Replace the interval with one of a NEW value number. Note that this
// value number isn't actually defined by an instruction, weird huh? :)
- LiveRange LR(Start, End, interval.getNextValue(~0U, 0));
+ LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
DOUT << " replace range with " << LR;
interval.addRange(LR);
+ interval.addKill(LR.valno, End);
DOUT << " RESULT: "; interval.print(DOUT, mri_);
}
// rest of the live range.
unsigned defIndex = getDefIndex(MIIdx);
- unsigned ValNum;
+ VNInfo *ValNo;
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNum = interval.getNextValue(~0U, 0);
+ if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
+ ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
+ else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+ ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
+ VNInfoAllocator);
else
- ValNum = interval.getNextValue(defIndex, SrcReg);
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
- LiveRange LR(defIndex,
- getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum);
+ unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
+ LiveRange LR(defIndex, killIndex, ValNo);
interval.addRange(LR);
+ interval.addKill(ValNo, killIndex-1); // odd # means phi node
DOUT << " +" << LR;
}
}
// Already exists? Extend old live interval.
LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
- unsigned Id = (OldLR != interval.end())
- ? OldLR->ValId
- : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg);
- LiveRange LR(start, end, Id);
+ VNInfo *ValNo = (OldLR != interval.end())
+ ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
+ LiveRange LR(start, end, ValNo);
interval.addRange(LR);
+ interval.addKill(LR.valno, end);
DOUT << " +" << LR << '\n';
}
handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
else if (allocatableRegs_[reg]) {
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
+ if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+ SrcReg = MI->getOperand(1).getReg();
+ else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
SrcReg = 0;
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
// Def of a register also defines its sub-registers.
}
exit:
- // Alias of a live-in register might not be used at all.
- if (isAlias && end == 0) {
- DOUT << " dead";
- end = getDefIndex(start) + 1;
+ // Live-in register might not be used at all.
+ if (end == MIIdx) {
+ if (isAlias) {
+ DOUT << " dead";
+ end = getDefIndex(MIIdx) + 1;
+ } else {
+ DOUT << " live through";
+ end = baseIndex;
+ }
}
- assert(start < end && "did not find end of interval?");
-
- LiveRange LR(start, end, interval.getNextValue(~0U, 0));
- DOUT << " +" << LR << '\n';
+ LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
interval.addRange(LR);
+ interval.addKill(LR.valno, end);
+ DOUT << " +" << LR << '\n';
}
/// computeIntervals - computes the live intervals for virtual
MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
- if (MBB->livein_begin() != MBB->livein_end()) {
- // Create intervals for live-ins to this BB first.
- for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
- LE = MBB->livein_end(); LI != LE; ++LI) {
- handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
- // Multiple live-ins can alias the same register.
- for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
- if (!hasInterval(*AS))
- handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true);
- }
+ // Create intervals for live-ins to this BB first.
+ for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
+ LE = MBB->livein_end(); LI != LE; ++LI) {
+ handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
+ // Multiple live-ins can alias the same register.
+ for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
+ if (!hasInterval(*AS))
+ handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
+ true);
}
for (; MI != miEnd; ++MI) {
projects / oota-llvm.git / blobdiff