From 977679d6034791fd48a344e5b990503ba50fc242 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Sat, 7 Jan 2012 03:02:36 +0000 Subject: Added a late machine instruction copy propagation pass. This catches opportunities that only present themselves after late optimizations such as tail duplication .e.g. ## BB#1: movl %eax, %ecx movl %ecx, %eax ret The register allocator also leaves some of them around (due to false dep between copies from phi-elimination, etc.) This required some changes in codegen passes. Post-ra scheduler and the pseudo-instruction expansion passes have been moved after branch folding and tail merging. They were before branch folding before because it did not always update block livein's. That's fixed now. The pass change makes independently since we want to properly schedule instructions after branch folding / tail duplication. rdar://10428165 rdar://10640363 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147716 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineCopyPropagation.cpp | 240 +++++++++++++++++++++++++++++++++ 1 file changed, 240 insertions(+) create mode 100644 lib/CodeGen/MachineCopyPropagation.cpp (limited to 'lib/CodeGen/MachineCopyPropagation.cpp') diff --git a/lib/CodeGen/MachineCopyPropagation.cpp b/lib/CodeGen/MachineCopyPropagation.cpp new file mode 100644 index 0000000000..861025ca0b --- /dev/null +++ b/lib/CodeGen/MachineCopyPropagation.cpp @@ -0,0 +1,240 @@ +//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is an extremely simple MachineInstr-level copy propagation pass. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "codegen-cp" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Pass.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Target/TargetRegisterInfo.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" +using namespace llvm; + +STATISTIC(NumDeletes, "Number of dead copies deleted"); + +namespace { + class MachineCopyPropagation : public MachineFunctionPass { + const TargetRegisterInfo *TRI; + BitVector ReservedRegs; + + public: + static char ID; // Pass identification, replacement for typeid + MachineCopyPropagation() : MachineFunctionPass(ID) { + initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnMachineFunction(MachineFunction &MF); + + private: + void SourceNoLongerAvailable(unsigned Reg, + DenseMap &SrcMap, + DenseMap &AvailCopyMap); + bool CopyPropagateBlock(MachineBasicBlock &MBB); + }; +} +char MachineCopyPropagation::ID = 0; + +INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", + "Machine Copy Propagation Pass", false, false) + +FunctionPass *llvm::createMachineCopyPropagationPass() { + return new MachineCopyPropagation(); +} + +void +MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, + DenseMap &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); + if (SI != SrcMap.end()) { + unsigned MappedDef = SI->second; + if (AvailCopyMap.erase(MappedDef)) { + for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) + AvailCopyMap.erase(*SR); + } + } + } +} + +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 + + 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::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))) { + // 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 + // ... nothing clobbered EAX. + // %EAX = COPY %ECX + // => + // %ECX = COPY %EAX + CopyMI->getOperand(1).setIsKill(false); + MI->eraseFromParent(); + Changed = true; + ++NumDeletes; + continue; + } + } + + // 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()) + MaybeDeadCopies.remove(CI->second); + } + + // Copy is now a candidate for deletion. + MaybeDeadCopies.insert(MI); + + // If 'Src' is previously source of another copy, then this earlier copy's + // source is no longer available. e.g. + // %xmm9 = copy %xmm2 + // ... + // %xmm2 = copy %xmm0 + // ... + // %xmm2 = copy %xmm9 + 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) { + 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; + + continue; + } + + // Not a copy. + SmallVector Defs; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(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; + } + + // 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()) + MaybeDeadCopies.remove(CI->second); + } + } + + 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); + } + + // If 'Reg' is previously source of a copy, it is no longer available for + // copy propagation. + SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); + } + } + + // If MBB doesn't have successors, delete the copies whose defs are not used. + // If MBB does have successors, then conservative assume the defs are live-out + // since we don't want to trust live-in lists. + if (MBB.succ_empty()) { + for (SmallSetVector::iterator + DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); + DI != DE; ++DI) { + if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { + (*DI)->eraseFromParent(); + Changed = true; + ++NumDeletes; + } + } + } + + return Changed; +} + +bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { + bool Changed = false; + + TRI = MF.getTarget().getRegisterInfo(); + ReservedRegs = TRI->getReservedRegs(MF); + + for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) + Changed |= CopyPropagateBlock(*I); + + return Changed; +} -- cgit v1.2.3-18-g5258