1 //===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This is an extremely simple MachineInstr-level copy propagation pass. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #define DEBUG_TYPE "codegen-cp" 15 #include "llvm/CodeGen/Passes.h" 16 #include "llvm/Pass.h" 17 #include "llvm/CodeGen/MachineFunction.h" 18 #include "llvm/CodeGen/MachineFunctionPass.h" 19 #include "llvm/Target/TargetRegisterInfo.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include "llvm/Support/raw_ostream.h" 23 #include "llvm/ADT/BitVector.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/SetVector.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/Statistic.h" 28 using namespace llvm; 29 30 STATISTIC(NumDeletes, "Number of dead copies deleted"); 31 32 namespace { 33 class MachineCopyPropagation : public MachineFunctionPass { 34 const TargetRegisterInfo *TRI; 35 BitVector ReservedRegs; 36 37 public: 38 static char ID; // Pass identification, replacement for typeid 39 MachineCopyPropagation() : MachineFunctionPass(ID) { 40 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 41 } 42 43 virtual bool runOnMachineFunction(MachineFunction &MF); 44 45 private: 46 void SourceNoLongerAvailable(unsigned Reg, 47 DenseMap<unsigned, unsigned> &SrcMap, 48 DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 49 bool CopyPropagateBlock(MachineBasicBlock &MBB); 50 }; 51 } 52 char MachineCopyPropagation::ID = 0; 53 54 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 55 "Machine Copy Propagation Pass", false, false) 56 57 FunctionPass *llvm::createMachineCopyPropagationPass() { 58 return new MachineCopyPropagation(); 59 } 60 61 void 62 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 63 DenseMap<unsigned, unsigned> &SrcMap, 64 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 65 DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg); 66 if (SI != SrcMap.end()) { 67 unsigned MappedDef = SI->second; 68 // Source of copy is no longer available for propagation. 69 if (AvailCopyMap.erase(MappedDef)) { 70 for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 71 AvailCopyMap.erase(*SR); 72 } 73 } 74 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 75 SI = SrcMap.find(*AS); 76 if (SI != SrcMap.end()) { 77 unsigned MappedDef = SI->second; 78 if (AvailCopyMap.erase(MappedDef)) { 79 for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 80 AvailCopyMap.erase(*SR); 81 } 82 } 83 } 84 } 85 86 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 87 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 88 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 89 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 90 DenseMap<unsigned, unsigned> SrcMap; // Src -> Def map 91 92 bool Changed = false; 93 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 94 MachineInstr *MI = &*I; 95 ++I; 96 97 if (MI->isCopy()) { 98 unsigned Def = MI->getOperand(0).getReg(); 99 unsigned Src = MI->getOperand(1).getReg(); 100 101 if (TargetRegisterInfo::isVirtualRegister(Def) || 102 TargetRegisterInfo::isVirtualRegister(Src)) 103 report_fatal_error("MachineCopyPropagation should be run after" 104 " register allocation!"); 105 106 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 107 if (CI != AvailCopyMap.end()) { 108 MachineInstr *CopyMI = CI->second; 109 unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 110 if (!ReservedRegs.test(Def) && 111 (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) { 112 // The two copies cancel out and the source of the first copy 113 // hasn't been overridden, eliminate the second one. e.g. 114 // %ECX<def> = COPY %EAX<kill> 115 // ... nothing clobbered EAX. 116 // %EAX<def> = COPY %ECX 117 // => 118 // %ECX<def> = COPY %EAX 119 CopyMI->getOperand(1).setIsKill(false); 120 MI->eraseFromParent(); 121 Changed = true; 122 ++NumDeletes; 123 continue; 124 } 125 } 126 127 // If Src is defined by a previous copy, it cannot be eliminated. 128 CI = CopyMap.find(Src); 129 if (CI != CopyMap.end()) 130 MaybeDeadCopies.remove(CI->second); 131 for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) { 132 CI = CopyMap.find(*AS); 133 if (CI != CopyMap.end()) 134 MaybeDeadCopies.remove(CI->second); 135 } 136 137 // Copy is now a candidate for deletion. 138 MaybeDeadCopies.insert(MI); 139 140 // If 'Src' is previously source of another copy, then this earlier copy's 141 // source is no longer available. e.g. 142 // %xmm9<def> = copy %xmm2 143 // ... 144 // %xmm2<def> = copy %xmm0 145 // ... 146 // %xmm2<def> = copy %xmm9 147 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 148 149 // Remember Def is defined by the copy. 150 CopyMap[Def] = MI; 151 AvailCopyMap[Def] = MI; 152 for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 153 CopyMap[*SR] = MI; 154 AvailCopyMap[*SR] = MI; 155 } 156 157 // Remember source that's copied to Def. Once it's clobbered, then 158 // it's no longer available for copy propagation. 159 SrcMap[Src] = Def; 160 161 continue; 162 } 163 164 // Not a copy. 165 SmallVector<unsigned, 2> Defs; 166 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 167 MachineOperand &MO = MI->getOperand(i); 168 if (!MO.isReg()) 169 continue; 170 unsigned Reg = MO.getReg(); 171 if (!Reg) 172 continue; 173 174 if (TargetRegisterInfo::isVirtualRegister(Reg)) 175 report_fatal_error("MachineCopyPropagation should be run after" 176 " register allocation!"); 177 178 if (MO.isDef()) { 179 Defs.push_back(Reg); 180 continue; 181 } 182 183 // If 'Reg' is defined by a copy, the copy is no longer a candidate 184 // for elimination. 185 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 186 if (CI != CopyMap.end()) 187 MaybeDeadCopies.remove(CI->second); 188 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 189 CI = CopyMap.find(*AS); 190 if (CI != CopyMap.end()) 191 MaybeDeadCopies.remove(CI->second); 192 } 193 } 194 195 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 196 unsigned Reg = Defs[i]; 197 198 // No longer defined by a copy. 199 CopyMap.erase(Reg); 200 AvailCopyMap.erase(Reg); 201 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 202 CopyMap.erase(*AS); 203 AvailCopyMap.erase(*AS); 204 } 205 206 // If 'Reg' is previously source of a copy, it is no longer available for 207 // copy propagation. 208 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 209 } 210 } 211 212 // If MBB doesn't have successors, delete the copies whose defs are not used. 213 // If MBB does have successors, then conservative assume the defs are live-out 214 // since we don't want to trust live-in lists. 215 if (MBB.succ_empty()) { 216 for (SmallSetVector<MachineInstr*, 8>::iterator 217 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 218 DI != DE; ++DI) { 219 if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 220 (*DI)->eraseFromParent(); 221 Changed = true; 222 ++NumDeletes; 223 } 224 } 225 } 226 227 return Changed; 228 } 229 230 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 231 bool Changed = false; 232 233 TRI = MF.getTarget().getRegisterInfo(); 234 ReservedRegs = TRI->getReservedRegs(MF); 235 236 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 237 Changed |= CopyPropagateBlock(*I); 238 239 return Changed; 240 } 241