X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=32c553ff12d0ff6bd3eb7d7e3a004ad487c69f25;hb=cb6404711b7fe6f583480adce8d7e9d5e4b99ae6;hp=854fb4d7f6d85f398ec1ea4dcb21adc031c800ed;hpb=3de23e6f6cf337451a0934159da494d645b93133;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 854fb4d7f6d..32c553ff12d 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -47,39 +47,41 @@ using namespace llvm; // Hidden options for help debugging. -static cl::opt DisableReMat("disable-rematerialization", +static cl::opt DisableReMat("disable-rematerialization", cl::init(false), cl::Hidden); -static cl::opt EnableFastSpilling("fast-spill", - cl::init(false), cl::Hidden); - -static cl::opt EarlyCoalescing("early-coalescing", cl::init(false)); - -static cl::opt CoalescingLimit("early-coalescing-limit", - cl::init(-1), cl::Hidden); - STATISTIC(numIntervals , "Number of original intervals"); STATISTIC(numFolds , "Number of loads/stores folded into instructions"); STATISTIC(numSplits , "Number of intervals split"); -STATISTIC(numCoalescing, "Number of early coalescing performed"); char LiveIntervals::ID = 0; -static RegisterPass X("liveintervals", "Live Interval Analysis"); +INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", + "Live Interval Analysis", false, false) +INITIALIZE_PASS_DEPENDENCY(LiveVariables) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(PHIElimination) +INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) +INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs) +INITIALIZE_PASS_DEPENDENCY(SlotIndexes) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(LiveIntervals, "liveintervals", + "Live Interval Analysis", false, false) void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); AU.addRequired(); - AU.addPreservedID(MachineLoopInfoID); + AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); AU.addPreservedID(MachineDominatorsID); - + if (!StrongPHIElim) { AU.addPreservedID(PHIEliminationID); AU.addRequiredID(PHIEliminationID); } - + AU.addRequiredID(TwoAddressInstructionPassID); AU.addPreserved(); AU.addRequired(); @@ -93,11 +95,10 @@ void LiveIntervals::releaseMemory() { for (DenseMap::iterator I = r2iMap_.begin(), E = r2iMap_.end(); I != E; ++I) delete I->second; - + r2iMap_.clear(); - phiJoinCopies.clear(); - // Release VNInfo memroy regions after all VNInfo objects are dtor'd. + // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. VNInfoAllocator.Reset(); while (!CloneMIs.empty()) { MachineInstr *MI = CloneMIs.back(); @@ -120,7 +121,6 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { allocatableRegs_ = tri_->getAllocatableSet(fn); computeIntervals(); - performEarlyCoalescing(); numIntervals += getNumIntervals(); @@ -141,66 +141,80 @@ void LiveIntervals::print(raw_ostream &OS, const Module* ) const { void LiveIntervals::printInstrs(raw_ostream &OS) const { OS << "********** MACHINEINSTRS **********\n"; - - for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); - mbbi != mbbe; ++mbbi) { - OS << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; - for (MachineBasicBlock::iterator mii = mbbi->begin(), - mie = mbbi->end(); mii != mie; ++mii) { - OS << getInstructionIndex(mii) << '\t' << *mii; - } - } + mf_->print(OS, indexes_); } void LiveIntervals::dumpInstrs() const { - printInstrs(errs()); + printInstrs(dbgs()); } -/// conflictsWithPhysRegDef - Returns true if the specified register -/// is defined during the duration of the specified interval. -bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, - VirtRegMap &vrm, unsigned reg) { - for (LiveInterval::Ranges::const_iterator - I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - for (SlotIndex index = I->start.getBaseIndex(), - end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); - index != end; - index = index.getNextIndex()) { - // skip deleted instructions - while (index != end && !getInstructionFromIndex(index)) - index = index.getNextIndex(); - if (index == end) break; +bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li, + VirtRegMap &vrm, unsigned reg) { + // We don't handle fancy stuff crossing basic block boundaries + if (li.ranges.size() != 1) + return true; + const LiveRange &range = li.ranges.front(); + SlotIndex idx = range.start.getBaseIndex(); + SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex(); + + // Skip deleted instructions + MachineInstr *firstMI = getInstructionFromIndex(idx); + while (!firstMI && idx != end) { + idx = idx.getNextIndex(); + firstMI = getInstructionFromIndex(idx); + } + if (!firstMI) + return false; - MachineInstr *MI = getInstructionFromIndex(index); - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) - if (SrcReg == li.reg || DstReg == li.reg) - continue; - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& mop = MI->getOperand(i); - if (!mop.isReg()) - continue; - unsigned PhysReg = mop.getReg(); - if (PhysReg == 0 || PhysReg == li.reg) + // Find last instruction in range + SlotIndex lastIdx = end.getPrevIndex(); + MachineInstr *lastMI = getInstructionFromIndex(lastIdx); + while (!lastMI && lastIdx != idx) { + lastIdx = lastIdx.getPrevIndex(); + lastMI = getInstructionFromIndex(lastIdx); + } + if (!lastMI) + return false; + + // Range cannot cross basic block boundaries or terminators + MachineBasicBlock *MBB = firstMI->getParent(); + if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator()) + return true; + + MachineBasicBlock::const_iterator E = lastMI; + ++E; + for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) { + const MachineInstr &MI = *I; + + // Allow copies to and from li.reg + if (MI.isCopy()) + if (MI.getOperand(0).getReg() == li.reg || + MI.getOperand(1).getReg() == li.reg) + continue; + + // Check for operands using reg + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + const MachineOperand& mop = MI.getOperand(i); + if (!mop.isReg()) + continue; + unsigned PhysReg = mop.getReg(); + if (PhysReg == 0 || PhysReg == li.reg) + continue; + if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { + if (!vrm.hasPhys(PhysReg)) continue; - if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { - if (!vrm.hasPhys(PhysReg)) - continue; - PhysReg = vrm.getPhys(PhysReg); - } - if (PhysReg && tri_->regsOverlap(PhysReg, reg)) - return true; + PhysReg = vrm.getPhys(PhysReg); } + if (PhysReg && tri_->regsOverlap(PhysReg, reg)) + return true; } } + // No conflicts found. return false; } -/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except -/// it can check use as well. -bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, - unsigned Reg, bool CheckUse, +bool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg, SmallPtrSet &JoinedCopies) { for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { @@ -208,15 +222,9 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, end = I->end.getPrevSlot().getBaseIndex().getNextIndex(); index != end; index = index.getNextIndex()) { - // Skip deleted instructions. - MachineInstr *MI = 0; - while (index != end) { - MI = getInstructionFromIndex(index); - if (MI) - break; - index = index.getNextIndex(); - } - if (index == end) break; + MachineInstr *MI = getInstructionFromIndex(index); + if (!MI) + continue; // skip deleted instructions if (JoinedCopies.count(MI)) continue; @@ -224,12 +232,11 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, MachineOperand& MO = MI->getOperand(i); if (!MO.isReg()) continue; - if (MO.isUse() && !CheckUse) - continue; unsigned PhysReg = MO.getReg(); - if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) + if (PhysReg == 0 || PhysReg == Reg || + TargetRegisterInfo::isVirtualRegister(PhysReg)) continue; - if (tri_->isSubRegister(Reg, PhysReg)) + if (tri_->regsOverlap(Reg, PhysReg)) return true; } } @@ -238,14 +245,40 @@ bool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, return false; } -#ifndef NDEBUG -static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) { - if (TargetRegisterInfo::isPhysicalRegister(reg)) - errs() << tri_->getName(reg); - else - errs() << "%reg" << reg; +static +bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { + unsigned Reg = MI.getOperand(MOIdx).getReg(); + for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { + const MachineOperand &MO = MI.getOperand(i); + if (!MO.isReg()) + continue; + if (MO.getReg() == Reg && MO.isDef()) { + assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && + MI.getOperand(MOIdx).getSubReg() && + (MO.getSubReg() || MO.isImplicit())); + return true; + } + } + return false; +} + +/// isPartialRedef - Return true if the specified def at the specific index is +/// partially re-defining the specified live interval. A common case of this is +/// a definition of the sub-register. +bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, + LiveInterval &interval) { + if (!MO.getSubReg() || MO.isEarlyClobber()) + return false; + + SlotIndex RedefIndex = MIIdx.getDefIndex(); + const LiveRange *OldLR = + interval.getLiveRangeContaining(RedefIndex.getUseIndex()); + MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); + if (DefMI != 0) { + return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; + } + return false; } -#endif void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineBasicBlock::iterator mi, @@ -253,10 +286,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, MachineOperand& MO, unsigned MOIdx, LiveInterval &interval) { - DEBUG({ - errs() << "\t\tregister: "; - printRegName(interval.reg, tri_); - }); + DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); // Virtual registers may be defined multiple times (due to phi // elimination and 2-addr elimination). Much of what we do only has to be @@ -270,17 +300,18 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // of inputs. if (MO.isEarlyClobber()) defIndex = MIIdx.getUseIndex(); - VNInfo *ValNo; + + // Make sure the first definition is not a partial redefinition. Add an + // of the full register. + if (MO.getSubReg()) + mi->addRegisterDefined(interval.reg); + MachineInstr *CopyMI = NULL; - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || - mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || - mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || - tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) + if (mi->isCopyLike()) { CopyMI = mi; - // Earlyclobbers move back one. - ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); + } + VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); assert(ValNo->id == 0 && "First value in interval is not 0?"); // Loop over all of the blocks that the vreg is defined in. There are @@ -302,8 +333,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, "Shouldn't be alive across any blocks!"); LiveRange LR(defIndex, killIdx, ValNo); interval.addRange(LR); - DEBUG(errs() << " +" << LR << "\n"); - ValNo->addKill(killIdx); + DEBUG(dbgs() << " +" << LR << "\n"); return; } } @@ -312,49 +342,74 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // of the defining block, potentially live across some blocks, then is // live into some number of blocks, but gets killed. Start by adding a // range that goes from this definition to the end of the defining block. - LiveRange NewLR(defIndex, getMBBEndIdx(mbb).getNextIndex().getLoadIndex(), - ValNo); - DEBUG(errs() << " +" << NewLR); + LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); + DEBUG(dbgs() << " +" << NewLR); interval.addRange(NewLR); - // Iterate over all of the blocks that the variable is completely - // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the - // live interval. - for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), - E = vi.AliveBlocks.end(); I != E; ++I) { - LiveRange LR( - getMBBStartIdx(mf_->getBlockNumbered(*I)), - getMBBEndIdx(mf_->getBlockNumbered(*I)).getNextIndex().getLoadIndex(), - ValNo); - interval.addRange(LR); - DEBUG(errs() << " +" << LR); + bool PHIJoin = lv_->isPHIJoin(interval.reg); + + if (PHIJoin) { + // A phi join register is killed at the end of the MBB and revived as a new + // valno in the killing blocks. + assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); + DEBUG(dbgs() << " phi-join"); + ValNo->setHasPHIKill(true); + } else { + // Iterate over all of the blocks that the variable is completely + // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the + // live interval. + for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), + E = vi.AliveBlocks.end(); I != E; ++I) { + MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); + LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); + interval.addRange(LR); + DEBUG(dbgs() << " +" << LR); + } } // Finally, this virtual register is live from the start of any killing // block to the 'use' slot of the killing instruction. for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { MachineInstr *Kill = vi.Kills[i]; - SlotIndex killIdx = - getInstructionIndex(Kill).getDefIndex(); - LiveRange LR(getMBBStartIdx(Kill->getParent()), killIdx, ValNo); + SlotIndex Start = getMBBStartIdx(Kill->getParent()); + SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex(); + + // Create interval with one of a NEW value number. Note that this value + // number isn't actually defined by an instruction, weird huh? :) + if (PHIJoin) { + assert(getInstructionFromIndex(Start) == 0 && + "PHI def index points at actual instruction."); + ValNo = interval.getNextValue(Start, 0, VNInfoAllocator); + ValNo->setIsPHIDef(true); + } + LiveRange LR(Start, killIdx, ValNo); interval.addRange(LR); - ValNo->addKill(killIdx); - DEBUG(errs() << " +" << LR); + DEBUG(dbgs() << " +" << LR); } } else { + if (MultipleDefsBySameMI(*mi, MOIdx)) + // Multiple defs of the same virtual register by the same instruction. + // e.g. %reg1031:5, %reg1031:6 = VLD1q16 %reg1024, ... + // This is likely due to elimination of REG_SEQUENCE instructions. Return + // here since there is nothing to do. + return; + // If this is the second time we see a virtual register definition, it // must be due to phi elimination or two addr elimination. If this is // the result of two address elimination, then the vreg is one of the // def-and-use register operand. - if (mi->isRegTiedToUseOperand(MOIdx)) { + + // It may also be partial redef like this: + // 80 %reg1041:6 = VSHRNv4i16 %reg1034, 12, pred:14, pred:%reg0 + // 120 %reg1041:5 = VSHRNv4i16 %reg1039, 12, pred:14, pred:%reg0 + bool PartReDef = isPartialRedef(MIIdx, MO, interval); + if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { // If this is a two-address definition, then we have already processed // the live range. The only problem is that we didn't realize there // are actually two values in the live interval. Because of this we // need to take the LiveRegion that defines this register and split it // into two values. - assert(interval.containsOneValue()); - SlotIndex DefIndex = interval.getValNumInfo(0)->def.getDefIndex(); SlotIndex RedefIndex = MIIdx.getDefIndex(); if (MO.isEarlyClobber()) RedefIndex = MIIdx.getUseIndex(); @@ -362,33 +417,28 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex.getUseIndex()); VNInfo *OldValNo = OldLR->valno; + SlotIndex DefIndex = OldValNo->def.getDefIndex(); - // Delete the initial value, which should be short and continuous, + // Delete the previous value, which should be short and continuous, // because the 2-addr copy must be in the same MBB as the redef. interval.removeRange(DefIndex, RedefIndex); - // Two-address vregs should always only be redefined once. This means - // that at this point, there should be exactly one value number in it. - assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); - // The new value number (#1) is defined by the instruction we claimed // defined value #0. - VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(), - false, // update at * - VNInfoAllocator); - ValNo->setFlags(OldValNo->getFlags()); // * <- updating here + VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); // Value#0 is now defined by the 2-addr instruction. OldValNo->def = RedefIndex; OldValNo->setCopy(0); - if (MO.isEarlyClobber()) - OldValNo->setHasRedefByEC(true); - + + // A re-def may be a copy. e.g. %reg1030:6 = VMOVD %reg1026, ... + if (PartReDef && mi->isCopyLike()) + OldValNo->setCopy(&*mi); + // Add the new live interval which replaces the range for the input copy. LiveRange LR(DefIndex, RedefIndex, ValNo); - DEBUG(errs() << " replace range with " << LR); + DEBUG(dbgs() << " replace range with " << LR); interval.addRange(LR); - ValNo->addKill(RedefIndex); // If this redefinition is dead, we need to add a dummy unit live // range covering the def slot. @@ -397,78 +447,35 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, OldValNo)); DEBUG({ - errs() << " RESULT: "; - interval.print(errs(), tri_); + dbgs() << " RESULT: "; + interval.print(dbgs(), tri_); }); - } else { - // Otherwise, this must be because of phi elimination. If this is the - // first redefinition of the vreg that we have seen, go back and change - // the live range in the PHI block to be a different value number. - if (interval.containsOneValue()) { - // Remove the old range that we now know has an incorrect number. - VNInfo *VNI = interval.getValNumInfo(0); - MachineInstr *Killer = vi.Kills[0]; - phiJoinCopies.push_back(Killer); - SlotIndex Start = getMBBStartIdx(Killer->getParent()); - SlotIndex End = getInstructionIndex(Killer).getDefIndex(); - DEBUG({ - errs() << " Removing [" << Start << "," << End << "] from: "; - interval.print(errs(), tri_); - errs() << "\n"; - }); - interval.removeRange(Start, End); - assert(interval.ranges.size() == 1 && - "Newly discovered PHI interval has >1 ranges."); - MachineBasicBlock *killMBB = getMBBFromIndex(interval.endIndex()); - VNI->addKill(indexes_->getTerminatorGap(killMBB)); - VNI->setHasPHIKill(true); - DEBUG({ - errs() << " RESULT: "; - interval.print(errs(), tri_); - }); - - // Replace the interval with one of a NEW value number. Note that this - // value number isn't actually defined by an instruction, weird huh? :) - LiveRange LR(Start, End, - interval.getNextValue(SlotIndex(getMBBStartIdx(mbb), true), - 0, false, VNInfoAllocator)); - LR.valno->setIsPHIDef(true); - DEBUG(errs() << " replace range with " << LR); - interval.addRange(LR); - LR.valno->addKill(End); - DEBUG({ - errs() << " RESULT: "; - interval.print(errs(), tri_); - }); - } - + } else if (lv_->isPHIJoin(interval.reg)) { // In the case of PHI elimination, each variable definition is only // live until the end of the block. We've already taken care of the // rest of the live range. + SlotIndex defIndex = MIIdx.getDefIndex(); if (MO.isEarlyClobber()) defIndex = MIIdx.getUseIndex(); VNInfo *ValNo; MachineInstr *CopyMI = NULL; - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || - mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || - mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || - tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) + if (mi->isCopyLike()) CopyMI = mi; - ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); - - SlotIndex killIndex = getMBBEndIdx(mbb).getNextIndex().getLoadIndex(); + ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); + + SlotIndex killIndex = getMBBEndIdx(mbb); LiveRange LR(defIndex, killIndex, ValNo); interval.addRange(LR); - ValNo->addKill(indexes_->getTerminatorGap(mbb)); ValNo->setHasPHIKill(true); - DEBUG(errs() << " +" << LR); + DEBUG(dbgs() << " phi-join +" << LR); + } else { + llvm_unreachable("Multiply defined register"); } } - DEBUG(errs() << '\n'); + DEBUG(dbgs() << '\n'); } void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, @@ -479,10 +486,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, MachineInstr *CopyMI) { // A physical register cannot be live across basic block, so its // lifetime must end somewhere in its defining basic block. - DEBUG({ - errs() << "\t\tregister: "; - printRegName(interval.reg, tri_); - }); + DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); SlotIndex baseIndex = MIIdx; SlotIndex start = baseIndex.getDefIndex(); @@ -497,7 +501,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // For earlyclobbers, the defSlot was pushed back one; the extra // advance below compensates. if (MO.isDead()) { - DEBUG(errs() << " dead"); + DEBUG(dbgs() << " dead"); end = start.getStoreIndex(); goto exit; } @@ -508,36 +512,36 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, baseIndex = baseIndex.getNextIndex(); while (++mi != MBB->end()) { + if (mi->isDebugValue()) + continue; if (getInstructionFromIndex(baseIndex) == 0) baseIndex = indexes_->getNextNonNullIndex(baseIndex); if (mi->killsRegister(interval.reg, tri_)) { - DEBUG(errs() << " killed"); + DEBUG(dbgs() << " killed"); end = baseIndex.getDefIndex(); goto exit; } else { - int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); + int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); if (DefIdx != -1) { if (mi->isRegTiedToUseOperand(DefIdx)) { // Two-address instruction. end = baseIndex.getDefIndex(); - assert(!mi->getOperand(DefIdx).isEarlyClobber() && - "Two address instruction is an early clobber?"); } else { // 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: + // Then the register is essentially dead at the instruction that + // defines it. Hence its interval is: // [defSlot(def), defSlot(def)+1) - DEBUG(errs() << " dead"); + DEBUG(dbgs() << " dead"); end = start.getStoreIndex(); } goto exit; } } - + 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 @@ -548,16 +552,15 @@ exit: assert(start < end && "did not find end of interval?"); // Already exists? Extend old live interval. - LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); - bool Extend = OldLR != interval.end(); - VNInfo *ValNo = Extend - ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); - if (MO.isEarlyClobber() && Extend) + VNInfo *ValNo = interval.getVNInfoAt(start); + bool Extend = ValNo != 0; + if (!Extend) + ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator); + if (Extend && MO.isEarlyClobber()) ValNo->setHasRedefByEC(true); LiveRange LR(start, end, ValNo); interval.addRange(LR); - LR.valno->addKill(end); - DEBUG(errs() << " +" << LR << '\n'); + DEBUG(dbgs() << " +" << LR << '\n'); } void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, @@ -570,11 +573,7 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, getOrCreateInterval(MO.getReg())); else if (allocatableRegs_[MO.getReg()]) { MachineInstr *CopyMI = NULL; - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || - MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || - MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || - tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) + if (MI->isCopyLike()) CopyMI = MI; handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, getOrCreateInterval(MO.getReg()), CopyMI); @@ -582,7 +581,7 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) // If MI also modifies the sub-register explicitly, avoid processing it // more than once. Do not pass in TRI here so it checks for exact match. - if (!MI->modifiesRegister(*AS)) + if (!MI->definesRegister(*AS)) handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, getOrCreateInterval(*AS), 0); } @@ -591,14 +590,21 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, SlotIndex MIIdx, LiveInterval &interval, bool isAlias) { - DEBUG({ - errs() << "\t\tlivein register: "; - printRegName(interval.reg, tri_); - }); + 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 // be considered a livein. MachineBasicBlock::iterator mi = MBB->begin(); + MachineBasicBlock::iterator E = MBB->end(); + // Skip over DBG_VALUE at the start of the MBB. + if (mi != E && mi->isDebugValue()) { + while (++mi != E && mi->isDebugValue()) + ; + if (mi == E) + // MBB is empty except for DBG_VALUE's. + return; + } + SlotIndex baseIndex = MIIdx; SlotIndex start = baseIndex; if (getInstructionFromIndex(baseIndex) == 0) @@ -606,185 +612,60 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, SlotIndex end = baseIndex; bool SeenDefUse = false; - - while (mi != MBB->end()) { + + while (mi != E) { if (mi->killsRegister(interval.reg, tri_)) { - DEBUG(errs() << " killed"); + DEBUG(dbgs() << " killed"); end = baseIndex.getDefIndex(); SeenDefUse = true; break; - } else if (mi->modifiesRegister(interval.reg, tri_)) { + } else if (mi->definesRegister(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: // [defSlot(def), defSlot(def)+1) - DEBUG(errs() << " dead"); + DEBUG(dbgs() << " dead"); end = start.getStoreIndex(); SeenDefUse = true; break; } - ++mi; - if (mi != MBB->end()) { + while (++mi != E && mi->isDebugValue()) + // Skip over DBG_VALUE. + ; + if (mi != E) baseIndex = indexes_->getNextNonNullIndex(baseIndex); - } } // Live-in register might not be used at all. if (!SeenDefUse) { if (isAlias) { - DEBUG(errs() << " dead"); + DEBUG(dbgs() << " dead"); end = MIIdx.getStoreIndex(); } else { - DEBUG(errs() << " live through"); + DEBUG(dbgs() << " live through"); end = baseIndex; } } + SlotIndex defIdx = getMBBStartIdx(MBB); + assert(getInstructionFromIndex(defIdx) == 0 && + "PHI def index points at actual instruction."); VNInfo *vni = - interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true), - 0, false, VNInfoAllocator); + interval.getNextValue(defIdx, 0, VNInfoAllocator); vni->setIsPHIDef(true); LiveRange LR(start, end, vni); interval.addRange(LR); - LR.valno->addKill(end); - DEBUG(errs() << " +" << LR << '\n'); -} - -bool LiveIntervals:: -isSafeAndProfitableToCoalesce(LiveInterval &DstInt, - LiveInterval &SrcInt, - SmallVector &IdentCopies, - SmallVector &OtherCopies) { - unsigned NumIdent = 0; - for (MachineRegisterInfo::def_iterator ri = mri_->def_begin(SrcInt.reg), - re = mri_->def_end(); ri != re; ++ri) { - MachineInstr *MI = &*ri; - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) - return false; - if (SrcReg != DstInt.reg) { - // Non-identity copy - we cannot handle overlapping intervals - if (DstInt.liveAt(getInstructionIndex(MI))) - return false; - OtherCopies.push_back(MI); - } else { - IdentCopies.push_back(MI); - ++NumIdent; - } - } - - return IdentCopies.size() > OtherCopies.size(); -} - -void LiveIntervals::performEarlyCoalescing() { - if (!EarlyCoalescing) - return; - - /// Perform early coalescing: eliminate copies which feed into phi joins - /// and whose sources are defined by the phi joins. - for (unsigned i = 0, e = phiJoinCopies.size(); i != e; ++i) { - MachineInstr *Join = phiJoinCopies[i]; - if (CoalescingLimit != -1 && (int)numCoalescing == CoalescingLimit) - break; - - unsigned PHISrc, PHIDst, SrcSubReg, DstSubReg; - bool isMove= tii_->isMoveInstr(*Join, PHISrc, PHIDst, SrcSubReg, DstSubReg); -#ifndef NDEBUG - assert(isMove && "PHI join instruction must be a move!"); -#else - isMove = isMove; -#endif - - LiveInterval &DstInt = getInterval(PHIDst); - LiveInterval &SrcInt = getInterval(PHISrc); - SmallVector IdentCopies; - SmallVector OtherCopies; - if (!isSafeAndProfitableToCoalesce(DstInt, SrcInt, - IdentCopies, OtherCopies)) - continue; - - DEBUG(errs() << "PHI Join: " << *Join); - assert(DstInt.containsOneValue() && "PHI join should have just one val#!"); - assert(std::distance(mri_->use_begin(PHISrc), mri_->use_end()) == 1 && - "PHI join src should not be used elsewhere"); - VNInfo *VNI = DstInt.getValNumInfo(0); - - // Change the non-identity copies to directly target the phi destination. - for (unsigned i = 0, e = OtherCopies.size(); i != e; ++i) { - MachineInstr *PHICopy = OtherCopies[i]; - SlotIndex MIIndex = getInstructionIndex(PHICopy); - DEBUG(errs() << "Moving: " << MIIndex << ' ' << *PHICopy); - SlotIndex DefIndex = MIIndex.getDefIndex(); - LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); - SlotIndex StartIndex = SLR->start; - SlotIndex EndIndex = SLR->end; - - // Delete val# defined by the now identity copy and add the range from - // beginning of the mbb to the end of the range. - SrcInt.removeValNo(SLR->valno); - DEBUG(errs() << " added range [" << StartIndex << ',' - << EndIndex << "] to reg" << DstInt.reg << '\n'); - assert (!DstInt.liveAt(StartIndex) && "Cannot coalesce when dst live!"); - VNInfo *NewVNI = DstInt.getNextValue(DefIndex, PHICopy, true, - VNInfoAllocator); - NewVNI->setHasPHIKill(true); - DstInt.addRange(LiveRange(StartIndex, EndIndex, NewVNI)); - for (unsigned j = 0, ee = PHICopy->getNumOperands(); j != ee; ++j) { - MachineOperand &MO = PHICopy->getOperand(j); - if (!MO.isReg() || MO.getReg() != PHISrc) - continue; - MO.setReg(PHIDst); - } - } - - // Now let's eliminate all the would-be identity copies. - for (unsigned i = 0, e = IdentCopies.size(); i != e; ++i) { - MachineInstr *PHICopy = IdentCopies[i]; - DEBUG(errs() << "Coalescing: " << *PHICopy); - - SlotIndex MIIndex = getInstructionIndex(PHICopy); - SlotIndex DefIndex = MIIndex.getDefIndex(); - LiveRange *SLR = SrcInt.getLiveRangeContaining(DefIndex); - SlotIndex StartIndex = SLR->start; - SlotIndex EndIndex = SLR->end; - - // Delete val# defined by the now identity copy and add the range from - // beginning of the mbb to the end of the range. - SrcInt.removeValNo(SLR->valno); - RemoveMachineInstrFromMaps(PHICopy); - PHICopy->eraseFromParent(); - DEBUG(errs() << " added range [" << StartIndex << ',' - << EndIndex << "] to reg" << DstInt.reg << '\n'); - DstInt.addRange(LiveRange(StartIndex, EndIndex, VNI)); - } - - // Remove the phi join and update the phi block liveness. - SlotIndex MIIndex = getInstructionIndex(Join); - SlotIndex UseIndex = MIIndex.getUseIndex(); - SlotIndex DefIndex = MIIndex.getDefIndex(); - LiveRange *SLR = SrcInt.getLiveRangeContaining(UseIndex); - LiveRange *DLR = DstInt.getLiveRangeContaining(DefIndex); - DLR->valno->setCopy(0); - DLR->valno->setIsDefAccurate(false); - DstInt.addRange(LiveRange(SLR->start, SLR->end, DLR->valno)); - SrcInt.removeRange(SLR->start, SLR->end); - assert(SrcInt.empty()); - removeInterval(PHISrc); - RemoveMachineInstrFromMaps(Join); - Join->eraseFromParent(); - - ++numCoalescing; - } + DEBUG(dbgs() << " +" << LR << '\n'); } /// computeIntervals - computes the live intervals for virtual /// registers. for some ordering of the machine instructions [1,N] a /// live interval is an interval [i, j) where 1 <= i <= j < N for /// which a variable is live -void LiveIntervals::computeIntervals() { - DEBUG(errs() << "********** COMPUTING LIVE INTERVALS **********\n" +void LiveIntervals::computeIntervals() { + DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'); @@ -792,14 +673,16 @@ void LiveIntervals::computeIntervals() { for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); MBBI != E; ++MBBI) { MachineBasicBlock *MBB = MBBI; + if (MBB->empty()) + continue; + // Track the index of the current machine instr. SlotIndex MIIndex = getMBBStartIdx(MBB); - DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); - - MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); + DEBUG(dbgs() << "BB#" << MBB->getNumber() + << ":\t\t# derived from " << MBB->getName() << "\n"); // Create intervals for live-ins to this BB first. - for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), + for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), LE = MBB->livein_end(); LI != LE; ++LI) { handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); // Multiple live-ins can alias the same register. @@ -808,13 +691,16 @@ void LiveIntervals::computeIntervals() { handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); } - + // Skip over empty initial indices. if (getInstructionFromIndex(MIIndex) == 0) MIIndex = indexes_->getNextNonNullIndex(MIIndex); - - for (; MI != miEnd; ++MI) { - DEBUG(errs() << MIIndex << "\t" << *MI); + + for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); + MI != miEnd; ++MI) { + DEBUG(dbgs() << MIIndex << "\t" << *MI); + if (MI->isDebugValue()) + continue; // Handle defs. for (int i = MI->getNumOperands() - 1; i >= 0; --i) { @@ -828,7 +714,7 @@ void LiveIntervals::computeIntervals() { else if (MO.isUndef()) UndefUses.push_back(MO.getReg()); } - + // Move to the next instr slot. MIIndex = indexes_->getNextNonNullIndex(MIIndex); } @@ -856,33 +742,32 @@ LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { return NewLI; } -/// getVNInfoSourceReg - Helper function that parses the specified VNInfo -/// copy field and returns the source register that defines it. -unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { - if (!VNI->getCopy()) - return 0; - - if (VNI->getCopy()->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { - // If it's extracting out of a physical register, return the sub-register. - unsigned Reg = VNI->getCopy()->getOperand(1).getReg(); - if (TargetRegisterInfo::isPhysicalRegister(Reg)) - Reg = tri_->getSubReg(Reg, VNI->getCopy()->getOperand(2).getImm()); - return Reg; - } else if (VNI->getCopy()->getOpcode() == TargetInstrInfo::INSERT_SUBREG || - VNI->getCopy()->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) - return VNI->getCopy()->getOperand(2).getReg(); - - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (tii_->isMoveInstr(*VNI->getCopy(), SrcReg, DstReg, SrcSubReg, DstSubReg)) - return SrcReg; - llvm_unreachable("Unrecognized copy instruction!"); - return 0; -} - //===----------------------------------------------------------------------===// // Register allocator hooks. // +MachineBasicBlock::iterator +LiveIntervals::getLastSplitPoint(const LiveInterval &li, + MachineBasicBlock *mbb) { + const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor(); + + // If li is not live into a landing pad, we can insert spill code before the + // first terminator. + if (!lpad || !isLiveInToMBB(li, lpad)) + return mbb->getFirstTerminator(); + + // When there is a landing pad, spill code must go before the call instruction + // that can throw. + MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin(); + while (I != B) { + --I; + if (I->getDesc().isCall()) + return I; + } + assert(0 && "Block with landing pad successor contains no call instruction"); + return mbb->getFirstTerminator(); +} + /// 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. @@ -896,7 +781,7 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, unsigned Reg = MO.getReg(); if (Reg == 0 || Reg == li.reg) continue; - + if (TargetRegisterInfo::isPhysicalRegister(Reg) && !allocatableRegs_[Reg]) continue; @@ -915,18 +800,17 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, /// which reaches the given instruction also reaches the specified use index. bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, SlotIndex UseIdx) const { - SlotIndex Index = getInstructionIndex(MI); - VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; - LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); - return UI != li.end() && UI->valno == ValNo; + VNInfo *UValNo = li.getVNInfoAt(UseIdx); + return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); } /// isReMaterializable - Returns true if the definition MI of the specified /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, - const VNInfo *ValNo, MachineInstr *MI, - SmallVectorImpl &SpillIs, - bool &isLoad) { +bool +LiveIntervals::isReMaterializable(const LiveInterval &li, + const VNInfo *ValNo, MachineInstr *MI, + const SmallVectorImpl &SpillIs, + bool &isLoad) { if (DisableReMat) return false; @@ -939,11 +823,12 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned ImpUse = getReMatImplicitUse(li, MI); if (ImpUse) { const LiveInterval &ImpLi = getInterval(ImpUse); - for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), - re = mri_->use_end(); ri != re; ++ri) { + for (MachineRegisterInfo::use_nodbg_iterator + ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); + ri != re; ++ri) { MachineInstr *UseMI = &*ri; SlotIndex UseIdx = getInstructionIndex(UseMI); - if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) + if (li.getVNInfoAt(UseIdx) != ValNo) continue; if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) return false; @@ -969,9 +854,10 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, - SmallVectorImpl &SpillIs, - bool &isLoad) { +bool +LiveIntervals::isReMaterializable(const LiveInterval &li, + const SmallVectorImpl &SpillIs, + bool &isLoad) { isLoad = false; for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); i != e; ++i) { @@ -979,9 +865,9 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, if (VNI->isUnused()) continue; // Dead val#. // Is the def for the val# rematerializable? - if (!VNI->isDefAccurate()) - return false; MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); + if (!ReMatDefMI) + return false; bool DefIsLoad = false; if (!ReMatDefMI || !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) @@ -1019,7 +905,7 @@ static bool FilterFoldedOps(MachineInstr *MI, } return false; } - + /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from /// slot / to reg or any rematerialized load into ith operand of specified @@ -1031,7 +917,7 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, SmallVector &Ops, bool isSS, int Slot, unsigned Reg) { // If it is an implicit def instruction, just delete it. - if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { + if (MI->isImplicitDef()) { RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -1051,22 +937,22 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, if (DefMI && (MRInfo & VirtRegMap::isMod)) return false; - MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) - : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); + MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot) + : tii_->foldMemoryOperand(MI, FoldOps, DefMI); if (fmi) { // Remember this instruction uses the spill slot. if (isSS) vrm.addSpillSlotUse(Slot, fmi); // Attempt to fold the memory reference into the instruction. If // we can do this, we don't need to insert spill code. - MachineBasicBlock &MBB = *MI->getParent(); if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); vrm.transferSpillPts(MI, fmi); vrm.transferRestorePts(MI, fmi); vrm.transferEmergencySpills(MI, fmi); ReplaceMachineInstrInMaps(MI, fmi); - MI = MBB.insert(MBB.erase(MI), fmi); + MI->eraseFromParent(); + MI = fmi; ++numFolds; return true; } @@ -1124,7 +1010,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); - if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) + if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; if (!vrm.isReMaterialized(Reg)) continue; @@ -1139,7 +1025,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, /// for addIntervalsForSpills to rewrite uses / defs for the given live range. bool LiveIntervals:: rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, - bool TrySplit, SlotIndex index, SlotIndex end, + bool TrySplit, SlotIndex index, SlotIndex end, MachineInstr *MI, MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, @@ -1158,8 +1044,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, if (!mop.isReg()) continue; unsigned Reg = mop.getReg(); - unsigned RegI = Reg; - if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) + if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; if (Reg != li.reg) continue; @@ -1171,8 +1056,8 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, // If this is the rematerializable definition MI itself and // all of its uses are rematerialized, simply delete it. if (MI == ReMatOrigDefMI && CanDelete) { - DEBUG(errs() << "\t\t\t\tErasing re-materlizable def: " - << MI << '\n'); + DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: " + << *MI << '\n'); RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); @@ -1199,27 +1084,9 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, // keep the src/dst regs pinned. // // Keep track of whether we replace a use and/or def so that we can - // create the spill interval with the appropriate range. - - HasUse = mop.isUse(); - HasDef = mop.isDef(); + // create the spill interval with the appropriate range. SmallVector Ops; - Ops.push_back(i); - for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { - const MachineOperand &MOj = MI->getOperand(j); - if (!MOj.isReg()) - continue; - unsigned RegJ = MOj.getReg(); - if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) - continue; - if (RegJ == RegI) { - Ops.push_back(j); - if (!MOj.isUndef()) { - HasUse |= MOj.isUse(); - HasDef |= MOj.isDef(); - } - } - } + tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops); // Create a new virtual register for the spill interval. // Create the new register now so we can map the fold instruction @@ -1230,6 +1097,12 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, NewVReg = mri_->createVirtualRegister(rc); vrm.grow(); CreatedNewVReg = true; + + // The new virtual register should get the same allocation hints as the + // old one. + std::pair Hint = mri_->getRegAllocationHint(Reg); + if (Hint.first || Hint.second) + mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second); } if (!TryFold) @@ -1267,13 +1140,16 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, rewriteImplicitOps(li, MI, NewVReg, vrm); // Reuse NewVReg for other reads. + bool HasEarlyClobber = false; for (unsigned j = 0, e = Ops.size(); j != e; ++j) { MachineOperand &mopj = MI->getOperand(Ops[j]); mopj.setReg(NewVReg); if (mopj.isImplicit()) rewriteImplicitOps(li, MI, NewVReg, vrm); + if (mopj.isEarlyClobber()) + HasEarlyClobber = true; } - + if (CreatedNewVReg) { if (DefIsReMat) { vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI); @@ -1317,29 +1193,33 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, if (HasUse) { if (CreatedNewVReg) { LiveRange LR(index.getLoadIndex(), index.getDefIndex(), - nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); - DEBUG(errs() << " +" << LR); + nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); + DEBUG(dbgs() << " +" << LR); nI.addRange(LR); } else { // Extend the split live interval to this def / use. SlotIndex End = index.getDefIndex(); LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, nI.getValNumInfo(nI.getNumValNums()-1)); - DEBUG(errs() << " +" << LR); + DEBUG(dbgs() << " +" << LR); nI.addRange(LR); } } if (HasDef) { - LiveRange LR(index.getDefIndex(), index.getStoreIndex(), - nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator)); - DEBUG(errs() << " +" << LR); + // An early clobber starts at the use slot, except for an early clobber + // tied to a use operand (yes, that is a thing). + LiveRange LR(HasEarlyClobber && !HasUse ? + index.getUseIndex() : index.getDefIndex(), + index.getStoreIndex(), + nI.getNextValue(SlotIndex(), 0, VNInfoAllocator)); + DEBUG(dbgs() << " +" << LR); nI.addRange(LR); } DEBUG({ - errs() << "\t\t\t\tAdded new interval: "; - nI.print(errs(), tri_); - errs() << '\n'; + dbgs() << "\t\t\t\tAdded new interval: "; + nI.print(dbgs(), tri_); + dbgs() << '\n'; }); } return CanFold; @@ -1348,16 +1228,7 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, MachineBasicBlock *MBB, SlotIndex Idx) const { - SlotIndex End = getMBBEndIdx(MBB); - for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { - if (VNI->kills[j].isPHI()) - continue; - - SlotIndex KillIdx = VNI->kills[j]; - if (KillIdx > Idx && KillIdx < End) - return true; - } - return false; + return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB)); } /// RewriteInfo - Keep track of machine instrs that will be rewritten @@ -1366,10 +1237,7 @@ namespace { struct RewriteInfo { SlotIndex Index; MachineInstr *MI; - bool HasUse; - bool HasDef; - RewriteInfo(SlotIndex i, MachineInstr *mi, bool u, bool d) - : Index(i), MI(mi), HasUse(u), HasDef(d) {} + RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {} }; struct RewriteInfoCompare { @@ -1408,7 +1276,31 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, MachineInstr *MI = &*ri; MachineOperand &O = ri.getOperand(); ++ri; - assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); + if (MI->isDebugValue()) { + // Modify DBG_VALUE now that the value is in a spill slot. + if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) { + uint64_t Offset = MI->getOperand(1).getImm(); + const MDNode *MDPtr = MI->getOperand(2).getMetadata(); + DebugLoc DL = MI->getDebugLoc(); + int FI = isLoadSS ? LdSlot : (int)Slot; + if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI, + Offset, MDPtr, DL)) { + DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI); + ReplaceMachineInstrInMaps(MI, NewDV); + MachineBasicBlock *MBB = MI->getParent(); + MBB->insert(MBB->erase(MI), NewDV); + continue; + } + } + + DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); + RemoveMachineInstrFromMaps(MI); + vrm.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + continue; + } + assert(!(O.isImplicit() && O.isUse()) && + "Spilling register that's used as implicit use?"); SlotIndex index = getInstructionIndex(MI); if (index < start || index >= end) continue; @@ -1424,7 +1316,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, // easily see a situation where both registers are reloaded before // the INSERT_SUBREG and both target registers that would overlap. continue; - RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); + RewriteMIs.push_back(RewriteInfo(index, MI)); } std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); @@ -1434,28 +1326,19 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, RewriteInfo &rwi = RewriteMIs[i]; ++i; SlotIndex index = rwi.Index; - bool MIHasUse = rwi.HasUse; - bool MIHasDef = rwi.HasDef; MachineInstr *MI = rwi.MI; // If MI def and/or use the same register multiple times, then there // are multiple entries. - unsigned NumUses = MIHasUse; while (i != e && RewriteMIs[i].MI == MI) { assert(RewriteMIs[i].Index == index); - bool isUse = RewriteMIs[i].HasUse; - if (isUse) ++NumUses; - MIHasUse |= isUse; - MIHasDef |= RewriteMIs[i].HasDef; ++i; } MachineBasicBlock *MBB = MI->getParent(); if (ImpUse && MI != ReMatDefMI) { - // Re-matting an instruction with virtual register use. Update the - // register interval's spill weight to HUGE_VALF to prevent it from - // being spilled. - LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + // Re-matting an instruction with virtual register use. Prevent interval + // from being spilled. + getInterval(ImpUse).markNotSpillable(); } unsigned MBBId = MBB->getNumber(); @@ -1472,7 +1355,8 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, // = use // It's better to start a new interval to avoid artifically // extend the new interval. - if (MIHasDef && !MIHasUse) { + if (MI->readsWritesVirtualRegister(li.reg) == + std::make_pair(false,true)) { MBBVRegsMap.erase(MBB->getNumber()); ThisVReg = 0; } @@ -1507,7 +1391,7 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval &nI = getOrCreateInterval(NewVReg); if (!TrySplit) { // The spill weight is now infinity as it cannot be spilled again. - nI.weight = HUGE_VALF; + nI.markNotSpillable(); continue; } @@ -1630,8 +1514,14 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, MachineOperand &O = ri.getOperand(); MachineInstr *MI = &*ri; ++ri; + if (MI->isDebugValue()) { + // Remove debug info for now. + O.setReg(0U); + DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI); + continue; + } if (O.isDef()) { - assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && + assert(MI->isImplicitDef() && "Register def was not rewritten?"); RemoveMachineInstrFromMaps(MI); vrm.RemoveMachineInstrFromMaps(MI); @@ -1655,115 +1545,38 @@ LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, } } -std::vector LiveIntervals:: -addIntervalsForSpillsFast(const LiveInterval &li, - const MachineLoopInfo *loopInfo, - VirtRegMap &vrm) { - unsigned slot = vrm.assignVirt2StackSlot(li.reg); +float +LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + // Limit the loop depth ridiculousness. + if (loopDepth > 200) + loopDepth = 200; - std::vector added; + // The loop depth is used to roughly estimate the number of times the + // instruction is executed. Something like 10^d is simple, but will quickly + // overflow a float. This expression behaves like 10^d for small d, but is + // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of + // headroom before overflow. + float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth); - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); - - DEBUG({ - errs() << "\t\t\t\tadding intervals for spills for interval: "; - li.dump(); - errs() << '\n'; - }); - - const TargetRegisterClass* rc = mri_->getRegClass(li.reg); - - MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); - while (RI != mri_->reg_end()) { - MachineInstr* MI = &*RI; - - SmallVector Indices; - bool HasUse = false; - bool HasDef = false; - - for (unsigned i = 0; i != MI->getNumOperands(); ++i) { - MachineOperand& mop = MI->getOperand(i); - if (!mop.isReg() || mop.getReg() != li.reg) continue; - - HasUse |= MI->getOperand(i).isUse(); - HasDef |= MI->getOperand(i).isDef(); - - Indices.push_back(i); - } - - if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), - Indices, true, slot, li.reg)) { - unsigned NewVReg = mri_->createVirtualRegister(rc); - vrm.grow(); - vrm.assignVirt2StackSlot(NewVReg, slot); - - // create a new register for this spill - LiveInterval &nI = getOrCreateInterval(NewVReg); - - // the spill weight is now infinity as it - // cannot be spilled again - nI.weight = HUGE_VALF; - - // Rewrite register operands to use the new vreg. - for (SmallVectorImpl::iterator I = Indices.begin(), - E = Indices.end(); I != E; ++I) { - MI->getOperand(*I).setReg(NewVReg); - - if (MI->getOperand(*I).isUse()) - MI->getOperand(*I).setIsKill(true); - } - - // Fill in the new live interval. - SlotIndex index = getInstructionIndex(MI); - if (HasUse) { - LiveRange LR(index.getLoadIndex(), index.getUseIndex(), - nI.getNextValue(SlotIndex(), 0, false, - getVNInfoAllocator())); - DEBUG(errs() << " +" << LR); - nI.addRange(LR); - vrm.addRestorePoint(NewVReg, MI); - } - if (HasDef) { - LiveRange LR(index.getDefIndex(), index.getStoreIndex(), - nI.getNextValue(SlotIndex(), 0, false, - getVNInfoAllocator())); - DEBUG(errs() << " +" << LR); - nI.addRange(LR); - vrm.addSpillPoint(NewVReg, true, MI); - } - - added.push_back(&nI); - - DEBUG({ - errs() << "\t\t\t\tadded new interval: "; - nI.dump(); - errs() << '\n'; - }); - } - - - RI = mri_->reg_begin(li.reg); - } + return (isDef + isUse) * lc; +} - return added; +void +LiveIntervals::normalizeSpillWeights(std::vector &NewLIs) { + for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) + normalizeSpillWeight(*NewLIs[i]); } std::vector LiveIntervals:: addIntervalsForSpills(const LiveInterval &li, - SmallVectorImpl &SpillIs, + const SmallVectorImpl &SpillIs, const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { - - if (EnableFastSpilling) - return addIntervalsForSpillsFast(li, loopInfo, vrm); - - assert(li.weight != HUGE_VALF && - "attempt to spill already spilled interval!"); + assert(li.isSpillable() && "attempt to spill already spilled interval!"); DEBUG({ - errs() << "\t\t\t\tadding intervals for spills for interval: "; - li.print(errs(), tri_); - errs() << '\n'; + dbgs() << "\t\t\t\tadding intervals for spills for interval: "; + li.print(dbgs(), tri_); + dbgs() << '\n'; }); // Each bit specify whether a spill is required in the MBB. @@ -1832,6 +1645,7 @@ addIntervalsForSpills(const LiveInterval &li, } handleSpilledImpDefs(li, vrm, rc, NewLIs); + normalizeSpillWeights(NewLIs); return NewLIs; } @@ -1846,8 +1660,7 @@ addIntervalsForSpills(const LiveInterval &li, if (VNI->isUnused()) continue; // Dead val#. // Is the def for the val# rematerializable? - MachineInstr *ReMatDefMI = VNI->isDefAccurate() - ? getInstructionFromIndex(VNI->def) : 0; + MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); bool dummy; if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { // Remember how to remat the def of this val#. @@ -1879,7 +1692,7 @@ addIntervalsForSpills(const LiveInterval &li, if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) Slot = vrm.assignVirt2StackSlot(li.reg); - + // This case only occurs when the prealloc splitter has already assigned // a stack slot to this vreg. else @@ -1907,6 +1720,7 @@ addIntervalsForSpills(const LiveInterval &li, // Insert spills / restores if we are splitting. if (!TrySplit) { handleSpilledImpDefs(li, vrm, rc, NewLIs); + normalizeSpillWeights(NewLIs); return NewLIs; } @@ -1935,7 +1749,7 @@ addIntervalsForSpills(const LiveInterval &li, Ops.push_back(j); if (MO.isDef()) continue; - if (isReMat || + if (isReMat || (!FoundUse && !alsoFoldARestore(Id, index, VReg, RestoreMBBs, RestoreIdxes))) { // MI has two-address uses of the same register. If the use @@ -2023,11 +1837,10 @@ addIntervalsForSpills(const LiveInterval &li, unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); if (ImpUse) { // Re-matting an instruction with virtual register use. Add the - // register as an implicit use on the use MI and update the register - // interval's spill weight to HUGE_VALF to prevent it from being - // spilled. + // register as an implicit use on the use MI and mark the register + // interval as unspillable. LiveInterval &ImpLi = getInterval(ImpUse); - ImpLi.weight = HUGE_VALF; + ImpLi.markNotSpillable(); MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); } } @@ -2049,7 +1862,6 @@ addIntervalsForSpills(const LiveInterval &li, for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { LiveInterval *LI = NewLIs[i]; if (!LI->empty()) { - LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI); if (!AddedKill.count(LI)) { LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; SlotIndex LastUseIdx = LR->end.getBaseIndex(); @@ -2066,6 +1878,7 @@ addIntervalsForSpills(const LiveInterval &li, } handleSpilledImpDefs(li, vrm, rc, RetNewLIs); + normalizeSpillWeights(RetNewLIs); return RetNewLIs; } @@ -2081,7 +1894,7 @@ bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { /// getRepresentativeReg - Find the largest super register of the specified /// physical register. unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { - // Find the largest super-register that is allocatable. + // Find the largest super-register that is allocatable. unsigned BestReg = Reg; for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { unsigned SuperReg = *AS; @@ -2103,6 +1916,8 @@ unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, E = mri_->reg_end(); I != E; ++I) { MachineOperand &O = I.getOperand(); MachineInstr *MI = O.getParent(); + if (MI->isDebugValue()) + continue; SlotIndex Index = getInstructionIndex(MI); if (pli.liveAt(Index)) ++NumConflicts; @@ -2117,6 +1932,9 @@ bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, unsigned PhysReg, VirtRegMap &vrm) { unsigned SpillReg = getRepresentativeReg(PhysReg); + DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg) + << " represented by " << tri_->getName(SpillReg) << '\n'); + for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) // If there are registers which alias PhysReg, but which are not a // sub-register of the chosen representative super register. Assert @@ -2128,56 +1946,54 @@ bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, SmallVector PRegs; if (hasInterval(SpillReg)) PRegs.push_back(SpillReg); - else { - SmallSet Added; - for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) - if (Added.insert(*AS) && hasInterval(*AS)) { - PRegs.push_back(*AS); - for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS) - Added.insert(*ASS); - } - } + for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR) + if (hasInterval(*SR)) + PRegs.push_back(*SR); + + DEBUG({ + dbgs() << "Trying to spill:"; + for (unsigned i = 0, e = PRegs.size(); i != e; ++i) + dbgs() << ' ' << tri_->getName(PRegs[i]); + dbgs() << '\n'; + }); SmallPtrSet SeenMIs; for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), E = mri_->reg_end(); I != E; ++I) { MachineOperand &O = I.getOperand(); MachineInstr *MI = O.getParent(); - if (SeenMIs.count(MI)) + if (MI->isDebugValue() || SeenMIs.count(MI)) continue; SeenMIs.insert(MI); SlotIndex Index = getInstructionIndex(MI); + bool LiveReg = false; for (unsigned i = 0, e = PRegs.size(); i != e; ++i) { unsigned PReg = PRegs[i]; LiveInterval &pli = getInterval(PReg); if (!pli.liveAt(Index)) continue; - vrm.addEmergencySpill(PReg, MI); + LiveReg = true; SlotIndex StartIdx = Index.getLoadIndex(); SlotIndex EndIdx = Index.getNextIndex().getBaseIndex(); - if (pli.isInOneLiveRange(StartIdx, EndIdx)) { - pli.removeRange(StartIdx, EndIdx); - Cut = true; - } else { + if (!pli.isInOneLiveRange(StartIdx, EndIdx)) { std::string msg; raw_string_ostream Msg(msg); Msg << "Ran out of registers during register allocation!"; - if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { + if (MI->isInlineAsm()) { Msg << "\nPlease check your inline asm statement for invalid " << "constraints:\n"; MI->print(Msg, tm_); } - llvm_report_error(Msg.str()); - } - for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) { - if (!hasInterval(*AS)) - continue; - LiveInterval &spli = getInterval(*AS); - if (spli.liveAt(Index)) - spli.removeRange(Index.getLoadIndex(), - Index.getNextIndex().getBaseIndex()); + report_fatal_error(Msg.str()); } + pli.removeRange(StartIdx, EndIdx); + LiveReg = true; } + if (!LiveReg) + continue; + DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI); + vrm.addEmergencySpill(SpillReg, MI); + Cut = true; } return Cut; } @@ -2187,14 +2003,13 @@ LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, LiveInterval& Interval = getOrCreateInterval(reg); VNInfo* VN = Interval.getNextValue( SlotIndex(getInstructionIndex(startInst).getDefIndex()), - startInst, true, getVNInfoAllocator()); + startInst, getVNInfoAllocator()); VN->setHasPHIKill(true); - VN->kills.push_back(indexes_->getTerminatorGap(startInst->getParent())); LiveRange LR( SlotIndex(getInstructionIndex(startInst).getDefIndex()), - getMBBEndIdx(startInst->getParent()).getNextIndex().getBaseIndex(), VN); + getMBBEndIdx(startInst->getParent()), VN); Interval.addRange(LR); - + return LR; }