CbC/CbC_llvm: lib/CodeGen/LiveIntervalAnalysis.cpp comparison

comparison lib/CodeGen/LiveIntervalAnalysis.cpp @ 95:afa8332a0e37 LLVM3.8

LLVM 3.8

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Tue, 13 Oct 2015 17:48:58 +0900
parents	60c9769439b8
children	7d135dc70f03

comparison

equal deleted inserted replaced

-:f3e34b893a5f
+:afa8332a0e37
 #include "llvm/IR/Value.h"
 #include "llvm/Support/BlockFrequency.h"
 #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"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <algorithm>
 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)
 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
 "Live Interval Analysis", false, false)
 "Use segment set for the computation of the live ranges of physregs."));
 }
 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
 AU.setPreservesCFG();
-AU.addRequired<AliasAnalysis>();
+AU.addRequired<AAResultsWrapperPass>();
-AU.addPreserved<AliasAnalysis>();
+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.
 AU.addRequired<LiveVariables>();
 AU.addPreserved<LiveVariables>();
 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 MF = &fn;
 MRI = &MF->getRegInfo();
 TRI = MF->getSubtarget().getRegisterInfo();
 TII = MF->getSubtarget().getInstrInfo();
-AA = &getAnalysis<AliasAnalysis>();
+AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 Indexes = &getAnalysis<SlotIndexes>();
 DomTree = &getAnalysis<MachineDominatorTree>();
 if (EnableSubRegLiveness && MF->getSubtarget().enableSubRegLiveness())
 MRI->enableSubRegLiveness(true);
 /// computeVirtRegInterval - Compute the live interval of a virtual register,
 /// based on defs and uses.
 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);
+LRCalc->calculate(LI, ShouldTrackSubRegLiveness);
-computeDeadValues(LI, nullptr);
+bool SeparatedComponents = computeDeadValues(LI, nullptr);
+if (SeparatedComponents) {
+assert(ShouldTrackSubRegLiveness
+&& "Separated components should only occur for unused subreg defs");
+SmallVector<LiveInterval*, 8> SplitLIs;
+splitSeparateComponents(LI, SplitLIs);
+}
 }
 void LiveIntervals::computeVirtRegs() {
 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 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;
+MachineBasicBlock *MBB = &*MBBI;
 std::pair<unsigned, unsigned> &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) {
+for (const MachineOperand &MO : MI->operands()) {
-if (!MO->isRegMask())
+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;
 }
 }
 SmallVector<unsigned, 8> NewRanges;
 // 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(),
+for (const auto &LI : MBB->liveins()) {
-LIE = MBB->livein_end(); LII != LIE; ++LII) {
+for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
-for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
 unsigned Unit = *Units;
 LiveRange *LR = RegUnitRanges[Unit];
 if (!LR) {
 // Use segment set to speed-up initial computation of the live range.
 LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
 WorkList.push_back(std::make_pair(Stop, VNI));
 }
 }
 }
-/// 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');
 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
 && "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;
 // Visit all instructions reading li->reg.
 return CanSeparate;
 }
 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
 SmallVectorImpl<MachineInstr*> *dead) {
-bool PHIRemoved = false;
+bool MayHaveSplitComponents = false;
 for (auto VNI : LI.valnos) {
 if (VNI->isUnused())
 continue;
 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()) {
+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->addRegisterDefReadUndef(LI.reg);
+MI->addRegisterDefReadUndef(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 " << Def << " may separate interval\n");
-PHIRemoved = true;
+MayHaveSplitComponents = true;
 } else {
 // This is a dead def. Make sure the instruction knows.
 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: " << Def << '\t' << *MI);
 dead->push_back(MI);
 }
 }
 }
-return PHIRemoved;
+return MayHaveSplitComponents;
 }
 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg)
 {
 DEBUG(dbgs() << "Shrink: " << SR << '\n');
 if (UseMI->isDebugValue())
 continue;
 // Maybe the operand is for a subregister we don't care about.
 unsigned SubReg = MO.getSubReg();
 if (SubReg != 0) {
-unsigned SubRegMask = TRI->getSubRegIndexLaneMask(SubReg);
+LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
-if ((SubRegMask & SR.LaneMask) == 0)
+if ((LaneMask & SR.LaneMask) == 0)
 continue;
 }
 // We only need to visit each instruction once.
 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
 if (Idx == LastIdx)
 if (RURange.empty())
 continue;
 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
 }
-if (MRI->tracksSubRegLiveness()) {
+if (MRI->subRegLivenessEnabled()) {
 SRs.clear();
 for (const LiveInterval::SubRange &SR : LI.subranges()) {
 SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
 }
 }
 continue;
 // I is overlapping RI.
 goto CancelKill;
 }
-if (MRI->tracksSubRegLiveness()) {
+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 %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;
+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;
 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());
+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());
 /// Update all live ranges touched by MI, assuming a move from OldIdx to
 /// NewIdx.
 void updateAllRanges(MachineInstr *MI) {
 DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
 bool hasRegMask = false;
-for (MIOperands MO(MI); MO.isValid(); ++MO) {
+for (MachineOperand &MO : MI->operands()) {
-if (MO->isRegMask())
+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())
+if (MO.isUse())
-MO->setIsKill(false);
+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);
+LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);
 for (LiveInterval::SubRange &S : LI.subranges()) {
 if ((S.LaneMask & LaneMask) == 0)
 continue;
 updateRange(S, Reg, S.LaneMask);
 }
 }
 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({
 dbgs() << "     ";
 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 dbgs() << PrintReg(Reg);
 if (LaneMask != 0)
-dbgs() << format(" L%04X", LaneMask);
+dbgs() << " L" << PrintLaneMask(LaneMask);
 } else {
 dbgs() << PrintRegUnit(Reg, &TRI);
 }
 dbgs() << ":\t" << LR << '\n';
 });
 ///
 /// 5. Value killed at OldIdx:
 ///    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();
 // Is LR even live at OldIdx?
 if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
 "Cannot move regmask instruction below another call");
 }
 // 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;
 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
 unsigned SubReg = MO.getSubReg();
 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)
 lastUseIdx = LII->end;
 else
 const MachineOperand &MO = *OI;
 if (!MO.isReg() || MO.getReg() != Reg)
 continue;
 unsigned SubReg = MO.getSubReg();
-unsigned Mask = TRI->getSubRegIndexLaneMask(SubReg);
+LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
 if ((Mask & LaneMask) == 0)
 continue;
 if (MO.isDef()) {
 if (!isStartValid) {
 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
 S.removeValNo(SVNI);
 }
 LI.removeEmptySubRanges();
 }
+void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
+SmallVectorImpl<LiveInterval*> &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);
+}

Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/LiveIntervalAnalysis.cpp @ 95:afa8332a0e37 LLVM3.8