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