#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/RecyclingAllocator.h"
-
using namespace llvm;
STATISTIC(NumCoalesces, "Number of copies coalesced");
STATISTIC(NumCSEs, "Number of common subexpression eliminated");
STATISTIC(NumPhysCSEs,
"Number of physreg referencing common subexpr eliminated");
-STATISTIC(NumCrossBlockPhysCSEs,
- "Number of physreg common subexprs cross-block eliminated");
+STATISTIC(NumCrossBBCSEs,
+ "Number of cross-MBB physreg referencing CS eliminated");
STATISTIC(NumCommutes, "Number of copies coalesced after commuting");
namespace {
}
virtual bool runOnMachineFunction(MachineFunction &MF);
-
+
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
virtual void releaseMemory() {
ScopeMap.clear();
Exps.clear();
+ AllocatableRegs.clear();
+ ReservedRegs.clear();
}
private:
ScopedHTType VNT;
SmallVector<MachineInstr*, 64> Exps;
unsigned CurrVN;
+ BitVector AllocatableRegs;
+ BitVector ReservedRegs;
bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
bool isPhysDefTriviallyDead(unsigned Reg,
bool hasLivePhysRegDefUses(const MachineInstr *MI,
const MachineBasicBlock *MBB,
SmallSet<unsigned,8> &PhysRefs,
- SmallVector<unsigned,8> &PhysDefs) const;
+ SmallVector<unsigned,2> &PhysDefs) const;
bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
- SmallSet<unsigned,8> &PhysRefs) const;
+ SmallSet<unsigned,8> &PhysRefs,
+ SmallVector<unsigned,2> &PhysDefs,
+ bool &NonLocal) const;
bool isCSECandidate(MachineInstr *MI);
bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
MachineInstr *CSMI, MachineInstr *MI);
} // end anonymous namespace
char MachineCSE::ID = 0;
+char &llvm::MachineCSEID = MachineCSE::ID;
INITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse",
"Machine Common Subexpression Elimination", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(MachineCSE, "machine-cse",
"Machine Common Subexpression Elimination", false, false)
-FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
-
bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
MachineBasicBlock *MBB) {
bool Changed = false;
SeenDef = true;
}
if (SeenDef)
- // See a def of Reg (or an alias) before encountering any use, it's
+ // See a def of Reg (or an alias) before encountering any use, it's
// trivially dead.
return true;
bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI,
const MachineBasicBlock *MBB,
SmallSet<unsigned,8> &PhysRefs,
- SmallVector<unsigned,8> &PhysDefs) const{
+ SmallVector<unsigned,2> &PhysDefs) const{
MachineBasicBlock::const_iterator I = MI; I = llvm::next(I);
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (MO.isDef() &&
(MO.isDead() || isPhysDefTriviallyDead(Reg, I, MBB->end())))
continue;
- PhysDefs.push_back(Reg);
PhysRefs.insert(Reg);
+ if (MO.isDef())
+ PhysDefs.push_back(Reg);
for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
PhysRefs.insert(*Alias);
}
}
bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
- SmallSet<unsigned,8> &PhysRefs) const {
- // Look backward from MI to find CSMI.
+ SmallSet<unsigned,8> &PhysRefs,
+ SmallVector<unsigned,2> &PhysDefs,
+ bool &NonLocal) const {
+ // For now conservatively returns false if the common subexpression is
+ // not in the same basic block as the given instruction. The only exception
+ // is if the common subexpression is in the sole predecessor block.
+ const MachineBasicBlock *MBB = MI->getParent();
+ const MachineBasicBlock *CSMBB = CSMI->getParent();
+
+ bool CrossMBB = false;
+ if (CSMBB != MBB) {
+ if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
+ return false;
+
+ for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
+ if (AllocatableRegs.test(PhysDefs[i]) || ReservedRegs.test(PhysDefs[i]))
+ // Avoid extending live range of physical registers if they are
+ //allocatable or reserved.
+ return false;
+ }
+ CrossMBB = true;
+ }
+ MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I);
+ MachineBasicBlock::const_iterator E = MI;
+ MachineBasicBlock::const_iterator EE = CSMBB->end();
unsigned LookAheadLeft = LookAheadLimit;
- MachineBasicBlock *CurBB = MI->getParent();
- MachineBasicBlock::const_reverse_iterator I(MI);
- MachineBasicBlock::const_reverse_iterator E(CurBB->rend());
while (LookAheadLeft) {
- while (LookAheadLeft && I != E) {
- // Skip over dbg_value's.
- while (I != E && I->isDebugValue())
- ++I;
-
- if (I == E) break;
+ // Skip over dbg_value's.
+ while (I != E && I != EE && I->isDebugValue())
+ ++I;
- if (&*I == CSMI)
- return true;
+ if (I == EE) {
+ assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
+ (void)CrossMBB;
+ CrossMBB = false;
+ NonLocal = true;
+ I = MBB->begin();
+ EE = MBB->end();
+ continue;
+ }
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
- const MachineOperand &MO = I->getOperand(i);
- if (!MO.isReg() || !MO.isDef())
- continue;
- unsigned MOReg = MO.getReg();
- if (TargetRegisterInfo::isVirtualRegister(MOReg))
- continue;
- if (PhysRefs.count(MOReg))
- return false;
- }
+ if (I == E)
+ return true;
- --LookAheadLeft;
- ++I;
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+ const MachineOperand &MO = I->getOperand(i);
+ if (!MO.isReg() || !MO.isDef())
+ continue;
+ unsigned MOReg = MO.getReg();
+ if (TargetRegisterInfo::isVirtualRegister(MOReg))
+ continue;
+ if (PhysRefs.count(MOReg))
+ return false;
}
- // Go back another BB; for now, only go back at most one BB.
- MachineBasicBlock *CSBB = CSMI->getParent();
- if (!CSBB->isSuccessor(CurBB) || CurBB->pred_size() != 1)
- return false;
- CurBB = CSBB;
- I = CSBB->rbegin();
- E = CSBB->rend();
+
+ --LookAheadLeft;
+ ++I;
}
return false;
return false;
// Ignore stuff that we obviously can't move.
- const TargetInstrDesc &TID = MI->getDesc();
- if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
+ if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
MI->hasUnmodeledSideEffects())
return false;
- if (TID.mayLoad()) {
+ if (MI->mayLoad()) {
// Okay, this instruction does a load. As a refinement, we allow the target
// to decide whether the loaded value is actually a constant. If so, we can
// actually use it as a load.
// Heuristics #1: Don't CSE "cheap" computation 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()) {
+ if (MI->isAsCheapAsAMove()) {
MachineBasicBlock *CSBB = CSMI->getParent();
MachineBasicBlock *BB = MI->getParent();
if (CSBB != BB && !CSBB->isSuccessor(BB))
// Commute commutable instructions.
bool Commuted = false;
- if (!FoundCSE && MI->getDesc().isCommutable()) {
+ if (!FoundCSE && MI->isCommutable()) {
MachineInstr *NewMI = TII->commuteInstruction(MI);
if (NewMI) {
Commuted = true;
// If the instruction defines physical registers and the values *may* be
// used, then it's not safe to replace it with a common subexpression.
// It's also not safe if the instruction uses physical registers.
+ bool CrossMBBPhysDef = false;
SmallSet<unsigned,8> PhysRefs;
- SmallVector<unsigned,8> DirectPhysRefs;
- if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, DirectPhysRefs)) {
+ SmallVector<unsigned, 2> PhysDefs;
+ if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, PhysDefs)) {
FoundCSE = false;
- // ... Unless the CS is local and it also defines the physical register
- // which is not clobbered in between and the physical register uses
- // were not clobbered.
+ // ... Unless the CS is local or is in the sole predecessor block
+ // and it also defines the physical register which is not clobbered
+ // in between and the physical register uses were not clobbered.
unsigned CSVN = VNT.lookup(MI);
MachineInstr *CSMI = Exps[CSVN];
- if (PhysRegDefsReach(CSMI, MI, PhysRefs))
+ if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef))
FoundCSE = true;
}
unsigned NewReg = CSMI->getOperand(i).getReg();
if (OldReg == NewReg)
continue;
+
assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
TargetRegisterInfo::isVirtualRegister(NewReg) &&
"Do not CSE physical register defs!");
+
if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
DoCSE = false;
break;
}
+
+ // Don't perform CSE if the result of the old instruction cannot exist
+ // within the register class of the new instruction.
+ const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg);
+ if (!MRI->constrainRegClass(NewReg, OldRC)) {
+ DoCSE = false;
+ break;
+ }
+
CSEPairs.push_back(std::make_pair(OldReg, NewReg));
--NumDefs;
}
MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
MRI->clearKillFlags(CSEPairs[i].second);
}
- MI->eraseFromParent();
- if (!DirectPhysRefs.empty() && CSMI->getParent() != MBB) {
- assert(CSMI->getParent()->isSuccessor(MBB));
- ++NumCrossBlockPhysCSEs;
- SmallVector<unsigned,8>::iterator PI = DirectPhysRefs.begin(),
- PE = DirectPhysRefs.end();
- for (; PI != PE; ++PI)
- MBB->addLiveIn(*PI);
+
+ if (CrossMBBPhysDef) {
+ // Add physical register defs now coming in from a predecessor to MBB
+ // livein list.
+ while (!PhysDefs.empty()) {
+ unsigned LiveIn = PhysDefs.pop_back_val();
+ if (!MBB->isLiveIn(LiveIn))
+ MBB->addLiveIn(LiveIn);
+ }
+ ++NumCrossBBCSEs;
}
+
+ MI->eraseFromParent();
++NumCSEs;
if (!PhysRefs.empty())
++NumPhysCSEs;
MRI = &MF.getRegInfo();
AA = &getAnalysis<AliasAnalysis>();
DT = &getAnalysis<MachineDominatorTree>();
+ AllocatableRegs = TRI->getAllocatableSet(MF);
+ ReservedRegs = TRI->getReservedRegs(MF);
return PerformCSE(DT->getRootNode());
}