MachineCopyPropagation.cpp revision e4fd907e72a599eddfa7a81eac4366b5b82523e3
1977679d6034791fd48a344e5b990503ba50fc242Evan Cheng//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// 3977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// The LLVM Compiler Infrastructure 4977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// 5977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// This file is distributed under the University of Illinois Open Source 6977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// License. See LICENSE.TXT for details. 7977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// 8977679d6034791fd48a344e5b990503ba50fc242Evan Cheng//===----------------------------------------------------------------------===// 9977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// 10977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// This is an extremely simple MachineInstr-level copy propagation pass. 11977679d6034791fd48a344e5b990503ba50fc242Evan Cheng// 12977679d6034791fd48a344e5b990503ba50fc242Evan Cheng//===----------------------------------------------------------------------===// 13977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 14977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#define DEBUG_TYPE "codegen-cp" 15977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/CodeGen/Passes.h" 16977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/Pass.h" 17977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/CodeGen/MachineFunction.h" 18977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 19977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/Target/TargetRegisterInfo.h" 20977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/Support/Debug.h" 21977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/Support/ErrorHandling.h" 22977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/Support/raw_ostream.h" 23977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/ADT/BitVector.h" 24977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/ADT/DenseMap.h" 25977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/ADT/SetVector.h" 26977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/ADT/SmallVector.h" 27977679d6034791fd48a344e5b990503ba50fc242Evan Cheng#include "llvm/ADT/Statistic.h" 28977679d6034791fd48a344e5b990503ba50fc242Evan Chengusing namespace llvm; 29977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 30977679d6034791fd48a344e5b990503ba50fc242Evan ChengSTATISTIC(NumDeletes, "Number of dead copies deleted"); 31977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 32977679d6034791fd48a344e5b990503ba50fc242Evan Chengnamespace { 33977679d6034791fd48a344e5b990503ba50fc242Evan Cheng class MachineCopyPropagation : public MachineFunctionPass { 34977679d6034791fd48a344e5b990503ba50fc242Evan Cheng const TargetRegisterInfo *TRI; 35977679d6034791fd48a344e5b990503ba50fc242Evan Cheng BitVector ReservedRegs; 361df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 37977679d6034791fd48a344e5b990503ba50fc242Evan Cheng public: 38977679d6034791fd48a344e5b990503ba50fc242Evan Cheng static char ID; // Pass identification, replacement for typeid 39977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineCopyPropagation() : MachineFunctionPass(ID) { 40977679d6034791fd48a344e5b990503ba50fc242Evan Cheng initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 41977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 42977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 43977679d6034791fd48a344e5b990503ba50fc242Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 44977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 45977679d6034791fd48a344e5b990503ba50fc242Evan Cheng private: 46977679d6034791fd48a344e5b990503ba50fc242Evan Cheng void SourceNoLongerAvailable(unsigned Reg, 47977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, unsigned> &SrcMap, 48977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 49977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool CopyPropagateBlock(MachineBasicBlock &MBB); 50977679d6034791fd48a344e5b990503ba50fc242Evan Cheng }; 51977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 52977679d6034791fd48a344e5b990503ba50fc242Evan Chengchar MachineCopyPropagation::ID = 0; 531dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 54977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 55977679d6034791fd48a344e5b990503ba50fc242Evan ChengINITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 56977679d6034791fd48a344e5b990503ba50fc242Evan Cheng "Machine Copy Propagation Pass", false, false) 57977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 58977679d6034791fd48a344e5b990503ba50fc242Evan Chengvoid 59977679d6034791fd48a344e5b990503ba50fc242Evan ChengMachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 60977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, unsigned> &SrcMap, 61977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 62977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg); 63977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (SI != SrcMap.end()) { 64977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned MappedDef = SI->second; 65977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Source of copy is no longer available for propagation. 66977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (AvailCopyMap.erase(MappedDef)) { 67977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 68977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(*SR); 69977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 70977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 71e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 72977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SI = SrcMap.find(*AS); 73977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (SI != SrcMap.end()) { 74977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned MappedDef = SI->second; 75977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (AvailCopyMap.erase(MappedDef)) { 76977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 77977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(*SR); 78977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 79977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 80977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 81977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 82977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 83e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Chengstatic bool NoInterveningSideEffect(const MachineInstr *CopyMI, 84e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng const MachineInstr *MI) { 85e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng const MachineBasicBlock *MBB = CopyMI->getParent(); 86e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng if (MI->getParent() != MBB) 87e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return false; 88e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator I = CopyMI; 89e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator E = MBB->end(); 90e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator E2 = MI; 91e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng 92e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng ++I; 93e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng while (I != E && I != E2) { 94e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng if (I->hasUnmodeledSideEffects() || I->isCall() || 95e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng I->isTerminator()) 96e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return false; 97e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng ++I; 98e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng } 99e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return true; 100e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng} 101e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng 10201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// isNopCopy - Return true if the specified copy is really a nop. That is 10301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// if the source of the copy is the same of the definition of the copy that 10401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// supplied the source. If the source of the copy is a sub-register than it 10501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// must check the sub-indices match. e.g. 10601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// ecx = mov eax 10701b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// al = mov cl 10801b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// But not 10901b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// ecx = mov eax 11001b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// al = mov ch 11101b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Chengstatic bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src, 11201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng const TargetRegisterInfo *TRI) { 11301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 11401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (Def == SrcSrc) 11501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return true; 11601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (TRI->isSubRegister(SrcSrc, Def)) { 11701b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SrcDef = CopyMI->getOperand(0).getReg(); 11801b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def); 11901b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (!SubIdx) 12001b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return false; 12101b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return SubIdx == TRI->getSubRegIndex(SrcDef, Src); 12201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng } 12301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng 12401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return false; 12501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng} 12601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng 127977679d6034791fd48a344e5b990503ba50fc242Evan Chengbool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 128977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 129977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 130977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 131977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, unsigned> SrcMap; // Src -> Def map 132977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 133977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool Changed = false; 134977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 135977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineInstr *MI = &*I; 136977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++I; 137977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 138977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MI->isCopy()) { 139977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Def = MI->getOperand(0).getReg(); 140977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Src = MI->getOperand(1).getReg(); 141977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 142977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Def) || 143977679d6034791fd48a344e5b990503ba50fc242Evan Cheng TargetRegisterInfo::isVirtualRegister(Src)) 144977679d6034791fd48a344e5b990503ba50fc242Evan Cheng report_fatal_error("MachineCopyPropagation should be run after" 145977679d6034791fd48a344e5b990503ba50fc242Evan Cheng " register allocation!"); 146977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 147977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 148977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != AvailCopyMap.end()) { 149977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineInstr *CopyMI = CI->second; 150977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!ReservedRegs.test(Def) && 151e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && 15201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng isNopCopy(CopyMI, Def, Src, TRI)) { 153977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // The two copies cancel out and the source of the first copy 154977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // hasn't been overridden, eliminate the second one. e.g. 155977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %ECX<def> = COPY %EAX<kill> 156977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... nothing clobbered EAX. 157977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %EAX<def> = COPY %ECX 158977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // => 159977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %ECX<def> = COPY %EAX 160e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // 161e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // Also avoid eliminating a copy from reserved registers unless the 162e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // definition is proven not clobbered. e.g. 163e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // %RSP<def> = COPY %RAX 164e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // CALL 165e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // %RAX<def> = COPY %RSP 1661a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen 1671a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen // Clear any kills of Def between CopyMI and MI. This extends the 1681a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen // live range. 1691a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 1701a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen I->clearRegisterKills(Def, TRI); 1711a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen 172977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MI->eraseFromParent(); 173977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed = true; 174977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++NumDeletes; 175977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 176977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 177977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 178977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 179977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If Src is defined by a previous copy, it cannot be eliminated. 180977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(Src); 181977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 182977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 183e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Src); *AS; ++AS) { 184977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(*AS); 185977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 186977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 187977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 188977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 189977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Copy is now a candidate for deletion. 190977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.insert(MI); 191977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 192977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Src' is previously source of another copy, then this earlier copy's 193977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // source is no longer available. e.g. 194977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm9<def> = copy %xmm2 195977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... 196977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm2<def> = copy %xmm0 197977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... 198977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm2<def> = copy %xmm9 199977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 200977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 201977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Remember Def is defined by the copy. 202b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng // ... Make sure to clear the def maps of aliases first. 203e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Def); *AS; ++AS) { 204b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng CopyMap.erase(*AS); 205b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng AvailCopyMap.erase(*AS); 206b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng } 207977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap[Def] = MI; 208977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap[Def] = MI; 209977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 210977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap[*SR] = MI; 211977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap[*SR] = MI; 212977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 213977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 214977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Remember source that's copied to Def. Once it's clobbered, then 215977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // it's no longer available for copy propagation. 216977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SrcMap[Src] = Def; 217977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 218977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 219977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 220977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 221977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Not a copy. 222977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SmallVector<unsigned, 2> Defs; 223f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen int RegMaskOpNum = -1; 224977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 225977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineOperand &MO = MI->getOperand(i); 226a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen if (MO.isRegMask()) 227f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen RegMaskOpNum = i; 228977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!MO.isReg()) 229977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 230977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Reg = MO.getReg(); 231977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!Reg) 232977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 233977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 234977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 235977679d6034791fd48a344e5b990503ba50fc242Evan Cheng report_fatal_error("MachineCopyPropagation should be run after" 236977679d6034791fd48a344e5b990503ba50fc242Evan Cheng " register allocation!"); 237977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 238977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MO.isDef()) { 239977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Defs.push_back(Reg); 240977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 241977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 242977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 243977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Reg' is defined by a copy, the copy is no longer a candidate 244977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // for elimination. 245977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 246977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 247977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 248e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 249977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(*AS); 250977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 251977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 252977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 253977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 254977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 255a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // The instruction has a register mask operand which means that it clobbers 256a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // a large set of registers. It is possible to use the register mask to 257a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // prune the available copies, but treat it like a basic block boundary for 258a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // now. 259f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen if (RegMaskOpNum >= 0) { 260f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen // Erase any MaybeDeadCopies whose destination register is clobbered. 261f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 262f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen for (SmallSetVector<MachineInstr*, 8>::iterator 263f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 264f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen DI != DE; ++DI) { 265f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen unsigned Reg = (*DI)->getOperand(0).getReg(); 266f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) 267f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen continue; 268f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen (*DI)->eraseFromParent(); 269f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen Changed = true; 270f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen ++NumDeletes; 271f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen } 272f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen 273f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen // Clear all data structures as if we were beginning a new basic block. 274a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen MaybeDeadCopies.clear(); 275a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen AvailCopyMap.clear(); 276a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen CopyMap.clear(); 277a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen SrcMap.clear(); 278a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen continue; 279a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen } 280a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen 281977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 282977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Reg = Defs[i]; 283977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 284977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // No longer defined by a copy. 285977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap.erase(Reg); 286977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(Reg); 287e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 288977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap.erase(*AS); 289977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(*AS); 290977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 291977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 292977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Reg' is previously source of a copy, it is no longer available for 293977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // copy propagation. 294977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 295977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 296977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 297977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 298977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If MBB doesn't have successors, delete the copies whose defs are not used. 299977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If MBB does have successors, then conservative assume the defs are live-out 300977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // since we don't want to trust live-in lists. 301977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MBB.succ_empty()) { 302977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (SmallSetVector<MachineInstr*, 8>::iterator 303977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 304977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DI != DE; ++DI) { 305977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 306977679d6034791fd48a344e5b990503ba50fc242Evan Cheng (*DI)->eraseFromParent(); 307977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed = true; 308977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++NumDeletes; 309977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 310977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 311977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 312977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 313977679d6034791fd48a344e5b990503ba50fc242Evan Cheng return Changed; 314977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 315977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 316977679d6034791fd48a344e5b990503ba50fc242Evan Chengbool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 317977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool Changed = false; 318977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 319977679d6034791fd48a344e5b990503ba50fc242Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 320977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 321977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 322977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 323977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed |= CopyPropagateBlock(*I); 324977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 325977679d6034791fd48a344e5b990503ba50fc242Evan Cheng return Changed; 326977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 327