#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
/// reMaterializeTrivialDef - If the source of a copy is defined by a
/// trivial computation, replace the copy by rematerialize the definition.
- bool reMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg,
- MachineInstr *CopyMI);
+ bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI,
+ bool &IsDefCopy);
/// canJoinPhys - Return true if a physreg copy should be joined.
bool canJoinPhys(const CoalescerPair &CP);
}
void RegisterCoalescer::eliminateDeadDefs() {
- SmallVector<LiveInterval*, 8> NewRegs;
+ SmallVector<unsigned, 8> NewRegs;
LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs);
}
for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
AI != AE; ++AI) {
if (AI->valno != AValNo) continue;
- LiveInterval::Ranges::iterator BI =
- std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
- if (BI != IntB.ranges.begin())
+ LiveInterval::iterator BI =
+ std::upper_bound(IntB.begin(), IntB.end(), AI->start);
+ if (BI != IntB.begin())
--BI;
- for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
+ for (; BI != IntB.end() && AI->end >= BI->start; ++BI) {
if (BI->valno == BValNo)
continue;
if (BI->start <= AI->start && BI->end > AI->start)
LiveInterval &IntB =
LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
- // BValNo is a value number in B that is defined by a copy from A. 'B3' in
+ // BValNo is a value number in B that is defined by a copy from A. 'B1' in
// the example above.
VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);
if (!BValNo || BValNo->def != CopyIdx)
return false;
- assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
-
// AValNo is the value number in A that defines the copy, A3 in the example.
VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));
assert(AValNo && "COPY source not live");
/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial
/// computation, replace the copy by rematerialize the definition.
-bool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt,
- unsigned DstReg,
- MachineInstr *CopyMI) {
- SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);
- LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
- assert(SrcLR != SrcInt.end() && "Live range not found!");
- VNInfo *ValNo = SrcLR->valno;
+bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP,
+ MachineInstr *CopyMI,
+ bool &IsDefCopy) {
+ IsDefCopy = false;
+ unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
+ unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
+ unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
+ unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
+ if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
+ return false;
+
+ LiveInterval &SrcInt = LIS->getInterval(SrcReg);
+ SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI);
+ VNInfo *ValNo = LiveRangeQuery(SrcInt, CopyIdx).valueIn();
+ assert(ValNo && "CopyMI input register not live");
if (ValNo->isPHIDef() || ValNo->isUnused())
return false;
MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
if (!DefMI)
return false;
- assert(DefMI && "Defining instruction disappeared");
+ if (DefMI->isCopyLike()) {
+ IsDefCopy = true;
+ return false;
+ }
if (!DefMI->isAsCheapAsAMove())
return false;
if (!TII->isTriviallyReMaterializable(DefMI, AA))
const MCInstrDesc &MCID = DefMI->getDesc();
if (MCID.getNumDefs() != 1)
return false;
+ // Only support subregister destinations when the def is read-undef.
+ MachineOperand &DstOperand = CopyMI->getOperand(0);
+ unsigned CopyDstReg = DstOperand.getReg();
+ if (DstOperand.getSubReg() && !DstOperand.isUndef())
+ return false;
+
+ const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
if (!DefMI->isImplicitDef()) {
- // Make sure the copy destination register class fits the instruction
- // definition register class. The mismatch can happen as a result of earlier
- // extract_subreg, insert_subreg, subreg_to_reg coalescing.
- const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF);
- if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
- if (MRI->getRegClass(DstReg) != RC)
+ if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
+ unsigned NewDstReg = DstReg;
+
+ unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(),
+ DefMI->getOperand(0).getSubReg());
+ if (NewDstIdx)
+ NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
+
+ // Finally, make sure that the physical subregister that will be
+ // constructed later is permitted for the instruction.
+ if (!DefRC->contains(NewDstReg))
return false;
- } else if (!RC->contains(DstReg))
- return false;
+ } else {
+ // Theoretically, some stack frame reference could exist. Just make sure
+ // it hasn't actually happened.
+ assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&
+ "Only expect to deal with virtual or physical registers");
+ }
}
MachineBasicBlock *MBB = CopyMI->getParent();
MachineBasicBlock::iterator MII =
llvm::next(MachineBasicBlock::iterator(CopyMI));
- TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI);
+ TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI);
MachineInstr *NewMI = prior(MII);
+ LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI);
+ CopyMI->eraseFromParent();
+ ErasedInstrs.insert(CopyMI);
+
// NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
// We need to remember these so we can add intervals once we insert
// NewMI into SlotIndexes.
}
}
+ if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
+ unsigned NewIdx = NewMI->getOperand(0).getSubReg();
+ const TargetRegisterClass *RCForInst;
+ if (NewIdx)
+ RCForInst = TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg), DefRC,
+ NewIdx);
+
+ if (MRI->constrainRegClass(DstReg, DefRC)) {
+ // The materialized instruction is quite capable of setting DstReg
+ // directly, but it may still have a now-trivial subregister index which
+ // we should clear.
+ NewMI->getOperand(0).setSubReg(0);
+ } else if (NewIdx && RCForInst) {
+ // The subreg index on NewMI is essential; we still have to make sure
+ // DstReg:idx is in a class that NewMI can use.
+ MRI->constrainRegClass(DstReg, RCForInst);
+ } else {
+ // DstReg is actually incompatible with NewMI, we have to move to a
+ // super-reg's class. This could come from a sequence like:
+ // GR32 = MOV32r0
+ // GR8 = COPY GR32:sub_8
+ MRI->setRegClass(DstReg, CP.getNewRC());
+ updateRegDefsUses(DstReg, DstReg, DstIdx);
+ NewMI->getOperand(0).setSubReg(
+ TRI->composeSubRegIndices(SrcIdx, DefMI->getOperand(0).getSubReg()));
+ }
+ } else if (NewMI->getOperand(0).getReg() != CopyDstReg) {
+ // The New instruction may be defining a sub-register of what's actually
+ // been asked for. If so it must implicitly define the whole thing.
+ assert(TargetRegisterInfo::isPhysicalRegister(DstReg) &&
+ "Only expect virtual or physical registers in remat");
+ NewMI->getOperand(0).setIsDead(true);
+ NewMI->addOperand(MachineOperand::CreateReg(CopyDstReg,
+ true /*IsDef*/,
+ true /*IsImp*/,
+ false /*IsKill*/));
+ }
+
+ if (NewMI->getOperand(0).getSubReg())
+ NewMI->getOperand(0).setIsUndef();
+
// CopyMI may have implicit operands, transfer them over to the newly
// rematerialized instruction. And update implicit def interval valnos.
for (unsigned i = CopyMI->getDesc().getNumOperands(),
}
}
- LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI);
-
SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
unsigned Reg = NewMIImplDefs[i];
LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
}
- CopyMI->eraseFromParent();
- ErasedInstrs.insert(CopyMI);
DEBUG(dbgs() << "Remat: " << *NewMI);
++NumReMats;
if (!canJoinPhys(CP)) {
// Before giving up coalescing, if definition of source is defined by
// trivial computation, try rematerializing it.
- if (!CP.isFlipped() &&
- reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()),
- CP.getDstReg(), CopyMI))
+ bool IsDefCopy;
+ if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
return true;
+ if (IsDefCopy)
+ Again = true; // May be possible to coalesce later.
return false;
}
} else {
});
// When possible, let DstReg be the larger interval.
- if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() >
- LIS->getInterval(CP.getDstReg()).ranges.size())
+ if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
+ LIS->getInterval(CP.getDstReg()).size())
CP.flip();
}
// If definition of source is defined by trivial computation, try
// rematerializing it.
- if (!CP.isFlipped() &&
- reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()),
- CP.getDstReg(), CopyMI))
+ bool IsDefCopy;
+ if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
return true;
// If we can eliminate the copy without merging the live ranges, do so now.
LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
// Join RHS into LHS.
- LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo,
- MRI);
+ LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
// Kill flags are going to be wrong if the live ranges were overlapping.
// Eventually, we should simply clear all kill flags when computing live
// block (the unsigned), and then on the MBB number.
//
// EnableGlobalCopies assumes that the primary sort key is loop depth.
-static int compareMBBPriority(const void *L, const void *R) {
- const MBBPriorityInfo *LHS = static_cast<const MBBPriorityInfo*>(L);
- const MBBPriorityInfo *RHS = static_cast<const MBBPriorityInfo*>(R);
+static int compareMBBPriority(const MBBPriorityInfo *LHS,
+ const MBBPriorityInfo *RHS) {
// Deeper loops first
if (LHS->Depth != RHS->Depth)
return LHS->Depth > RHS->Depth ? -1 : 1;
if (!Copy->isCopy())
return false;
+ if (Copy->getOperand(1).isUndef())
+ return false;
+
unsigned SrcReg = Copy->getOperand(1).getReg();
unsigned DstReg = Copy->getOperand(0).getReg();
if (TargetRegisterInfo::isPhysicalRegister(SrcReg)
// are not inherently easier to resolve, but slightly preferable until we
// have local live range splitting. In particular this is required by
// cmp+jmp macro fusion.
- for (MachineBasicBlock::reverse_iterator
- MII = MBB->rbegin(), E = MBB->rend(); MII != E; ++MII) {
+ for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
+ MII != E; ++MII) {
if (!MII->isCopyLike())
continue;
if (isLocalCopy(&(*MII), LIS))