//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "liveintervals"
+#define DEBUG_TYPE "regalloc"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "VirtRegMap.h"
#include "llvm/Value.h"
#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveVariables.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineInstrBuilder.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
-#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/CodeGen/ProcessImplicitDefs.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/DepthFirstIterator.h"
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
char LiveIntervals::ID = 0;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
"Live Interval Analysis", false, false)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_DEPENDENCY(LiveVariables)
-INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
-INITIALIZE_PASS_DEPENDENCY(PHIElimination)
-INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
-INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
"Live Interval Analysis", false, false)
AU.addPreserved<AliasAnalysis>();
AU.addRequired<LiveVariables>();
AU.addPreserved<LiveVariables>();
- AU.addRequired<MachineLoopInfo>();
- AU.addPreserved<MachineLoopInfo>();
+ AU.addPreservedID(MachineLoopInfoID);
AU.addPreservedID(MachineDominatorsID);
-
- if (!StrongPHIElim) {
- AU.addPreservedID(PHIEliminationID);
- AU.addRequiredID(PHIEliminationID);
- }
-
- AU.addRequiredID(TwoAddressInstructionPassID);
- AU.addPreserved<ProcessImplicitDefs>();
- AU.addRequired<ProcessImplicitDefs>();
AU.addPreserved<SlotIndexes>();
AU.addRequiredTransitive<SlotIndexes>();
MachineFunctionPass::getAnalysisUsage(AU);
delete I->second;
r2iMap_.clear();
+ RegMaskSlots.clear();
+ RegMaskBits.clear();
+ RegMaskBlocks.clear();
// Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
VNInfoAllocator.Reset();
- while (!CloneMIs.empty()) {
- MachineInstr *MI = CloneMIs.back();
- CloneMIs.pop_back();
- mf_->DeleteMachineInstr(MI);
- }
}
/// runOnMachineFunction - Register allocate the whole function
lv_ = &getAnalysis<LiveVariables>();
indexes_ = &getAnalysis<SlotIndexes>();
allocatableRegs_ = tri_->getAllocatableSet(fn);
+ reservedRegs_ = tri_->getReservedRegs(fn);
computeIntervals();
/// print - Implement the dump method.
void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
OS << "********** INTERVALS **********\n";
- for (const_iterator I = begin(), E = end(); I != E; ++I) {
- I->second->print(OS, tri_);
- OS << "\n";
- }
+
+ // Dump the physregs.
+ for (unsigned Reg = 1, RegE = tri_->getNumRegs(); Reg != RegE; ++Reg)
+ if (const LiveInterval *LI = r2iMap_.lookup(Reg)) {
+ LI->print(OS, tri_);
+ OS << '\n';
+ }
+
+ // Dump the virtregs.
+ for (unsigned Reg = 0, RegE = mri_->getNumVirtRegs(); Reg != RegE; ++Reg)
+ if (const LiveInterval *LI =
+ r2iMap_.lookup(TargetRegisterInfo::index2VirtReg(Reg))) {
+ LI->print(OS, tri_);
+ OS << '\n';
+ }
printInstrs(OS);
}
if (!MO.getSubReg() || MO.isEarlyClobber())
return false;
- SlotIndex RedefIndex = MIIdx.getDefIndex();
+ SlotIndex RedefIndex = MIIdx.getRegSlot();
const LiveRange *OldLR =
- interval.getLiveRangeContaining(RedefIndex.getUseIndex());
+ interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
if (DefMI != 0) {
return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
if (interval.empty()) {
// Get the Idx of the defining instructions.
- SlotIndex defIndex = MIIdx.getDefIndex();
- // Earlyclobbers move back one, so that they overlap the live range
- // of inputs.
- if (MO.isEarlyClobber())
- defIndex = MIIdx.getUseIndex();
+ SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
// Make sure the first definition is not a partial redefinition. Add an
// <imp-def> of the full register.
}
}
- MachineInstr *CopyMI = NULL;
- if (mi->isCopyLike()) {
- CopyMI = mi;
- }
-
- VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
+ VNInfo *ValNo = interval.getNextValue(defIndex, 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
// FIXME: what about dead vars?
SlotIndex killIdx;
if (vi.Kills[0] != mi)
- killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
+ killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot();
else
- killIdx = defIndex.getStoreIndex();
+ killIdx = defIndex.getDeadSlot();
// If the kill happens after the definition, we have an intra-block
// live range.
for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
MachineInstr *Kill = vi.Kills[i];
SlotIndex Start = getMBBStartIdx(Kill->getParent());
- SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
+ SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot();
// Create interval with one of a NEW value number. Note that this value
// number isn't actually defined by an instruction, weird huh? :)
if (PHIJoin) {
assert(getInstructionFromIndex(Start) == 0 &&
"PHI def index points at actual instruction.");
- ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
+ ValNo = interval.getNextValue(Start, VNInfoAllocator);
ValNo->setIsPHIDef(true);
}
LiveRange LR(Start, killIdx, ValNo);
// are actually two values in the live interval. Because of this we
// need to take the LiveRegion that defines this register and split it
// into two values.
- SlotIndex RedefIndex = MIIdx.getDefIndex();
- if (MO.isEarlyClobber())
- RedefIndex = MIIdx.getUseIndex();
+ SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
const LiveRange *OldLR =
- interval.getLiveRangeContaining(RedefIndex.getUseIndex());
+ interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
VNInfo *OldValNo = OldLR->valno;
- SlotIndex DefIndex = OldValNo->def.getDefIndex();
+ SlotIndex DefIndex = OldValNo->def.getRegSlot();
// Delete the previous value, which should be short and continuous,
// because the 2-addr copy must be in the same MBB as the redef.
VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
// Value#0 is now defined by the 2-addr instruction.
- OldValNo->def = RedefIndex;
- OldValNo->setCopy(0);
-
- // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
- if (PartReDef && mi->isCopyLike())
- OldValNo->setCopy(&*mi);
+ OldValNo->def = RedefIndex;
// Add the new live interval which replaces the range for the input copy.
LiveRange LR(DefIndex, RedefIndex, ValNo);
// If this redefinition is dead, we need to add a dummy unit live
// range covering the def slot.
if (MO.isDead())
- interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
+ interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(),
OldValNo));
DEBUG({
// live until the end of the block. We've already taken care of the
// rest of the live range.
- SlotIndex defIndex = MIIdx.getDefIndex();
+ SlotIndex defIndex = MIIdx.getRegSlot();
if (MO.isEarlyClobber())
- defIndex = MIIdx.getUseIndex();
+ defIndex = MIIdx.getRegSlot(true);
- VNInfo *ValNo;
- MachineInstr *CopyMI = NULL;
- if (mi->isCopyLike())
- CopyMI = mi;
- ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
+ VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
SlotIndex killIndex = getMBBEndIdx(mbb);
LiveRange LR(defIndex, killIndex, ValNo);
DEBUG(dbgs() << '\n');
}
+#ifndef NDEBUG
+static bool isRegLiveOutOf(const MachineBasicBlock *MBB, unsigned Reg) {
+ for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
+ SE = MBB->succ_end();
+ SI != SE; ++SI) {
+ const MachineBasicBlock* succ = *SI;
+ if (succ->isLiveIn(Reg))
+ return true;
+ }
+ return false;
+}
+#endif
+
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
SlotIndex MIIdx,
MachineOperand& MO,
- LiveInterval &interval,
- MachineInstr *CopyMI) {
- // A physical register cannot be live across basic block, so its
- // lifetime must end somewhere in its defining basic block.
+ LiveInterval &interval) {
DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
SlotIndex baseIndex = MIIdx;
- SlotIndex start = baseIndex.getDefIndex();
- // Earlyclobbers move back one.
- if (MO.isEarlyClobber())
- start = MIIdx.getUseIndex();
+ SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber());
SlotIndex end = start;
// If it is not used after definition, it is considered dead at
// advance below compensates.
if (MO.isDead()) {
DEBUG(dbgs() << " dead");
- end = start.getStoreIndex();
+ end = start.getDeadSlot();
goto exit;
}
if (mi->killsRegister(interval.reg, tri_)) {
DEBUG(dbgs() << " killed");
- end = baseIndex.getDefIndex();
+ end = baseIndex.getRegSlot();
goto exit;
} else {
int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
if (DefIdx != -1) {
if (mi->isRegTiedToUseOperand(DefIdx)) {
// Two-address instruction.
- end = baseIndex.getDefIndex();
+ end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber());
} else {
// 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:
// [defSlot(def), defSlot(def)+1)
DEBUG(dbgs() << " dead");
- end = start.getStoreIndex();
+ end = start.getDeadSlot();
}
goto exit;
}
baseIndex = baseIndex.getNextIndex();
}
- // The only case we should have a dead physreg here without a killing or
- // instruction where we know it's dead is if it is live-in to the function
- // and never used. Another possible case is the implicit use of the
- // physical register has been deleted by two-address pass.
- end = start.getStoreIndex();
+ // If we get here the register *should* be live out.
+ assert(!isAllocatable(interval.reg) && "Physregs shouldn't be live out!");
+ // FIXME: We need saner rules for reserved regs.
+ if (isReserved(interval.reg)) {
+ end = start.getDeadSlot();
+ } else {
+ // Unreserved, unallocable registers like EFLAGS can be live across basic
+ // block boundaries.
+ assert(isRegLiveOutOf(MBB, interval.reg) && "Unreserved reg not live-out?");
+ end = getMBBEndIdx(MBB);
+ }
exit:
assert(start < end && "did not find end of interval?");
VNInfo *ValNo = interval.getVNInfoAt(start);
bool Extend = ValNo != 0;
if (!Extend)
- ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
- if (Extend && MO.isEarlyClobber())
- ValNo->setHasRedefByEC(true);
+ ValNo = interval.getNextValue(start, VNInfoAllocator);
LiveRange LR(start, end, ValNo);
interval.addRange(LR);
DEBUG(dbgs() << " +" << LR << '\n');
if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
getOrCreateInterval(MO.getReg()));
- else {
- MachineInstr *CopyMI = NULL;
- if (MI->isCopyLike())
- CopyMI = MI;
+ else
handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
- getOrCreateInterval(MO.getReg()), CopyMI);
- }
+ getOrCreateInterval(MO.getReg()));
}
void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
SlotIndex MIIdx,
- LiveInterval &interval, bool isAlias) {
+ LiveInterval &interval) {
+ assert(TargetRegisterInfo::isPhysicalRegister(interval.reg) &&
+ "Only physical registers can be live in.");
+ assert((!isAllocatable(interval.reg) || MBB->getParent()->begin() ||
+ MBB->isLandingPad()) &&
+ "Allocatable live-ins only valid for entry blocks and landing pads.");
+
DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
// Look for kills, if it reaches a def before it's killed, then it shouldn't
while (mi != E) {
if (mi->killsRegister(interval.reg, tri_)) {
DEBUG(dbgs() << " killed");
- end = baseIndex.getDefIndex();
+ end = baseIndex.getRegSlot();
SeenDefUse = true;
break;
- } else if (mi->definesRegister(interval.reg, tri_)) {
+ } 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:
// [defSlot(def), defSlot(def)+1)
DEBUG(dbgs() << " dead");
- end = start.getStoreIndex();
+ end = start.getDeadSlot();
SeenDefUse = true;
break;
}
// Live-in register might not be used at all.
if (!SeenDefUse) {
- if (isAlias) {
+ if (isAllocatable(interval.reg) || isReserved(interval.reg)) {
+ // This must be an entry block or landing pad - we asserted so on entry
+ // to the function. For these blocks the interval is dead on entry, so
+ // we won't emit a live-range for it.
DEBUG(dbgs() << " dead");
- end = MIIdx.getStoreIndex();
+ return;
} else {
+ assert(isRegLiveOutOf(MBB, interval.reg) &&
+ "Live in reg untouched in block should be be live through.");
DEBUG(dbgs() << " live through");
end = getMBBEndIdx(MBB);
}
SlotIndex defIdx = getMBBStartIdx(MBB);
assert(getInstructionFromIndex(defIdx) == 0 &&
"PHI def index points at actual instruction.");
- VNInfo *vni =
- interval.getNextValue(defIdx, 0, VNInfoAllocator);
+ VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator);
vni->setIsPHIDef(true);
LiveRange LR(start, end, vni);
<< "********** Function: "
<< ((Value*)mf_->getFunction())->getName() << '\n');
+ RegMaskBlocks.resize(mf_->getNumBlockIDs());
+
SmallVector<unsigned, 8> UndefUses;
for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
MBBI != E; ++MBBI) {
MachineBasicBlock *MBB = MBBI;
+ RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size();
+
if (MBB->empty())
continue;
for (MachineBasicBlock::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 = tri_->getSubRegisters(*LI); *AS; ++AS)
- if (!hasInterval(*AS))
- handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
- true);
}
// Skip over empty initial indices.
DEBUG(dbgs() << MIIndex << "\t" << *MI);
if (MI->isDebugValue())
continue;
+ assert(indexes_->getInstructionFromIndex(MIIndex) == MI &&
+ "Lost SlotIndex synchronization");
// Handle defs.
for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
MachineOperand &MO = MI->getOperand(i);
+
+ // Collect register masks.
+ if (MO.isRegMask()) {
+ RegMaskSlots.push_back(MIIndex.getRegSlot());
+ RegMaskBits.push_back(MO.getRegMask());
+ continue;
+ }
+
if (!MO.isReg() || !MO.getReg())
continue;
// Move to the next instr slot.
MIIndex = indexes_->getNextNonNullIndex(MIIndex);
}
+
+ // Compute the number of register mask instructions in this block.
+ std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
+ RMB.second = RegMaskSlots.size() - RMB.first;;
}
// Create empty intervals for registers defined by implicit_def's (except
SmallVectorImpl<MachineInstr*> *dead) {
DEBUG(dbgs() << "Shrink: " << *li << '\n');
assert(TargetRegisterInfo::isVirtualRegister(li->reg)
- && "Can't only shrink physical registers");
+ && "Can only shrink virtual registers");
// Find all the values used, including PHI kills.
SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
MachineInstr *UseMI = I.skipInstruction();) {
if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
continue;
- SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
- VNInfo *VNI = li->getVNInfoAt(Idx);
+ SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
+ // Note: This intentionally picks up the wrong VNI in case of an EC redef.
+ // See below.
+ VNInfo *VNI = li->getVNInfoBefore(Idx);
if (!VNI) {
// This shouldn't happen: readsVirtualRegister returns true, but there is
// no live value. It is likely caused by a target getting <undef> flags
<< *li << '\n');
continue;
}
- if (VNI->def == Idx) {
- // Special case: An early-clobber tied operand reads and writes the
- // register one slot early.
- Idx = Idx.getPrevSlot();
- VNI = li->getVNInfoAt(Idx);
+ // Special case: An early-clobber tied operand reads and writes the
+ // register one slot early. The getVNInfoBefore call above would have
+ // picked up the value defined by UseMI. Adjust the kill slot and value.
+ if (SlotIndex::isSameInstr(VNI->def, Idx)) {
+ Idx = VNI->def;
+ VNI = li->getVNInfoBefore(Idx);
assert(VNI && "Early-clobber tied value not available");
}
WorkList.push_back(std::make_pair(Idx, VNI));
VNInfo *VNI = *I;
if (VNI->isUnused())
continue;
- NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
-
- // A use tied to an early-clobber def ends at the load slot and isn't caught
- // above. Catch it here instead. This probably only ever happens for inline
- // assembly.
- if (VNI->def.isUse())
- if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
- WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
+ NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
}
// Keep track of the PHIs that are in use.
SlotIndex Idx = WorkList.back().first;
VNInfo *VNI = WorkList.back().second;
WorkList.pop_back();
- const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
+ const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
SlotIndex BlockStart = getMBBStartIdx(MBB);
// Extend the live range for VNI to be live at Idx.
- if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx.getNextSlot())) {
+ if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
(void)ExtVNI;
assert(ExtVNI == VNI && "Unexpected existing value number");
// Is this a PHIDef we haven't seen before?
PE = MBB->pred_end(); PI != PE; ++PI) {
if (!LiveOut.insert(*PI))
continue;
- SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
+ SlotIndex Stop = getMBBEndIdx(*PI);
// A predecessor is not required to have a live-out value for a PHI.
- if (VNInfo *PVNI = li->getVNInfoAt(Stop))
+ if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
WorkList.push_back(std::make_pair(Stop, PVNI));
}
continue;
// VNI is live-in to MBB.
DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
- NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
+ NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
// 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))
continue;
- SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
- assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
+ SlotIndex Stop = getMBBEndIdx(*PI);
+ assert(li->getVNInfoBefore(Stop) == VNI &&
+ "Wrong value out of predecessor");
WorkList.push_back(std::make_pair(Stop, VNI));
}
}
continue;
LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
assert(LII != NewLI.end() && "Missing live range for PHI");
- if (LII->end != VNI->def.getNextSlot())
+ if (LII->end != VNI->def.getDeadSlot())
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
// Register allocator hooks.
//
-MachineBasicBlock::iterator
-LiveIntervals::getLastSplitPoint(const LiveInterval &li,
- MachineBasicBlock *mbb) const {
- const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
-
- // If li is not live into a landing pad, we can insert spill code before the
- // first terminator.
- if (!lpad || !isLiveInToMBB(li, lpad))
- return mbb->getFirstTerminator();
-
- // When there is a landing pad, spill code must go before the call instruction
- // that can throw.
- MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
- while (I != B) {
- --I;
- if (I->getDesc().isCall())
- return I;
- }
- // The block contains no calls that can throw, so use the first terminator.
- return mbb->getFirstTerminator();
-}
-
void LiveIntervals::addKillFlags() {
for (iterator I = begin(), E = end(); I != E; ++I) {
unsigned Reg = I->first;
// Every instruction that kills Reg corresponds to a live range end point.
for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
++RI) {
- // A LOAD index indicates an MBB edge.
- if (RI->end.isLoad())
+ // A block index indicates an MBB edge.
+ if (RI->end.isBlock())
continue;
MachineInstr *MI = getInstructionFromIndex(RI->end);
if (!MI)
}
}
+#ifndef NDEBUG
+static bool intervalRangesSane(const LiveInterval& li) {
+ if (li.empty()) {
+ return true;
+ }
+
+ SlotIndex lastEnd = li.begin()->start;
+ for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end();
+ lrItr != lrEnd; ++lrItr) {
+ const LiveRange& lr = *lrItr;
+ if (lastEnd > lr.start || lr.start >= lr.end)
+ return false;
+ lastEnd = lr.end;
+ }
+
+ return true;
+}
+#endif
+
+template <typename DefSetT>
+static void handleMoveDefs(LiveIntervals& lis, SlotIndex origIdx,
+ SlotIndex miIdx, const DefSetT& defs) {
+ for (typename DefSetT::const_iterator defItr = defs.begin(),
+ defEnd = defs.end();
+ defItr != defEnd; ++defItr) {
+ unsigned def = *defItr;
+ LiveInterval& li = lis.getInterval(def);
+ LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
+ assert(lr != 0 && "No range for def?");
+ lr->start = miIdx.getRegSlot();
+ lr->valno->def = miIdx.getRegSlot();
+ assert(intervalRangesSane(li) && "Broke live interval moving def.");
+ }
+}
+
+template <typename DeadDefSetT>
+static void handleMoveDeadDefs(LiveIntervals& lis, SlotIndex origIdx,
+ SlotIndex miIdx, const DeadDefSetT& deadDefs) {
+ for (typename DeadDefSetT::const_iterator deadDefItr = deadDefs.begin(),
+ deadDefEnd = deadDefs.end();
+ deadDefItr != deadDefEnd; ++deadDefItr) {
+ unsigned deadDef = *deadDefItr;
+ LiveInterval& li = lis.getInterval(deadDef);
+ LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
+ assert(lr != 0 && "No range for dead def?");
+ assert(lr->start == origIdx.getRegSlot() && "Bad dead range start?");
+ assert(lr->end == origIdx.getDeadSlot() && "Bad dead range end?");
+ assert(lr->valno->def == origIdx.getRegSlot() && "Bad dead valno def.");
+ LiveRange t(*lr);
+ t.start = miIdx.getRegSlot();
+ t.valno->def = miIdx.getRegSlot();
+ t.end = miIdx.getDeadSlot();
+ li.removeRange(*lr);
+ li.addRange(t);
+ assert(intervalRangesSane(li) && "Broke live interval moving dead def.");
+ }
+}
+
+template <typename ECSetT>
+static void handleMoveECs(LiveIntervals& lis, SlotIndex origIdx,
+ SlotIndex miIdx, const ECSetT& ecs) {
+ for (typename ECSetT::const_iterator ecItr = ecs.begin(), ecEnd = ecs.end();
+ ecItr != ecEnd; ++ecItr) {
+ unsigned ec = *ecItr;
+ LiveInterval& li = lis.getInterval(ec);
+ LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot(true));
+ assert(lr != 0 && "No range for early clobber?");
+ assert(lr->start == origIdx.getRegSlot(true) && "Bad EC range start?");
+ assert(lr->end == origIdx.getRegSlot() && "Bad EC range end.");
+ assert(lr->valno->def == origIdx.getRegSlot(true) && "Bad EC valno def.");
+ LiveRange t(*lr);
+ t.start = miIdx.getRegSlot(true);
+ t.valno->def = miIdx.getRegSlot(true);
+ t.end = miIdx.getRegSlot();
+ li.removeRange(*lr);
+ li.addRange(t);
+ assert(intervalRangesSane(li) && "Broke live interval moving EC.");
+ }
+}
+
+static void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newIdx,
+ LiveIntervals& lis,
+ const TargetRegisterInfo& tri) {
+ MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx);
+ MachineInstr* newKillMI = lis.getInstructionFromIndex(newIdx);
+ assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
+ assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill.");
+ oldKillMI->clearRegisterKills(reg, &tri);
+ newKillMI->addRegisterKilled(reg, &tri);
+}
+
+template <typename UseSetT>
+static void handleMoveUses(const MachineBasicBlock *mbb,
+ const MachineRegisterInfo& mri,
+ const TargetRegisterInfo& tri,
+ const BitVector& reservedRegs, LiveIntervals &lis,
+ SlotIndex origIdx, SlotIndex miIdx,
+ const UseSetT &uses) {
+ bool movingUp = miIdx < origIdx;
+ for (typename UseSetT::const_iterator usesItr = uses.begin(),
+ usesEnd = uses.end();
+ usesItr != usesEnd; ++usesItr) {
+ unsigned use = *usesItr;
+ if (!lis.hasInterval(use))
+ continue;
+ if (TargetRegisterInfo::isPhysicalRegister(use) && reservedRegs.test(use))
+ continue;
+ LiveInterval& li = lis.getInterval(use);
+ LiveRange* lr = li.getLiveRangeBefore(origIdx.getRegSlot());
+ assert(lr != 0 && "No range for use?");
+ bool liveThrough = lr->end > origIdx.getRegSlot();
+
+ if (movingUp) {
+ // If moving up and liveThrough - nothing to do.
+ // If not live through we need to extend the range to the last use
+ // between the old location and the new one.
+ if (!liveThrough) {
+ SlotIndex lastUseInRange = miIdx.getRegSlot();
+ for (MachineRegisterInfo::use_iterator useI = mri.use_begin(use),
+ useE = mri.use_end();
+ useI != useE; ++useI) {
+ const MachineInstr* mopI = &*useI;
+ const MachineOperand& mop = useI.getOperand();
+ SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI);
+ SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber());
+ if (opSlot > lastUseInRange && opSlot < origIdx)
+ lastUseInRange = opSlot;
+ }
+
+ // If we found a new instr endpoint update the kill flags.
+ if (lastUseInRange != miIdx.getRegSlot())
+ moveKillFlags(use, miIdx, lastUseInRange, lis, tri);
+
+ // Fix up the range end.
+ lr->end = lastUseInRange;
+ }
+ } else {
+ // Moving down is easy - the existing live range end tells us where
+ // the last kill is.
+ if (!liveThrough) {
+ // Easy fix - just update the range endpoint.
+ lr->end = miIdx.getRegSlot();
+ } else {
+ bool liveOut = lr->end >= lis.getSlotIndexes()->getMBBEndIdx(mbb);
+ if (!liveOut && miIdx.getRegSlot() > lr->end) {
+ moveKillFlags(use, lr->end, miIdx, lis, tri);
+ lr->end = miIdx.getRegSlot();
+ }
+ }
+ }
+ assert(intervalRangesSane(li) && "Broke live interval moving use.");
+ }
+}
+
+
+
+void LiveIntervals::handleMove(MachineInstr* mi) {
+ SlotIndex origIdx = indexes_->getInstructionIndex(mi);
+ indexes_->removeMachineInstrFromMaps(mi);
+ SlotIndex miIdx = mi->isInsideBundle() ?
+ indexes_->getInstructionIndex(mi->getBundleStart()) :
+ indexes_->insertMachineInstrInMaps(mi);
+ MachineBasicBlock* mbb = mi->getParent();
+ assert(getMBBStartIdx(mbb) <= origIdx && origIdx < getMBBEndIdx(mbb) &&
+ "Cannot handle moves across basic block boundaries.");
+ assert(!mi->isBundled() && "Can't handle bundled instructions yet.");
+
+ // Pick the direction.
+ bool movingUp = miIdx < origIdx;
+
+ // Collect the operands.
+ DenseSet<unsigned> uses, defs, deadDefs, ecs;
+ for (MachineInstr::mop_iterator mopItr = mi->operands_begin(),
+ mopEnd = mi->operands_end();
+ mopItr != mopEnd; ++mopItr) {
+ const MachineOperand& mop = *mopItr;
+
+ if (!mop.isReg() || mop.getReg() == 0)
+ continue;
+ unsigned reg = mop.getReg();
+
+ if (mop.readsReg() && !ecs.count(reg)) {
+ uses.insert(reg);
+ }
+ if (mop.isDef()) {
+ if (mop.isDead()) {
+ assert(!defs.count(reg) && "Can't mix defs with dead-defs.");
+ deadDefs.insert(reg);
+ } else if (mop.isEarlyClobber()) {
+ uses.erase(reg);
+ ecs.insert(reg);
+ } else {
+ assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs.");
+ defs.insert(reg);
+ }
+ }
+ }
+
+ if (movingUp) {
+ handleMoveUses(mbb, *mri_, *tri_, reservedRegs_, *this, origIdx, miIdx, uses);
+ handleMoveECs(*this, origIdx, miIdx, ecs);
+ handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
+ handleMoveDefs(*this, origIdx, miIdx, defs);
+ } else {
+ handleMoveDefs(*this, origIdx, miIdx, defs);
+ handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
+ handleMoveECs(*this, origIdx, miIdx, ecs);
+ handleMoveUses(mbb, *mri_, *tri_, reservedRegs_, *this, origIdx, miIdx, uses);
+ }
+}
+
/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
/// allow one) virtual register operand, then its uses are implicitly using
/// the register. Returns the virtual register.
if (Reg == 0 || Reg == li.reg)
continue;
- if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
- !allocatableRegs_[Reg])
+ if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isAllocatable(Reg))
continue;
- // FIXME: For now, only remat MI with at most one register operand.
- assert(!RegOp &&
- "Can't rematerialize instruction with multiple register operand!");
RegOp = MO.getReg();
-#ifndef NDEBUG
- break;
-#endif
+ break; // Found vreg operand - leave the loop.
}
return RegOp;
}
return true;
}
-bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
- LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
-
- MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
-
- if (mbb == 0)
- return false;
-
- for (++itr; itr != li.ranges.end(); ++itr) {
- MachineBasicBlock *mbb2 =
- indexes_->getMBBCoveringRange(itr->start, itr->end);
-
- if (mbb2 != mbb)
- return false;
- }
-
- return true;
+MachineBasicBlock*
+LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
+ // A local live range must be fully contained inside the block, meaning it is
+ // defined and killed at instructions, not at block boundaries. It is not
+ // live in or or out of any block.
+ //
+ // It is technically possible to have a PHI-defined live range identical to a
+ // single block, but we are going to return false in that case.
+
+ SlotIndex Start = LI.beginIndex();
+ if (Start.isBlock())
+ return NULL;
+
+ SlotIndex Stop = LI.endIndex();
+ if (Stop.isBlock())
+ return NULL;
+
+ // 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;
}
float
MachineInstr* startInst) {
LiveInterval& Interval = getOrCreateInterval(reg);
VNInfo* VN = Interval.getNextValue(
- SlotIndex(getInstructionIndex(startInst).getDefIndex()),
- startInst, getVNInfoAllocator());
+ SlotIndex(getInstructionIndex(startInst).getRegSlot()),
+ getVNInfoAllocator());
VN->setHasPHIKill(true);
LiveRange LR(
- SlotIndex(getInstructionIndex(startInst).getDefIndex()),
+ SlotIndex(getInstructionIndex(startInst).getRegSlot()),
getMBBEndIdx(startInst->getParent()), VN);
Interval.addRange(LR);
return LR;
}
+
+//===----------------------------------------------------------------------===//
+// Register mask functions
+//===----------------------------------------------------------------------===//
+
+bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
+ BitVector &UsableRegs) {
+ if (LI.empty())
+ return false;
+ LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
+
+ // Use a smaller arrays for local live ranges.
+ ArrayRef<SlotIndex> Slots;
+ ArrayRef<const uint32_t*> Bits;
+ if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
+ Slots = getRegMaskSlotsInBlock(MBB->getNumber());
+ Bits = getRegMaskBitsInBlock(MBB->getNumber());
+ } else {
+ Slots = getRegMaskSlots();
+ Bits = getRegMaskBits();
+ }
+
+ // We are going to enumerate all the register mask slots contained in LI.
+ // Start with a binary search of RegMaskSlots to find a starting point.
+ ArrayRef<SlotIndex>::iterator SlotI =
+ std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
+ ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
+
+ // No slots in range, LI begins after the last call.
+ if (SlotI == SlotE)
+ return false;
+
+ bool Found = false;
+ for (;;) {
+ assert(*SlotI >= LiveI->start);
+ // Loop over all slots overlapping this segment.
+ while (*SlotI < LiveI->end) {
+ // *SlotI overlaps LI. Collect mask bits.
+ if (!Found) {
+ // This is the first overlap. Initialize UsableRegs to all ones.
+ UsableRegs.clear();
+ UsableRegs.resize(tri_->getNumRegs(), true);
+ Found = true;
+ }
+ // Remove usable registers clobbered by this mask.
+ UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
+ if (++SlotI == SlotE)
+ return Found;
+ }
+ // *SlotI is beyond the current LI segment.
+ LiveI = LI.advanceTo(LiveI, *SlotI);
+ if (LiveI == LiveE)
+ return Found;
+ // Advance SlotI until it overlaps.
+ while (*SlotI < LiveI->start)
+ if (++SlotI == SlotE)
+ return Found;
+ }
+}
projects / oota-llvm.git / blobdiff