X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCopyPropagation.cpp;h=a6863412132bdb800b907c43406764f205051f80;hb=d26a2e75e58f56a289b911c0bf582be4f8f655f1;hp=9ed7b7357ed8bb38f35f6dbd38729c389d3682ca;hpb=01b623c8c2d1bd015a8bb20eafee3322575eff8f;p=oota-llvm.git diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp index 9ed7b7357ed..a6863412132 100644 --- a/lib/CodeGen/MachineCopyPropagation.cpp +++ b/lib/CodeGen/MachineCopyPropagation.cpp @@ -11,28 +11,32 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "codegen-cp" #include "llvm/CodeGen/Passes.h" -#include "llvm/Pass.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/Target/TargetRegisterInfo.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/ADT/BitVector.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "codegen-cp" + STATISTIC(NumDeletes, "Number of dead copies deleted"); namespace { class MachineCopyPropagation : public MachineFunctionPass { const TargetRegisterInfo *TRI; - BitVector ReservedRegs; + const TargetInstrInfo *TII; + MachineRegisterInfo *MRI; public: static char ID; // Pass identification, replacement for typeid @@ -40,12 +44,15 @@ namespace { initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); } - virtual bool runOnMachineFunction(MachineFunction &MF); + bool runOnMachineFunction(MachineFunction &MF) override; private: + typedef SmallVector DestList; + typedef DenseMap SourceMap; + void SourceNoLongerAvailable(unsigned Reg, - DenseMap &SrcMap, - DenseMap &AvailCopyMap); + SourceMap &SrcMap, + DenseMap &AvailCopyMap); bool CopyPropagateBlock(MachineBasicBlock &MBB); }; } @@ -57,23 +64,18 @@ INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", void MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, - DenseMap &SrcMap, + SourceMap &SrcMap, DenseMap &AvailCopyMap) { - DenseMap::iterator SI = SrcMap.find(Reg); - if (SI != SrcMap.end()) { - unsigned MappedDef = SI->second; - // Source of copy is no longer available for propagation. - if (AvailCopyMap.erase(MappedDef)) { - for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) - AvailCopyMap.erase(*SR); - } - } - for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { - SI = SrcMap.find(*AS); + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + SourceMap::iterator SI = SrcMap.find(*AI); if (SI != SrcMap.end()) { - unsigned MappedDef = SI->second; - if (AvailCopyMap.erase(MappedDef)) { - for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) + const DestList& Defs = SI->second; + for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); + I != E; ++I) { + unsigned MappedDef = *I; + // Source of copy is no longer available for propagation. + AvailCopyMap.erase(MappedDef); + for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) AvailCopyMap.erase(*SR); } } @@ -125,10 +127,12 @@ static bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src, } bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { - SmallSetVector MaybeDeadCopies; // Candidates for deletion - DenseMap AvailCopyMap; // Def -> available copies map - DenseMap CopyMap; // Def -> copies map - DenseMap SrcMap; // Src -> Def map + SmallSetVector MaybeDeadCopies; // Candidates for deletion + DenseMap AvailCopyMap; // Def -> available copies map + DenseMap CopyMap; // Def -> copies map + SourceMap SrcMap; // Src -> Def map + + DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); bool Changed = false; for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { @@ -147,8 +151,8 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { DenseMap::iterator CI = AvailCopyMap.find(Src); if (CI != AvailCopyMap.end()) { MachineInstr *CopyMI = CI->second; - if (!ReservedRegs.test(Def) && - (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && + if (!MRI->isReserved(Def) && + (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) && isNopCopy(CopyMI, Def, Src, TRI)) { // The two copies cancel out and the source of the first copy // hasn't been overridden, eliminate the second one. e.g. @@ -164,6 +168,8 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { // CALL // %RAX = COPY %RSP + DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; MI->dump()); + // Clear any kills of Def between CopyMI and MI. This extends the // live range. for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) @@ -177,15 +183,16 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { } // If Src is defined by a previous copy, it cannot be eliminated. - CI = CopyMap.find(Src); - if (CI != CopyMap.end()) - MaybeDeadCopies.remove(CI->second); - for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) { - CI = CopyMap.find(*AS); - if (CI != CopyMap.end()) + for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { + CI = CopyMap.find(*AI); + if (CI != CopyMap.end()) { + DEBUG(dbgs() << "MCP: Copy is no longer dead: "; CI->second->dump()); MaybeDeadCopies.remove(CI->second); + } } + DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); + // Copy is now a candidate for deletion. MaybeDeadCopies.insert(MI); @@ -199,16 +206,23 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); // Remember Def is defined by the copy. - CopyMap[Def] = MI; - AvailCopyMap[Def] = MI; - for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { + // ... Make sure to clear the def maps of aliases first. + for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) { + CopyMap.erase(*AI); + AvailCopyMap.erase(*AI); + } + for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); + ++SR) { CopyMap[*SR] = MI; AvailCopyMap[*SR] = MI; } // Remember source that's copied to Def. Once it's clobbered, then // it's no longer available for copy propagation. - SrcMap[Src] = Def; + if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == + SrcMap[Src].end()) { + SrcMap[Src].push_back(Def); + } continue; } @@ -237,14 +251,21 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { // If 'Reg' is defined by a copy, the copy is no longer a candidate // for elimination. - DenseMap::iterator CI = CopyMap.find(Reg); - if (CI != CopyMap.end()) - MaybeDeadCopies.remove(CI->second); - for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { - CI = CopyMap.find(*AS); - if (CI != CopyMap.end()) + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + DenseMap::iterator CI = CopyMap.find(*AI); + if (CI != CopyMap.end()) { + DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); MaybeDeadCopies.remove(CI->second); + } } + // Treat undef use like defs for copy propagation but not for + // dead copy. We would need to do a liveness check to be sure the copy + // is dead for undef uses. + // The backends are allowed to do whatever they want with undef value + // and we cannot be sure this register will not be rewritten to break + // some false dependencies for the hardware for instance. + if (MO.isUndef()) + Defs.push_back(Reg); } // The instruction has a register mask operand which means that it clobbers @@ -258,8 +279,10 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); DI != DE; ++DI) { unsigned Reg = (*DI)->getOperand(0).getReg(); - if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) + if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg)) continue; + DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; + (*DI)->dump()); (*DI)->eraseFromParent(); Changed = true; ++NumDeletes; @@ -277,11 +300,9 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { unsigned Reg = Defs[i]; // No longer defined by a copy. - CopyMap.erase(Reg); - AvailCopyMap.erase(Reg); - for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { - CopyMap.erase(*AS); - AvailCopyMap.erase(*AS); + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + CopyMap.erase(*AI); + AvailCopyMap.erase(*AI); } // If 'Reg' is previously source of a copy, it is no longer available for @@ -297,7 +318,7 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { for (SmallSetVector::iterator DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); DI != DE; ++DI) { - if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { + if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { (*DI)->eraseFromParent(); Changed = true; ++NumDeletes; @@ -309,10 +330,14 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { } bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { + if (skipOptnoneFunction(*MF.getFunction())) + return false; + bool Changed = false; - TRI = MF.getTarget().getRegisterInfo(); - ReservedRegs = TRI->getReservedRegs(MF); + TRI = MF.getSubtarget().getRegisterInfo(); + TII = MF.getSubtarget().getInstrInfo(); + MRI = &MF.getRegInfo(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) Changed |= CopyPropagateBlock(*I);