diff options
author | Evan Cheng <evan.cheng@apple.com> | 2007-11-17 00:40:40 +0000 |
---|---|---|
committer | Evan Cheng <evan.cheng@apple.com> | 2007-11-17 00:40:40 +0000 |
commit | 81a038218171860ee4c382849c647d3dc841fe8b (patch) | |
tree | cda5d87b9f13b8a4b752538a0b31b538ea6372b0 | |
parent | 38b0be01ded327a50ac600dd7710016b2326d841 (diff) | |
download | external_llvm-81a038218171860ee4c382849c647d3dc841fe8b.zip external_llvm-81a038218171860ee4c382849c647d3dc841fe8b.tar.gz external_llvm-81a038218171860ee4c382849c647d3dc841fe8b.tar.bz2 |
Live interval splitting:
When a live interval is being spilled, rather than creating short, non-spillable
intervals for every def / use, split the interval at BB boundaries. That is, for
every BB where the live interval is defined or used, create a new interval that
covers all the defs and uses in the BB.
This is designed to eliminate one common problem: multiple reloads of the same
value in a single basic block. Note, it does *not* decrease the number of spills
since no copies are inserted so the split intervals are *connected* through
spill and reloads (or rematerialization). The newly created intervals can be
spilled again, in that case, since it does not span multiple basic blocks, it's
spilled in the usual manner. However, it can reuse the same stack slot as the
previously split interval.
This is currently controlled by -split-intervals-at-bb.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44198 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/CodeGen/LiveIntervalAnalysis.h | 25 | ||||
-rw-r--r-- | include/llvm/CodeGen/LiveVariables.h | 41 | ||||
-rw-r--r-- | lib/CodeGen/LiveIntervalAnalysis.cpp | 355 | ||||
-rw-r--r-- | lib/CodeGen/LiveVariables.cpp | 49 | ||||
-rw-r--r-- | lib/CodeGen/RegAllocLinearScan.cpp | 18 | ||||
-rw-r--r-- | lib/CodeGen/SimpleRegisterCoalescing.cpp | 3 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 198 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.h | 104 |
8 files changed, 631 insertions, 162 deletions
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 16dff55..e4582f7 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -32,6 +32,7 @@ namespace llvm { class LiveVariables; + class LoopInfo; class MRegisterInfo; class SSARegMap; class TargetInstrInfo; @@ -104,8 +105,8 @@ namespace llvm { return getBaseIndex(index) + InstrSlots::STORE; } - static float getSpillWeight(const MachineOperand &mop, unsigned loopDepth) { - return (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth); + static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { + return (isDef + isUse) * powf(10.0F, (float)loopDepth); } typedef Reg2IntervalMap::iterator iterator; @@ -229,7 +230,8 @@ namespace llvm { /// addIntervalsForSpills - Create new intervals for spilled defs / uses of /// the given interval. std::vector<LiveInterval*> - addIntervalsForSpills(const LiveInterval& i, VirtRegMap& vrm); + addIntervalsForSpills(const LiveInterval& i, + const LoopInfo *loopInfo, VirtRegMap& vrm); private: /// computeIntervals - Compute live intervals. @@ -275,21 +277,32 @@ namespace llvm { MachineInstr *DefMI, unsigned index, unsigned i, bool isSS, int slot, unsigned reg); + bool anyKillInMBBAfterIdx(const LiveInterval &li, + MachineBasicBlock *MBB, unsigned Idx, + const VNInfo *VNI = NULL) const; + + bool intervalIsInOneMBB(const LiveInterval &li) const; + /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions /// for addIntervalsForSpills to rewrite uses / defs for the given live range. - void rewriteInstructionForSpills(const LiveInterval &li, + void rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, unsigned id, unsigned index, unsigned end, MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, SmallVector<int, 4> &ReMatIds, + unsigned &NewVReg, bool &HasDef, bool &HasUse, const LoopInfo *loopInfo, + std::vector<unsigned> &NewVRegs, std::vector<LiveInterval*> &NewLIs); - void rewriteInstructionsForSpills(const LiveInterval &li, + void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, - SmallVector<int, 4> &ReMatIds, + SmallVector<int, 4> &ReMatIds, const LoopInfo *loopInfo, + BitVector &SpillMBBs, + std::vector<std::pair<int, unsigned> > &SpillIdxes, + std::vector<unsigned> &NewVRegs, std::vector<LiveInterval*> &NewLIs); static LiveInterval createInterval(unsigned Reg); diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index 8938330..b9d5784 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -154,20 +154,6 @@ private: // Intermediate data structures SmallVector<unsigned, 4> *PHIVarInfo; - /// addRegisterKilled - We have determined MI kills a register. Look for the - /// operand that uses it and mark it as IsKill. If AddIfNotFound is true, - /// add a implicit operand if it's not found. Returns true if the operand - /// exists / is added. - bool addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, - bool AddIfNotFound = false); - - /// addRegisterDead - We have determined MI defined a register without a use. - /// Look for the operand that defines it and mark it as IsDead. If - /// AddIfNotFound is true, add a implicit operand if it's not found. Returns - /// true if the operand exists / is added. - bool addRegisterDead(unsigned IncomingReg, MachineInstr *MI, - bool AddIfNotFound = false); - void addRegisterKills(unsigned Reg, MachineInstr *MI, SmallSet<unsigned, 4> &SubKills); @@ -210,15 +196,28 @@ public: /// the records for NewMI. void instructionChanged(MachineInstr *OldMI, MachineInstr *NewMI); + /// transferKillDeadInfo - Similar to instructionChanged except it does not + /// update live variables internal data structures. + static void transferKillDeadInfo(MachineInstr *OldMI, MachineInstr *NewMI, + const MRegisterInfo *RegInfo); + + /// addRegisterKilled - We have determined MI kills a register. Look for the + /// operand that uses it and mark it as IsKill. If AddIfNotFound is true, + /// add a implicit operand if it's not found. Returns true if the operand + /// exists / is added. + static bool addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, + const MRegisterInfo *RegInfo, + bool AddIfNotFound = false); + /// addVirtualRegisterKilled - Add information about the fact that the /// specified register is killed after being used by the specified /// instruction. If AddIfNotFound is true, add a implicit operand if it's /// not found. void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI, bool AddIfNotFound = false) { - if (addRegisterKilled(IncomingReg, MI, AddIfNotFound)) + if (addRegisterKilled(IncomingReg, MI, RegInfo, AddIfNotFound)) getVarInfo(IncomingReg).Kills.push_back(MI); - } + } /// removeVirtualRegisterKilled - Remove the specified virtual /// register from the live variable information. Returns true if the @@ -248,12 +247,20 @@ public: /// instruction. void removeVirtualRegistersKilled(MachineInstr *MI); + /// addRegisterDead - We have determined MI defined a register without a use. + /// Look for the operand that defines it and mark it as IsDead. If + /// AddIfNotFound is true, add a implicit operand if it's not found. Returns + /// true if the operand exists / is added. + static bool addRegisterDead(unsigned IncomingReg, MachineInstr *MI, + const MRegisterInfo *RegInfo, + bool AddIfNotFound = false); + /// addVirtualRegisterDead - Add information about the fact that the specified /// register is dead after being used by the specified instruction. If /// AddIfNotFound is true, add a implicit operand if it's not found. void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI, bool AddIfNotFound = false) { - if (addRegisterDead(IncomingReg, MI, AddIfNotFound)) + if (addRegisterDead(IncomingReg, MI, RegInfo, AddIfNotFound)) getVarInfo(IncomingReg).Kills.push_back(MI); } diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 55094e3..d2e32ab 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -19,6 +19,7 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "VirtRegMap.h" #include "llvm/Value.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstr.h" @@ -39,6 +40,9 @@ namespace { // Hidden options for help debugging. cl::opt<bool> DisableReMat("disable-rematerialization", cl::init(false), cl::Hidden); + + cl::opt<bool> SplitAtBB("split-intervals-at-bb", + cl::init(false), cl::Hidden); } STATISTIC(numIntervals, "Number of original intervals"); @@ -632,7 +636,8 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li, /// slot / to reg or any rematerialized load into ith operand of specified /// MI. If it is successul, MI is updated with the newly created MI and /// returns true. -bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, +bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, + VirtRegMap &vrm, MachineInstr *DefMI, unsigned index, unsigned i, bool isSS, int slot, unsigned reg) { @@ -644,8 +649,11 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, // we can do this, we don't need to insert spill code. if (lv_) lv_->instructionChanged(MI, fmi); + else + LiveVariables::transferKillDeadInfo(MI, fmi, mri_); MachineBasicBlock &MBB = *MI->getParent(); vrm.virtFolded(reg, MI, i, fmi); + vrm.transferSpillPts(MI, fmi); mi2iMap_.erase(MI); i2miMap_[index/InstrSlots::NUM] = fmi; mi2iMap_[fmi] = index; @@ -656,17 +664,50 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, return false; } +bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { + SmallPtrSet<MachineBasicBlock*, 4> MBBs; + for (LiveInterval::Ranges::const_iterator + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + std::vector<IdxMBBPair>::const_iterator II = + std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); + if (II == Idx2MBBMap.end()) + continue; + if (I->end > II->first) // crossing a MBB. + return false; + MBBs.insert(II->second); + if (MBBs.size() > 1) + return false; + } + return true; +} + +static +bool hasALaterUse(MachineBasicBlock *MBB, MachineInstr *MI, unsigned Reg) { + MachineBasicBlock::iterator I = MI; + if (I == MBB->end()) + return false; + ++I; + while (I != MBB->end()) { + if (I->findRegisterUseOperandIdx(Reg) != -1) + return true; + ++I; + } + return false; +} + /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions /// for addIntervalsForSpills to rewrite uses / defs for the given live range. void LiveIntervals:: -rewriteInstructionForSpills(const LiveInterval &li, - unsigned id, unsigned index, unsigned end, - MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, +rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, + unsigned id, unsigned index, unsigned end, MachineInstr *MI, + MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, SmallVector<int, 4> &ReMatIds, + unsigned &NewVReg, bool &HasDef, bool &HasUse, + const LoopInfo *loopInfo, std::vector<unsigned> &NewVRegs, std::vector<LiveInterval*> &NewLIs) { RestartInstruction: for (unsigned i = 0; i != MI->getNumOperands(); ++i) { @@ -688,14 +729,15 @@ rewriteInstructionForSpills(const LiveInterval &li, if (DefIsReMat) { // If this is the rematerializable definition MI itself and // all of its uses are rematerialized, simply delete it. - if (MI == OrigDefMI && CanDelete) { + if (MI == ReMatOrigDefMI && CanDelete) { RemoveMachineInstrFromMaps(MI); MI->eraseFromParent(); break; } // If def for this use can't be rematerialized, then try folding. - TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad)); + TryFold = !ReMatOrigDefMI || + (ReMatOrigDefMI && (MI == ReMatOrigDefMI || isLoad)); if (isLoad) { // Try fold loads (from stack slot, constant pool, etc.) into uses. FoldSS = isLoadSS; @@ -703,16 +745,32 @@ rewriteInstructionForSpills(const LiveInterval &li, } } + // If we are splitting live intervals, only fold if it's 1) the first + // use and it's a kill or 2) there isn't another use later in this MBB. + TryFold &= NewVReg == 0; + if (TryFold && TrySplit) + // Do not fold store into def here if we are splitting. We'll find an + // optimal point to insert a store later. + if (HasDef || mop.isDef() || + (!mop.isKill() && hasALaterUse(MI->getParent(), MI, li.reg))) + TryFold = false; + // FIXME: fold subreg use if (!isSubReg && TryFold && - tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg)) + tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, i, FoldSS, FoldSlot, + Reg)) // Folding the load/store can completely change the instruction in // unpredictable ways, rescan it from the beginning. goto RestartInstruction; // Create a new virtual register for the spill interval. - unsigned NewVReg = RegMap->createVirtualRegister(rc); - vrm.grow(); + bool CreatedNewVReg = false; + if (NewVReg == 0) { + NewVReg = RegMap->createVirtualRegister(rc); + vrm.grow(); + CreatedNewVReg = true; + } + mop.setReg(NewVReg); // Scan all of the operands of this instruction rewriting operands // to use NewVReg instead of li.reg as appropriate. We do this for @@ -725,10 +783,9 @@ rewriteInstructionForSpills(const LiveInterval &li, // // Keep track of whether we replace a use and/or def so that we can // create the spill interval with the appropriate range. - mop.setReg(NewVReg); - bool HasUse = mop.isUse(); - bool HasDef = mop.isDef(); + HasUse = mop.isUse(); + HasDef = mop.isDef(); for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { if (!MI->getOperand(j).isRegister()) continue; @@ -742,38 +799,49 @@ rewriteInstructionForSpills(const LiveInterval &li, } } - if (DefIsReMat) { - vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/); - if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) { - // Each valnum may have its own remat id. - ReMatIds[id] = vrm.assignVirtReMatId(NewVReg); + if (CreatedNewVReg) { + if (DefIsReMat) { + vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); + if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) { + // Each valnum may have its own remat id. + ReMatIds[id] = vrm.assignVirtReMatId(NewVReg); + } else { + vrm.assignVirtReMatId(NewVReg, ReMatIds[id]); + } + if (!CanDelete || (HasUse && HasDef)) { + // If this is a two-addr instruction then its use operands are + // rematerializable but its def is not. It should be assigned a + // stack slot. + vrm.assignVirt2StackSlot(NewVReg, Slot); + } } else { - vrm.assignVirtReMatId(NewVReg, ReMatIds[id]); - } - if (!CanDelete || (HasUse && HasDef)) { - // If this is a two-addr instruction then its use operands are - // rematerializable but its def is not. It should be assigned a - // stack slot. vrm.assignVirt2StackSlot(NewVReg, Slot); } - } else { - vrm.assignVirt2StackSlot(NewVReg, Slot); } // create a new register interval for this spill / remat. LiveInterval &nI = getOrCreateInterval(NewVReg); - assert(nI.empty()); - NewLIs.push_back(&nI); - - // the spill weight is now infinity as it - // cannot be spilled again - nI.weight = HUGE_VALF; + if (CreatedNewVReg) { + NewLIs.push_back(&nI); + NewVRegs[MI->getParent()->getNumber()] = NewVReg; + if (TrySplit) + vrm.setIsSplitFromReg(NewVReg, li.reg); + } if (HasUse) { - LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, - nI.getNextValue(~0U, 0, VNInfoAllocator)); - DOUT << " +" << LR; - nI.addRange(LR); + if (CreatedNewVReg) { + LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, + nI.getNextValue(~0U, 0, VNInfoAllocator)); + DOUT << " +" << LR; + nI.addRange(LR); + } else { + // Extend the split live interval to this def / use. + unsigned End = getUseIndex(index)+1; + LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, + nI.getValNumInfo(nI.getNumValNums()-1)); + DOUT << " +" << LR; + nI.addRange(LR); + } } if (HasDef) { LiveRange LR(getDefIndex(index), getStoreIndex(index), @@ -781,29 +849,57 @@ rewriteInstructionForSpills(const LiveInterval &li, DOUT << " +" << LR; nI.addRange(LR); } - - // update live variables if it is available - if (lv_) - lv_->addVirtualRegisterKilled(NewVReg, MI); - + DOUT << "\t\t\t\tAdded new interval: "; nI.print(DOUT, mri_); DOUT << '\n'; } } +bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, + MachineBasicBlock *MBB, unsigned Idx, + const VNInfo *VNI) const { + unsigned End = getMBBEndIdx(MBB); + if (VNI) { + for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { + unsigned KillIdx = VNI->kills[j]; + if (KillIdx > Idx && KillIdx < End) + return true; + } + return false; + } + + // Look at all the VNInfo's. + for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); + i != e; ++i) { + const VNInfo *VNI = *i; + for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { + unsigned KillIdx = VNI->kills[j]; + if (KillIdx > Idx && KillIdx < End) + return true; + } + } + return false; +} + void LiveIntervals:: -rewriteInstructionsForSpills(const LiveInterval &li, +rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, LiveInterval::Ranges::const_iterator &I, - MachineInstr *OrigDefMI, MachineInstr *DefMI, + MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, unsigned Slot, int LdSlot, bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc, SmallVector<int, 4> &ReMatIds, + const LoopInfo *loopInfo, + BitVector &SpillMBBs, + std::vector<std::pair<int, unsigned> > &SpillIdxes, + std::vector<unsigned> &NewVRegs, std::vector<LiveInterval*> &NewLIs) { + unsigned NewVReg = 0; unsigned index = getBaseIndex(I->start); unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; + bool TrySplitMI = TrySplit && vrm.getPreSplitReg(li.reg) == 0; for (; index != end; index += InstrSlots::NUM) { // skip deleted instructions while (index != end && !getInstructionFromIndex(index)) @@ -811,15 +907,71 @@ rewriteInstructionsForSpills(const LiveInterval &li, if (index == end) break; MachineInstr *MI = getInstructionFromIndex(index); - rewriteInstructionForSpills(li, I->valno->id, index, end, MI, - OrigDefMI, DefMI, Slot, LdSlot, isLoad, - isLoadSS, DefIsReMat, CanDelete, vrm, - RegMap, rc, ReMatIds, NewLIs); + MachineBasicBlock *MBB = MI->getParent(); + NewVReg = !TrySplitMI ? 0 : NewVRegs[MBB->getNumber()]; + bool IsNew = NewVReg == 0; + bool HasDef = false; + bool HasUse = false; + rewriteInstructionForSpills(li, TrySplitMI, I->valno->id, index, end, + MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot, + isLoad, isLoadSS, DefIsReMat, CanDelete, vrm, + RegMap, rc, ReMatIds, NewVReg, HasDef, HasUse, + loopInfo, NewVRegs, NewLIs); + if (!HasDef && !HasUse) + continue; + + // Update weight of spill interval. + LiveInterval &nI = getOrCreateInterval(NewVReg); + if (!TrySplitMI) + // The spill weight is now infinity as it cannot be spilled again. + nI.weight = HUGE_VALF; + else { + // Keep track of the last def in each MBB. + if (HasDef) { + if (MI != ReMatOrigDefMI || !CanDelete) { + // If this is a two-address code, then this index probably starts a + // VNInfo so we should examine all the VNInfo's. + bool HasKill = HasUse + ? anyKillInMBBAfterIdx(li, MBB, getDefIndex(index)) + : anyKillInMBBAfterIdx(li, MBB, getDefIndex(index), I->valno); + if (!HasKill) { + unsigned MBBId = MBB->getNumber(); + if ((int)index > SpillIdxes[MBBId].first) + // High bit specify whether this spill ought to be folded if + // possible. + SpillIdxes[MBBId] = std::make_pair(index, NewVReg | (1 << 31)); + SpillMBBs.set(MBBId); + } + } + if (!IsNew) { + // It this interval hasn't been assigned a stack slot + // (because earlier def is remat), do it now. + int SS = vrm.getStackSlot(NewVReg); + if (SS != (int)Slot) { + assert(SS == VirtRegMap::NO_STACK_SLOT); + vrm.assignVirt2StackSlot(NewVReg, Slot); + } + } + } else if (HasUse) { + // Use(s) following the last def, it's not safe to fold the spill. + unsigned MBBId = MBB->getNumber(); + if ((SpillIdxes[MBBId].second & ((1<<31)-1)) == NewVReg && + (int)getUseIndex(index) > SpillIdxes[MBBId].first) + SpillIdxes[MBBId].second &= (1<<31)-1; + } + + // Update spill weight. + unsigned loopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock()); + nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); + } } } + + std::vector<LiveInterval*> LiveIntervals:: -addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { +addIntervalsForSpills(const LiveInterval &li, + const LoopInfo *loopInfo, VirtRegMap &vrm) { // Since this is called after the analysis is done we don't know if // LiveVariables is available lv_ = getAnalysisToUpdate<LiveVariables>(); @@ -831,6 +983,11 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { li.print(DOUT, mri_); DOUT << '\n'; + // Each bit specify whether it a spill is required in the MBB. + BitVector SpillMBBs(mf_->getNumBlockIDs()); + std::vector<std::pair<int, unsigned> > SpillIdxes(mf_->getNumBlockIDs(), + std::make_pair(-1,0)); + std::vector<unsigned> NewVRegs(mf_->getNumBlockIDs(), 0); std::vector<LiveInterval*> NewLIs; SSARegMap *RegMap = mf_->getSSARegMap(); const TargetRegisterClass* rc = RegMap->getRegClass(li.reg); @@ -845,6 +1002,43 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { BitVector ReMatDelete(NumValNums); unsigned Slot = VirtRegMap::MAX_STACK_SLOT; + // Spilling a split live interval. It cannot be split any further. Also, + // it's also guaranteed to be a single val# / range interval. + if (vrm.getPreSplitReg(li.reg)) { + vrm.setIsSplitFromReg(li.reg, 0); + bool DefIsReMat = vrm.isReMaterialized(li.reg); + Slot = vrm.getStackSlot(li.reg); + assert(Slot != VirtRegMap::MAX_STACK_SLOT); + MachineInstr *ReMatDefMI = DefIsReMat ? + vrm.getReMaterializedMI(li.reg) : NULL; + int LdSlot = 0; + bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); + bool isLoad = isLoadSS || + (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); + vrm.removeAllSpillPtsForReg(li.reg); + bool IsFirstRange = true; + for (LiveInterval::Ranges::const_iterator + I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { + // If this is a split live interval with multiple ranges, it means there + // are two-address instructions that re-defined the value. Only the + // first def can be rematerialized! + if (IsFirstRange) { + rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, + Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, + false, vrm, RegMap, rc, ReMatIds, + loopInfo, SpillMBBs, SpillIdxes, NewVRegs, NewLIs); + } else { + rewriteInstructionsForSpills(li, false, I, NULL, 0, + Slot, 0, false, false, false, + false, vrm, RegMap, rc, ReMatIds, + loopInfo, SpillMBBs, SpillIdxes, NewVRegs, NewLIs); + } + IsFirstRange = false; + } + return NewLIs; + } + + bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); bool NeedStackSlot = false; for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); i != e; ++i) { @@ -854,14 +1048,15 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { if (DefIdx == ~1U) continue; // Dead val#. // Is the def for the val# rematerializable? - MachineInstr *DefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); - if (DefMI && isReMaterializable(li, VNI, DefMI)) { + MachineInstr *ReMatDefMI = (DefIdx == ~0u) + ? 0 : getInstructionFromIndex(DefIdx); + if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI)) { // Remember how to remat the def of this val#. - ReMatOrigDefs[VN] = DefMI; + ReMatOrigDefs[VN] = ReMatDefMI; // Original def may be modified so we have to make a copy here. vrm must // delete these! - ReMatDefs[VN] = DefMI = DefMI->clone(); - vrm.setVirtIsReMaterialized(li.reg, DefMI); + ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); + vrm.setVirtIsReMaterialized(li.reg, ReMatDefMI); bool CanDelete = true; for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { @@ -889,24 +1084,62 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { } // One stack slot per live interval. - if (NeedStackSlot) + if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) Slot = vrm.assignVirt2StackSlot(li.reg); + // Create new intervals and rewrite defs and uses. for (LiveInterval::Ranges::const_iterator I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { - MachineInstr *DefMI = ReMatDefs[I->valno->id]; - MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id]; - bool DefIsReMat = DefMI != NULL; + MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; + MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; + bool DefIsReMat = ReMatDefMI != NULL; bool CanDelete = ReMatDelete[I->valno->id]; int LdSlot = 0; - bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot); + bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); bool isLoad = isLoadSS || - (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); - rewriteInstructionsForSpills(li, I, OrigDefMI, DefMI, Slot, LdSlot, - isLoad, isLoadSS, DefIsReMat, CanDelete, - vrm, RegMap, rc, ReMatIds, NewLIs); + (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); + rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, + Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, + CanDelete, vrm, RegMap, rc, ReMatIds, + loopInfo, SpillMBBs, SpillIdxes, NewVRegs, NewLIs); } + // Insert spills if we are splitting. + if (TrySplit && NeedStackSlot) { + int Id = SpillMBBs.find_first(); + while (Id != -1) { + unsigned index = SpillIdxes[Id].first; + unsigned VReg = SpillIdxes[Id].second & ((1 << 31)-1); + bool TryFold = SpillIdxes[Id].second & (1 << 31); + MachineInstr *MI = getInstructionFromIndex(index); + int OpIdx = -1; + if (TryFold) { + for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { + MachineOperand &MO = MI->getOperand(j); + if (!MO.isRegister() || MO.getReg() != VReg) + continue; + if (MO.isUse()) { + // Can't fold if it's two-address code. + OpIdx = -1; + break; + } + OpIdx = (int)j; + } + } + // Fold the store into the def if possible. + if (OpIdx == -1 || + !tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx, true, Slot, VReg)) + // Else tell the spiller to issue a store for us. + vrm.addSpillPoint(VReg, MI); + Id = SpillMBBs.find_next(Id); + } + } + + // Finalize spill weights. + if (TrySplit) + for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) + NewLIs[i]->weight /= NewLIs[i]->getSize(); + return NewLIs; } diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 2af8bf3..a42011d 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -193,6 +193,7 @@ void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, } bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, + const MRegisterInfo *RegInfo, bool AddIfNotFound) { bool Found = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -224,6 +225,7 @@ bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, } bool LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI, + const MRegisterInfo *RegInfo, bool AddIfNotFound) { bool Found = false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -331,7 +333,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI, void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI, SmallSet<unsigned, 4> &SubKills) { if (SubKills.count(Reg) == 0) - addRegisterKilled(Reg, MI, true); + addRegisterKilled(Reg, MI, RegInfo, true); else { for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) @@ -342,7 +344,7 @@ void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI, bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) { SmallSet<unsigned, 4> SubKills; if (HandlePhysRegKill(Reg, RefMI, SubKills)) { - addRegisterKilled(Reg, RefMI, true); + addRegisterKilled(Reg, RefMI, RegInfo, true); return true; } else { // Some sub-registers are killed by another MI. @@ -359,15 +361,15 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { if (PhysRegUsed[Reg]) { if (!HandlePhysRegKill(Reg, LastRef)) { if (PhysRegPartUse[Reg]) - addRegisterKilled(Reg, PhysRegPartUse[Reg], true); + addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); } } else if (PhysRegPartUse[Reg]) // Add implicit use / kill to last partial use. - addRegisterKilled(Reg, PhysRegPartUse[Reg], true); + addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); else if (LastRef != MI) // Defined, but not used. However, watch out for cases where a super-reg // is also defined on the same MI. - addRegisterDead(Reg, LastRef); + addRegisterDead(Reg, LastRef, RegInfo); } for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); @@ -376,14 +378,14 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { if (PhysRegUsed[SubReg]) { if (!HandlePhysRegKill(SubReg, LastRef)) { if (PhysRegPartUse[SubReg]) - addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true); + addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); } } else if (PhysRegPartUse[SubReg]) // Add implicit use / kill to last use of a sub-register. - addRegisterKilled(SubReg, PhysRegPartUse[SubReg], true); + addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); else if (LastRef != MI) // This must be a def of the subreg on the same MI. - addRegisterDead(SubReg, LastRef); + addRegisterDead(SubReg, LastRef, RegInfo); } } @@ -561,10 +563,10 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) { if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) addRegisterDead(i + MRegisterInfo::FirstVirtualRegister, - VirtRegInfo[i].Kills[j]); + VirtRegInfo[i].Kills[j], RegInfo); else addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister, - VirtRegInfo[i].Kills[j]); + VirtRegInfo[i].Kills[j], RegInfo); } // Check to make sure there are no unreachable blocks in the MC CFG for the @@ -618,6 +620,33 @@ void LiveVariables::instructionChanged(MachineInstr *OldMI, } } +/// transferKillDeadInfo - Similar to instructionChanged except it does not +/// update live variables internal data structures. +void LiveVariables::transferKillDeadInfo(MachineInstr *OldMI, + MachineInstr *NewMI, + const MRegisterInfo *RegInfo) { + // If the instruction defines any virtual registers, update the VarInfo, + // kill and dead information for the instruction. + for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = OldMI->getOperand(i); + if (MO.isRegister() && MO.getReg() && + MRegisterInfo::isVirtualRegister(MO.getReg())) { + unsigned Reg = MO.getReg(); + if (MO.isDef()) { + if (MO.isDead()) { + MO.unsetIsDead(); + addRegisterDead(Reg, NewMI, RegInfo); + } + } + if (MO.isKill()) { + MO.unsetIsKill(); + addRegisterKilled(Reg, NewMI, RegInfo); + } + } + } +} + + /// removeVirtualRegistersKilled - Remove all killed info for the specified /// instruction. void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index bc9febf..ad9c5ec 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -16,6 +16,7 @@ #include "PhysRegTracker.h" #include "VirtRegMap.h" #include "llvm/Function.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/Passes.h" @@ -66,6 +67,7 @@ namespace { SSARegMap *regmap_; BitVector allocatableRegs_; LiveIntervals* li_; + const LoopInfo *loopInfo; /// handled_ - Intervals are added to the handled_ set in the order of their /// start value. This is uses for backtracking. @@ -101,6 +103,7 @@ namespace { // Make sure PassManager knows which analyses to make available // to coalescing and which analyses coalescing invalidates. AU.addRequiredTransitive<RegisterCoalescer>(); + AU.addRequired<LoopInfo>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -251,6 +254,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { regmap_ = mf_->getSSARegMap(); allocatableRegs_ = mri_->getAllocatableSet(fn); li_ = &getAnalysis<LiveIntervals>(); + loopInfo = &getAnalysis<LoopInfo>(); // We don't run the coalescer here because we have no reason to // interact with it. If the coalescer requires interaction, it @@ -347,18 +351,22 @@ void RALinScan::linearScan() DOUT << "\tinterval " << *i->first << " expired\n"); inactive_.clear(); - // Add live-ins to every BB except for entry. + // Add live-ins to every BB except for entry. Also perform trivial coalescing. MachineFunction::iterator EntryMBB = mf_->begin(); SmallVector<MachineBasicBlock*, 8> LiveInMBBs; for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { LiveInterval &cur = i->second; unsigned Reg = 0; - if (MRegisterInfo::isPhysicalRegister(cur.reg)) + bool isPhys = MRegisterInfo::isPhysicalRegister(cur.reg); + if (isPhys) Reg = i->second.reg; else if (vrm_->isAssignedReg(cur.reg)) Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg)); if (!Reg) continue; + // Ignore splited live intervals. + if (!isPhys && vrm_->getPreSplitReg(cur.reg)) + continue; for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end(); I != E; ++I) { const LiveRange &LR = *I; @@ -686,7 +694,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { DOUT << "\t\t\tspilling(c): " << *cur << '\n'; std::vector<LiveInterval*> added = - li_->addIntervalsForSpills(*cur, *vrm_); + li_->addIntervalsForSpills(*cur, loopInfo, *vrm_); if (added.empty()) return; // Early exit if all spills were folded. @@ -738,7 +746,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DOUT << "\t\t\tspilling(a): " << *i->first << '\n'; earliestStart = std::min(earliestStart, i->first->beginNumber()); std::vector<LiveInterval*> newIs = - li_->addIntervalsForSpills(*i->first, *vrm_); + li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(reg); } @@ -751,7 +759,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DOUT << "\t\t\tspilling(i): " << *i->first << '\n'; earliestStart = std::min(earliestStart, i->first->beginNumber()); std::vector<LiveInterval*> newIs = - li_->addIntervalsForSpills(*i->first, *vrm_); + li_->addIntervalsForSpills(*i->first, loopInfo, *vrm_); std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); spilled.insert(reg); } diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp index b919e8a..4b96cac 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.cpp +++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp @@ -1463,7 +1463,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { if (UniqueUses.count(reg) != 0) continue; LiveInterval &RegInt = li_->getInterval(reg); - RegInt.weight += li_->getSpillWeight(mop, loopDepth); + RegInt.weight += + li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth); UniqueUses.insert(reg); } } diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index bc63066..fe4f7b7 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -63,8 +63,8 @@ namespace { VirtRegMap::VirtRegMap(MachineFunction &mf) : TII(*mf.getTarget().getInstrInfo()), MF(mf), Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT), - Virt2ReMatIdMap(NO_STACK_SLOT), ReMatMap(NULL), - ReMatId(MAX_STACK_SLOT+1) { + Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0), + ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1) { grow(); } @@ -73,6 +73,8 @@ void VirtRegMap::grow() { Virt2PhysMap.grow(LastVirtReg); Virt2StackSlotMap.grow(LastVirtReg); Virt2ReMatIdMap.grow(LastVirtReg); + Virt2SplitMap.grow(LastVirtReg); + Virt2SpillPtsMap.grow(LastVirtReg); ReMatMap.grow(LastVirtReg); } @@ -278,6 +280,16 @@ namespace { AvailableSpills &Spills, BitVector &RegKills, std::vector<MachineOperand*> &KillOps, VirtRegMap &VRM); + void SpillRegToStackSlot(MachineBasicBlock &MBB, + MachineBasicBlock::iterator &MII, + int Idx, unsigned PhysReg, int StackSlot, + const TargetRegisterClass *RC, + MachineInstr *&LastStore, + AvailableSpills &Spills, + SmallSet<MachineInstr*, 4> &ReMatDefs, + BitVector &RegKills, + std::vector<MachineOperand*> &KillOps, + VirtRegMap &VRM); void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); }; } @@ -817,7 +829,8 @@ bool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB, assert(NewMIs.size() == 1); MachineInstr *NewMI = NewMIs.back(); NewMIs.clear(); - unsigned Idx = NewMI->findRegisterUseOperandIdx(VirtReg); + int Idx = NewMI->findRegisterUseOperandIdx(VirtReg); + assert(Idx != -1); MachineInstr *FoldedMI = MRI->foldMemoryOperand(NewMI, Idx, SS); if (FoldedMI) { if (!VRM.hasPhys(UnfoldVR)) @@ -847,8 +860,66 @@ static unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg, return 0; } +/// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if +/// the last store to the same slot is now dead. If so, remove the last store. +void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB, + MachineBasicBlock::iterator &MII, + int Idx, unsigned PhysReg, int StackSlot, + const TargetRegisterClass *RC, + MachineInstr *&LastStore, + AvailableSpills &Spills, + SmallSet<MachineInstr*, 4> &ReMatDefs, + BitVector &RegKills, + std::vector<MachineOperand*> &KillOps, + VirtRegMap &VRM) { + MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC); + DOUT << "Store:\t" << *next(MII); + + // If there is a dead store to this stack slot, nuke it now. + if (LastStore) { + DOUT << "Removed dead store:\t" << *LastStore; + ++NumDSE; + SmallVector<unsigned, 2> KillRegs; + InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs); + MachineBasicBlock::iterator PrevMII = LastStore; + bool CheckDef = PrevMII != MBB.begin(); + if (CheckDef) + --PrevMII; + MBB.erase(LastStore); + VRM.RemoveFromFoldedVirtMap(LastStore); + if (CheckDef) { + // Look at defs of killed registers on the store. Mark the defs + // as dead since the store has been deleted and they aren't + // being reused. + for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) { + bool HasOtherDef = false; + if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) { + MachineInstr *DeadDef = PrevMII; + if (ReMatDefs.count(DeadDef) && !HasOtherDef) { + // FIXME: This assumes a remat def does not have side + // effects. + MBB.erase(DeadDef); + VRM.RemoveFromFoldedVirtMap(DeadDef); + ++NumDRM; + } + } + } + } + } + + LastStore = next(MII); + + // If the stack slot value was previously available in some other + // register, change it now. Otherwise, make the register available, + // in PhysReg. + Spills.ModifyStackSlotOrReMat(StackSlot); + Spills.ClobberPhysReg(PhysReg); + Spills.addAvailable(StackSlot, LastStore, PhysReg); + ++NumStores; +} + /// rewriteMBB - Keep track of which spills are available even after the -/// register allocator is done with them. If possible, avoid reloading vregs. +/// register allocator is done with them. If possible, avid reloading vregs. void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { DOUT << MBB.getBasicBlock()->getName() << ":\n"; @@ -870,6 +941,10 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { // ReMatDefs - These are rematerializable def MIs which are not deleted. SmallSet<MachineInstr*, 4> ReMatDefs; + // ReloadedSplits - Splits must be reloaded once per MBB. This keeps track + // which have been reloaded. + SmallSet<unsigned, 8> ReloadedSplits; + // Keep track of kill information. BitVector RegKills(MRI->getNumRegs()); std::vector<MachineOperand*> KillOps; @@ -886,13 +961,24 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { MaybeDeadStores, Spills, RegKills, KillOps, VRM)) NextMII = next(MII); - /// ReusedOperands - Keep track of operand reuse in case we need to undo - /// reuse. MachineInstr &MI = *MII; - ReuseInfo ReusedOperands(MI, MRI); - const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); + // Insert spills here if asked to. + std::vector<unsigned> SpillRegs = VRM.getSpillPtSpills(&MI); + for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) { + unsigned VirtReg = SpillRegs[i]; + const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg); + unsigned Phys = VRM.getPhys(VirtReg); + int StackSlot = VRM.getStackSlot(VirtReg); + MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; + SpillRegToStackSlot(MBB, MII, i, Phys, StackSlot, RC, + LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM); + } + + /// ReusedOperands - Keep track of operand reuse in case we need to undo + /// reuse. + ReuseInfo ReusedOperands(MI, MRI); // Process all of the spilled uses and all non spilled reg references. for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { MachineOperand &MO = MI.getOperand(i); @@ -917,6 +1003,43 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { MF.setPhysRegUsed(Phys); if (MO.isDef()) ReusedOperands.markClobbered(Phys); + + // If it's a split live interval, insert a reload for the first use + // unless it's previously defined in the MBB. + unsigned SplitReg = VRM.getPreSplitReg(VirtReg); + if (SplitReg) { + if (ReloadedSplits.insert(VirtReg)) { + bool HasUse = MO.isUse(); + // If it's a def, we don't need to reload the value unless it's + // a two-address code. + if (!HasUse) { + for (unsigned j = i+1; j != e; ++j) { + MachineOperand &MOJ = MI.getOperand(j); + if (MOJ.isRegister() && MOJ.getReg() == VirtReg) { + HasUse = true; + break; + } + } + } + + if (HasUse) { + if (VRM.isReMaterialized(VirtReg)) { + MRI->reMaterialize(MBB, &MI, Phys, + VRM.getReMaterializedMI(VirtReg)); + ++NumReMats; + } else { + const TargetRegisterClass* RC = RegMap->getRegClass(VirtReg); + MRI->loadRegFromStackSlot(MBB, &MI, Phys, VRM.getStackSlot(VirtReg), RC); + ++NumLoads; + } + // This invalidates Phys. + Spills.ClobberPhysReg(Phys); + UpdateKills(*prior(MII), RegKills, KillOps); + DOUT << '\t' << *prior(MII); + } + } + } + unsigned RReg = SubIdx ? MRI->getSubReg(Phys, SubIdx) : Phys; MI.getOperand(i).setReg(RReg); continue; @@ -1128,6 +1251,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { DOUT << '\t' << MI; + // If we have folded references to memory operands, make sure we clear all // physical registers that may contain the value of the spilled virtual // register @@ -1136,11 +1260,16 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { unsigned VirtReg = I->second.first; VirtRegMap::ModRef MR = I->second.second; DOUT << "Folded vreg: " << VirtReg << " MR: " << MR; - if (VRM.isAssignedReg(VirtReg)) { - DOUT << ": No stack slot!\n"; - continue; - } + + // If this is a split live interval, remember we have seen this so + // we do not need to reload it for later uses. + unsigned SplitReg = VRM.getPreSplitReg(VirtReg); + if (SplitReg) + ReloadedSplits.insert(VirtReg); + int SS = VRM.getStackSlot(VirtReg); + if (SS == VirtRegMap::NO_STACK_SLOT) + continue; FoldedSS.insert(SS); DOUT << " - StackSlot: " << SS << "\n"; @@ -1338,50 +1467,9 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { MI.getOperand(i).setReg(RReg); if (!MO.isDead()) { - MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC); - DOUT << "Store:\t" << *next(MII); - - // If there is a dead store to this stack slot, nuke it now. MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; - if (LastStore) { - DOUT << "Removed dead store:\t" << *LastStore; - ++NumDSE; - SmallVector<unsigned, 2> KillRegs; - InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs); - MachineBasicBlock::iterator PrevMII = LastStore; - bool CheckDef = PrevMII != MBB.begin(); - if (CheckDef) - --PrevMII; - MBB.erase(LastStore); - VRM.RemoveFromFoldedVirtMap(LastStore); - if (CheckDef) { - // Look at defs of killed registers on the store. Mark the defs - // as dead since the store has been deleted and they aren't - // being reused. - for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) { - bool HasOtherDef = false; - if (InvalidateRegDef(PrevMII, MI, KillRegs[j], HasOtherDef)) { - MachineInstr *DeadDef = PrevMII; - if (ReMatDefs.count(DeadDef) && !HasOtherDef) { - // FIXME: This assumes a remat def does not have side - // effects. - MBB.erase(DeadDef); - VRM.RemoveFromFoldedVirtMap(DeadDef); - ++NumDRM; - } - } - } - } - } - LastStore = next(MII); - - // If the stack slot value was previously available in some other - // register, change it now. Otherwise, make the register available, - // in PhysReg. - Spills.ModifyStackSlotOrReMat(StackSlot); - Spills.ClobberPhysReg(PhysReg); - Spills.addAvailable(StackSlot, LastStore, PhysReg); - ++NumStores; + SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, LastStore, + Spills, ReMatDefs, RegKills, KillOps, VRM); // Check to see if this is a noop copy. If so, eliminate the // instruction before considering the dest reg to be changed. diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h index f6d305e..dc2f1cd 100644 --- a/lib/CodeGen/VirtRegMap.h +++ b/lib/CodeGen/VirtRegMap.h @@ -18,7 +18,7 @@ #define LLVM_CODEGEN_VIRTREGMAP_H #include "llvm/Target/MRegisterInfo.h" -#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/Support/Streams.h" #include <map> @@ -50,22 +50,42 @@ namespace llvm { /// spilled register is the temporary used to load it from the /// stack). IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; + /// Virt2StackSlotMap - This is virtual register to stack slot /// mapping. Each spilled virtual register has an entry in it /// which corresponds to the stack slot this register is spilled /// at. IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; + + /// Virt2StackSlotMap - This is virtual register to rematerialization id + /// mapping. Each spilled virtual register that should be remat'd has an + /// entry in it which corresponds to the remat id. IndexedMap<int, VirtReg2IndexFunctor> Virt2ReMatIdMap; + + /// Virt2SplitMap - This is virtual register to splitted virtual register + /// mapping. + IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap; + + /// ReMatMap - This is virtual register to re-materialized instruction + /// mapping. Each virtual register whose definition is going to be + /// re-materialized has an entry in it. + IndexedMap<MachineInstr*, VirtReg2IndexFunctor> ReMatMap; + /// MI2VirtMap - This is MachineInstr to virtual register /// mapping. In the case of memory spill code being folded into /// instructions, we need to know which virtual register was /// read/written by this instruction. MI2VirtMapTy MI2VirtMap; - /// ReMatMap - This is virtual register to re-materialized instruction - /// mapping. Each virtual register whose definition is going to be - /// re-materialized has an entry in it. - IndexedMap<MachineInstr*, VirtReg2IndexFunctor> ReMatMap; + /// SpillPt2VirtMap - This records the virtual registers which should + /// be spilled right after the MachineInstr due to live interval + /// splitting. + DenseMap<MachineInstr*, std::vector<unsigned> > SpillPt2VirtMap; + + /// Virt2SplitMap - This records the MachineInstrs where a virtual + /// register should be spilled due to live interval splitting. + IndexedMap<std::vector<MachineInstr*>, VirtReg2IndexFunctor> + Virt2SpillPtsMap; /// ReMatId - Instead of assigning a stack slot to a to be rematerialized /// virtual register, an unique id is being assigned. This keeps track of @@ -120,11 +140,25 @@ namespace llvm { grow(); } + /// @brief records virtReg is a split live interval from SReg. + void setIsSplitFromReg(unsigned virtReg, unsigned SReg) { + Virt2SplitMap[virtReg] = SReg; + } + + /// @brief returns the live interval virtReg is split from. + unsigned getPreSplitReg(unsigned virtReg) { + return Virt2SplitMap[virtReg]; + } + /// @brief returns true is the specified virtual register is not /// mapped to a stack slot or rematerialized. bool isAssignedReg(unsigned virtReg) const { - return getStackSlot(virtReg) == NO_STACK_SLOT && - getReMatId(virtReg) == NO_STACK_SLOT; + if (getStackSlot(virtReg) == NO_STACK_SLOT && + getReMatId(virtReg) == NO_STACK_SLOT) + return true; + // Split register can be assigned a physical register as well as a + // stack slot or remat id. + return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG); } /// @brief returns the stack slot mapped to the specified virtual @@ -175,6 +209,62 @@ namespace llvm { ReMatMap[virtReg] = def; } + /// @brief returns the virtual registers that should be spilled due to + /// splitting right after the specified MachineInstr. + std::vector<unsigned> &getSpillPtSpills(MachineInstr *Pt) { + return SpillPt2VirtMap[Pt]; + } + + /// @brief records the specified MachineInstr as a spill point for virtReg. + void addSpillPoint(unsigned virtReg, MachineInstr *Pt) { + SpillPt2VirtMap[Pt].push_back(virtReg); + Virt2SpillPtsMap[virtReg].push_back(Pt); + } + + /// @brief remove the virtReg from the list of registers that should be + /// spilled (due to splitting) right after the specified MachineInstr. + void removeRegFromSpillPt(MachineInstr *Pt, unsigned virtReg) { + std::vector<unsigned> &Regs = SpillPt2VirtMap[Pt]; + if (Regs.back() == virtReg) // Most common case. + Regs.pop_back(); + for (unsigned i = 0, e = Regs.size(); i != e; ++i) + if (Regs[i] == virtReg) { + Regs.erase(Regs.begin()+i-1); + break; + } + } + + /// @brief specify virtReg is no longer being spilled due to splitting. + void removeAllSpillPtsForReg(unsigned virtReg) { + std::vector<MachineInstr*> &SpillPts = Virt2SpillPtsMap[virtReg]; + for (unsigned i = 0, e = SpillPts.size(); i != e; ++i) + removeRegFromSpillPt(SpillPts[i], virtReg); + Virt2SpillPtsMap[virtReg].clear(); + } + + /// @brief remove the specified MachineInstr as a spill point for the + /// specified register. + void removeRegSpillPt(unsigned virtReg, MachineInstr *Pt) { + std::vector<MachineInstr*> &SpillPts = Virt2SpillPtsMap[virtReg]; + if (SpillPts.back() == Pt) // Most common case. + SpillPts.pop_back(); + for (unsigned i = 0, e = SpillPts.size(); i != e; ++i) + if (SpillPts[i] == Pt) { + SpillPts.erase(SpillPts.begin()+i-1); + break; + } + } + + void transferSpillPts(MachineInstr *Old, MachineInstr *New) { + std::vector<unsigned> &OldRegs = SpillPt2VirtMap[Old]; + while (!OldRegs.empty()) { + unsigned virtReg = OldRegs.back(); + OldRegs.pop_back(); + removeRegSpillPt(virtReg, Old); + addSpillPoint(virtReg, New); + } + } + /// @brief Updates information about the specified virtual register's value /// folded into newMI machine instruction. The OpNum argument indicates the /// operand number of OldMI that is folded. |