aboutsummaryrefslogtreecommitdiff
path: root/lib/CodeGen/LiveIntervalAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/LiveIntervalAnalysis.cpp')
-rw-r--r--lib/CodeGen/LiveIntervalAnalysis.cpp349
1 files changed, 236 insertions, 113 deletions
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index ebf3c57230..bd8137730b 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -30,7 +30,6 @@
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
@@ -60,6 +59,8 @@ void LiveIntervals::releaseMemory() {
mi2iMap_.clear();
i2miMap_.clear();
r2iMap_.clear();
+ for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
+ delete ClonedMIs[i];
}
/// runOnMachineFunction - Register allocate the whole function
@@ -74,13 +75,12 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
// Number MachineInstrs and MachineBasicBlocks.
// Initialize MBB indexes to a sentinal.
- MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U);
+ MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
unsigned MIIndex = 0;
for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
MBB != E; ++MBB) {
- // Set the MBB2IdxMap entry for this MBB.
- MBB2IdxMap[MBB->getNumber()] = MIIndex;
+ unsigned StartIdx = MIIndex;
for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
I != E; ++I) {
@@ -89,6 +89,9 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
i2miMap_.push_back(I);
MIIndex += InstrSlots::NUM;
}
+
+ // Set the MBB2IdxMap entry for this MBB.
+ MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
}
computeIntervals();
@@ -175,8 +178,76 @@ LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI,
return NewLI;
}
+/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to
+/// two addr elimination.
+static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg,
+ const TargetInstrInfo *TII) {
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ MachineOperand &MO1 = MI->getOperand(i);
+ if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
+ for (unsigned j = i+1; j < e; ++j) {
+ MachineOperand &MO2 = MI->getOperand(j);
+ if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
+ MI->getInstrDescriptor()->
+ getOperandConstraint(j, TOI::TIED_TO) == (int)i)
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+/// isReMaterializable - Returns true if the definition MI of the specified
+/// val# of the specified interval is re-materializable.
+bool LiveIntervals::isReMaterializable(const LiveInterval &li, unsigned ValNum,
+ MachineInstr *MI) {
+ if (tii_->isTriviallyReMaterializable(MI))
+ return true;
+
+ int FrameIdx = 0;
+ if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
+ !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
+ return false;
+
+ // This is a load from fixed stack slot. It can be rematerialized unless it's
+ // re-defined by a two-address instruction.
+ for (unsigned i = 0, e = li.getNumValNums(); i != e; ++i) {
+ if (i == ValNum)
+ continue;
+ unsigned DefIdx = li.getDefForValNum(i);
+ if (DefIdx == ~1U)
+ continue; // Dead val#.
+ MachineInstr *DefMI = (DefIdx == ~0u)
+ ? NULL : getInstructionFromIndex(DefIdx);
+ if (DefMI && isReDefinedByTwoAddr(DefMI, li.reg, tii_))
+ return false;
+ }
+ return true;
+}
+
+bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
+ unsigned index, unsigned i,
+ int slot, unsigned reg) {
+ MachineInstr *fmi = mri_->foldMemoryOperand(MI, i, slot);
+ if (fmi) {
+ // Attempt to fold the memory reference into the instruction. If
+ // we can do this, we don't need to insert spill code.
+ if (lv_)
+ lv_->instructionChanged(MI, fmi);
+ MachineBasicBlock &MBB = *MI->getParent();
+ vrm.virtFolded(reg, MI, i, fmi);
+ mi2iMap_.erase(MI);
+ i2miMap_[index/InstrSlots::NUM] = fmi;
+ mi2iMap_[fmi] = index;
+ MI = MBB.insert(MBB.erase(MI), fmi);
+ ++numFolded;
+ return true;
+ }
+ return false;
+}
+
std::vector<LiveInterval*> LiveIntervals::
-addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
+addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
// since this is called after the analysis is done we don't know if
// LiveVariables is available
lv_ = getAnalysisToUpdate<LiveVariables>();
@@ -192,10 +263,72 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
+ unsigned NumValNums = li.getNumValNums();
+ SmallVector<MachineInstr*, 4> ReMatDefs;
+ ReMatDefs.resize(NumValNums, NULL);
+ SmallVector<MachineInstr*, 4> ReMatOrigDefs;
+ ReMatOrigDefs.resize(NumValNums, NULL);
+ SmallVector<int, 4> ReMatIds;
+ ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
+ BitVector ReMatDelete(NumValNums);
+ unsigned slot = VirtRegMap::MAX_STACK_SLOT;
+
+ bool NeedStackSlot = false;
+ for (unsigned i = 0; i != NumValNums; ++i) {
+ unsigned DefIdx = li.getDefForValNum(i);
+ if (DefIdx == ~1U)
+ continue; // Dead val#.
+ // Is the def for the val# rematerializable?
+ MachineInstr *DefMI = (DefIdx == ~0u)
+ ? NULL : getInstructionFromIndex(DefIdx);
+ if (DefMI && isReMaterializable(li, i, DefMI)) {
+ // Remember how to remat the def of this val#.
+ ReMatOrigDefs[i] = DefMI;
+ // Original def may be modified so we have to make a copy here. vrm must
+ // delete these!
+ ReMatDefs[i] = DefMI = DefMI->clone();
+ vrm.setVirtIsReMaterialized(reg, DefMI);
+
+ bool CanDelete = true;
+ const SmallVector<unsigned, 4> &kills = li.getKillsForValNum(i);
+ for (unsigned j = 0, ee = kills.size(); j != ee; ++j) {
+ unsigned KillIdx = kills[j];
+ MachineInstr *KillMI = (KillIdx & 1)
+ ? NULL : getInstructionFromIndex(KillIdx);
+ // Kill is a phi node, not all of its uses can be rematerialized.
+ // It must not be deleted.
+ if (!KillMI) {
+ CanDelete = false;
+ // Need a stack slot if there is any live range where uses cannot be
+ // rematerialized.
+ NeedStackSlot = true;
+ break;
+ }
+ }
+
+ if (CanDelete)
+ ReMatDelete.set(i);
+ } else {
+ // Need a stack slot if there is any live range where uses cannot be
+ // rematerialized.
+ NeedStackSlot = true;
+ }
+ }
+
+ // One stack slot per live interval.
+ if (NeedStackSlot)
+ slot = vrm.assignVirt2StackSlot(reg);
+
for (LiveInterval::Ranges::const_iterator
- i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
- unsigned index = getBaseIndex(i->start);
- unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM;
+ I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
+ MachineInstr *DefMI = ReMatDefs[I->ValId];
+ MachineInstr *OrigDefMI = ReMatOrigDefs[I->ValId];
+ bool DefIsReMat = DefMI != NULL;
+ bool CanDelete = ReMatDelete[I->ValId];
+ int LdSlot = 0;
+ bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot);
+ unsigned index = getBaseIndex(I->start);
+ unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
for (; index != end; index += InstrSlots::NUM) {
// skip deleted instructions
while (index != end && !getInstructionFromIndex(index))
@@ -208,87 +341,109 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
MachineOperand& mop = MI->getOperand(i);
if (mop.isRegister() && mop.getReg() == li.reg) {
- MachineInstr *fmi = li.remat ? NULL
- : mri_->foldMemoryOperand(MI, i, slot);
- if (fmi) {
- // Attempt to fold the memory reference into the instruction. If we
- // can do this, we don't need to insert spill code.
- if (lv_)
- lv_->instructionChanged(MI, fmi);
- MachineBasicBlock &MBB = *MI->getParent();
- vrm.virtFolded(li.reg, MI, i, fmi);
- mi2iMap_.erase(MI);
- i2miMap_[index/InstrSlots::NUM] = fmi;
- mi2iMap_[fmi] = index;
- MI = MBB.insert(MBB.erase(MI), fmi);
- ++numFolded;
- // Folding the load/store can completely change the instruction in
- // unpredictable ways, rescan it from the beginning.
- goto RestartInstruction;
+ if (DefIsReMat) {
+ // If this is the rematerializable definition MI itself and
+ // all of its uses are rematerialized, simply delete it.
+ if (MI == OrigDefMI) {
+ if (CanDelete) {
+ RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ break;
+ } else if (tryFoldMemoryOperand(MI, vrm, index, i, slot, li.reg))
+ // Folding the load/store can completely change the instruction
+ // in unpredictable ways, rescan it from the beginning.
+ goto RestartInstruction;
+ } else if (isLoadSS &&
+ tryFoldMemoryOperand(MI, vrm, index, i, LdSlot, li.reg)){
+ // FIXME: Other rematerializable loads can be folded as well.
+ // Folding the load/store can completely change the
+ // instruction in unpredictable ways, rescan it from
+ // the beginning.
+ goto RestartInstruction;
+ }
} else {
- // Create a new virtual register for the spill interval.
- unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc);
+ if (tryFoldMemoryOperand(MI, vrm, index, i, slot, li.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 = mf_->getSSARegMap()->createVirtualRegister(rc);
- // Scan all of the operands of this instruction rewriting operands
- // to use NewVReg instead of li.reg as appropriate. We do this for
- // two reasons:
- //
- // 1. If the instr reads the same spilled vreg multiple times, we
- // want to reuse the NewVReg.
- // 2. If the instr is a two-addr instruction, we are required to
- // 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.
- 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
+ // two reasons:
+ //
+ // 1. If the instr reads the same spilled vreg multiple times, we
+ // want to reuse the NewVReg.
+ // 2. If the instr is a two-addr instruction, we are required to
+ // 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.
+ mop.setReg(NewVReg);
- bool HasUse = mop.isUse();
- bool HasDef = mop.isDef();
- for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
- if (MI->getOperand(j).isReg() &&
- MI->getOperand(j).getReg() == li.reg) {
- MI->getOperand(j).setReg(NewVReg);
- HasUse |= MI->getOperand(j).isUse();
- HasDef |= MI->getOperand(j).isDef();
- }
+ bool HasUse = mop.isUse();
+ bool HasDef = mop.isDef();
+ for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
+ if (MI->getOperand(j).isReg() &&
+ MI->getOperand(j).getReg() == li.reg) {
+ MI->getOperand(j).setReg(NewVReg);
+ HasUse |= MI->getOperand(j).isUse();
+ HasDef |= MI->getOperand(j).isDef();
}
+ }
- // create a new register for this spill
- vrm.grow();
- if (li.remat)
- vrm.setVirtIsReMaterialized(NewVReg, li.remat);
- vrm.assignVirt2StackSlot(NewVReg, slot);
- LiveInterval &nI = getOrCreateInterval(NewVReg);
- nI.remat = li.remat;
- assert(nI.empty());
-
- // the spill weight is now infinity as it
- // cannot be spilled again
- nI.weight = HUGE_VALF;
-
- if (HasUse) {
- LiveRange LR(getLoadIndex(index), getUseIndex(index),
- nI.getNextValue(~0U, 0));
- DOUT << " +" << LR;
- nI.addRange(LR);
+ vrm.grow();
+ if (DefIsReMat) {
+ vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
+ if (ReMatIds[I->ValId] == VirtRegMap::MAX_STACK_SLOT) {
+ // Each valnum may have its own remat id.
+ ReMatIds[I->ValId] = vrm.assignVirtReMatId(NewVReg);
+ } else {
+ vrm.assignVirtReMatId(NewVReg, ReMatIds[I->ValId]);
}
- if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(~0U, 0));
- DOUT << " +" << LR;
- nI.addRange(LR);
+ 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());
+
+ // the spill weight is now infinity as it
+ // cannot be spilled again
+ nI.weight = HUGE_VALF;
+
+ if (HasUse) {
+ LiveRange LR(getLoadIndex(index), getUseIndex(index),
+ nI.getNextValue(~0U, 0));
+ DOUT << " +" << LR;
+ nI.addRange(LR);
+ }
+ if (HasDef) {
+ LiveRange LR(getDefIndex(index), getStoreIndex(index),
+ nI.getNextValue(~0U, 0));
+ DOUT << " +" << LR;
+ nI.addRange(LR);
+ }
- added.push_back(&nI);
+ added.push_back(&nI);
- // update live variables if it is available
- if (lv_)
- lv_->addVirtualRegisterKilled(NewVReg, MI);
+ // 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';
- }
+ DOUT << "\t\t\t\tadded new interval: ";
+ nI.print(DOUT, mri_);
+ DOUT << '\n';
}
}
}
@@ -304,25 +459,6 @@ void LiveIntervals::printRegName(unsigned reg) const {
cerr << "%reg" << reg;
}
-/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to
-/// two addr elimination.
-static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg,
- const TargetInstrInfo *TII) {
- for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
- MachineOperand &MO1 = MI->getOperand(i);
- if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
- for (unsigned j = i+1; j < e; ++j) {
- MachineOperand &MO2 = MI->getOperand(j);
- if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
- MI->getInstrDescriptor()->
- getOperandConstraint(j, TOI::TIED_TO) == (int)i)
- return true;
- }
- }
- }
- return false;
-}
-
void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
MachineBasicBlock::iterator mi,
unsigned MIIdx,
@@ -335,16 +471,6 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
// done once for the vreg. We use an empty interval to detect the first
// time we see a vreg.
if (interval.empty()) {
- // Remember if the definition can be rematerialized. All load's from fixed
- // stack slots are re-materializable. The target may permit other
- // instructions to be re-materialized as well.
- int FrameIdx = 0;
- if (vi.DefInst &&
- (tii_->isTriviallyReMaterializable(vi.DefInst) ||
- (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) &&
- mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))))
- interval.remat = vi.DefInst;
-
// Get the Idx of the defining instructions.
unsigned defIndex = getDefIndex(MIIdx);
unsigned ValNum;
@@ -421,9 +547,6 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
}
} else {
- // Can no longer safely assume definition is rematerializable.
- interval.remat = NULL;
-
// 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
@@ -487,7 +610,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
DOUT << " Removing [" << Start << "," << End << "] from: ";
interval.print(DOUT, mri_); DOUT << "\n";
interval.removeRange(Start, End);
- interval.addKillForValNum(0, Start);
+ interval.addKillForValNum(0, Start-1); // odd # means phi node
DOUT << " RESULT: "; interval.print(DOUT, mri_);
// Replace the interval with one of a NEW value number. Note that this
@@ -514,7 +637,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
LiveRange LR(defIndex, killIndex, ValNum);
interval.addRange(LR);
- interval.addKillForValNum(ValNum, killIndex);
+ interval.addKillForValNum(ValNum, killIndex-1); // odd # means phi node
DOUT << " +" << LR;
}
}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-04 19:56:44 +0000