char &llvm::LiveIntervalsID = LiveIntervals::ID;
INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
"Live Interval Analysis", false, false)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveVariables)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
"enable-subreg-liveness", cl::Hidden, cl::init(true),
cl::desc("Enable subregister liveness tracking."));
+namespace llvm {
+cl::opt<bool> UseSegmentSetForPhysRegs(
+ "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
+ cl::desc(
+ "Use segment set for the computation of the live ranges of physregs."));
+}
+
void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
- AU.addRequired<AliasAnalysis>();
- AU.addPreserved<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
+ AU.addPreserved<AAResultsWrapperPass>();
// LiveVariables isn't really required by this analysis, it is only required
// here to make sure it is live during TwoAddressInstructionPass and
// PHIElimination. This is temporary.
MRI = &MF->getRegInfo();
TRI = MF->getSubtarget().getRegisterInfo();
TII = MF->getSubtarget().getInstrInfo();
- AA = &getAnalysis<AliasAnalysis>();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Indexes = &getAnalysis<SlotIndexes>();
DomTree = &getAnalysis<MachineDominatorTree>();
assert(LRCalc && "LRCalc not initialized.");
assert(LI.empty() && "Should only compute empty intervals.");
LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
- LRCalc->calculate(LI);
+ LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
computeDeadValues(LI, nullptr);
}
RMB.first = RegMaskSlots.size();
for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
MI != ME; ++MI)
- for (MIOperands MO(MI); MO.isValid(); ++MO) {
- if (!MO->isRegMask())
+ for (const MachineOperand &MO : MI->operands()) {
+ if (!MO.isRegMask())
continue;
RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
- RegMaskBits.push_back(MO->getRegMask());
+ RegMaskBits.push_back(MO.getRegMask());
}
// Compute the number of register mask instructions in this block.
RMB.second = RegMaskSlots.size() - RMB.first;
LRCalc->extendToUses(LR, Reg);
}
}
+
+ // Flush the segment set to the segment vector.
+ if (UseSegmentSetForPhysRegs)
+ LR.flushSegmentSet();
}
const MachineBasicBlock *MBB = MFI;
// We only care about ABI blocks: Entry + landing pads.
- if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
+ if ((MFI != MF->begin() && !MBB->isEHPad()) || MBB->livein_empty())
continue;
// Create phi-defs at Begin for all live-in registers.
SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
- for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
- LIE = MBB->livein_end(); LII != LIE; ++LII) {
- for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
+ for (const auto &LI : MBB->liveins()) {
+ for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
unsigned Unit = *Units;
LiveRange *LR = RegUnitRanges[Unit];
if (!LR) {
- LR = RegUnitRanges[Unit] = new LiveRange();
+ // Use segment set to speed-up initial computation of the live range.
+ LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
NewRanges.push_back(Unit);
}
VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
}
}
-/// shrinkToUses - After removing some uses of a register, shrink its live
-/// range to just the remaining uses. This method does not compute reaching
-/// defs for new uses, and it doesn't remove dead defs.
bool LiveIntervals::shrinkToUses(LiveInterval *li,
SmallVectorImpl<MachineInstr*> *dead) {
DEBUG(dbgs() << "Shrink: " << *li << '\n');
&& "Can only shrink virtual registers");
// Shrink subregister live ranges.
+ bool NeedsCleanup = false;
for (LiveInterval::SubRange &S : li->subranges()) {
shrinkToUses(S, li->reg);
+ if (S.empty())
+ NeedsCleanup = true;
}
+ if (NeedsCleanup)
+ li->removeEmptySubRanges();
// Find all the values used, including PHI kills.
ShrinkToUsesWorkList WorkList;
for (auto VNI : LI.valnos) {
if (VNI->isUnused())
continue;
- LiveRange::iterator I = LI.FindSegmentContaining(VNI->def);
+ SlotIndex Def = VNI->def;
+ LiveRange::iterator I = LI.FindSegmentContaining(Def);
assert(I != LI.end() && "Missing segment for VNI");
- if (I->end != VNI->def.getDeadSlot())
+
+ // Is the register live before? Otherwise we may have to add a read-undef
+ // flag for subregister defs.
+ if (MRI->shouldTrackSubRegLiveness(LI.reg)) {
+ if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
+ MachineInstr *MI = getInstructionFromIndex(Def);
+ MI->addRegisterDefReadUndef(LI.reg);
+ }
+ }
+
+ if (I->end != Def.getDeadSlot())
continue;
if (VNI->isPHIDef()) {
// This is a dead PHI. Remove it.
VNI->markUnused();
LI.removeSegment(I);
- DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
+ DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
PHIRemoved = true;
} else {
// This is a dead def. Make sure the instruction knows.
- MachineInstr *MI = getInstructionFromIndex(VNI->def);
+ MachineInstr *MI = getInstructionFromIndex(Def);
assert(MI && "No instruction defining live value");
MI->addRegisterDead(LI.reg, TRI);
if (dead && MI->allDefsAreDead()) {
- DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
+ DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
dead->push_back(MI);
}
}
}
}
-void LiveIntervals::pruneValue(LiveInterval &LI, SlotIndex Kill,
- SmallVectorImpl<SlotIndex> *EndPoints) {
- pruneValue((LiveRange&)LI, Kill, EndPoints);
-
- for (LiveInterval::SubRange &SR : LI.subranges()) {
- pruneValue(SR, Kill, nullptr);
- }
-}
-
//===----------------------------------------------------------------------===//
// Register allocator hooks.
//
void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
// Keep track of regunit ranges.
- SmallVector<std::pair<LiveRange*, LiveRange::iterator>, 8> RU;
+ SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
+ // Keep track of subregister ranges.
+ SmallVector<std::pair<const LiveInterval::SubRange*,
+ LiveRange::const_iterator>, 4> SRs;
for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
if (MRI->reg_nodbg_empty(Reg))
continue;
- LiveInterval *LI = &getInterval(Reg);
- if (LI->empty())
+ const LiveInterval &LI = getInterval(Reg);
+ if (LI.empty())
continue;
// Find the regunit intervals for the assigned register. They may overlap
RU.clear();
for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
++Units) {
- LiveRange &RURanges = getRegUnit(*Units);
- if (RURanges.empty())
+ const LiveRange &RURange = getRegUnit(*Units);
+ if (RURange.empty())
continue;
- RU.push_back(std::make_pair(&RURanges, RURanges.find(LI->begin()->end)));
+ RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
+ }
+
+ if (MRI->subRegLivenessEnabled()) {
+ SRs.clear();
+ for (const LiveInterval::SubRange &SR : LI.subranges()) {
+ SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
+ }
}
// Every instruction that kills Reg corresponds to a segment range end
// point.
- for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
+ for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
++RI) {
// A block index indicates an MBB edge.
if (RI->end.isBlock())
// BAR %EAX<kill>
//
// There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
- bool CancelKill = false;
- for (unsigned u = 0, e = RU.size(); u != e; ++u) {
- LiveRange &RRanges = *RU[u].first;
- LiveRange::iterator &I = RU[u].second;
- if (I == RRanges.end())
+ for (auto &RUP : RU) {
+ const LiveRange &RURange = *RUP.first;
+ LiveRange::const_iterator &I = RUP.second;
+ if (I == RURange.end())
continue;
- I = RRanges.advanceTo(I, RI->end);
- if (I == RRanges.end() || I->start >= RI->end)
+ I = RURange.advanceTo(I, RI->end);
+ if (I == RURange.end() || I->start >= RI->end)
continue;
// I is overlapping RI.
- CancelKill = true;
- break;
+ goto CancelKill;
}
- // If an instruction writes to a subregister, a new segment starts in the
- // LiveInterval. In this case adding Kill-Flags is incorrect if no
- // super registers defs/uses are appended to the instruction which is
- // what we do when subregister liveness tracking is enabled.
- if (MRI->tracksSubRegLiveness()) {
- // Next segment has to be adjacent in the subregister write case.
- LiveRange::iterator N = std::next(RI);
- if (N != LI->end() && N->start == RI->end) {
- // See if we have a partial write operand
- bool IsFullWrite = false;
- for (MachineInstr::const_mop_iterator MOp = MI->operands_begin(),
- MOpE = MI->operands_end(); MOp != MOpE; ++MOp) {
- if (MOp->isReg() && !MOp->isDef() && MOp->getReg() == Reg
- && MOp->getSubReg() == 0) {
- IsFullWrite = true;
- break;
- }
+ if (MRI->subRegLivenessEnabled()) {
+ // When reading a partial undefined value we must not add a kill flag.
+ // The regalloc might have used the undef lane for something else.
+ // Example:
+ // %vreg1 = ... ; R32: %vreg1
+ // %vreg2:high16 = ... ; R64: %vreg2
+ // = read %vreg2<kill> ; R64: %vreg2
+ // = read %vreg1 ; R32: %vreg1
+ // The <kill> flag is correct for %vreg2, but the register allocator may
+ // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0
+ // are actually never written by %vreg2. After assignment the <kill>
+ // flag at the read instruction is invalid.
+ unsigned DefinedLanesMask;
+ if (!SRs.empty()) {
+ // Compute a mask of lanes that are defined.
+ DefinedLanesMask = 0;
+ for (auto &SRP : SRs) {
+ const LiveInterval::SubRange &SR = *SRP.first;
+ LiveRange::const_iterator &I = SRP.second;
+ if (I == SR.end())
+ continue;
+ I = SR.advanceTo(I, RI->end);
+ if (I == SR.end() || I->start >= RI->end)
+ continue;
+ // I is overlapping RI
+ DefinedLanesMask |= SR.LaneMask;
+ }
+ } else
+ DefinedLanesMask = ~0u;
+
+ bool IsFullWrite = false;
+ for (const MachineOperand &MO : MI->operands()) {
+ if (!MO.isReg() || MO.getReg() != Reg)
+ continue;
+ if (MO.isUse()) {
+ // Reading any undefined lanes?
+ unsigned UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
+ if ((UseMask & ~DefinedLanesMask) != 0)
+ goto CancelKill;
+ } else if (MO.getSubReg() == 0) {
+ // Writing to the full register?
+ assert(MO.isDef());
+ IsFullWrite = true;
}
- if (!IsFullWrite)
- CancelKill = true;
+ }
+
+ // If an instruction writes to a subregister, a new segment starts in
+ // the LiveInterval. But as this is only overriding part of the register
+ // adding kill-flags is not correct here after registers have been
+ // assigned.
+ if (!IsFullWrite) {
+ // Next segment has to be adjacent in the subregister write case.
+ LiveRange::const_iterator N = std::next(RI);
+ if (N != LI.end() && N->start == RI->end)
+ goto CancelKill;
}
}
- if (CancelKill)
- MI->clearRegisterKills(Reg, nullptr);
- else
- MI->addRegisterKilled(Reg, nullptr);
+ MI->addRegisterKilled(Reg, nullptr);
+ continue;
+CancelKill:
+ MI->clearRegisterKills(Reg, nullptr);
}
}
}
void updateAllRanges(MachineInstr *MI) {
DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
bool hasRegMask = false;
- for (MIOperands MO(MI); MO.isValid(); ++MO) {
- if (MO->isRegMask())
+ for (MachineOperand &MO : MI->operands()) {
+ if (MO.isRegMask())
hasRegMask = true;
- if (!MO->isReg())
+ if (!MO.isReg())
continue;
// Aggressively clear all kill flags.
// They are reinserted by VirtRegRewriter.
- if (MO->isUse())
- MO->setIsKill(false);
+ if (MO.isUse())
+ MO.setIsKill(false);
- unsigned Reg = MO->getReg();
+ unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
LiveInterval &LI = LIS.getInterval(Reg);
if (LI.hasSubRanges()) {
- unsigned SubReg = MO->getSubReg();
+ unsigned SubReg = MO.getSubReg();
unsigned LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
for (LiveInterval::SubRange &S : LI.subranges()) {
if ((S.LaneMask & LaneMask) == 0)
repairOldRegInRange(Begin, End, endIdx, LI, Reg);
}
}
+
+void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
+ for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
+ if (LiveRange *LR = getCachedRegUnit(*Units))
+ if (VNInfo *VNI = LR->getVNInfoAt(Pos))
+ LR->removeValNo(VNI);
+ }
+}
+
+void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
+ VNInfo *VNI = LI.getVNInfoAt(Pos);
+ if (VNI == nullptr)
+ return;
+ LI.removeValNo(VNI);
+
+ // Also remove the value in subranges.
+ for (LiveInterval::SubRange &S : LI.subranges()) {
+ if (VNInfo *SVNI = S.getVNInfoAt(Pos))
+ S.removeValNo(SVNI);
+ }
+ LI.removeEmptySubRanges();
+}
projects / oota-llvm.git / blobdiff