aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/LiveInterval.h18
-rw-r--r--include/llvm/CodeGen/LiveIntervalAnalysis.h9
-rw-r--r--include/llvm/CodeGen/MachineInstr.h4
-rw-r--r--include/llvm/CodeGen/SSARegMap.h19
-rw-r--r--include/llvm/CodeGen/SimpleRegisterCoalescing.h4
-rw-r--r--lib/CodeGen/LiveInterval.cpp37
-rw-r--r--lib/CodeGen/LiveIntervalAnalysis.cpp300
-rw-r--r--lib/CodeGen/MachineInstr.cpp18
-rw-r--r--lib/CodeGen/SelectionDAG/ScheduleDAG.cpp3
-rw-r--r--lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp13
-rw-r--r--lib/CodeGen/SimpleRegisterCoalescing.cpp123
-rw-r--r--lib/CodeGen/VirtRegMap.cpp108
12 files changed, 415 insertions, 241 deletions
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 50ac158590..34e53a9a67 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -155,7 +155,7 @@ namespace llvm {
/// copyValNumInfo - Copy the value number info for one value number to
/// another.
- void copyValNumInfo(VNInfo *DstValNo, VNInfo *SrcValNo) {
+ void copyValNumInfo(VNInfo *DstValNo, const VNInfo *SrcValNo) {
DstValNo->def = SrcValNo->def;
DstValNo->reg = SrcValNo->reg;
DstValNo->kills = SrcValNo->kills;
@@ -241,11 +241,23 @@ namespace llvm {
void MergeInClobberRanges(const LiveInterval &Clobbers,
BumpPtrAllocator &VNInfoAllocator);
- /// MergeRangesInAsValue - Merge all of the intervals in RHS into this live
- /// interval as the specified value number. The LiveRanges in RHS are
+ /// MergeRangesInAsValue - Merge all of the live ranges in RHS into this
+ /// live interval as the specified value number. The LiveRanges in RHS are
/// allowed to overlap with LiveRanges in the current interval, but only if
/// the overlapping LiveRanges have the specified value number.
void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo);
+
+ /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+ /// in RHS into this live interval as the specified value number.
+ /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
+ /// current interval, but only if the overlapping LiveRanges have the
+ /// specified value number.
+ void MergeValueInAsValue(const LiveInterval &RHS,
+ VNInfo *RHSValNo, VNInfo *LHSValNo);
+
+ /// Copy - Copy the specified live interval. This copies all the fields
+ /// except for the register of the interval.
+ void Copy(const LiveInterval &RHS, BumpPtrAllocator &VNInfoAllocator);
bool empty() const { return ranges.empty(); }
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 671de02eee..bf0a8295d5 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -167,11 +167,6 @@ namespace llvm {
return I->second;
}
- /// CreateNewLiveInterval - Create a new live interval with the given live
- /// ranges. The new live interval will have an infinite spill weight.
- LiveInterval &CreateNewLiveInterval(const LiveInterval *LI,
- const std::vector<LiveRange> &LRs);
-
std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
VirtRegMap& vrm, unsigned reg);
@@ -254,8 +249,8 @@ namespace llvm {
/// MI. If it is successul, MI is updated with the newly created MI and
/// returns true.
bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
- unsigned index, unsigned i, bool isSS,
- MachineInstr *DefMI, int slot, unsigned reg);
+ MachineInstr *DefMI, unsigned index, unsigned i,
+ bool isSS, int slot, unsigned reg);
static LiveInterval createInterval(unsigned Reg);
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 3dbda8dc78..beba6923ee 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -418,6 +418,10 @@ public:
/// none is found.
int findFirstPredOperandIdx() const;
+ /// isRegReDefinedByTwoAddr - Returns true if the Reg re-definition is due
+ /// to two addr elimination.
+ bool isRegReDefinedByTwoAddr(unsigned Reg) const;
+
/// copyKillDeadInfo - Copies kill / dead operand properties from MI.
///
void copyKillDeadInfo(const MachineInstr *MI);
diff --git a/include/llvm/CodeGen/SSARegMap.h b/include/llvm/CodeGen/SSARegMap.h
index 97d8d6988c..a92222a5c3 100644
--- a/include/llvm/CodeGen/SSARegMap.h
+++ b/include/llvm/CodeGen/SSARegMap.h
@@ -26,6 +26,7 @@ class TargetRegisterClass;
class SSARegMap {
IndexedMap<const TargetRegisterClass*, VirtReg2IndexFunctor> RegClassMap;
+ IndexedMap<std::pair<unsigned, unsigned>, VirtReg2IndexFunctor> RegSubIdxMap;
unsigned NextRegNum;
public:
@@ -42,12 +43,30 @@ class SSARegMap {
assert(RegClass && "Cannot create register without RegClass!");
RegClassMap.grow(NextRegNum);
RegClassMap[NextRegNum] = RegClass;
+ RegSubIdxMap.grow(NextRegNum);
+ RegSubIdxMap[NextRegNum] = std::make_pair(0,0);
return NextRegNum++;
}
unsigned getLastVirtReg() const {
return NextRegNum - 1;
}
+
+ void setIsSubRegister(unsigned Reg, unsigned SuperReg, unsigned SubIdx) {
+ RegSubIdxMap[Reg] = std::make_pair(SuperReg, SubIdx);
+ }
+
+ bool isSubRegister(unsigned Reg) const {
+ return RegSubIdxMap[Reg].first != 0;
+ }
+
+ unsigned getSuperRegister(unsigned Reg) const {
+ return RegSubIdxMap[Reg].first;
+ }
+
+ unsigned getSubRegisterIndex(unsigned Reg) const {
+ return RegSubIdxMap[Reg].second;
+ }
};
} // End llvm namespace
diff --git a/include/llvm/CodeGen/SimpleRegisterCoalescing.h b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
index 4e760815b9..00095dd176 100644
--- a/include/llvm/CodeGen/SimpleRegisterCoalescing.h
+++ b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
@@ -47,6 +47,10 @@ namespace llvm {
/// with other intervals.
BitVector JoinedLIs;
+ /// SubRegIdxes - Keep track of sub-register and sub-indexes.
+ ///
+ std::vector<std::pair<unsigned, unsigned> > SubRegIdxes;
+
public:
static char ID; // Pass identifcation, replacement for typeid
SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index f205d0c5e2..b2f7d7fe13 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -383,6 +383,26 @@ void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
}
+/// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+/// in RHS into this live interval as the specified value number.
+/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
+/// current interval, but only if the overlapping LiveRanges have the
+/// specified value number.
+void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
+ VNInfo *RHSValNo, VNInfo *LHSValNo) {
+ // TODO: Make this more efficient.
+ iterator InsertPos = begin();
+ for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
+ if (I->valno != RHSValNo)
+ continue;
+ // Map the valno in the other live range to the current live range.
+ LiveRange Tmp = *I;
+ Tmp.valno = LHSValNo;
+ InsertPos = addRangeFrom(Tmp, InsertPos);
+ }
+}
+
+
/// MergeInClobberRanges - For any live ranges that are not defined in the
/// current interval, but are defined in the Clobbers interval, mark them
/// used with an unknown definition value.
@@ -485,6 +505,23 @@ void LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
}
}
+void LiveInterval::Copy(const LiveInterval &RHS,
+ BumpPtrAllocator &VNInfoAllocator) {
+ ranges.clear();
+ valnos.clear();
+ preference = RHS.preference;
+ weight = RHS.weight;
+ for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
+ const VNInfo *VNI = RHS.getValNumInfo(i);
+ VNInfo *NewVNI = getNextValue(~0U, 0, VNInfoAllocator);
+ copyValNumInfo(NewVNI, VNI);
+ }
+ for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
+ const LiveRange &LR = RHS.ranges[i];
+ addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
+ }
+}
+
unsigned LiveInterval::getSize() const {
unsigned Sum = 0;
for (const_iterator I = begin(), E = end(); I != E; ++I)
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 5ada75ca01..5ed24a3be2 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -136,75 +136,6 @@ void LiveIntervals::print(std::ostream &O, const Module* ) const {
}
}
-// Not called?
-/// CreateNewLiveInterval - Create a new live interval with the given live
-/// ranges. The new live interval will have an infinite spill weight.
-LiveInterval&
-LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI,
- const std::vector<LiveRange> &LRs) {
- const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg);
-
- // Create a new virtual register for the spill interval.
- unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC);
-
- // Replace the old virtual registers in the machine operands with the shiny
- // new one.
- for (std::vector<LiveRange>::const_iterator
- I = LRs.begin(), E = LRs.end(); I != E; ++I) {
- 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))
- Index += InstrSlots::NUM;
-
- if (Index == End) break;
-
- MachineInstr *MI = getInstructionFromIndex(Index);
-
- for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) {
- MachineOperand &MOp = MI->getOperand(J);
- if (MOp.isRegister() && MOp.getReg() == LI->reg)
- MOp.setReg(NewVReg);
- }
- }
- }
-
- LiveInterval &NewLI = getOrCreateInterval(NewVReg);
-
- // The spill weight is now infinity as it cannot be spilled again
- NewLI.weight = float(HUGE_VAL);
-
- for (std::vector<LiveRange>::const_iterator
- I = LRs.begin(), E = LRs.end(); I != E; ++I) {
- DOUT << " Adding live range " << *I << " to new interval\n";
- NewLI.addRange(*I);
- }
-
- DOUT << "Created new live interval " << NewLI << "\n";
- 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,
@@ -232,7 +163,7 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
continue; // Dead val#.
MachineInstr *DefMI = (DefIdx == ~0u)
? NULL : getInstructionFromIndex(DefIdx);
- if (DefMI && isReDefinedByTwoAddr(DefMI, li.reg, tii_))
+ if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
return false;
}
return true;
@@ -243,9 +174,9 @@ bool LiveIntervals::isReMaterializable(const LiveInterval &li,
/// MI. If it is successul, MI is updated with the newly created MI and
/// returns true.
bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
+ MachineInstr *DefMI,
unsigned index, unsigned i,
- bool isSS, MachineInstr *DefMI,
- int slot, unsigned reg) {
+ bool isSS, int slot, unsigned reg) {
MachineInstr *fmi = isSS
? mri_->foldMemoryOperand(MI, i, slot)
: mri_->foldMemoryOperand(MI, i, DefMI);
@@ -281,7 +212,8 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
li.print(DOUT, mri_);
DOUT << '\n';
- const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
+ SSARegMap *RegMap = mf_->getSSARegMap();
+ const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
unsigned NumValNums = li.getNumValNums();
SmallVector<MachineInstr*, 4> ReMatDefs;
@@ -364,113 +296,126 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
RestartInstruction:
for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
MachineOperand& mop = MI->getOperand(i);
- if (mop.isRegister() && mop.getReg() == li.reg) {
- 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, true,
- DefMI, slot, li.reg)) {
- // Folding the load/store can completely change the instruction
- // in unpredictable ways, rescan it from the beginning.
- goto RestartInstruction;
- }
- } else if (isLoad &&
- tryFoldMemoryOperand(MI, vrm, index, i, isLoadSS,
- DefMI, LdSlot, li.reg))
- // Folding the load/store can completely change the
- // instruction in unpredictable ways, rescan it from
- // the beginning.
- goto RestartInstruction;
- } else {
- if (tryFoldMemoryOperand(MI, vrm, index, i, true, DefMI,
- slot, li.reg))
- // Folding the load/store can completely change the instruction in
- // unpredictable ways, rescan it from the beginning.
- goto RestartInstruction;
+ if (!mop.isRegister())
+ continue;
+ unsigned Reg = mop.getReg();
+ if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
+ continue;
+ bool isSubReg = RegMap->isSubRegister(Reg);
+ unsigned SubIdx = 0;
+ if (isSubReg) {
+ SubIdx = RegMap->getSubRegisterIndex(Reg);
+ Reg = RegMap->getSuperRegister(Reg);
+ }
+ if (Reg != li.reg)
+ continue;
+
+ bool TryFold = !DefIsReMat;
+ bool FoldSS = true;
+ int FoldSlot = slot;
+ if (DefIsReMat) {
+ // If this is the rematerializable definition MI itself and
+ // all of its uses are rematerialized, simply delete it.
+ if (MI == OrigDefMI && CanDelete) {
+ RemoveMachineInstrFromMaps(MI);
+ MI->eraseFromParent();
+ break;
}
- // Create a new virtual register for the spill interval.
- unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc);
+ // If def for this use can't be rematerialized, then try folding.
+ TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad));
+ if (isLoad) {
+ // Try fold loads (from stack slot, constant pool, etc.) into uses.
+ FoldSS = isLoadSS;
+ FoldSlot = LdSlot;
+ }
+ }
+
+ // FIXME: fold subreg use
+ if (!isSubReg && TryFold &&
+ tryFoldMemoryOperand(MI, vrm, DefMI, 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);
+ if (isSubReg)
+ RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx);
- // 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).isRegister() &&
- 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).isRegister() &&
+ MI->getOperand(j).getReg() == li.reg) {
+ MI->getOperand(j).setReg(NewVReg);
+ HasUse |= MI->getOperand(j).isUse();
+ HasDef |= MI->getOperand(j).isDef();
}
+ }
- vrm.grow();
- if (DefIsReMat) {
- vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
- if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
- // Each valnum may have its own remat id.
- ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
- } else {
- vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->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);
- }
+ vrm.grow();
+ if (DefIsReMat) {
+ vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
+ if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
+ // Each valnum may have its own remat id.
+ ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
} else {
+ vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->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());
+ // 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;
+ // the spill weight is now infinity as it
+ // cannot be spilled again
+ nI.weight = HUGE_VALF;
- if (HasUse) {
- LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
- nI.getNextValue(~0U, 0, VNInfoAllocator));
- DOUT << " +" << LR;
- nI.addRange(LR);
- }
- if (HasDef) {
- LiveRange LR(getDefIndex(index), getStoreIndex(index),
- nI.getNextValue(~0U, 0, VNInfoAllocator));
- DOUT << " +" << LR;
- nI.addRange(LR);
- }
+ if (HasUse) {
+ LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
+ DOUT << " +" << LR;
+ nI.addRange(LR);
+ }
+ if (HasDef) {
+ LiveRange LR(getDefIndex(index), getStoreIndex(index),
+ nI.getNextValue(~0U, 0, VNInfoAllocator));
+ 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';
}
}
}
@@ -501,10 +446,14 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
unsigned defIndex = getDefIndex(MIIdx);
VNInfo *ValNo;
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
- else
+ if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
+ else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
+ mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
+ ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
+ VNInfoAllocator);
+ else
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
assert(ValNo->id == 0 && "First value in interval is not 0?");
@@ -576,7 +525,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
// 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 (isReDefinedByTwoAddr(mi, interval.reg, tii_)) {
+ if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
// 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
@@ -656,10 +605,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
VNInfo *ValNo;
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
- ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
- else
+ if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
+ else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+ ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
+ VNInfoAllocator);
+ else
+ ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
LiveRange LR(defIndex, killIndex, ValNo);
@@ -741,7 +693,9 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
else if (allocatableRegs_[reg]) {
unsigned SrcReg, DstReg;
- if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
+ if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
+ SrcReg = MI->getOperand(1).getReg();
+ else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
SrcReg = 0;
handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
// Def of a register also defines its sub-registers.
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 1634c7880e..1ac955a743 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -220,6 +220,24 @@ int MachineInstr::findFirstPredOperandIdx() const {
return -1;
}
+/// isRegReDefinedByTwoAddr - Returns true if the Reg re-definition is due
+/// to two addr elimination.
+bool MachineInstr::isRegReDefinedByTwoAddr(unsigned Reg) const {
+ const TargetInstrDescriptor *TID = getInstrDescriptor();
+ for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO1 = getOperand(i);
+ if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
+ for (unsigned j = i+1; j < e; ++j) {
+ const MachineOperand &MO2 = getOperand(j);
+ if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
+ TID->getOperandConstraint(j, TOI::TIED_TO) == (int)i)
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
/// copyKillDeadInfo - Copies kill / dead operand properties from MI.
///
void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) {
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index b616b7e482..bb5379c349 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -567,9 +567,6 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
// TODO: If the node is a use of a CopyFromReg from a physical register
// fold the extract into the copy now
- // TODO: Add tracking info to SSARegMap of which vregs are subregs
- // to allow coalescing in the allocator
-
// Create the extract_subreg machine instruction.
MachineInstr *MI =
new MachineInstr(BB, TII->get(TargetInstrInfo::EXTRACT_SUBREG));
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index c1a8509615..2baf24d7d5 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -1097,6 +1097,11 @@ namespace {
// CopyToReg should be close to its uses to facilitate coalescing and
// avoid spilling.
return 0;
+ else if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
+ Opc == TargetInstrInfo::INSERT_SUBREG)
+ // EXTRACT_SUBREG / INSERT_SUBREG should be close to its use to
+ // facilitate coalescing.
+ return 0;
else if (SU->NumSuccs == 0)
// If SU does not have a use, i.e. it doesn't produce a value that would
// be consumed (e.g. store), then it terminates a chain of computation.
@@ -1308,6 +1313,14 @@ void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
// Be conservative. Ignore if nodes aren't at the same depth.
if (SuccSU->Depth != SU->Depth)
continue;
+ if (!SuccSU->Node || !SuccSU->Node->isTargetOpcode())
+ continue;
+ // Don't constraint extract_subreg / insert_subreg these may be
+ // coalesced away. We don't them close to their uses.
+ unsigned SuccOpc = SuccSU->Node->getTargetOpcode();
+ if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
+ SuccOpc == TargetInstrInfo::INSERT_SUBREG)
+ continue;
if ((!canClobber(SuccSU, DUSU) ||
(hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
(!SU->isCommutable && SuccSU->isCommutable)) &&
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 59e9e4501a..9d43750f1c 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -226,11 +226,55 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
DOUT << "\tDst reg is unallocatable physreg.\n";
return true; // Not coalescable.
}
-
- // If they are not of the same register class, we cannot join them.
- if (differingRegisterClasses(repSrcReg, repDstReg)) {
+
+ bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG;
+ unsigned RealDstReg = 0;
+ if (isExtSubReg) {
+ unsigned SubIdx = CopyMI->getOperand(2).getImm();
+ if (SrcIsPhys)
+ // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be
+ // coalesced with AX.
+ repSrcReg = mri_->getSubReg(repSrcReg, SubIdx);
+ else if (DstIsPhys) {
+ // If this is a extract_subreg where dst is a physical register, e.g.
+ // cl = EXTRACT_SUBREG reg1024, 1
+ // then create and update the actual physical register allocated to RHS.
+ const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(SrcReg);
+ for (const unsigned *SRs = mri_->getSuperRegisters(repDstReg);
+ unsigned SR = *SRs; ++SRs) {
+ if (repDstReg == mri_->getSubReg(SR, SubIdx) &&
+ RC->contains(SR)) {
+ RealDstReg = SR;
+ break;
+ }
+ }
+ assert(RealDstReg && "Invalid extra_subreg instruction!");
+
+ // For this type of EXTRACT_SUBREG, conservatively
+ // check if the live interval of the source register interfere with the
+ // actual super physical register we are trying to coalesce with.
+ LiveInterval &RHS = li_->getInterval(repSrcReg);
+ if (li_->hasInterval(RealDstReg) &&
+ RHS.overlaps(li_->getInterval(RealDstReg))) {
+ DOUT << "Interfere with register ";
+ DEBUG(li_->getInterval(RealDstReg).print(DOUT, mri_));
+ return true; // Not coalescable
+ }
+ for (const unsigned* SR = mri_->getSubRegisters(RealDstReg); *SR; ++SR)
+ if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) {
+ DOUT << "Interfere with sub-register ";
+ DEBUG(li_->getInterval(*SR).print(DOUT, mri_));
+ return true;
+ }
+ }
+ } else if (differingRegisterClasses(repSrcReg, repDstReg)) {
+ // If they are not of the same register class, we cannot join them.
DOUT << "\tSrc/Dest are different register classes.\n";
- return true; // Not coalescable.
+ // Allow the coalescer to try again in case either side gets coalesced to
+ // a physical register that's compatible with the other side. e.g.
+ // r1024 = MOV32to32_ r1025
+ // but later r1024 is assigned EAX then r1025 may be coalesced with EAX.
+ return false;
}
LiveInterval &SrcInt = li_->getInterval(repSrcReg);
@@ -286,14 +330,14 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
// virtual register. Once the coalescing is done, it cannot be broken and
// these are not spillable! If the destination interval uses are far away,
// think twice about coalescing them!
- if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) {
+ if (!mopd->isDead() && (SrcIsPhys || DstIsPhys) && !isExtSubReg) {
LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg;
unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg;
const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg);
unsigned Threshold = allocatableRCRegs_[RC].count();
- // If the virtual register live interval is long has it has low use desity,
+ // If the virtual register live interval is long but it has low use desity,
// do not join them, instead mark the physical register as its allocation
// preference.
unsigned Length = JoinVInt.getSize() / InstrSlots::NUM;
@@ -340,7 +384,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
// Coalescing failed.
// If we can eliminate the copy without merging the live ranges, do so now.
- if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI))
+ if (!isExtSubReg && AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI))
return true;
// Otherwise, we are unable to join the intervals.
@@ -368,9 +412,24 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
unsetRegisterKills(I->start, I->end, repDstReg);
}
+ // If this is a extract_subreg where dst is a physical register, e.g.
+ // cl = EXTRACT_SUBREG reg1024, 1
+ // then create and update the actual physical register allocated to RHS.
+ if (RealDstReg) {
+ unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
+ VNInfo *DstValNo =
+ ResDstInt->getLiveRangeContaining(li_->getUseIndex(CopyIdx))->valno;
+ LiveInterval &RealDstInt = li_->getOrCreateInterval(RealDstReg);
+ VNInfo *ValNo = RealDstInt.getNextValue(DstValNo->def, DstValNo->reg,
+ li_->getVNInfoAllocator());
+ RealDstInt.addKills(ValNo, DstValNo->kills);
+ RealDstInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo);
+ repDstReg = RealDstReg;
+ }
+
// Update the liveintervals of sub-registers.
for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS)
- li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt,
+ li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt,
li_->getVNInfoAllocator());
} else {
// Merge use info if the destination is a virtual register.
@@ -379,14 +438,25 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
dVI.NumUses += sVI.NumUses;
}
- DOUT << "\n\t\tJoined. Result = "; ResDstInt->print(DOUT, mri_);
- DOUT << "\n";
-
// Remember these liveintervals have been joined.
JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister);
if (MRegisterInfo::isVirtualRegister(repDstReg))
JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister);
+ if (isExtSubReg && !SrcIsPhys && !DstIsPhys) {
+ if (!Swapped) {
+ // Make sure we allocate the larger super-register.
+ ResSrcInt->Copy(*ResDstInt, li_->getVNInfoAllocator());
+ std::swap(repSrcReg, repDstReg);
+ std::swap(ResSrcInt, ResDstInt);
+ }
+ S