X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveIntervalAnalysis.cpp;h=d6c8a6561e4f85c680c201bca826a46e817b8fee;hb=f9410141f703f4e8a6aba717617ef958249f6d13;hp=dae20caa41aa9547af635c1dc7149b0a6e6f5ff4;hpb=ae339babb2a2445e7bb009912a39994718f10d54;p=oota-llvm.git diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index dae20caa41a..d6c8a6561e4 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -30,6 +30,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" @@ -67,8 +68,12 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addPreservedID(MachineLoopInfoID); AU.addPreservedID(MachineDominatorsID); - AU.addPreservedID(PHIEliminationID); - AU.addRequiredID(PHIEliminationID); + + if (!StrongPHIElim) { + AU.addPreservedID(PHIEliminationID); + AU.addRequiredID(PHIEliminationID); + } + AU.addRequiredID(TwoAddressInstructionPassID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -125,9 +130,13 @@ void LiveIntervals::computeNumbering() { MIIndex += InstrSlots::NUM; FunctionSize++; - // Insert an empty slot after every instruction. - MIIndex += InstrSlots::NUM; - i2miMap_.push_back(0); + // Insert max(1, numdefs) empty slots after every instruction. + unsigned Slots = I->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; + while (Slots--) + i2miMap_.push_back(0); } // Set the MBB2IdxMap entry for this MBB. @@ -213,7 +222,7 @@ void LiveIntervals::computeNumbering() { unsigned index = (vni->kills[i]-1) / InstrSlots::NUM; unsigned offset = vni->kills[i] % InstrSlots::NUM; - if (offset == InstrSlots::STORE) { + if (offset == InstrSlots::LOAD) { std::vector::const_iterator I = std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); --I; @@ -302,7 +311,7 @@ bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, continue; for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned PhysReg = mop.getReg(); if (PhysReg == 0 || PhysReg == li.reg) @@ -348,6 +357,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, if (interval.empty()) { // Get the Idx of the defining instructions. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; unsigned SrcReg, DstReg; @@ -431,6 +443,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, assert(interval.containsOneValue()); unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); unsigned RedefIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + RedefIndex = getUseIndex(MIIdx); const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); VNInfo *OldValNo = OldLR->valno; @@ -498,6 +513,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // live until the end of the block. We've already taken care of the // rest of the live range. unsigned defIndex = getDefIndex(MIIdx); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + defIndex = getUseIndex(MIIdx); VNInfo *ValNo; MachineInstr *CopyMI = NULL; @@ -532,6 +550,9 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, unsigned baseIndex = MIIdx; unsigned start = getDefIndex(baseIndex); + // Earlyclobbers move back one. + if (MO.isEarlyClobber()) + start = getUseIndex(MIIdx); unsigned end = start; // If it is not used after definition, it is considered dead at @@ -539,7 +560,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // [defSlot(def), defSlot(def)+1) if (MO.isDead()) { DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } @@ -561,7 +582,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // it. Hence its interval is: // [defSlot(def), defSlot(def)+1) DOUT << " dead"; - end = getDefIndex(start) + 1; + end = start + 1; goto exit; } @@ -572,7 +593,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, // instruction where we know it's dead is if it is live-in to the function // and never used. assert(!CopyMI && "physreg was not killed in defining block!"); - end = getDefIndex(start) + 1; // It's dead. + end = start + 1; exit: assert(start < end && "did not find end of interval?"); @@ -624,7 +645,11 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, MachineBasicBlock::iterator mi = MBB->begin(); unsigned baseIndex = MIIdx; unsigned start = baseIndex; - unsigned end = start; + while (baseIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(baseIndex) == 0) + baseIndex += InstrSlots::NUM; + unsigned end = baseIndex; + while (mi != MBB->end()) { if (mi->killsRegister(interval.reg, tri_)) { DOUT << " killed"; @@ -659,7 +684,7 @@ exit: } } - LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); + LiveRange LR(start, end, interval.getNextValue(~0U, 0, VNInfoAllocator)); interval.addRange(LR); interval.addKill(LR.valno, end); DOUT << " +" << LR << '\n'; @@ -669,21 +694,17 @@ exit: /// 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() { +void LiveIntervals::computeIntervals() { + DOUT << "********** COMPUTING LIVE INTERVALS **********\n" << "********** Function: " << ((Value*)mf_->getFunction())->getName() << '\n'; - // Track the index of the current machine instr. - unsigned MIIndex = 0; - - // Skip over empty initial indices. - while (MIIndex / InstrSlots::NUM < i2miMap_.size() && - getInstructionFromIndex(MIIndex) == 0) - MIIndex += InstrSlots::NUM; for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); MBBI != E; ++MBBI) { MachineBasicBlock *MBB = MBBI; + // Track the index of the current machine instr. + unsigned MIIndex = getMBBStartIdx(MBB); DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); @@ -699,6 +720,11 @@ void LiveIntervals::computeIntervals() { true); } + // Skip over empty initial indices. + while (MIIndex / InstrSlots::NUM < i2miMap_.size() && + getInstructionFromIndex(MIIndex) == 0) + MIIndex += InstrSlots::NUM; + for (; MI != miEnd; ++MI) { DOUT << MIIndex << "\t" << *MI; @@ -706,11 +732,16 @@ void LiveIntervals::computeIntervals() { for (int i = MI->getNumOperands() - 1; i >= 0; --i) { MachineOperand &MO = MI->getOperand(i); // handle register defs - build intervals - if (MO.isRegister() && MO.getReg() && MO.isDef()) + if (MO.isReg() && MO.getReg() && MO.isDef()) { handleRegisterDef(MBB, MI, MIIndex, MO, i); + } } - - MIIndex += InstrSlots::NUM; + + // Skip over the empty slots after each instruction. + unsigned Slots = MI->getDesc().getNumDefs(); + if (Slots == 0) + Slots = 1; + MIIndex += InstrSlots::NUM * Slots; // Skip over empty indices. while (MIIndex / InstrSlots::NUM < i2miMap_.size() && @@ -736,7 +767,6 @@ bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, return ResVal; } - LiveInterval* LiveIntervals::createInterval(unsigned reg) { float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; @@ -772,7 +802,7 @@ unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, unsigned RegOp = 0; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister() || !MO.isUse()) + if (!MO.isReg() || !MO.isUse()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || Reg == li.reg) @@ -802,6 +832,7 @@ bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, /// val# of the specified interval is re-materializable. bool LiveIntervals::isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI, + SmallVectorImpl &SpillIs, bool &isLoad) { if (DisableReMat) return false; @@ -838,8 +869,8 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, // If the instruction accesses memory and the memory could be non-constant, // assume the instruction is not rematerializable. - for (std::list::const_iterator I = MI->memoperands_begin(), - E = MI->memoperands_end(); I != E; ++I) { + for (std::list::const_iterator + I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ const MachineMemOperand &MMO = *I; if (MMO.isVolatile() || MMO.isStore()) return false; @@ -907,13 +938,21 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) return false; } + + // If a register operand of the re-materialized instruction is going to + // be spilled next, then it's not legal to re-materialize this instruction. + for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) + if (ImpUse == SpillIs[i]->reg) + return false; } return true; } /// isReMaterializable - Returns true if every definition of MI of every /// val# of the specified interval is re-materializable. -bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { +bool LiveIntervals::isReMaterializable(const LiveInterval &li, + SmallVectorImpl &SpillIs, + bool &isLoad) { isLoad = false; for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); i != e; ++i) { @@ -927,7 +966,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); bool DefIsLoad = false; if (!ReMatDefMI || - !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) + !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) return false; isLoad |= DefIsLoad; } @@ -1067,7 +1106,7 @@ void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, // use operand. Make sure we rewrite that as well. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (!MO.isRegister()) + if (!MO.isReg()) continue; unsigned Reg = MO.getReg(); if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) @@ -1102,7 +1141,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { MachineOperand& mop = MI->getOperand(i); - if (!mop.isRegister()) + if (!mop.isReg()) continue; unsigned Reg = mop.getReg(); unsigned RegI = Reg; @@ -1154,7 +1193,7 @@ rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, Ops.push_back(i); for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { const MachineOperand &MOj = MI->getOperand(j); - if (!MOj.isRegister()) + if (!MOj.isReg()) continue; unsigned RegJ = MOj.getReg(); if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) @@ -1624,74 +1663,86 @@ addIntervalsForSpillsFast(const LiveInterval &li, const TargetRegisterClass* rc = mri_->getRegClass(li.reg); - DenseMap VRegMap; - DenseMap VNMap; - SSWeight = 0.0f; - for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg), - RE = mri_->reg_end(); RI != RE; ) { - // Create a new virtual register for the spill interval. - MachineOperand& MO = RI.getOperand(); - unsigned NewVReg = 0; - bool newInt = false; - if (!VRegMap.count(MO.getParent())) { - VRegMap[MO.getParent()] = NewVReg = mri_->createVirtualRegister(rc); - vrm.grow(); - vrm.assignVirt2StackSlot(NewVReg, slot); - - newInt = true; - } else - NewVReg = VRegMap[MO.getParent()]; + MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); + while (RI != mri_->reg_end()) { + MachineInstr* MI = &*RI; - // Increment iterator to avoid invalidation. - ++RI; + SmallVector Indices; + bool HasUse = false; + bool HasDef = false; - MO.setReg(NewVReg); - - // 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; - - unsigned index = getInstructionIndex(MO.getParent()); - bool HasUse = MO.isUse(); - bool HasDef = MO.isDef(); - if (!VNMap.count(MO.getParent())) - VNMap[MO.getParent()] = nI.getNextValue(~0U, 0, getVNInfoAllocator()); - if (HasUse) { - LiveRange LR(getLoadIndex(index), getUseIndex(index), - VNMap[MO.getParent()]); - DOUT << " +" << LR; - nI.addRange(LR); - } - if (HasDef) { - LiveRange LR(getDefIndex(index), getStoreIndex(index), - VNMap[MO.getParent()]); - DOUT << " +" << LR; - nI.addRange(LR); + 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 (newInt) + 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. + unsigned index = getInstructionIndex(MI); + if (HasUse) { + LiveRange LR(getLoadIndex(index), getUseIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addRestorePoint(NewVReg, MI); + } + if (HasDef) { + LiveRange LR(getDefIndex(index), getStoreIndex(index), + nI.getNextValue(~0U, 0, getVNInfoAllocator())); + DOUT << " +" << LR; + nI.addRange(LR); + vrm.addSpillPoint(NewVReg, true, MI); + } + added.push_back(&nI); - DOUT << "\t\t\t\tadded new interval: "; - DEBUG(nI.dump()); - DOUT << '\n'; + DOUT << "\t\t\t\tadded new interval: "; + DEBUG(nI.dump()); + DOUT << '\n'; + + unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); + if (HasUse) { + if (HasDef) + SSWeight += getSpillWeight(true, true, loopDepth); + else + SSWeight += getSpillWeight(false, true, loopDepth); + } else + SSWeight += getSpillWeight(true, false, loopDepth); + } - unsigned loopDepth = loopInfo->getLoopDepth(MO.getParent()->getParent()); - if (HasUse) { - if (HasDef) - SSWeight += getSpillWeight(true, true, loopDepth); - else - SSWeight += getSpillWeight(false, true, loopDepth); - } else - SSWeight += getSpillWeight(true, false, loopDepth); + RI = mri_->reg_begin(li.reg); } + // Clients expect the new intervals to be returned in sorted order. std::sort(added.begin(), added.end(), LISorter()); return added; @@ -1699,6 +1750,7 @@ addIntervalsForSpillsFast(const LiveInterval &li, std::vector LiveIntervals:: addIntervalsForSpills(const LiveInterval &li, + SmallVectorImpl &SpillIs, const MachineLoopInfo *loopInfo, VirtRegMap &vrm, float &SSWeight) { @@ -1802,7 +1854,7 @@ addIntervalsForSpills(const LiveInterval &li, MachineInstr *ReMatDefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); bool dummy; - if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { + if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { // Remember how to remat the def of this val#. ReMatOrigDefs[VN] = ReMatDefMI; // Original def may be modified so we have to make a copy here. @@ -1877,7 +1929,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; Ops.push_back(j); @@ -1948,7 +2000,7 @@ addIntervalsForSpills(const LiveInterval &li, CanFold = true; for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { MachineOperand &MO = MI->getOperand(j); - if (!MO.isRegister() || MO.getReg() != VReg) + if (!MO.isReg() || MO.getReg() != VReg) continue; if (MO.isDef()) {