//
//===----------------------------------------------------------------------===//
-#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,
// Check if it's safe to move this instruction.
bool SeenStore = true; // Be conservative.
- if (!MI->isSafeToMove(TII, AA, SeenStore))
+ if (!MI->isSafeToMove(AA, SeenStore))
return false;
unsigned DefReg = 0;
}
// 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;
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;
// go with what the kill flag says.
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;
}
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() &&
return false;
bool SeenStore = true;
- if (!MI->isSafeToMove(TII, AA, SeenStore))
+ if (!MI->isSafeToMove(AA, SeenStore))
return false;
if (TII->getInstrLatency(InstrItins, MI) > 1)
/// 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() &&
return false;
bool SeenStore = true;
- if (!KillMI->isSafeToMove(TII, AA, SeenStore))
+ if (!KillMI->isSafeToMove(AA, SeenStore))
return false;
SmallSet<unsigned, 2> Uses;
}
}
+ // If the instruction is convertible to 3 Addr, instead
+ // of returning try 3 Addr transformation aggresively and
+ // use this variable to check later. Because it might be better.
+ // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
+ // instead of the following code.
+ // addl %esi, %edi
+ // movl %edi, %eax
+ // ret
+ bool Commuted = false;
+
// If it's profitable to commute, try to do so.
if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) {
+ Commuted = true;
++NumCommuted;
if (AggressiveCommute)
++NumAggrCommuted;
- return false;
+ if (!MI.isConvertibleTo3Addr())
+ return false;
}
if (shouldOnlyCommute)
// If there is one more use of regB later in the same MBB, consider
// re-schedule this MI below it.
- if (EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
+ if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
++NumReSchedDowns;
return true;
}
}
}
+ // Return if it is commuted but 3 addr conversion is failed.
+ if (Commuted)
+ return false;
+
// If there is one more use of regB later in the same MBB, consider
// re-schedule it before this MI if it's legal.
if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
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))
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>();
TargetRegisterInfo::isPhysicalRegister(DstReg) ||
!(MI->getNumOperands() & 1)) {
DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI);
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
SmallVector<unsigned, 4> OrigRegs;
projects / oota-llvm.git / blobdiff