X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FMachineCopyPropagation.cpp;h=bac3aa2c155eef46f0a712488cce35dcdef88000;hb=a4b5050cf5af18ac18565073fecbfcb95f93556b;hp=f96c86914376e106a0330a6c692dd4865c56ee72;hpb=1a96c914315b0286d84c507d696484e2c95875a4;p=oota-llvm.git diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp index f96c8691437..bac3aa2c155 100644 --- a/lib/CodeGen/MachineCopyPropagation.cpp +++ b/lib/CodeGen/MachineCopyPropagation.cpp @@ -33,7 +33,7 @@ namespace { class MachineCopyPropagation : public MachineFunctionPass { const TargetRegisterInfo *TRI; BitVector ReservedRegs; - + public: static char ID; // Pass identification, replacement for typeid MachineCopyPropagation() : MachineFunctionPass(ID) { @@ -43,41 +43,37 @@ 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); }; } 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 +98,36 @@ 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; +} + 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 +146,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))) { + 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 @@ -156,11 +176,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 +195,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 +241,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 (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) + continue; + (*DI)->eraseFromParent(); + 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