MachineCopyPropagation.cpp revision f56ce5312448e5876ee1822facab48385ea5c0c0
1e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// 3e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// The LLVM Compiler Infrastructure 4e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// 5e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// This file is distributed under the University of Illinois Open Source 6e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// License. See LICENSE.TXT for details. 7e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// 8e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson//===----------------------------------------------------------------------===// 9e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// 10e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// This is an extremely simple MachineInstr-level copy propagation pass. 11e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson// 12e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson//===----------------------------------------------------------------------===// 13e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson 141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#define DEBUG_TYPE "codegen-cp" 15e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/CodeGen/Passes.h" 16e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/Pass.h" 17e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/CodeGen/MachineFunction.h" 18283a062a633d6e868aa2be319da812341fe73728Anders Carlsson#include "llvm/CodeGen/MachineFunctionPass.h" 19e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/Target/TargetRegisterInfo.h" 20742cd1b7bb86b52b23b335d47abbd842dac0e1bfFariborz Jahanian#include "llvm/Support/Debug.h" 21e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/Support/ErrorHandling.h" 22774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson#include "llvm/Support/raw_ostream.h" 2386e9644199d91a33d0090395395bc718bd3a4981Anders Carlsson#include "llvm/ADT/BitVector.h" 246815e941998659a55c20c147861b0f437928c3d8Anders Carlsson#include "llvm/ADT/DenseMap.h" 25e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/ADT/SetVector.h" 26e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/ADT/SmallVector.h" 27e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson#include "llvm/ADT/Statistic.h" 28e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlssonusing namespace llvm; 291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 303b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders CarlssonSTATISTIC(NumDeletes, "Number of dead copies deleted"); 313b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 326815e941998659a55c20c147861b0f437928c3d8Anders Carlssonnamespace { 336815e941998659a55c20c147861b0f437928c3d8Anders Carlsson class MachineCopyPropagation : public MachineFunctionPass { 341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const TargetRegisterInfo *TRI; 353b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson BitVector ReservedRegs; 363b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump public: 383b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson static char ID; // Pass identification, replacement for typeid 391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump MachineCopyPropagation() : MachineFunctionPass(ID) { 400032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 413b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 433b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson virtual bool runOnMachineFunction(MachineFunction &MF); 443b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 453b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson private: 463b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson void SourceNoLongerAvailable(unsigned Reg, 471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DenseMap<unsigned, unsigned> &SrcMap, 483b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 493b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson bool CopyPropagateBlock(MachineBasicBlock &MBB); 501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump }; 513b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson} 521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpchar MachineCopyPropagation::ID = 0; 533b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlssonchar &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 543b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 551eb4433ac451dc16f4133a88af2d002ac26c58efMike StumpINITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 563b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson "Machine Copy Propagation Pass", false, false) 573b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpvoid 593b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders CarlssonMachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DenseMap<unsigned, unsigned> &SrcMap, 613b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 623b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg); 633b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson if (SI != SrcMap.end()) { 643b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson unsigned MappedDef = SI->second; 653b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson // Source of copy is no longer available for propagation. 663b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson if (AvailCopyMap.erase(MappedDef)) { 671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 683b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson AvailCopyMap.erase(*SR); 693b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 703b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 723b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson SI = SrcMap.find(*AS); 733b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson if (SI != SrcMap.end()) { 741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump unsigned MappedDef = SI->second; 753b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson if (AvailCopyMap.erase(MappedDef)) { 76622f9dc76bdc4f4d6920907f4fb64a3222aa6566Anders Carlsson for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 773b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson AvailCopyMap.erase(*SR); 783b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 793b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 803b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson } 813b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson} 823b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 833b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlssonstatic bool NoInterveningSideEffect(const MachineInstr *CopyMI, 841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump const MachineInstr *MI) { 853b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson const MachineBasicBlock *MBB = CopyMI->getParent(); 863b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson if (MI->getParent() != MBB) 873b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson return false; 883b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson MachineBasicBlock::const_iterator I = CopyMI; 893b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson MachineBasicBlock::const_iterator E = MBB->end(); 903b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson MachineBasicBlock::const_iterator E2 = MI; 913b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 923b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson ++I; 9389ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson while (I != E && I != E2) { 9489ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson if (I->hasUnmodeledSideEffects() || I->isCall() || 9589ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson I->isTerminator()) 9689ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson return false; 971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ++I; 980032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson } 9989ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson return true; 1001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump} 10189ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson 10289ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlssonbool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 1031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 10489ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 10589ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 1061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DenseMap<unsigned, unsigned> SrcMap; // Src -> Def map 10789ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson 10810c40eee98c600d24437474463b056f323d0cfd2Benjamin Kramer bool Changed = false; 10989ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 11089ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson MachineInstr *MI = &*I; 11189ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson ++I; 11289ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson 11389ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson if (MI->isCopy()) { 11489ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson unsigned Def = MI->getOperand(0).getReg(); 11589ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson unsigned Src = MI->getOperand(1).getReg(); 1160ff8bafde95f6fa51ccea70738c1b99db870bddcAnders Carlsson 11789ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson if (TargetRegisterInfo::isVirtualRegister(Def) || 1181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump TargetRegisterInfo::isVirtualRegister(Src)) 11989ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson report_fatal_error("MachineCopyPropagation should be run after" 12089ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson " register allocation!"); 1211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 12289ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 12389ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson if (CI != AvailCopyMap.end()) { 12489ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson MachineInstr *CopyMI = CI->second; 12589ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 12689ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson if (!ReservedRegs.test(Def) && 12789ed31d3f9eeb8ec77c284a5cf404a74bf5e7acfAnders Carlsson (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && 1281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) { 1291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // The two copies cancel out and the source of the first copy 1303b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson // hasn't been overridden, eliminate the second one. e.g. 1310096acf421c4609ce7f43e8b05f8c5ca866d4611Daniel Dunbar // %ECX<def> = COPY %EAX<kill> 1320096acf421c4609ce7f43e8b05f8c5ca866d4611Daniel Dunbar // ... nothing clobbered EAX. 133e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // %EAX<def> = COPY %ECX 134e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // => 135e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // %ECX<def> = COPY %EAX 136283a062a633d6e868aa2be319da812341fe73728Anders Carlsson // 137283a062a633d6e868aa2be319da812341fe73728Anders Carlsson // Also avoid eliminating a copy from reserved registers unless the 138283a062a633d6e868aa2be319da812341fe73728Anders Carlsson // definition is proven not clobbered. e.g. 1391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // %RSP<def> = COPY %RAX 140e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // CALL 1411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // %RAX<def> = COPY %RSP 1420032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson 1430096acf421c4609ce7f43e8b05f8c5ca866d4611Daniel Dunbar // Clear any kills of Def between CopyMI and MI. This extends the 1440032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson // live range. 1457765934ad7e157b5fcf925792a38e01b1edbcf8aDaniel Dunbar for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 1461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump I->clearRegisterKills(Def, TRI); 147e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson 1480032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson MI->eraseFromParent(); 1491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Changed = true; 150e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson ++NumDeletes; 1511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump continue; 152e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson } 1530032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson } 154e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson 1551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // If Src is defined by a previous copy, it cannot be eliminated. 15655e874299f2ad827646a4ca9ea38c402aaeb38c9Daniel Dunbar CI = CopyMap.find(Src); 1579615ecb44f549ae9fa2b4db6ff46bc78befbf62cDaniel Dunbar if (CI != CopyMap.end()) 158e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson MaybeDeadCopies.remove(CI->second); 159e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) { 160e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson CI = CopyMap.find(*AS); 1611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (CI != CopyMap.end()) 162e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson MaybeDeadCopies.remove(CI->second); 163e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson } 1643b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson 1653b2e16b3d25f6b311dba2871e2a566c96238c3d2Anders Carlsson // Copy is now a candidate for deletion. 1660032b2781b4deb131f8c9b7968f2030bf2489cddOwen Anderson MaybeDeadCopies.insert(MI); 167e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson 1681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // If 'Src' is previously source of another copy, then this earlier copy's 169e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // source is no longer available. e.g. 170e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // %xmm9<def> = copy %xmm2 171e1b29efab32d02e114046d33cca242a88585bf8aAnders Carlsson // ... 172b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson // %xmm2<def> = copy %xmm0 173b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson // ... 174b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson // %xmm2<def> = copy %xmm9 175b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 176b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson 1771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Remember Def is defined by the copy. 178774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson CopyMap[Def] = MI; 179b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson AvailCopyMap[Def] = MI; 1804fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 1814fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor CopyMap[*SR] = MI; 1824fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor AvailCopyMap[*SR] = MI; 1834fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor } 1841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 185183700f494ec9b6701b6efe82bcb25f4c79ba561John McCall // Remember source that's copied to Def. Once it's clobbered, then 1861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // it's no longer available for copy propagation. 187b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson SrcMap[Src] = Def; 1881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 189b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson continue; 190b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson } 191b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Not a copy. 193b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson SmallVector<unsigned, 2> Defs; 194b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson int RegMaskOpNum = -1; 1951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 196183700f494ec9b6701b6efe82bcb25f4c79ba561John McCall MachineOperand &MO = MI->getOperand(i); 197b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson if (MO.isRegMask()) 198b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson RegMaskOpNum = i; 199b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson if (!MO.isReg()) 200b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson continue; 201b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson unsigned Reg = MO.getReg(); 202b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson if (!Reg) 203b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson continue; 204b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson 2052472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson if (TargetRegisterInfo::isVirtualRegister(Reg)) 2062472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson report_fatal_error("MachineCopyPropagation should be run after" 2072472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson " register allocation!"); 2082472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson 2092472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson if (MO.isDef()) { 2102472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson Defs.push_back(Reg); 2112472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson continue; 2122472bf0a1735fa9c60a01946d5ed53b64c9c2422Anders Carlsson } 213183700f494ec9b6701b6efe82bcb25f4c79ba561John McCall 2147116da1efe23f90eb22524ac9aa036153b74f482Mike Stump // If 'Reg' is defined by a copy, the copy is no longer a candidate 2151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // for elimination. 2161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 217e9918d2443ad524e0f488e8f15d9bce4e7373cd1Anders Carlsson if (CI != CopyMap.end()) 218b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson MaybeDeadCopies.remove(CI->second); 2191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 220774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson CI = CopyMap.find(*AS); 221b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson if (CI != CopyMap.end()) 222774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson MaybeDeadCopies.remove(CI->second); 223774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson } 224b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson } 225774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson 226f0070dbae9535836ad41711081465dec2259786bMike Stump // The instruction has a register mask operand which means that it clobbers 227bd4c4aebe6035e7a7125470cc9f0f92511230ee3Douglas Gregor // a large set of registers. It is possible to use the register mask to 2281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // prune the available copies, but treat it like a basic block boundary for 229bd4c4aebe6035e7a7125470cc9f0f92511230ee3Douglas Gregor // now. 230f0070dbae9535836ad41711081465dec2259786bMike Stump if (RegMaskOpNum >= 0) { 2310979c805475d1ba49b5d6ef93c4d2ce6d2eab6edDouglas Gregor // Erase any MaybeDeadCopies whose destination register is clobbered. 232740256bafbba6c5b5cb95a5c5bd7db161f3b2833Mike Stump const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 233740256bafbba6c5b5cb95a5c5bd7db161f3b2833Mike Stump for (SmallSetVector<MachineInstr*, 8>::iterator 2341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 2354fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor DI != DE; ++DI) { 2364fe95f99a2693f1145785ea5835ba6937e49c730Douglas Gregor unsigned Reg = (*DI)->getOperand(0).getReg(); 2370979c805475d1ba49b5d6ef93c4d2ce6d2eab6edDouglas Gregor if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) 238555b4bb2749aea2ec8e2adc351a71ec1cb9bdc33Anders Carlsson continue; 2391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump (*DI)->eraseFromParent(); 2401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Changed = true; 241b9de2c55b2a33776e2bee8ee57df7599b374c8a5Anders Carlsson ++NumDeletes; 242774e7c6881ee6cb970cd42239d700dce87ed402aAnders Carlsson } 2435f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson 2441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Clear all data structures as if we were beginning a new basic block. 2450f294632f36459174199b77699e339715244b5abAnders Carlsson MaybeDeadCopies.clear(); 2460f294632f36459174199b77699e339715244b5abAnders Carlsson AvailCopyMap.clear(); 2471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump CopyMap.clear(); 2480f294632f36459174199b77699e339715244b5abAnders Carlsson SrcMap.clear(); 2491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump continue; 250ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian } 251ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian 252ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 253ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian unsigned Reg = Defs[i]; 254ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian 255ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian // No longer defined by a copy. 256ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian CopyMap.erase(Reg); 257ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian AvailCopyMap.erase(Reg); 258ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 259ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian CopyMap.erase(*AS); 260ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian AvailCopyMap.erase(*AS); 261ad25883a644dd6b52c7923dd128a7d05fb26213cFariborz Jahanian } 2621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 263183700f494ec9b6701b6efe82bcb25f4c79ba561John McCall // If 'Reg' is previously source of a copy, it is no longer available for 2641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // copy propagation. 2651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 266ed032eb5c18b99528cbd76415337b6056a72b911Mike Stump } 267555b4bb2749aea2ec8e2adc351a71ec1cb9bdc33Anders Carlsson } 2681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2690f294632f36459174199b77699e339715244b5abAnders Carlsson // If MBB doesn't have successors, delete the copies whose defs are not used. 2701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // If MBB does have successors, then conservative assume the defs are live-out 2710f294632f36459174199b77699e339715244b5abAnders Carlsson // since we don't want to trust live-in lists. 2720f294632f36459174199b77699e339715244b5abAnders Carlsson if (MBB.succ_empty()) { 2730f294632f36459174199b77699e339715244b5abAnders Carlsson for (SmallSetVector<MachineInstr*, 8>::iterator 2740f294632f36459174199b77699e339715244b5abAnders Carlsson DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 2755f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson DI != DE; ++DI) { 2761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 2775f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson (*DI)->eraseFromParent(); 2785f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson Changed = true; 2795f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson ++NumDeletes; 2801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 2815f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson } 282f5408fe484495ee4efbdd709c8a2c2fdbbbdb328Mike Stump } 283f5408fe484495ee4efbdd709c8a2c2fdbbbdb328Mike Stump 2845f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson return Changed; 2855f4307b7ba164b03c853c8d3eb4674d33f8967a6Anders Carlsson} 28695d4e5d2f87a0f07fb143ccb824dfc4c5c595c78Anders Carlsson 287288dcaf329c49b01dacd5c1dd9f35609555feecdFariborz Jahanianbool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 288288dcaf329c49b01dacd5c1dd9f35609555feecdFariborz Jahanian bool Changed = false; 289569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson 290569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson TRI = MF.getTarget().getRegisterInfo(); 291569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson ReservedRegs = TRI->getReservedRegs(MF); 292569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson 293288dcaf329c49b01dacd5c1dd9f35609555feecdFariborz Jahanian for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 294288dcaf329c49b01dacd5c1dd9f35609555feecdFariborz Jahanian Changed |= CopyPropagateBlock(*I); 295569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson 296569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson return Changed; 297569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson} 298569c1f4a6c703eaa8b963bed7d5c2fd5d4569e93Anders Carlsson