X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=a506e0571c09242c6e8d8969f921e26d558604a4;hb=HEAD;hp=0d24075f0263c816db558bb961d61ea129ad0b1e;hpb=1f6bcf1b85a41e582005de91568e4f1abb7f7e98;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 0d24075f026..a506e0571c0 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -32,7 +32,6 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/Format.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -48,7 +47,7 @@ char LiveIntervals::ID = 0; 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) @@ -67,10 +66,17 @@ 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(); - AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); // 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. @@ -117,7 +123,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { MRI = &MF->getRegInfo(); TRI = MF->getSubtarget().getRegisterInfo(); TII = MF->getSubtarget().getInstrInfo(); - AA = &getAnalysis(); + AA = &getAnalysis().getAAResults(); Indexes = &getAnalysis(); DomTree = &getAnalysis(); @@ -191,9 +197,16 @@ LiveInterval* LiveIntervals::createInterval(unsigned reg) { void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); assert(LI.empty() && "Should only compute empty intervals."); + bool ShouldTrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(LI.reg); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); - LRCalc->calculate(LI); - computeDeadValues(LI, nullptr); + LRCalc->calculate(LI, ShouldTrackSubRegLiveness); + bool SeparatedComponents = computeDeadValues(LI, nullptr); + if (SeparatedComponents) { + assert(ShouldTrackSubRegLiveness + && "Separated components should only occur for unused subreg defs"); + SmallVector SplitLIs; + splitSeparateComponents(LI, SplitLIs); + } } void LiveIntervals::computeVirtRegs() { @@ -209,19 +222,31 @@ void LiveIntervals::computeRegMasks() { RegMaskBlocks.resize(MF->getNumBlockIDs()); // Find all instructions with regmask operands. - for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end(); - MBBI != E; ++MBBI) { - MachineBasicBlock *MBB = MBBI; - std::pair &RMB = RegMaskBlocks[MBB->getNumber()]; + for (MachineBasicBlock &MBB : *MF) { + std::pair &RMB = RegMaskBlocks[MBB.getNumber()]; 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()) + + // Some block starts, such as EH funclets, create masks. + if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) { + RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB)); + RegMaskBits.push_back(Mask); + } + + for (MachineInstr &MI : MBB) { + for (const MachineOperand &MO : MI.operands()) { + if (!MO.isRegMask()) continue; - RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot()); - RegMaskBits.push_back(MO->getRegMask()); + RegMaskSlots.push_back(Indexes->getInstructionIndex(&MI).getRegSlot()); + RegMaskBits.push_back(MO.getRegMask()); } + } + + // Some block ends, such as funclet returns, create masks. + if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) { + RegMaskSlots.push_back(Indexes->getMBBEndIdx(&MBB)); + RegMaskBits.push_back(Mask); + } + // Compute the number of register mask instructions in this block. RMB.second = RegMaskSlots.size() - RMB.first; } @@ -268,6 +293,10 @@ void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) { LRCalc->extendToUses(LR, Reg); } } + + // Flush the segment set to the segment vector. + if (UseSegmentSetForPhysRegs) + LR.flushSegmentSet(); } @@ -285,22 +314,22 @@ void LiveIntervals::computeLiveInRegUnits() { // Check all basic blocks for live-ins. for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end(); MFI != MFE; ++MFI) { - const MachineBasicBlock *MBB = MFI; + 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()); @@ -384,9 +413,6 @@ static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes, } } -/// 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 *dead) { DEBUG(dbgs() << "Shrink: " << *li << '\n'); @@ -394,9 +420,14 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, && "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; @@ -444,32 +475,54 @@ bool LiveIntervals::shrinkToUses(LiveInterval *li, bool LiveIntervals::computeDeadValues(LiveInterval &LI, SmallVectorImpl *dead) { - bool PHIRemoved = false; + bool MayHaveSplitComponents = false; 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. + bool DeadBeforeDef = false; + unsigned VReg = LI.reg; + if (MRI->shouldTrackSubRegLiveness(VReg)) { + if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) { + MachineInstr *MI = getInstructionFromIndex(Def); + MI->setRegisterDefReadUndef(VReg); + DeadBeforeDef = true; + } + } + + 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"); - PHIRemoved = true; + DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n"); + MayHaveSplitComponents = 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); + MI->addRegisterDead(VReg, TRI); + + // If we have a dead def that is completely separate from the rest of + // the liverange then we rewrite it to use a different VReg to not violate + // the rule that the liveness of a virtual register forms a connected + // component. This should only happen if subregister liveness is tracked. + if (DeadBeforeDef) + MayHaveSplitComponents = true; + 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); } } } - return PHIRemoved; + return MayHaveSplitComponents; } void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) @@ -489,8 +542,8 @@ void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) // Maybe the operand is for a subregister we don't care about. unsigned SubReg = MO.getSubReg(); if (SubReg != 0) { - unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg); - if ((SubRegMask & SR.LaneMask) == 0) + LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); + if ((LaneMask & SR.LaneMask) == 0) continue; } // We only need to visit each instruction once. @@ -609,15 +662,6 @@ void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill, } } -void LiveIntervals::pruneValue(LiveInterval &LI, SlotIndex Kill, - SmallVectorImpl *EndPoints) { - pruneValue((LiveRange&)LI, Kill, EndPoints); - - for (LiveInterval::SubRange &SR : LI.subranges()) { - pruneValue(SR, Kill, nullptr); - } -} - //===----------------------------------------------------------------------===// // Register allocator hooks. // @@ -625,6 +669,9 @@ void LiveIntervals::pruneValue(LiveInterval &LI, SlotIndex Kill, void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { // Keep track of regunit ranges. 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); @@ -645,6 +692,13 @@ void LiveIntervals::addKillFlags(const VirtRegMap *VRM) { 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::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE; @@ -664,46 +718,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 (auto &RUP : RU) { const LiveRange &RURange = *RUP.first; - LiveRange::const_iterator I = RUP.second; + LiveRange::const_iterator &I = RUP.second; if (I == RURange.end()) continue; 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::const_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 (const MachineOperand &MO : MI->operands()) { - if (MO.isReg() && MO.isUse() && MO.getReg() == Reg - && MO.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 ; 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. + LaneBitmask 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? + LaneBitmask 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); } } } @@ -869,24 +957,24 @@ public: 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 LaneMask = TRI.getSubRegIndexLaneMask(SubReg); + unsigned SubReg = MO.getSubReg(); + LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg); for (LiveInterval::SubRange &S : LI.subranges()) { if ((S.LaneMask & LaneMask) == 0) continue; @@ -910,7 +998,7 @@ public: private: /// Update a single live range, assuming an instruction has been moved from /// OldIdx to NewIdx. - void updateRange(LiveRange &LR, unsigned Reg, unsigned LaneMask) { + void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { if (!Updated.insert(&LR).second) return; DEBUG({ @@ -918,7 +1006,7 @@ private: if (TargetRegisterInfo::isVirtualRegister(Reg)) { dbgs() << PrintReg(Reg); if (LaneMask != 0) - dbgs() << format(" L%04X", LaneMask); + dbgs() << " L" << PrintLaneMask(LaneMask); } else { dbgs() << PrintRegUnit(Reg, &TRI); } @@ -1040,7 +1128,7 @@ private: /// Hoist kill to NewIdx, then scan for last kill between NewIdx and /// OldIdx. /// - void handleMoveUp(LiveRange &LR, unsigned Reg, unsigned LaneMask) { + void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) { // First look for a kill at OldIdx. LiveRange::iterator I = LR.find(OldIdx.getBaseIndex()); LiveRange::iterator E = LR.end(); @@ -1117,7 +1205,7 @@ private: } // Return the last use of reg between NewIdx and OldIdx. - SlotIndex findLastUseBefore(unsigned Reg, unsigned LaneMask) { + SlotIndex findLastUseBefore(unsigned Reg, LaneBitmask LaneMask) { if (TargetRegisterInfo::isVirtualRegister(Reg)) { SlotIndex LastUse = NewIdx; @@ -1197,7 +1285,7 @@ void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, const MachineBasicBlock::iterator End, const SlotIndex endIdx, LiveRange &LR, const unsigned Reg, - const unsigned LaneMask) { + LaneBitmask LaneMask) { LiveInterval::iterator LII = LR.find(endIdx); SlotIndex lastUseIdx; if (LII != LR.end() && LII->start < endIdx) @@ -1224,7 +1312,7 @@ void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin, continue; unsigned SubReg = MO.getSubReg(); - unsigned Mask = TRI->getSubRegIndexLaneMask(SubReg); + LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg); if ((Mask & LaneMask) == 0) continue; @@ -1332,3 +1420,42 @@ LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB, 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(); +} + +void LiveIntervals::splitSeparateComponents(LiveInterval &LI, + SmallVectorImpl &SplitLIs) { + ConnectedVNInfoEqClasses ConEQ(*this); + unsigned NumComp = ConEQ.Classify(LI); + if (NumComp <= 1) + return; + DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n'); + unsigned Reg = LI.reg; + const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); + for (unsigned I = 1; I < NumComp; ++I) { + unsigned NewVReg = MRI->createVirtualRegister(RegClass); + LiveInterval &NewLI = createEmptyInterval(NewVReg); + SplitLIs.push_back(&NewLI); + } + ConEQ.Distribute(LI, SplitLIs.data(), *MRI); +}