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: 465f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames typedef SmallVector<unsigned, 4> DestList; 475f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames typedef DenseMap<unsigned, DestList> SourceMap; 485f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames 49977679d6034791fd48a344e5b990503ba50fc242Evan Cheng void SourceNoLongerAvailable(unsigned Reg, 505f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SourceMap &SrcMap, 515f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 52977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool CopyPropagateBlock(MachineBasicBlock &MBB); 53977679d6034791fd48a344e5b990503ba50fc242Evan Cheng }; 54977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 55977679d6034791fd48a344e5b990503ba50fc242Evan Chengchar MachineCopyPropagation::ID = 0; 561dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 57977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 58977679d6034791fd48a344e5b990503ba50fc242Evan ChengINITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 59977679d6034791fd48a344e5b990503ba50fc242Evan Cheng "Machine Copy Propagation Pass", false, false) 60977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 61977679d6034791fd48a344e5b990503ba50fc242Evan Chengvoid 62977679d6034791fd48a344e5b990503ba50fc242Evan ChengMachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 635f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SourceMap &SrcMap, 64977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 655f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SourceMap::iterator SI = SrcMap.find(Reg); 66977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (SI != SrcMap.end()) { 675f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames const DestList& Defs = SI->second; 685f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 69d9eb1d77979f10d0237af22d87789803162044faLang Hames I != E; ++I) { 70d9eb1d77979f10d0237af22d87789803162044faLang Hames unsigned MappedDef = *I; 71d9eb1d77979f10d0237af22d87789803162044faLang Hames // Source of copy is no longer available for propagation. 72d9eb1d77979f10d0237af22d87789803162044faLang Hames if (AvailCopyMap.erase(MappedDef)) { 73d9eb1d77979f10d0237af22d87789803162044faLang Hames for (const uint16_t *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 74d9eb1d77979f10d0237af22d87789803162044faLang Hames AvailCopyMap.erase(*SR); 75d9eb1d77979f10d0237af22d87789803162044faLang Hames } 76977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 77977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 78e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 79977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SI = SrcMap.find(*AS); 80977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (SI != SrcMap.end()) { 815f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames const DestList& Defs = SI->second; 825f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 83d9eb1d77979f10d0237af22d87789803162044faLang Hames I != E; ++I) { 84d9eb1d77979f10d0237af22d87789803162044faLang Hames unsigned MappedDef = *I; 85d9eb1d77979f10d0237af22d87789803162044faLang Hames if (AvailCopyMap.erase(MappedDef)) { 86d9eb1d77979f10d0237af22d87789803162044faLang Hames for (const uint16_t *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 87d9eb1d77979f10d0237af22d87789803162044faLang Hames AvailCopyMap.erase(*SR); 88d9eb1d77979f10d0237af22d87789803162044faLang Hames } 89977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 90977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 91977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 92977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 93977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 94e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Chengstatic bool NoInterveningSideEffect(const MachineInstr *CopyMI, 95e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng const MachineInstr *MI) { 96e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng const MachineBasicBlock *MBB = CopyMI->getParent(); 97e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng if (MI->getParent() != MBB) 98e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return false; 99e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator I = CopyMI; 100e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator E = MBB->end(); 101e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng MachineBasicBlock::const_iterator E2 = MI; 102e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng 103e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng ++I; 104e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng while (I != E && I != E2) { 105e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng if (I->hasUnmodeledSideEffects() || I->isCall() || 106e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng I->isTerminator()) 107e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return false; 108e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng ++I; 109e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng } 110e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng return true; 111e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng} 112e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng 11301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// isNopCopy - Return true if the specified copy is really a nop. That is 11401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// if the source of the copy is the same of the definition of the copy that 11501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// supplied the source. If the source of the copy is a sub-register than it 11601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// must check the sub-indices match. e.g. 11701b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// ecx = mov eax 11801b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// al = mov cl 11901b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// But not 12001b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// ecx = mov eax 12101b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng/// al = mov ch 12201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Chengstatic bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src, 12301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng const TargetRegisterInfo *TRI) { 12401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 12501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (Def == SrcSrc) 12601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return true; 12701b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (TRI->isSubRegister(SrcSrc, Def)) { 12801b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SrcDef = CopyMI->getOperand(0).getReg(); 12901b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def); 13001b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng if (!SubIdx) 13101b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return false; 13201b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return SubIdx == TRI->getSubRegIndex(SrcDef, Src); 13301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng } 13401b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng 13501b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng return false; 13601b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng} 13701b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng 138977679d6034791fd48a344e5b990503ba50fc242Evan Chengbool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 139d9eb1d77979f10d0237af22d87789803162044faLang Hames SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 140d9eb1d77979f10d0237af22d87789803162044faLang Hames DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 141d9eb1d77979f10d0237af22d87789803162044faLang Hames DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 1425f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SourceMap SrcMap; // Src -> Def map 143977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 144977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool Changed = false; 145977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 146977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineInstr *MI = &*I; 147977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++I; 148977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 149977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MI->isCopy()) { 150977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Def = MI->getOperand(0).getReg(); 151977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Src = MI->getOperand(1).getReg(); 152977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 153977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Def) || 154977679d6034791fd48a344e5b990503ba50fc242Evan Cheng TargetRegisterInfo::isVirtualRegister(Src)) 155977679d6034791fd48a344e5b990503ba50fc242Evan Cheng report_fatal_error("MachineCopyPropagation should be run after" 156977679d6034791fd48a344e5b990503ba50fc242Evan Cheng " register allocation!"); 157977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 158977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 159977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != AvailCopyMap.end()) { 160977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineInstr *CopyMI = CI->second; 161977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!ReservedRegs.test(Def) && 162e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && 16301b623c8c2d1bd015a8bb20eafee3322575eff8fEvan Cheng isNopCopy(CopyMI, Def, Src, TRI)) { 164977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // The two copies cancel out and the source of the first copy 165977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // hasn't been overridden, eliminate the second one. e.g. 166977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %ECX<def> = COPY %EAX<kill> 167977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... nothing clobbered EAX. 168977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %EAX<def> = COPY %ECX 169977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // => 170977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %ECX<def> = COPY %EAX 171e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // 172e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // Also avoid eliminating a copy from reserved registers unless the 173e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // definition is proven not clobbered. e.g. 174e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // %RSP<def> = COPY %RAX 175e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // CALL 176e811d0dd30e8949df5d72bedfaa46dc579dad97eEvan Cheng // %RAX<def> = COPY %RSP 1771a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen 1781a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen // Clear any kills of Def between CopyMI and MI. This extends the 1791a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen // live range. 1801a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 1811a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen I->clearRegisterKills(Def, TRI); 1821a96c914315b0286d84c507d696484e2c95875a4Jakob Stoklund Olesen 183977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MI->eraseFromParent(); 184977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed = true; 185977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++NumDeletes; 186977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 187977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 188977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 189977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 190977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If Src is defined by a previous copy, it cannot be eliminated. 191977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(Src); 192977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 193977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 194e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Src); *AS; ++AS) { 195977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(*AS); 196977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 197977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 198977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 199977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 200977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Copy is now a candidate for deletion. 201977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.insert(MI); 202977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 203977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Src' is previously source of another copy, then this earlier copy's 204977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // source is no longer available. e.g. 205977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm9<def> = copy %xmm2 206977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... 207977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm2<def> = copy %xmm0 208977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // ... 209977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // %xmm2<def> = copy %xmm9 210977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 211977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 212977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Remember Def is defined by the copy. 213b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng // ... Make sure to clear the def maps of aliases first. 214e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Def); *AS; ++AS) { 215b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng CopyMap.erase(*AS); 216b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng AvailCopyMap.erase(*AS); 217b266cd0e9824db48804c785b2c48b43be0c0f7ddEvan Cheng } 218977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap[Def] = MI; 219977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap[Def] = MI; 2209ebfbf8b9fd5f982e0db9293808bd32168615ba9Craig Topper for (const uint16_t *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 221977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap[*SR] = MI; 222977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap[*SR] = MI; 223977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 224977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 225977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Remember source that's copied to Def. Once it's clobbered, then 226977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // it's no longer available for copy propagation. 2275f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == 2285f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SrcMap[Src].end()) { 2295f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames SrcMap[Src].push_back(Def); 2305f46eb157e58df285e1a0a7ce6ff1c9ed972bf65Lang Hames } 231977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 232977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 233977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 234977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 235977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // Not a copy. 236977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SmallVector<unsigned, 2> Defs; 237f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen int RegMaskOpNum = -1; 238977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 239977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MachineOperand &MO = MI->getOperand(i); 240a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen if (MO.isRegMask()) 241f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen RegMaskOpNum = i; 242977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!MO.isReg()) 243977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 244977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Reg = MO.getReg(); 245977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!Reg) 246977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 247977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 248977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) 249977679d6034791fd48a344e5b990503ba50fc242Evan Cheng report_fatal_error("MachineCopyPropagation should be run after" 250977679d6034791fd48a344e5b990503ba50fc242Evan Cheng " register allocation!"); 251977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 252977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MO.isDef()) { 253977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Defs.push_back(Reg); 254977679d6034791fd48a344e5b990503ba50fc242Evan Cheng continue; 255977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 256977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 257977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Reg' is defined by a copy, the copy is no longer a candidate 258977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // for elimination. 259977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 260977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 261977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 262e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 263977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CI = CopyMap.find(*AS); 264977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (CI != CopyMap.end()) 265977679d6034791fd48a344e5b990503ba50fc242Evan Cheng MaybeDeadCopies.remove(CI->second); 266977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 267977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 268977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 269a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // The instruction has a register mask operand which means that it clobbers 270a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // a large set of registers. It is possible to use the register mask to 271a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // prune the available copies, but treat it like a basic block boundary for 272a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen // now. 273f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen if (RegMaskOpNum >= 0) { 274f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen // Erase any MaybeDeadCopies whose destination register is clobbered. 275f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 276f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen for (SmallSetVector<MachineInstr*, 8>::iterator 277f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 278f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen DI != DE; ++DI) { 279f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen unsigned Reg = (*DI)->getOperand(0).getReg(); 280f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) 281f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen continue; 282f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen (*DI)->eraseFromParent(); 283f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen Changed = true; 284f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen ++NumDeletes; 285f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen } 286f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen 287f56ce5312448e5876ee1822facab48385ea5c0c0Jakob Stoklund Olesen // Clear all data structures as if we were beginning a new basic block. 288a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen MaybeDeadCopies.clear(); 289a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen AvailCopyMap.clear(); 290a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen CopyMap.clear(); 291a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen SrcMap.clear(); 292a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen continue; 293a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen } 294a8fc171b3f703ad8bda50a22e9227eee0822eeecJakob Stoklund Olesen 295977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 296977679d6034791fd48a344e5b990503ba50fc242Evan Cheng unsigned Reg = Defs[i]; 297977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 298977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // No longer defined by a copy. 299977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap.erase(Reg); 300977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(Reg); 301e4fd907e72a599eddfa7a81eac4366b5b82523e3Craig Topper for (const uint16_t *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 302977679d6034791fd48a344e5b990503ba50fc242Evan Cheng CopyMap.erase(*AS); 303977679d6034791fd48a344e5b990503ba50fc242Evan Cheng AvailCopyMap.erase(*AS); 304977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 305977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 306977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If 'Reg' is previously source of a copy, it is no longer available for 307977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // copy propagation. 308977679d6034791fd48a344e5b990503ba50fc242Evan Cheng SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 309977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 310977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 311977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 312977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If MBB doesn't have successors, delete the copies whose defs are not used. 313977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // If MBB does have successors, then conservative assume the defs are live-out 314977679d6034791fd48a344e5b990503ba50fc242Evan Cheng // since we don't want to trust live-in lists. 315977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (MBB.succ_empty()) { 316977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (SmallSetVector<MachineInstr*, 8>::iterator 317977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 318977679d6034791fd48a344e5b990503ba50fc242Evan Cheng DI != DE; ++DI) { 319977679d6034791fd48a344e5b990503ba50fc242Evan Cheng if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 320977679d6034791fd48a344e5b990503ba50fc242Evan Cheng (*DI)->eraseFromParent(); 321977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed = true; 322977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ++NumDeletes; 323977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 324977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 325977679d6034791fd48a344e5b990503ba50fc242Evan Cheng } 326977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 327977679d6034791fd48a344e5b990503ba50fc242Evan Cheng return Changed; 328977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 329977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 330977679d6034791fd48a344e5b990503ba50fc242Evan Chengbool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 331977679d6034791fd48a344e5b990503ba50fc242Evan Cheng bool Changed = false; 332977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 333977679d6034791fd48a344e5b990503ba50fc242Evan Cheng TRI = MF.getTarget().getRegisterInfo(); 334977679d6034791fd48a344e5b990503ba50fc242Evan Cheng ReservedRegs = TRI->getReservedRegs(MF); 335977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 336977679d6034791fd48a344e5b990503ba50fc242Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 337977679d6034791fd48a344e5b990503ba50fc242Evan Cheng Changed |= CopyPropagateBlock(*I); 338977679d6034791fd48a344e5b990503ba50fc242Evan Cheng 339977679d6034791fd48a344e5b990503ba50fc242Evan Cheng return Changed; 340977679d6034791fd48a344e5b990503ba50fc242Evan Cheng} 341