MachineCopyPropagation.cpp [plain text]
#define DEBUG_TYPE "codegen-cp"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Pass.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/TargetRegisterInfo.h"
using namespace llvm;
STATISTIC(NumDeletes, "Number of dead copies deleted");
namespace {
class MachineCopyPropagation : public MachineFunctionPass {
const TargetRegisterInfo *TRI;
const TargetInstrInfo *TII;
MachineRegisterInfo *MRI;
public:
static char ID; MachineCopyPropagation() : MachineFunctionPass(ID) {
initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
}
virtual bool runOnMachineFunction(MachineFunction &MF);
private:
typedef SmallVector<unsigned, 4> DestList;
typedef DenseMap<unsigned, DestList> SourceMap;
void SourceNoLongerAvailable(unsigned Reg,
SourceMap &SrcMap,
DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
bool CopyPropagateBlock(MachineBasicBlock &MBB);
void removeCopy(MachineInstr *MI);
};
}
char MachineCopyPropagation::ID = 0;
char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
"Machine Copy Propagation Pass", false, false)
void
MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
SourceMap &SrcMap,
DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
SourceMap::iterator SI = SrcMap.find(*AI);
if (SI != SrcMap.end()) {
const DestList& Defs = SI->second;
for (DestList::const_iterator I = Defs.begin(), E = Defs.end();
I != E; ++I) {
unsigned MappedDef = *I;
if (AvailCopyMap.erase(MappedDef)) {
for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR)
AvailCopyMap.erase(*SR);
}
}
}
}
}
static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
const MachineInstr *MI) {
const MachineBasicBlock *MBB = CopyMI->getParent();
if (MI->getParent() != MBB)
return false;
MachineBasicBlock::const_iterator I = CopyMI;
MachineBasicBlock::const_iterator E = MBB->end();
MachineBasicBlock::const_iterator E2 = MI;
++I;
while (I != E && I != E2) {
if (I->hasUnmodeledSideEffects() || I->isCall() ||
I->isTerminator())
return false;
++I;
}
return true;
}
static bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src,
const TargetRegisterInfo *TRI) {
unsigned SrcSrc = CopyMI->getOperand(1).getReg();
if (Def == SrcSrc)
return true;
if (TRI->isSubRegister(SrcSrc, Def)) {
unsigned SrcDef = CopyMI->getOperand(0).getReg();
unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def);
if (!SubIdx)
return false;
return SubIdx == TRI->getSubRegIndex(SrcDef, Src);
}
return false;
}
void MachineCopyPropagation::removeCopy(MachineInstr *MI) {
if (MI->getNumOperands() == 2)
MI->eraseFromParent();
else
MI->setDesc(TII->get(TargetOpcode::KILL));
}
bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; DenseMap<unsigned, MachineInstr*> AvailCopyMap; DenseMap<unsigned, MachineInstr*> CopyMap; SourceMap SrcMap;
bool Changed = false;
for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
MachineInstr *MI = &*I;
++I;
if (MI->isCopy()) {
unsigned Def = MI->getOperand(0).getReg();
unsigned Src = MI->getOperand(1).getReg();
if (TargetRegisterInfo::isVirtualRegister(Def) ||
TargetRegisterInfo::isVirtualRegister(Src))
report_fatal_error("MachineCopyPropagation should be run after"
" register allocation!");
DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
if (CI != AvailCopyMap.end()) {
MachineInstr *CopyMI = CI->second;
if (!MRI->isReserved(Def) &&
(!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
isNopCopy(CopyMI, Def, Src, TRI)) {
for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I)
I->clearRegisterKills(Def, TRI);
removeCopy(MI);
Changed = true;
++NumDeletes;
continue;
}
}
for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) {
CI = CopyMap.find(*AI);
if (CI != CopyMap.end())
MaybeDeadCopies.remove(CI->second);
}
MaybeDeadCopies.insert(MI);
SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap);
for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) {
CopyMap.erase(*AI);
AvailCopyMap.erase(*AI);
}
CopyMap[Def] = MI;
AvailCopyMap[Def] = MI;
for (MCSubRegIterator SR(Def, TRI); SR.isValid(); ++SR) {
CopyMap[*SR] = MI;
AvailCopyMap[*SR] = MI;
}
if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) ==
SrcMap[Src].end()) {
SrcMap[Src].push_back(Def);
}
continue;
}
SmallVector<unsigned, 2> Defs;
int RegMaskOpNum = -1;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isRegMask())
RegMaskOpNum = i;
if (!MO.isReg())
continue;
unsigned Reg = MO.getReg();
if (!Reg)
continue;
if (TargetRegisterInfo::isVirtualRegister(Reg))
report_fatal_error("MachineCopyPropagation should be run after"
" register allocation!");
if (MO.isDef()) {
Defs.push_back(Reg);
continue;
}
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(*AI);
if (CI != CopyMap.end())
MaybeDeadCopies.remove(CI->second);
}
}
if (RegMaskOpNum >= 0) {
const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum);
for (SmallSetVector<MachineInstr*, 8>::iterator
DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
DI != DE; ++DI) {
unsigned Reg = (*DI)->getOperand(0).getReg();
if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg))
continue;
removeCopy(*DI);
Changed = true;
++NumDeletes;
}
MaybeDeadCopies.clear();
AvailCopyMap.clear();
CopyMap.clear();
SrcMap.clear();
continue;
}
for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
unsigned Reg = Defs[i];
for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
CopyMap.erase(*AI);
AvailCopyMap.erase(*AI);
}
SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap);
}
}
if (MBB.succ_empty()) {
for (SmallSetVector<MachineInstr*, 8>::iterator
DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
DI != DE; ++DI) {
if (!MRI->isReserved((*DI)->getOperand(0).getReg())) {
removeCopy(*DI);
Changed = true;
++NumDeletes;
}
}
}
return Changed;
}
bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
bool Changed = false;
TRI = MF.getTarget().getRegisterInfo();
TII = MF.getTarget().getInstrInfo();
MRI = &MF.getRegInfo();
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
Changed |= CopyPropagateBlock(*I);
return Changed;
}