X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=cc08045c7b898825b8d80aa1e2017f368b8129ed;hb=6de0a12927845ca49cd5cb1da9206fe503b565ec;hp=dde55f9dd48f66757a730b51f7328a37850307af;hpb=6e616d2e97209988a846f3448cb60173be1c7fa9;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index dde55f9dd48..cc08045c7b8 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -67,6 +67,13 @@ static cl::opt EnableSubRegLiveness( "enable-subreg-liveness", cl::Hidden, cl::init(true), cl::desc("Enable subregister liveness tracking.")); +namespace llvm { +cl::opt 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(); @@ -192,9 +199,8 @@ void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); assert(LI.empty() && "Should only compute empty intervals."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->createDeadDefs(LI); - LRCalc->extendToUses(LI); - computeDeadValues(LI, LI); + LRCalc->calculate(LI); + computeDeadValues(LI, nullptr); } void LiveIntervals::computeVirtRegs() { @@ -269,6 +275,10 @@ void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { LRCalc->extendToUses(LR, Reg); } } + + // Flush the segment set to the segment vector. + if (UseSegmentSetForPhysRegs) + LR.flushSegmentSet(); } @@ -301,7 +311,8 @@ void LiveIntervals::computeLiveInRegUnits() { 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()); @@ -395,9 +406,8 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, && "Can only shrink virtual registers"); // Shrink subregister live ranges. - for (LiveInterval::subrange_iterator I = li->subrange_begin(), - E = li->subrange_end(); I != E; ++I) { - shrinkToUses(*I, li->reg); + for (LiveInterval::SubRange &S : li->subranges()) { + shrinkToUses(S, li->reg); } // Find all the values used, including PHI kills. @@ -435,49 +445,57 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end())); extendSegmentsToUses(NewLR, *Indexes, WorkList, *li); - // Handle dead values. - bool CanSeparate; - computeDeadValues(NewLR, *li, &CanSeparate, li->reg, dead); - // Move the trimmed segments back. li->segments.swap(NewLR.segments); + + // Handle dead values. + bool CanSeparate = computeDeadValues(*li, dead); DEBUG(dbgs() << "Shrunk: " << *li << '\n'); return CanSeparate; } -void LiveIntervals::computeDeadValues(LiveRange &Segments, LiveRange &LR, - bool *CanSeparateRes, unsigned Reg, +bool LiveIntervals::computeDeadValues(LiveInterval &LI, SmallVectorImpl *dead) { - bool CanSeparate = false; - for (auto VNI : make_range(LR.vni_begin(), LR.vni_end())) { + bool PHIRemoved = false; + for (auto VNI : LI.valnos) { if (VNI->isUnused()) continue; - LiveRange::iterator LRI = Segments.FindSegmentContaining(VNI->def); - assert(LRI != Segments.end() && "Missing segment for PHI"); - if (LRI->end != VNI->def.getDeadSlot()) + SlotIndex Def = VNI->def; + LiveRange::iterator I = LI.FindSegmentContaining(Def); + assert(I != LI.end() && "Missing segment for VNI"); + + // Is the register live before? Otherwise we may have to add a read-undef + // flag for subregister defs. + if (MRI->tracksSubRegLiveness()) { + 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(); - Segments.removeSegment(LRI->start, LRI->end); - DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); - CanSeparate = true; - } else if (dead != nullptr) { + LI.removeSegment(I); + 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(Reg, TRI); + 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); } } } - if (CanSeparateRes != nullptr) - *CanSeparateRes = CanSeparate; + return PHIRemoved; } -bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) +void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) { DEBUG(dbgs() << "Shrink: " << SR << '\n'); assert(TargetRegisterInfo::isVirtualRegister(Reg) @@ -524,14 +542,26 @@ bool LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end())); extendSegmentsToUses(NewLR, *Indexes, WorkList, SR); - // Handle dead values. - bool CanSeparate; - computeDeadValues(NewLR, SR, &CanSeparate); - // Move the trimmed ranges back. SR.segments.swap(NewLR.segments); + + // Remove dead PHI value numbers + for (auto VNI : SR.valnos) { + if (VNI->isUnused()) + continue; + const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def); + assert(Segment != nullptr && "Missing segment for VNI"); + if (Segment->end != VNI->def.getDeadSlot()) + continue; + if (VNI->isPHIDef()) { + // This is a dead PHI. Remove it. + VNI->markUnused(); + SR.removeSegment(*Segment); + DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); + } + } + DEBUG(dbgs() << "Shrunk: " << SR << '\n'); - return CanSeparate; } void LiveIntervals::extendToIndices(LiveRange &LR, @@ -602,30 +632,23 @@ void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, } } -void LiveIntervals::pruneValue(LiveInterval &LI, SlotIndex Kill, - SmallVectorImpl *EndPoints) { - pruneValue((LiveRange&)LI, Kill, EndPoints); - - for (LiveInterval::subrange_iterator SR = LI.subrange_begin(), - SE = LI.subrange_end(); SR != SE; ++SR) { - pruneValue(*SR, Kill, nullptr); - } -} - //===----------------------------------------------------------------------===// // Register allocator hooks. // void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // Keep track of regunit ranges. - SmallVector, 8> RU; + SmallVector, 8> RU; + // Keep track of subregister ranges. + SmallVector, 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 @@ -633,15 +656,22 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 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->tracksSubRegLiveness()) { + 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()) @@ -658,23 +688,80 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // BAR %EAX // // 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 (CancelKill) - MI->clearRegisterKills(Reg, nullptr); - else - MI->addRegisterKilled(Reg, nullptr); + + if (MRI->tracksSubRegLiveness()) { + // 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 ; R64: %vreg2 + // = read %vreg1 ; R32: %vreg1 + // The 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 + // 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 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; + } + } + + MI->addRegisterKilled(Reg, nullptr); + continue; +CancelKill: + MI->clearRegisterKills(Reg, nullptr); } } } @@ -705,9 +792,7 @@ LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { bool LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const { - for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end(); - I != E; ++I) { - const VNInfo *PHI = *I; + for (const VNInfo *PHI : LI.valnos) { if (PHI->isUnused() || !PHI->isPHIDef()) continue; const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def); @@ -860,11 +945,10 @@ public: if (LI.hasSubRanges()) { unsigned SubReg = MO->getSubReg(); unsigned LaneMask = TRI.getSubRegIndexLaneMask(SubReg); - for (LiveInterval::subrange_iterator S = LI.subrange_begin(), - SE = LI.subrange_end(); S != SE; ++S) { - if ((S->LaneMask & LaneMask) == 0) + for (LiveInterval::SubRange &S : LI.subranges()) { + if ((S.LaneMask & LaneMask) == 0) continue; - updateRange(*S, Reg, S->LaneMask); + updateRange(S, Reg, S.LaneMask); } } updateRange(LI, Reg, 0); @@ -1300,10 +1384,31 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, if (!LI.hasAtLeastOneValue()) continue; - for (LiveInterval::subrange_iterator S = LI.subrange_begin(), - SE = LI.subrange_end(); S != SE; ++S) { - repairOldRegInRange(Begin, End, endIdx, *S, Reg, S->LaneMask); + for (LiveInterval::SubRange &S : LI.subranges()) { + repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask); } 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(); +}