X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCopyPropagation.cpp;h=4f48e2cd9720a96d3ada07f5fec611ba3174e22f;hb=66f464ee266b31bb02058c49a5abe3a6b77f080b;hp=861025ca0b580832fb2889b4c90e894d31d4378d;hpb=977679d6034791fd48a344e5b990503ba50fc242;p=oota-llvm.git diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp index 861025ca0b5..4f48e2cd972 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,51 +45,102 @@ 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); + } } } } } +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; +} + +/// 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; ) { @@ -106,9 +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) && - (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 @@ -116,8 +169,19 @@ bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { // %EAX = COPY %ECX // => // %ECX = COPY %EAX - CopyMI->getOperand(1).setIsKill(false); - MI->eraseFromParent(); + // + // Also avoid eliminating a copy from reserved registers unless the + // definition is proven not clobbered. e.g. + // %RSP = COPY %RAX + // CALL + // %RAX = COPY %RSP + + // Clear any kills of Def between CopyMI and MI. This extends the + // live range. + for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) + I->clearRegisterKills(Def, TRI); + + removeCopy(MI); Changed = true; ++NumDeletes; continue; @@ -125,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); } @@ -147,24 +208,34 @@ 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; } // 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(); @@ -182,25 +253,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 @@ -216,8 +308,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; } @@ -231,7 +323,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);