X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCopyPropagation.cpp;h=dc8a2241c7e1b4e65b343d93f14ce2f1e43ff767;hb=614dacc9102ed3bf3fe4c985b5bc12857a26bae2;hp=f96c86914376e106a0330a6c692dd4865c56ee72;hpb=1a96c914315b0286d84c507d696484e2c95875a4;p=oota-llvm.git diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp index f96c8691437..dc8a2241c7e 100644 --- a/lib/CodeGen/MachineCopyPropagation.cpp +++ b/lib/CodeGen/MachineCopyPropagation.cpp @@ -13,18 +13,19 @@ #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" using namespace llvm; STATISTIC(NumDeletes, "Number of dead copies deleted"); @@ -32,8 +33,9 @@ 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 MachineCopyPropagation() : MachineFunctionPass(ID) { @@ -43,41 +45,38 @@ namespace { virtual bool runOnMachineFunction(MachineFunction &MF); private: + typedef SmallVector DestList; + typedef DenseMap SourceMap; + void SourceNoLongerAvailable(unsigned Reg, - DenseMap &SrcMap, - DenseMap &AvailCopyMap); + SourceMap &SrcMap, + DenseMap &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) -FunctionPass *llvm::createMachineCopyPropagationPass() { - return new MachineCopyPropagation(); -} - 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) - AvailCopyMap.erase(*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. + if (AvailCopyMap.erase(MappedDef)) { + for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) + AvailCopyMap.erase(*SR); + } } } } @@ -102,11 +101,46 @@ static bool NoInterveningSideEffect(const MachineInstr *CopyMI, return true; } +/// isNopCopy - Return true if the specified copy is really a nop. That is +/// if the source of the copy is the same of the definition of the copy that +/// supplied the source. If the source of the copy is a sub-register than it +/// must check the sub-indices match. e.g. +/// ecx = mov eax +/// al = mov cl +/// But not +/// ecx = mov eax +/// al = mov ch +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; +} + +// Remove MI from the function because it has been determined it is dead. +// Turn it into a noop KILL instruction if it has super-register liveness +// adjustments. +void MachineCopyPropagation::removeCopy(MachineInstr *MI) { + if (MI->getNumOperands() == 2) + MI->eraseFromParent(); + else + MI->setDesc(TII->get(TargetOpcode::KILL)); +} + 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 bool Changed = false; for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { @@ -125,10 +159,9 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { DenseMap::iterator CI = AvailCopyMap.find(Src); if (CI != AvailCopyMap.end()) { MachineInstr *CopyMI = CI->second; - unsigned SrcSrc = CopyMI->getOperand(1).getReg(); - if (!ReservedRegs.test(Def) && - (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && - (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) { + 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. // %ECX = COPY %EAX @@ -148,7 +181,7 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) I->clearRegisterKills(Def, TRI); - MI->eraseFromParent(); + removeCopy(MI); Changed = true; ++NumDeletes; continue; @@ -156,11 +189,8 @@ 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); + for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { + CI = CopyMap.find(*AI); if (CI != CopyMap.end()) MaybeDeadCopies.remove(CI->second); } @@ -178,24 +208,35 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); // Remember Def is defined by the copy. + // ... 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); + } CopyMap[Def] = MI; AvailCopyMap[Def] = MI; - for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { + for (MCSubRegIterator SR(Def, TRI); 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; } // Not a copy. SmallVector 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(); @@ -213,25 +254,46 @@ 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); + for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { + DenseMap::iterator CI = CopyMap.find(*AI); if (CI != CopyMap.end()) MaybeDeadCopies.remove(CI->second); } } + // The instruction has a register mask operand which means that it clobbers + // a large set of registers. It is possible to use the register mask to + // prune the available copies, but treat it like a basic block boundary for + // now. + if (RegMaskOpNum >= 0) { + // Erase any MaybeDeadCopies whose destination register is clobbered. + const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); + for (SmallSetVector::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; + } + + // Clear all data structures as if we were beginning a new basic block. + MaybeDeadCopies.clear(); + AvailCopyMap.clear(); + CopyMap.clear(); + SrcMap.clear(); + continue; + } + for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 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 @@ -247,8 +309,8 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { for (SmallSetVector::iterator DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); DI != DE; ++DI) { - if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { - (*DI)->eraseFromParent(); + if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { + removeCopy(*DI); Changed = true; ++NumDeletes; } @@ -262,7 +324,8 @@ bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { bool Changed = false; TRI = MF.getTarget().getRegisterInfo(); - ReservedRegs = TRI->getReservedRegs(MF); + TII = MF.getTarget().getInstrInfo(); + MRI = &MF.getRegInfo(); for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) Changed |= CopyPropagateBlock(*I);