#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/MachineLoopInfo.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/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.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();
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);
}
DEBUG(dbgs() << '\n');
}
+static bool isRegLiveIntoSuccessor(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;
+}
+
void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
MachineBasicBlock::iterator mi,
SlotIndex MIIdx,
MachineOperand& MO,
LiveInterval &interval) {
- // A physical register cannot be live across basic block, so its
- // lifetime must end somewhere in its defining basic block.
DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
SlotIndex baseIndex = MIIdx;
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.getDeadSlot();
+ // 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(isRegLiveIntoSuccessor(MBB, interval.reg) &&
+ "Unreserved reg not live-out?");
+ end = getMBBEndIdx(MBB);
+ }
exit:
assert(start < end && "did not find end of interval?");
bool Extend = ValNo != 0;
if (!Extend)
ValNo = interval.getNextValue(start, VNInfoAllocator);
- if (Extend && MO.isEarlyClobber())
- ValNo->setHasRedefByEC(true);
LiveRange LR(start, end, ValNo);
interval.addRange(LR);
DEBUG(dbgs() << " +" << LR << '\n');
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
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:
// Live-in register might not be used at all.
if (!SeenDefUse) {
- if (isAlias) {
+ if (isAllocatable(interval.reg) ||
+ !isRegLiveIntoSuccessor(MBB, interval.reg)) {
+ // Allocatable registers are never live through.
+ // Non-allocatable registers that aren't live into any successors also
+ // aren't live through.
DEBUG(dbgs() << " dead");
- end = MIIdx.getDeadSlot();
+ return;
} else {
+ // If we get here the register is non-allocatable and live into some
+ // successor. We'll conservatively assume it's live-through.
DEBUG(dbgs() << " live through");
end = getMBBEndIdx(MBB);
}
<< "********** 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;
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
}
}
-#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.");
- }
-}
-
-template <typename UseSetT>
-static void handleMoveUses(const MachineBasicBlock *mbb,
- const MachineRegisterInfo& mri,
- 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;
- }
- }
- 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) {
- lr->end = miIdx.getRegSlot();
- }
- }
- }
- assert(intervalRangesSane(li) && "Broke live interval moving use.");
- }
-}
-
-void LiveIntervals::moveInstr(MachineBasicBlock::iterator insertPt,
- MachineInstr *mi) {
- MachineBasicBlock* mbb = mi->getParent();
- assert((insertPt == mbb->end() || insertPt->getParent() == mbb) &&
- "Cannot handle moves across basic block boundaries.");
- assert(&*insertPt != mi && "No-op move requested?");
- assert(!mi->isInsideBundle() && "Can't handle bundled instructions yet.");
-
- // Grab the original instruction index.
- SlotIndex origIdx = indexes_->getInstructionIndex(mi);
-
- // Move the machine instr and obtain its new index.
- indexes_->removeMachineInstrFromMaps(mi);
- mbb->remove(mi);
- mbb->insert(insertPt, mi);
- SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi);
-
- // 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.isUse()) {
- assert(mop.readsReg());
- }
-
- 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);
- }
- }
- }
-
- BitVector reservedRegs(tri_->getReservedRegs(*mbb->getParent()));
-
- if (movingUp) {
- handleMoveUses(mbb, *mri_, 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_, 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;
RegOp = MO.getReg();
break; // Found vreg operand - leave the loop.
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
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;
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// IntervalUpdate class.
+//===----------------------------------------------------------------------===//
+
+/// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
+class LiveIntervals::HMEditor {
+private:
+ LiveIntervals& LIS;
+ const MachineRegisterInfo& MRI;
+ const TargetRegisterInfo& TRI;
+ SlotIndex NewIdx;
+
+ typedef std::pair<LiveInterval*, LiveRange*> IntRangePair;
+ typedef DenseSet<IntRangePair> RangeSet;
+
+public:
+ HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
+ const TargetRegisterInfo& TRI, SlotIndex NewIdx)
+ : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {}
+
+ // Update intervals for all operands of MI from OldIdx to NewIdx.
+ // This assumes that MI used to be at OldIdx, and now resides at
+ // NewIdx.
+ void moveAllOperandsFrom(MachineInstr* MI, SlotIndex OldIdx) {
+ // Collect the operands.
+ RangeSet Entering, Internal, Exiting;
+ bool hasRegMaskOp = false;
+ collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
+
+ moveAllEnteringFrom(OldIdx, Entering);
+ moveAllInternalFrom(OldIdx, Internal);
+ moveAllExitingFrom(OldIdx, Exiting);
+
+ if (hasRegMaskOp)
+ updateRegMaskSlots(OldIdx);
+
+#ifndef NDEBUG
+ LIValidator validator;
+ std::for_each(Entering.begin(), Entering.end(), validator);
+ std::for_each(Internal.begin(), Internal.end(), validator);
+ std::for_each(Exiting.begin(), Exiting.end(), validator);
+ assert(validator.rangesOk() && "moveOperandsFrom broke liveness.");
+#endif
+
+ }
+
+private:
+
+#ifndef NDEBUG
+ class LIValidator {
+ private:
+ DenseSet<const LiveInterval*> Checked, Bogus;
+ public:
+ void operator()(const IntRangePair& P) {
+ const LiveInterval* LI = P.first;
+ if (Checked.count(LI))
+ return;
+ Checked.insert(LI);
+ if (LI->empty())
+ return;
+ SlotIndex LastEnd = LI->begin()->start;
+ for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end();
+ LRI != LRE; ++LRI) {
+ const LiveRange& LR = *LRI;
+ if (LastEnd > LR.start || LR.start >= LR.end)
+ Bogus.insert(LI);
+ LastEnd = LR.end;
+ }
+ }
+
+ bool rangesOk() const {
+ return Bogus.empty();
+ }
+ };
+#endif
+
+ // Collect IntRangePairs for all operands of MI that may need fixing.
+ // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes'
+ // maps).
+ void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal,
+ RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) {
+ hasRegMaskOp = false;
+ for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
+ MOE = MI->operands_end();
+ MOI != MOE; ++MOI) {
+ const MachineOperand& MO = *MOI;
+
+ if (MO.isRegMask()) {
+ hasRegMaskOp = true;
+ continue;
+ }
+
+ if (!MO.isReg() || MO.getReg() == 0)
+ continue;
+
+ unsigned Reg = MO.getReg();
+
+ // TODO: Currently we're skipping uses that are reserved or have no
+ // interval, but we're not updating their kills. This should be
+ // fixed.
+ if (!LIS.hasInterval(Reg) ||
+ (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg)))
+ continue;
+
+ LiveInterval* LI = &LIS.getInterval(Reg);
+
+ if (MO.readsReg()) {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx);
+ if (LR != 0)
+ Entering.insert(std::make_pair(LI, LR));
+ }
+ if (MO.isDef()) {
+ if (MO.isEarlyClobber()) {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot(true));
+ assert(LR != 0 && "No EC range?");
+ if (LR->end > OldIdx.getDeadSlot())
+ Exiting.insert(std::make_pair(LI, LR));
+ else
+ Internal.insert(std::make_pair(LI, LR));
+ } else if (MO.isDead()) {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot());
+ assert(LR != 0 && "No dead-def range?");
+ Internal.insert(std::make_pair(LI, LR));
+ } else {
+ LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getDeadSlot());
+ assert(LR && LR->end > OldIdx.getDeadSlot() &&
+ "Non-dead-def should have live range exiting.");
+ Exiting.insert(std::make_pair(LI, LR));
+ }
+ }
+ }
+ }
+
+ void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) {
+ MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx);
+ if (!OldKillMI->killsRegister(reg))
+ return; // Bail out if we don't have kill flags on the old register.
+ MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx);
+ 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);
+ }
+
+ void updateRegMaskSlots(SlotIndex OldIdx) {
+ SmallVectorImpl<SlotIndex>::iterator RI =
+ std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
+ OldIdx);
+ assert(*RI == OldIdx && "No RegMask at OldIdx.");
+ *RI = NewIdx;
+ assert(*prior(RI) < *RI && *RI < *next(RI) &&
+ "RegSlots out of order. Did you move one call across another?");
+ }
+
+ // Return the last use of reg between NewIdx and OldIdx.
+ SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {
+ SlotIndex LastUse = NewIdx;
+ for (MachineRegisterInfo::use_nodbg_iterator
+ UI = MRI.use_nodbg_begin(Reg),
+ UE = MRI.use_nodbg_end();
+ UI != UE; ++UI) {
+ const MachineInstr* MI = &*UI;
+ SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
+ if (InstSlot > LastUse && InstSlot < OldIdx)
+ LastUse = InstSlot;
+ }
+ return LastUse;
+ }
+
+ void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ bool LiveThrough = LR->end > OldIdx.getRegSlot();
+ if (LiveThrough)
+ return;
+ SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
+ if (LastUse != NewIdx)
+ moveKillFlags(LI->reg, NewIdx, LastUse);
+ LR->end = LastUse.getRegSlot(LR->end.isEarlyClobber());
+ }
+
+ void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ bool LiveThrough = LR->end > OldIdx.getRegSlot();
+ if (LiveThrough) {
+ MachineBasicBlock* MBB = LIS.getInstructionFromIndex(NewIdx)->getParent();
+ bool LiveOut = LR->end >= LIS.getSlotIndexes()->getMBBEndIdx(MBB);
+ if (!LiveOut) {
+ moveKillFlags(LI->reg, LR->end, NewIdx);
+ LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
+ }
+ } else {
+ // Not live through. Easy - just update the range endpoint.
+ LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
+ }
+ }
+
+ void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) {
+ bool GoingUp = NewIdx < OldIdx;
+
+ if (GoingUp) {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringUpFrom(OldIdx, *EI);
+ } else {
+ for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
+ EI != EE; ++EI)
+ moveEnteringDownFrom(OldIdx, *EI);
+ }
+ }
+
+ void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveInterval* LI = P.first;
+ LiveRange* LR = P.second;
+ assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+ LR->end <= OldIdx.getDeadSlot() &&
+ "Range should be internal to OldIdx.");
+ LiveRange Tmp(*LR);
+ Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+ Tmp.valno->def = Tmp.start;
+ Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot();
+ LI->removeRange(*LR);
+ LI->addRange(Tmp);
+ }
+
+ void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) {
+ for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
+ II != IE; ++II)
+ moveInternalFrom(OldIdx, *II);
+ }
+
+ void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) {
+ LiveRange* LR = P.second;
+ assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
+ "Range should start in OldIdx.");
+ assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx.");
+ SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber());
+ LR->start = NewStart;
+ LR->valno->def = NewStart;
+ }
+
+ void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) {
+ for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
+ EI != EE; ++EI)
+ moveExitingFrom(OldIdx, *EI);
+ }
+
+};
+
+void LiveIntervals::handleMove(MachineInstr* MI) {
+ SlotIndex OldIndex = indexes_->getInstructionIndex(MI);
+ indexes_->removeMachineInstrFromMaps(MI);
+ SlotIndex NewIndex = MI->isInsideBundle() ?
+ indexes_->getInstructionIndex(MI->getBundleStart()) :
+ indexes_->insertMachineInstrInMaps(MI);
+ assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
+ OldIndex < getMBBEndIdx(MI->getParent()) &&
+ "Cannot handle moves across basic block boundaries.");
+ assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
+
+ HMEditor HME(*this, *mri_, *tri_, NewIndex);
+ HME.moveAllOperandsFrom(MI, OldIndex);
+}
projects / oota-llvm.git / blobdiff