class MachineCSE : public MachineFunctionPass {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
- MachineRegisterInfo *MRI;
- MachineDominatorTree *DT;
AliasAnalysis *AA;
+ MachineDominatorTree *DT;
+ MachineRegisterInfo *MRI;
public:
static char ID; // Pass identification
MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
MachineBasicBlock::const_iterator E);
bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB);
bool isCSECandidate(MachineInstr *MI);
+ bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
+ MachineInstr *CSMI, MachineInstr *MI);
bool ProcessBlock(MachineDomTreeNode *Node);
};
} // end anonymous namespace
if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
TargetRegisterInfo::isVirtualRegister(SrcReg) &&
!SrcSubIdx && !DstSubIdx) {
+ const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
+ const TargetRegisterClass *RC = MRI->getRegClass(Reg);
+ const TargetRegisterClass *NewRC = getCommonSubClass(RC, SRC);
+ if (!NewRC)
+ continue;
+ DEBUG(dbgs() << "Coalescing: " << *DefMI);
+ DEBUG(dbgs() << "*** to: " << *MI);
MO.setReg(SrcReg);
+ if (NewRC != SRC)
+ MRI->setRegClass(SrcReg, NewRC);
DefMI->eraseFromParent();
++NumCoalesces;
Changed = true;
MachineBasicBlock::const_iterator I,
MachineBasicBlock::const_iterator E) {
unsigned LookAheadLeft = 5;
- while (LookAheadLeft--) {
+ while (LookAheadLeft) {
+ // Skip over dbg_value's.
+ while (I != E && I->isDebugValue())
+ ++I;
+
if (I == E)
// Reached end of block, register is obviously dead.
return true;
- if (I->isDebugValue())
- continue;
bool SeenDef = false;
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = I->getOperand(i);
// See a def of Reg (or an alias) before encountering any use, it's
// trivially dead.
return true;
+
+ --LookAheadLeft;
++I;
}
return false;
}
+/// hasLivePhysRegDefUse - Return true if the specified instruction read / write
+/// physical registers (except for dead defs of physical registers).
bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){
unsigned PhysDef = 0;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
return false;
}
-bool MachineCSE::isCSECandidate(MachineInstr *MI) {
- // Ignore copies or instructions that read / write physical registers
- // (except for dead defs of physical registers).
+static bool isCopy(const MachineInstr *MI, const TargetInstrInfo *TII) {
unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
- if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
- MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
+ return TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
+ MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg();
+}
+
+bool MachineCSE::isCSECandidate(MachineInstr *MI) {
+ if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
+ MI->isKill() || MI->isInlineAsm() || MI->isDebugValue())
+ return false;
+
+ // Ignore copies.
+ if (isCopy(MI, TII))
return false;
// Ignore stuff that we obviously can't move.
return true;
}
+/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
+/// common expression that defines Reg.
+bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
+ MachineInstr *CSMI, MachineInstr *MI) {
+ // FIXME: Heuristics that works around the lack the live range splitting.
+
+ // Heuristics #1: Don't cse "cheap" computating if the def is not local or in an
+ // immediate predecessor. We don't want to increase register pressure and end up
+ // causing other computation to be spilled.
+ if (MI->getDesc().isAsCheapAsAMove()) {
+ MachineBasicBlock *CSBB = CSMI->getParent();
+ MachineBasicBlock *BB = MI->getParent();
+ if (CSBB != BB &&
+ find(CSBB->succ_begin(), CSBB->succ_end(), BB) == CSBB->succ_end())
+ return false;
+ }
+
+ // Heuristics #2: If the expression doesn't not use a vr and the only use
+ // of the redundant computation are copies, do not cse.
+ bool HasVRegUse = false;
+ for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO = MI->getOperand(i);
+ if (MO.isReg() && MO.isUse() && MO.getReg() &&
+ TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
+ HasVRegUse = true;
+ break;
+ }
+ }
+ if (!HasVRegUse) {
+ bool HasNonCopyUse = false;
+ for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg),
+ E = MRI->use_nodbg_end(); I != E; ++I) {
+ MachineInstr *Use = &*I;
+ // Ignore copies.
+ if (!isCopy(Use, TII)) {
+ HasNonCopyUse = true;
+ break;
+ }
+ }
+ if (!HasNonCopyUse)
+ return false;
+ }
+
+ // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
+ // it unless the defined value is already used in the BB of the new use.
+ bool HasPHI = false;
+ SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
+ for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg),
+ E = MRI->use_nodbg_end(); I != E; ++I) {
+ MachineInstr *Use = &*I;
+ HasPHI |= Use->isPHI();
+ CSBBs.insert(Use->getParent());
+ }
+
+ if (!HasPHI)
+ return true;
+ return CSBBs.count(MI->getParent());
+}
+
bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
bool Changed = false;
+ SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
ScopedHashTableScope<MachineInstr*, unsigned,
MachineInstrExpressionTrait> VNTS(VNT);
MachineBasicBlock *MBB = Node->getBlock();
bool FoundCSE = VNT.count(MI);
if (!FoundCSE) {
// Look for trivial copy coalescing opportunities.
- if (PerformTrivialCoalescing(MI, MBB))
+ if (PerformTrivialCoalescing(MI, MBB)) {
+ // After coalescing MI itself may become a copy.
+ if (isCopy(MI, TII))
+ continue;
FoundCSE = VNT.count(MI);
+ }
}
// FIXME: commute commutable instructions?
MachineInstr *CSMI = Exps[CSVN];
DEBUG(dbgs() << "Examining: " << *MI);
DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
+
+ // Check if it's profitable to perform this CSE.
+ bool DoCSE = true;
unsigned NumDefs = MI->getDesc().getNumDefs();
for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
continue;
unsigned OldReg = MO.getReg();
unsigned NewReg = CSMI->getOperand(i).getReg();
- assert(OldReg != NewReg &&
- TargetRegisterInfo::isVirtualRegister(OldReg) &&
+ if (OldReg == NewReg)
+ continue;
+ assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
TargetRegisterInfo::isVirtualRegister(NewReg) &&
"Do not CSE physical register defs!");
- MRI->replaceRegWith(OldReg, NewReg);
+ if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
+ DoCSE = false;
+ break;
+ }
+ CSEPairs.push_back(std::make_pair(OldReg, NewReg));
--NumDefs;
}
- MI->eraseFromParent();
- ++NumCSEs;
+
+ // Actually perform the elimination.
+ if (DoCSE) {
+ for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i)
+ MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
+ MI->eraseFromParent();
+ ++NumCSEs;
+ } else {
+ DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
+ VNT.insert(MI, CurrVN++);
+ Exps.push_back(MI);
+ }
+ CSEPairs.clear();
}
// Recursively call ProcessBlock with childred.
TII = MF.getTarget().getInstrInfo();
TRI = MF.getTarget().getRegisterInfo();
MRI = &MF.getRegInfo();
- DT = &getAnalysis<MachineDominatorTree>();
AA = &getAnalysis<AliasAnalysis>();
+ DT = &getAnalysis<MachineDominatorTree>();
return ProcessBlock(DT->getRootNode());
}
projects / oota-llvm.git / blobdiff