}
// Set the MBB2IdxMap entry for this MBB.
- MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
+ MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex)
+ ? std::make_pair(StartIdx, StartIdx) // Empty MBB
+ : std::make_pair(StartIdx, MIIndex - 1);
Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
}
std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
+ if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ DOUT << "is a implicit_def\n";
+ return;
+ }
+
// Virtual registers may be defined multiple times (due to phi
// elimination and 2-addr elimination). Much of what we do only has to be
// done once for the vreg. We use an empty interval to detect the first
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
- if (lv_->RegisterDefIsDead(mi, interval.reg))
+ if (mi->registerDefIsDead(interval.reg, tri_))
interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
DOUT << " RESULT: ";
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*mi, SrcReg, DstReg))
CopyMI = mi;
ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
// If it is not used after definition, it is considered dead at
// the instruction defining it. Hence its interval is:
// [defSlot(def), defSlot(def)+1)
- if (lv_->RegisterDefIsDead(mi, interval.reg)) {
+ if (mi->registerDefIsDead(interval.reg, tri_)) {
DOUT << " dead";
end = getDefIndex(start) + 1;
goto exit;
// [defSlot(def), useSlot(kill)+1)
while (++mi != MBB->end()) {
baseIndex += InstrSlots::NUM;
- if (lv_->KillsRegister(mi, interval.reg)) {
+ if (mi->killsRegister(interval.reg, tri_)) {
DOUT << " killed";
end = getUseIndex(baseIndex) + 1;
goto exit;
- } else if (lv_->ModifiesRegister(mi, interval.reg)) {
+ } else if (mi->modifiesRegister(interval.reg, tri_)) {
// Another instruction redefines the register before it is ever read.
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
MachineInstr *CopyMI = NULL;
unsigned SrcReg, DstReg;
if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
tii_->isMoveInstr(*MI, SrcReg, DstReg))
CopyMI = MI;
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
// Def of a register also defines its sub-registers.
for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS)
- // Avoid processing some defs more than once.
- if (!MI->findRegisterDefOperand(*AS))
+ // If MI also modifies the sub-register explicitly, avoid processing it
+ // more than once. Do not pass in TRI here so it checks for exact match.
+ if (!MI->modifiesRegister(*AS))
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
}
}
unsigned start = baseIndex;
unsigned end = start;
while (mi != MBB->end()) {
- if (lv_->KillsRegister(mi, interval.reg)) {
+ if (mi->killsRegister(interval.reg, tri_)) {
DOUT << " killed";
end = getUseIndex(baseIndex) + 1;
goto exit;
- } else if (lv_->ModifiesRegister(mi, interval.reg)) {
+ } else if (mi->modifiesRegister(interval.reg, tri_)) {
// Another instruction redefines the register before it is ever read.
// Then the register is essentially dead at the instruction that defines
// it. Hence its interval is:
if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
return VNI->copy->getOperand(1).getReg();
+ if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+ return VNI->copy->getOperand(2).getReg();
unsigned SrcReg, DstReg;
if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
return SrcReg;
return false;
isLoad = false;
- const TargetInstrDesc &TID = MI->getDesc();
- if (TID.isImplicitDef())
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
return true;
+
+ int FrameIdx = 0;
+ if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
+ mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
+ // FIXME: Let target specific isReallyTriviallyReMaterializable determines
+ // this but remember this is not safe to fold into a two-address
+ // instruction.
+ // This is a load from fixed stack slot. It can be rematerialized.
+ return true;
+
if (tii_->isTriviallyReMaterializable(MI)) {
+ const TargetInstrDesc &TID = MI->getDesc();
isLoad = TID.isSimpleLoad();
unsigned ImpUse = getReMatImplicitUse(li, MI);
unsigned UseIdx = getInstructionIndex(UseMI);
if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
continue;
- if (!canFoldMemoryOperand(UseMI, li.reg) &&
- !isValNoAvailableAt(ImpLi, MI, UseIdx))
+ if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
return false;
}
}
return true;
}
- int FrameIdx = 0;
- if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
- !mf_->getFrameInfo()->isImmutableObjectIndex(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.
- isLoad = true;
- 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)) {
- isLoad = false;
- return false;
- }
- }
- return true;
+ return false;
}
/// isReMaterializable - Returns true if every definition of MI of every
return true;
}
-/// 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 InstrIdx,
- SmallVector<unsigned, 2> &Ops,
- bool isSS, int Slot, unsigned Reg) {
- unsigned MRInfo = 0;
+/// FilterFoldedOps - Filter out two-address use operands. Return
+/// true if it finds any issue with the operands that ought to prevent
+/// folding.
+static bool FilterFoldedOps(MachineInstr *MI,
+ SmallVector<unsigned, 2> &Ops,
+ unsigned &MRInfo,
+ SmallVector<unsigned, 2> &FoldOps) {
const TargetInstrDesc &TID = MI->getDesc();
- // If it is an implicit def instruction, just delete it.
- if (TID.isImplicitDef()) {
- RemoveMachineInstrFromMaps(MI);
- vrm.RemoveMachineInstrFromMaps(MI);
- MI->eraseFromParent();
- ++numFolds;
- return true;
- }
- SmallVector<unsigned, 2> FoldOps;
+ MRInfo = 0;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
unsigned OpIdx = Ops[i];
MachineOperand &MO = MI->getOperand(OpIdx);
// FIXME: fold subreg use.
if (MO.getSubReg())
- return false;
+ return true;
if (MO.isDef())
MRInfo |= (unsigned)VirtRegMap::isMod;
else {
}
FoldOps.push_back(OpIdx);
}
+ return false;
+}
+
+
+/// 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 InstrIdx,
+ SmallVector<unsigned, 2> &Ops,
+ bool isSS, int Slot, unsigned Reg) {
+ // If it is an implicit def instruction, just delete it.
+ if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
+ RemoveMachineInstrFromMaps(MI);
+ vrm.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ ++numFolds;
+ return true;
+ }
+
+ // Filter the list of operand indexes that are to be folded. Abort if
+ // any operand will prevent folding.
+ unsigned MRInfo = 0;
+ SmallVector<unsigned, 2> FoldOps;
+ if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
+ return false;
+
+ // The only time it's safe to fold into a two address instruction is when
+ // it's folding reload and spill from / into a spill stack slot.
+ if (DefMI && (MRInfo & VirtRegMap::isMod))
+ return false;
MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
: tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
if (fmi) {
+ // Remember this instruction uses the spill slot.
+ if (isSS) vrm.addSpillSlotUse(Slot, 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_)
vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
vrm.transferSpillPts(MI, fmi);
vrm.transferRestorePts(MI, fmi);
+ vrm.transferEmergencySpills(MI, fmi);
mi2iMap_.erase(MI);
i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
mi2iMap_[fmi] = InstrIdx;
/// canFoldMemoryOperand - Returns true if the specified load / store
/// folding is possible.
bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
- SmallVector<unsigned, 2> &Ops) const {
+ SmallVector<unsigned, 2> &Ops,
+ bool ReMat) const {
+ // Filter the list of operand indexes that are to be folded. Abort if
+ // any operand will prevent folding.
+ unsigned MRInfo = 0;
SmallVector<unsigned, 2> FoldOps;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- unsigned OpIdx = Ops[i];
- // FIXME: fold subreg use.
- if (MI->getOperand(OpIdx).getSubReg())
- return false;
- FoldOps.push_back(OpIdx);
- }
+ if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
+ return false;
- return tii_->canFoldMemoryOperand(MI, FoldOps);
-}
+ // It's only legal to remat for a use, not a def.
+ if (ReMat && (MRInfo & VirtRegMap::isMod))
+ return false;
-bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, unsigned Reg) const {
- SmallVector<unsigned, 2> FoldOps;
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand& mop = MI->getOperand(i);
- if (!mop.isRegister())
- continue;
- unsigned UseReg = mop.getReg();
- if (UseReg != Reg)
- continue;
- // FIXME: fold subreg use.
- if (mop.getSubReg())
- return false;
- FoldOps.push_back(i);
- }
return tii_->canFoldMemoryOperand(MI, FoldOps);
}
if (!vrm.isReMaterialized(Reg))
continue;
MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
- int OpIdx = ReMatMI->findRegisterUseOperandIdx(li.reg);
- if (OpIdx != -1)
- ReMatMI->getOperand(OpIdx).setReg(NewVReg);
+ MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
+ if (UseMO)
+ UseMO->setReg(NewVReg);
}
}
if (MI == ReMatOrigDefMI && CanDelete) {
DOUT << "\t\t\t\tErasing re-materlizable def: ";
DOUT << MI << '\n';
- unsigned ImpUse = getReMatImplicitUse(li, MI);
- if (ImpUse) {
- // To be deleted MI has a virtual register operand, update the
- // spill weight of the register interval.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
- LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight -=
- getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
- }
RemoveMachineInstrFromMaps(MI);
vrm.RemoveMachineInstrFromMaps(MI);
MI->eraseFromParent();
HasUse = false;
HasDef = false;
CanFold = false;
+ if (isRemoved(MI))
+ break;
goto RestartInstruction;
}
} else {
- CanFold = canFoldMemoryOperand(MI, Ops);
+ CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
}
} else
CanFold = false;
unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
// First collect all the def / use in this live range that will be rewritten.
- // Make sure they are sorted according instruction index.
+ // Make sure they are sorted according to instruction index.
std::vector<RewriteInfo> RewriteMIs;
for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
re = mri_->reg_end(); ri != re; ) {
- MachineInstr *MI = &(*ri);
+ MachineInstr *MI = &*ri;
MachineOperand &O = ri.getOperand();
++ri;
+ assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
unsigned index = getInstructionIndex(MI);
if (index < start || index >= end)
continue;
if (ImpUse && MI != ReMatDefMI) {
// Re-matting an instruction with virtual register use. Update the
- // register interval's spill weight.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
+ // register interval's spill weight to HUGE_VALF to prevent it from
+ // being spilled.
LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight +=
- getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize();
+ ImpLi.weight = HUGE_VALF;
}
unsigned MBBId = MBB->getNumber();
Restores[i].index = -1;
}
+/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
+/// spilled and create empty intervals for their uses.
+void
+LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
+ const TargetRegisterClass* rc,
+ std::vector<LiveInterval*> &NewLIs) {
+ for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
+ re = mri_->reg_end(); ri != re; ) {
+ MachineOperand &O = ri.getOperand();
+ MachineInstr *MI = &*ri;
+ ++ri;
+ if (O.isDef()) {
+ assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
+ "Register def was not rewritten?");
+ RemoveMachineInstrFromMaps(MI);
+ vrm.RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ } else {
+ // This must be an use of an implicit_def so it's not part of the live
+ // interval. Create a new empty live interval for it.
+ // FIXME: Can we simply erase some of the instructions? e.g. Stores?
+ unsigned NewVReg = mri_->createVirtualRegister(rc);
+ vrm.grow();
+ vrm.setIsImplicitlyDefined(NewVReg);
+ NewLIs.push_back(&getOrCreateInterval(NewVReg));
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO = MI->getOperand(i);
+ if (MO.isReg() && MO.getReg() == li.reg)
+ MO.setReg(NewVReg);
+ }
+ }
+ }
+}
+
std::vector<LiveInterval*> LiveIntervals::
addIntervalsForSpills(const LiveInterval &li,
}
IsFirstRange = false;
}
+
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
}
}
// Insert spills / restores if we are splitting.
- if (!TrySplit)
+ if (!TrySplit) {
+ handleSpilledImpDefs(li, vrm, rc, NewLIs);
return NewLIs;
+ }
SmallPtrSet<LiveInterval*, 4> AddedKill;
SmallVector<unsigned, 2> Ops;
}
}
- // Else tell the spiller to issue a spill.
+ // Otherwise tell the spiller to issue a spill.
if (!Folded) {
LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
bool isKill = LR->end == getStoreIndex(index);
if (ImpUse) {
// Re-matting an instruction with virtual register use. Add the
// register as an implicit use on the use MI and update the register
- // interval's spill weight.
- unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
+ // interval's spill weight to HUGE_VALF to prevent it from being
+ // spilled.
LiveInterval &ImpLi = getInterval(ImpUse);
- ImpLi.weight +=
- getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
-
+ ImpLi.weight = HUGE_VALF;
MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
}
}
LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
unsigned LastUseIdx = getBaseIndex(LR->end);
MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
- int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg);
+ int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
assert(UseIdx != -1);
if (LastUse->getOperand(UseIdx).isImplicit() ||
LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
}
}
+ handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
return RetNewLIs;
}
+
+/// hasAllocatableSuperReg - Return true if the specified physical register has
+/// any super register that's allocatable.
+bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
+ for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
+ if (allocatableRegs_[*AS] && hasInterval(*AS))
+ return true;
+ return false;
+}
+
+/// getRepresentativeReg - Find the largest super register of the specified
+/// physical register.
+unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
+ // Find the largest super-register that is allocatable.
+ unsigned BestReg = Reg;
+ for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
+ unsigned SuperReg = *AS;
+ if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
+ BestReg = SuperReg;
+ break;
+ }
+ }
+ return BestReg;
+}
+
+/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
+/// specified interval that conflicts with the specified physical register.
+unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
+ unsigned PhysReg) const {
+ unsigned NumConflicts = 0;
+ const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
+ for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
+ E = mri_->reg_end(); I != E; ++I) {
+ MachineOperand &O = I.getOperand();
+ MachineInstr *MI = O.getParent();
+ unsigned Index = getInstructionIndex(MI);
+ if (pli.liveAt(Index))
+ ++NumConflicts;
+ }
+ return NumConflicts;
+}
+
+/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
+/// around all defs and uses of the specified interval.
+void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
+ unsigned PhysReg, VirtRegMap &vrm) {
+ unsigned SpillReg = getRepresentativeReg(PhysReg);
+
+ for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
+ // If there are registers which alias PhysReg, but which are not a
+ // sub-register of the chosen representative super register. Assert
+ // since we can't handle it yet.
+ assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
+ tri_->isSuperRegister(*AS, SpillReg));
+
+ LiveInterval &pli = getInterval(SpillReg);
+ SmallPtrSet<MachineInstr*, 8> SeenMIs;
+ for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
+ E = mri_->reg_end(); I != E; ++I) {
+ MachineOperand &O = I.getOperand();
+ MachineInstr *MI = O.getParent();
+ if (SeenMIs.count(MI))
+ continue;
+ SeenMIs.insert(MI);
+ unsigned Index = getInstructionIndex(MI);
+ if (pli.liveAt(Index)) {
+ vrm.addEmergencySpill(SpillReg, MI);
+ pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
+ for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
+ if (!hasInterval(*AS))
+ continue;
+ LiveInterval &spli = getInterval(*AS);
+ if (spli.liveAt(Index))
+ spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
+ }
+ }
+ }
+}
projects / oota-llvm.git / blobdiff