//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "twoaddrinstr"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "twoaddrinstr"
+
STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
STATISTIC(NumCommuted , "Number of instructions commuted to coalesce");
STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted");
bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg,
MachineBasicBlock::iterator OldPos);
+ bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen);
+
bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef);
bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC,
initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addRequired<AliasAnalysis>();
AU.addPreserved<LiveVariables>();
}
/// runOnMachineFunction - Pass entry point.
- bool runOnMachineFunction(MachineFunction&);
+ bool runOnMachineFunction(MachineFunction&) override;
};
} // end anonymous namespace
}
// Find the instruction that kills SavedReg.
- MachineInstr *KillMI = NULL;
+ MachineInstr *KillMI = nullptr;
if (LIS) {
LiveInterval &LI = LIS->getInterval(SavedReg);
assert(LI.end() != LI.begin() &&
for (MachineRegisterInfo::use_nodbg_iterator
UI = MRI->use_nodbg_begin(SavedReg),
UE = MRI->use_nodbg_end(); UI != UE; ++UI) {
- MachineOperand &UseMO = UI.getOperand();
+ MachineOperand &UseMO = *UI;
if (!UseMO.isKill())
continue;
KillMI = UseMO.getParent();
// FIXME: This can be sped up if there is an easy way to query whether an
// instruction is before or after another instruction. Then we can use
// MachineRegisterInfo def / use instead.
- MachineOperand *KillMO = NULL;
+ MachineOperand *KillMO = nullptr;
MachineBasicBlock::iterator KillPos = KillMI;
++KillPos;
unsigned NumVisited = 0;
- for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) {
+ for (MachineBasicBlock::iterator I = std::next(OldPos); I != KillPos; ++I) {
MachineInstr *OtherMI = I;
// DBG_VALUE cannot be counted against the limit.
if (OtherMI->isDebugValue())
return true;
}
+/// getSingleDef -- return the MachineInstr* if it is the single def of the Reg
+/// in current BB.
+static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB,
+ const MachineRegisterInfo *MRI) {
+ MachineInstr *Ret = nullptr;
+ for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
+ if (DefMI.getParent() != BB || DefMI.isDebugValue())
+ continue;
+ if (!Ret)
+ Ret = &DefMI;
+ else if (Ret != &DefMI)
+ return nullptr;
+ }
+ return Ret;
+}
+
+/// Check if there is a reversed copy chain from FromReg to ToReg:
+/// %Tmp1 = copy %Tmp2;
+/// %FromReg = copy %Tmp1;
+/// %ToReg = add %FromReg ...
+/// %Tmp2 = copy %ToReg;
+/// MaxLen specifies the maximum length of the copy chain the func
+/// can walk through.
+bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg,
+ int Maxlen) {
+ unsigned TmpReg = FromReg;
+ for (int i = 0; i < Maxlen; i++) {
+ MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI);
+ if (!Def || !Def->isCopy())
+ return false;
+
+ TmpReg = Def->getOperand(1).getReg();
+
+ if (TmpReg == ToReg)
+ return true;
+ }
+ return false;
+}
+
/// noUseAfterLastDef - Return true if there are no intervening uses between the
/// last instruction in the MBB that defines the specified register and the
/// two-address instruction which is being processed. It also returns the last
unsigned &LastDef) {
LastDef = 0;
unsigned LastUse = Dist;
- for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
- E = MRI->reg_end(); I != E; ++I) {
- MachineOperand &MO = I.getOperand();
+ for (MachineOperand &MO : MRI->reg_operands(Reg)) {
MachineInstr *MI = MO.getParent();
if (MI->getParent() != MBB || MI->isDebugValue())
continue;
MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
// If there are multiple defs, we can't do a simple analysis, so just
// go with what the kill flag says.
- if (llvm::next(Begin) != MRI->def_end())
+ if (std::next(Begin) != MRI->def_end())
return true;
- DefMI = &*Begin;
+ DefMI = Begin->getParent();
bool IsSrcPhys, IsDstPhys;
unsigned SrcReg, DstReg;
// If the def is something other than a copy, then it isn't going to
unsigned &DstReg, bool &IsDstPhys) {
if (!MRI->hasOneNonDBGUse(Reg))
// None or more than one use.
- return 0;
- MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg);
+ return nullptr;
+ MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg);
if (UseMI.getParent() != MBB)
- return 0;
+ return nullptr;
unsigned SrcReg;
bool IsSrcPhys;
if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
return &UseMI;
}
- return 0;
+ return nullptr;
}
/// getMappedReg - Return the physical register the specified virtual register
if (ToRegA) {
unsigned FromRegB = getMappedReg(regB, SrcRegMap);
unsigned FromRegC = getMappedReg(regC, SrcRegMap);
- bool BComp = !FromRegB || regsAreCompatible(FromRegB, ToRegA, TRI);
- bool CComp = !FromRegC || regsAreCompatible(FromRegC, ToRegA, TRI);
- if (BComp != CComp)
- return !BComp && CComp;
+ bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI);
+ bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI);
+
+ // Compute if any of the following are true:
+ // -RegB is not tied to a register and RegC is compatible with RegA.
+ // -RegB is tied to the wrong physical register, but RegC is.
+ // -RegB is tied to the wrong physical register, and RegC isn't tied.
+ if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC)))
+ return true;
+ // Don't compute if any of the following are true:
+ // -RegC is not tied to a register and RegB is compatible with RegA.
+ // -RegC is tied to the wrong physical register, but RegB is.
+ // -RegC is tied to the wrong physical register, and RegB isn't tied.
+ if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB)))
+ return false;
}
// If there is a use of regC between its last def (could be livein) and this
if (!noUseAfterLastDef(regB, Dist, LastDefB))
return true;
+ // Look for situation like this:
+ // %reg101 = MOV %reg100
+ // %reg102 = ...
+ // %reg103 = ADD %reg102, %reg101
+ // ... = %reg103 ...
+ // %reg100 = MOV %reg103
+ // If there is a reversed copy chain from reg101 to reg103, commute the ADD
+ // to eliminate an otherwise unavoidable copy.
+ // FIXME:
+ // We can extend the logic further: If an pair of operands in an insn has
+ // been merged, the insn could be regarded as a virtual copy, and the virtual
+ // copy could also be used to construct a copy chain.
+ // To more generally minimize register copies, ideally the logic of two addr
+ // instruction pass should be integrated with register allocation pass where
+ // interference graph is available.
+ if (isRevCopyChain(regC, regA, 3))
+ return true;
+
+ if (isRevCopyChain(regB, regA, 3))
+ return false;
+
// Since there are no intervening uses for both registers, then commute
// if the def of regC is closer. Its live interval is shorter.
return LastDefB && LastDefC && LastDefC > LastDefB;
DEBUG(dbgs() << "2addr: COMMUTING : " << *MI);
MachineInstr *NewMI = TII->commuteInstruction(MI);
- if (NewMI == 0) {
+ if (NewMI == nullptr) {
DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n");
return false;
}
if (!Sunk) {
DistanceMap.insert(std::make_pair(NewMI, Dist));
mi = NewMI;
- nmi = llvm::next(mi);
+ nmi = std::next(mi);
}
// Update source and destination register maps.
unsigned Reg = DstReg;
while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy,
NewReg, IsDstPhys)) {
- if (IsCopy && !Processed.insert(UseMI))
+ if (IsCopy && !Processed.insert(UseMI).second)
break;
DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
// Must be created from unfolded load. Don't waste time trying this.
return false;
- MachineInstr *KillMI = 0;
+ MachineInstr *KillMI = nullptr;
if (LIS) {
LiveInterval &LI = LIS->getInterval(Reg);
assert(LI.end() != LI.begin() &&
// Move the copies connected to MI down as well.
MachineBasicBlock::iterator Begin = MI;
- MachineBasicBlock::iterator AfterMI = llvm::next(Begin);
+ MachineBasicBlock::iterator AfterMI = std::next(Begin);
MachineBasicBlock::iterator End = AfterMI;
while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) {
}
// Move debug info as well.
- while (Begin != MBB->begin() && llvm::prior(Begin)->isDebugValue())
+ while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue())
--Begin;
nmi = End;
LIS->handleMove(CopyMI);
InsertPos = CopyMI;
}
- End = llvm::next(MachineBasicBlock::iterator(MI));
+ End = std::next(MachineBasicBlock::iterator(MI));
}
// Copies following MI may have been moved as well.
/// instruction too close to the defs of its register dependencies.
bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist,
MachineInstr *MI) {
- for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg),
- DE = MRI->def_end(); DI != DE; ++DI) {
- MachineInstr *DefMI = &*DI;
- if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike())
+ for (MachineInstr &DefMI : MRI->def_instructions(Reg)) {
+ if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike())
continue;
- if (DefMI == MI)
+ if (&DefMI == MI)
return true; // MI is defining something KillMI uses
- DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(DefMI);
+ DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI);
if (DDI == DistanceMap.end())
return true; // Below MI
unsigned DefDist = DDI->second;
assert(Dist > DefDist && "Visited def already?");
- if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist))
+ if (TII->getInstrLatency(InstrItins, &DefMI) > (Dist - DefDist))
return true;
}
return false;
// Must be created from unfolded load. Don't waste time trying this.
return false;
- MachineInstr *KillMI = 0;
+ MachineInstr *KillMI = nullptr;
if (LIS) {
LiveInterval &LI = LIS->getInterval(Reg);
assert(LI.end() != LI.begin() &&
// Move the old kill above MI, don't forget to move debug info as well.
MachineBasicBlock::iterator InsertPos = mi;
- while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue())
+ while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue())
--InsertPos;
MachineBasicBlock::iterator From = KillMI;
- MachineBasicBlock::iterator To = llvm::next(From);
- while (llvm::prior(From)->isDebugValue())
+ MachineBasicBlock::iterator To = std::next(From);
+ while (std::prev(From)->isDebugValue())
--From;
MBB->splice(InsertPos, MBB, From, To);
- nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr.
+ nmi = std::prev(InsertPos); // Backtrack so we process the moved instr.
DistanceMap.erase(DI);
// Update live variables
assert(SrcReg && SrcMO.isUse() && "two address instruction invalid");
// Deal with <undef> uses immediately - simply rewrite the src operand.
- if (SrcMO.isUndef()) {
+ if (SrcMO.isUndef() && !DstMO.getSubReg()) {
// Constrain the DstReg register class if required.
if (TargetRegisterInfo::isVirtualRegister(DstReg))
if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx,
TRI, *MF))
MRI->constrainRegClass(DstReg, RC);
SrcMO.setReg(DstReg);
+ SrcMO.setSubReg(0);
DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI);
continue;
}
const TargetRegisterClass *RC = MRI->getRegClass(RegB);
if (SubRegB) {
if (TargetRegisterInfo::isVirtualRegister(RegA)) {
- assert(TRI->getMatchingSuperRegClass(MRI->getRegClass(RegB),
- MRI->getRegClass(RegA), SubRegB) &&
+ assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA),
+ SubRegB) &&
"tied subregister must be a truncation");
// The superreg class will not be used to constrain the subreg class.
- RC = 0;
+ RC = nullptr;
}
else {
assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB))
TargetRegisterInfo::isVirtualRegister(RegB))
MRI->constrainRegClass(RegA, RC);
MO.setReg(RegA);
+ // The getMatchingSuper asserts guarantee that the register class projected
+ // by SubRegB is compatible with RegA with no subregister. So regardless of
+ // whether the dest oper writes a subreg, the source oper should not.
MO.setSubReg(0);
// Propagate SrcRegMap.
MF = &Func;
const TargetMachine &TM = MF->getTarget();
MRI = &MF->getRegInfo();
- TII = TM.getInstrInfo();
- TRI = TM.getRegisterInfo();
- InstrItins = TM.getInstrItineraryData();
+ TII = MF->getSubtarget().getInstrInfo();
+ TRI = MF->getSubtarget().getRegisterInfo();
+ InstrItins = MF->getSubtarget().getInstrItineraryData();
LV = getAnalysisIfAvailable<LiveVariables>();
LIS = getAnalysisIfAvailable<LiveIntervals>();
AA = &getAnalysis<AliasAnalysis>();
Processed.clear();
for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end();
mi != me; ) {
- MachineBasicBlock::iterator nmi = llvm::next(mi);
+ MachineBasicBlock::iterator nmi = std::next(mi);
if (mi->isDebugValue()) {
mi = nmi;
continue;
TargetRegisterInfo::isPhysicalRegister(DstReg) ||
!(MI->getNumOperands() & 1)) {
DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
SmallVector<unsigned, 4> OrigRegs;
}
MachineBasicBlock::iterator EndMBBI =
- llvm::next(MachineBasicBlock::iterator(MI));
+ std::next(MachineBasicBlock::iterator(MI));
if (!DefEmitted) {
DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");
projects / oota-llvm.git / blobdiff