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/ADT/DenseMap.h" 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineFunctionPass.h" 22 #include "llvm/CodeGen/MachineRegisterInfo.h" 23 #include "llvm/Pass.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/ErrorHandling.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/Target/TargetInstrInfo.h" 28 #include "llvm/Target/TargetRegisterInfo.h" 29 using namespace llvm; 30 31 STATISTIC(NumDeletes, "Number of dead copies deleted"); 32 33 namespace { 34 class MachineCopyPropagation : public MachineFunctionPass { 35 const TargetRegisterInfo *TRI; 36 const TargetInstrInfo *TII; 37 MachineRegisterInfo *MRI; 38 39 public: 40 static char ID; // Pass identification, replacement for typeid 41 MachineCopyPropagation() : MachineFunctionPass(ID) { 42 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 43 } 44 45 bool runOnMachineFunction(MachineFunction &MF) override; 46 47 private: 48 typedef SmallVector<unsigned, 4> DestList; 49 typedef DenseMap<unsigned, DestList> SourceMap; 50 51 void SourceNoLongerAvailable(unsigned Reg, 52 SourceMap &SrcMap, 53 DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 54 bool CopyPropagateBlock(MachineBasicBlock &MBB); 55 void removeCopy(MachineInstr *MI); 56 }; 57 } 58 char MachineCopyPropagation::ID = 0; 59 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 60 61 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 62 "Machine Copy Propagation Pass", false, false) 63 64 void 65 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 66 SourceMap &SrcMap, 67 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 68 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 69 SourceMap::iterator SI = SrcMap.find(*AI); 70 if (SI != SrcMap.end()) { 71 const DestList& Defs = SI->second; 72 for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 73 I != E; ++I) { 74 unsigned MappedDef = *I; 75 // Source of copy is no longer available for propagation. 76 if (AvailCopyMap.erase(MappedDef)) { 77 for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) 78 AvailCopyMap.erase(*SR); 79 } 80 } 81 } 82 } 83 } 84 85 static bool NoInterveningSideEffect(const MachineInstr *CopyMI, 86 const MachineInstr *MI) { 87 const MachineBasicBlock *MBB = CopyMI->getParent(); 88 if (MI->getParent() != MBB) 89 return false; 90 MachineBasicBlock::const_iterator I = CopyMI; 91 MachineBasicBlock::const_iterator E = MBB->end(); 92 MachineBasicBlock::const_iterator E2 = MI; 93 94 ++I; 95 while (I != E && I != E2) { 96 if (I->hasUnmodeledSideEffects() || I->isCall() || 97 I->isTerminator()) 98 return false; 99 ++I; 100 } 101 return true; 102 } 103 104 /// isNopCopy - Return true if the specified copy is really a nop. That is 105 /// if the source of the copy is the same of the definition of the copy that 106 /// supplied the source. If the source of the copy is a sub-register than it 107 /// must check the sub-indices match. e.g. 108 /// ecx = mov eax 109 /// al = mov cl 110 /// But not 111 /// ecx = mov eax 112 /// al = mov ch 113 static bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src, 114 const TargetRegisterInfo *TRI) { 115 unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 116 if (Def == SrcSrc) 117 return true; 118 if (TRI->isSubRegister(SrcSrc, Def)) { 119 unsigned SrcDef = CopyMI->getOperand(0).getReg(); 120 unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def); 121 if (!SubIdx) 122 return false; 123 return SubIdx == TRI->getSubRegIndex(SrcDef, Src); 124 } 125 126 return false; 127 } 128 129 // Remove MI from the function because it has been determined it is dead. 130 // Turn it into a noop KILL instruction as opposed to removing it to 131 // maintain imp-use/imp-def chains. 132 void MachineCopyPropagation::removeCopy(MachineInstr *MI) { 133 MI->setDesc(TII->get(TargetOpcode::KILL)); 134 } 135 136 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 137 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 138 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 139 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 140 SourceMap SrcMap; // Src -> Def map 141 142 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); 143 144 bool Changed = false; 145 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 146 MachineInstr *MI = &*I; 147 ++I; 148 149 if (MI->isCopy()) { 150 unsigned Def = MI->getOperand(0).getReg(); 151 unsigned Src = MI->getOperand(1).getReg(); 152 153 if (TargetRegisterInfo::isVirtualRegister(Def) || 154 TargetRegisterInfo::isVirtualRegister(Src)) 155 report_fatal_error("MachineCopyPropagation should be run after" 156 " register allocation!"); 157 158 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 159 if (CI != AvailCopyMap.end()) { 160 MachineInstr *CopyMI = CI->second; 161 if (!MRI->isReserved(Def) && 162 (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) && 163 isNopCopy(CopyMI, Def, Src, TRI)) { 164 // The two copies cancel out and the source of the first copy 165 // hasn't been overridden, eliminate the second one. e.g. 166 // %ECX<def> = COPY %EAX<kill> 167 // ... nothing clobbered EAX. 168 // %EAX<def> = COPY %ECX 169 // => 170 // %ECX<def> = COPY %EAX 171 // 172 // Also avoid eliminating a copy from reserved registers unless the 173 // definition is proven not clobbered. e.g. 174 // %RSP<def> = COPY %RAX 175 // CALL 176 // %RAX<def> = COPY %RSP 177 178 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; MI->dump()); 179 180 // Clear any kills of Def between CopyMI and MI. This extends the 181 // live range. 182 for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 183 I->clearRegisterKills(Def, TRI); 184 185 removeCopy(MI); 186 Changed = true; 187 ++NumDeletes; 188 continue; 189 } 190 } 191 192 // If Src is defined by a previous copy, it cannot be eliminated. 193 for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { 194 CI = CopyMap.find(*AI); 195 if (CI != CopyMap.end()) { 196 DEBUG(dbgs() << "MCP: Copy is no longer dead: "; CI->second->dump()); 197 MaybeDeadCopies.remove(CI->second); 198 } 199 } 200 201 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 202 203 // Copy is now a candidate for deletion. 204 MaybeDeadCopies.insert(MI); 205 206 // If 'Src' is previously source of another copy, then this earlier copy's 207 // source is no longer available. e.g. 208 // %xmm9<def> = copy %xmm2 209 // ... 210 // %xmm2<def> = copy %xmm0 211 // ... 212 // %xmm2<def> = copy %xmm9 213 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 214 215 // Remember Def is defined by the copy. 216 // ... Make sure to clear the def maps of aliases first. 217 for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) { 218 CopyMap.erase(*AI); 219 AvailCopyMap.erase(*AI); 220 } 221 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); 222 ++SR) { 223 CopyMap[*SR] = MI; 224 AvailCopyMap[*SR] = MI; 225 } 226 227 // Remember source that's copied to Def. Once it's clobbered, then 228 // it's no longer available for copy propagation. 229 if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == 230 SrcMap[Src].end()) { 231 SrcMap[Src].push_back(Def); 232 } 233 234 continue; 235 } 236 237 // Not a copy. 238 SmallVector<unsigned, 2> Defs; 239 int RegMaskOpNum = -1; 240 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 241 MachineOperand &MO = MI->getOperand(i); 242 if (MO.isRegMask()) 243 RegMaskOpNum = i; 244 if (!MO.isReg()) 245 continue; 246 unsigned Reg = MO.getReg(); 247 if (!Reg) 248 continue; 249 250 if (TargetRegisterInfo::isVirtualRegister(Reg)) 251 report_fatal_error("MachineCopyPropagation should be run after" 252 " register allocation!"); 253 254 if (MO.isDef()) { 255 Defs.push_back(Reg); 256 continue; 257 } 258 259 // If 'Reg' is defined by a copy, the copy is no longer a candidate 260 // for elimination. 261 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 262 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(*AI); 263 if (CI != CopyMap.end()) { 264 DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); 265 MaybeDeadCopies.remove(CI->second); 266 } 267 } 268 } 269 270 // The instruction has a register mask operand which means that it clobbers 271 // a large set of registers. It is possible to use the register mask to 272 // prune the available copies, but treat it like a basic block boundary for 273 // now. 274 if (RegMaskOpNum >= 0) { 275 // Erase any MaybeDeadCopies whose destination register is clobbered. 276 const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 277 for (SmallSetVector<MachineInstr*, 8>::iterator 278 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 279 DI != DE; ++DI) { 280 unsigned Reg = (*DI)->getOperand(0).getReg(); 281 if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg)) 282 continue; 283 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 284 (*DI)->dump()); 285 removeCopy(*DI); 286 Changed = true; 287 ++NumDeletes; 288 } 289 290 // Clear all data structures as if we were beginning a new basic block. 291 MaybeDeadCopies.clear(); 292 AvailCopyMap.clear(); 293 CopyMap.clear(); 294 SrcMap.clear(); 295 continue; 296 } 297 298 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 299 unsigned Reg = Defs[i]; 300 301 // No longer defined by a copy. 302 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 303 CopyMap.erase(*AI); 304 AvailCopyMap.erase(*AI); 305 } 306 307 // If 'Reg' is previously source of a copy, it is no longer available for 308 // copy propagation. 309 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 310 } 311 } 312 313 // If MBB doesn't have successors, delete the copies whose defs are not used. 314 // If MBB does have successors, then conservative assume the defs are live-out 315 // since we don't want to trust live-in lists. 316 if (MBB.succ_empty()) { 317 for (SmallSetVector<MachineInstr*, 8>::iterator 318 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 319 DI != DE; ++DI) { 320 if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { 321 removeCopy(*DI); 322 Changed = true; 323 ++NumDeletes; 324 } 325 } 326 } 327 328 return Changed; 329 } 330 331 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 332 bool Changed = false; 333 334 TRI = MF.getTarget().getRegisterInfo(); 335 TII = MF.getTarget().getInstrInfo(); 336 MRI = &MF.getRegInfo(); 337 338 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 339 Changed |= CopyPropagateBlock(*I); 340 341 return Changed; 342 } 343