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 }; 58 } 59 char MachineCopyPropagation::ID = 0; 60 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 61 62 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 63 "Machine Copy Propagation Pass", false, false) 64 65 void 66 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 67 SourceMap &SrcMap, 68 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 69 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 70 SourceMap::iterator SI = SrcMap.find(*AI); 71 if (SI != SrcMap.end()) { 72 const DestList& Defs = SI->second; 73 for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 74 I != E; ++I) { 75 unsigned MappedDef = *I; 76 // Source of copy is no longer available for propagation. 77 AvailCopyMap.erase(MappedDef); 78 for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) 79 AvailCopyMap.erase(*SR); 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 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 130 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 131 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 132 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 133 SourceMap SrcMap; // Src -> Def map 134 135 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); 136 137 bool Changed = false; 138 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 139 MachineInstr *MI = &*I; 140 ++I; 141 142 if (MI->isCopy()) { 143 unsigned Def = MI->getOperand(0).getReg(); 144 unsigned Src = MI->getOperand(1).getReg(); 145 146 if (TargetRegisterInfo::isVirtualRegister(Def) || 147 TargetRegisterInfo::isVirtualRegister(Src)) 148 report_fatal_error("MachineCopyPropagation should be run after" 149 " register allocation!"); 150 151 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 152 if (CI != AvailCopyMap.end()) { 153 MachineInstr *CopyMI = CI->second; 154 if (!MRI->isReserved(Def) && 155 (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) && 156 isNopCopy(CopyMI, Def, Src, TRI)) { 157 // The two copies cancel out and the source of the first copy 158 // hasn't been overridden, eliminate the second one. e.g. 159 // %ECX<def> = COPY %EAX<kill> 160 // ... nothing clobbered EAX. 161 // %EAX<def> = COPY %ECX 162 // => 163 // %ECX<def> = COPY %EAX 164 // 165 // Also avoid eliminating a copy from reserved registers unless the 166 // definition is proven not clobbered. e.g. 167 // %RSP<def> = COPY %RAX 168 // CALL 169 // %RAX<def> = COPY %RSP 170 171 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; MI->dump()); 172 173 // Clear any kills of Def between CopyMI and MI. This extends the 174 // live range. 175 for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 176 I->clearRegisterKills(Def, TRI); 177 178 MI->eraseFromParent(); 179 Changed = true; 180 ++NumDeletes; 181 continue; 182 } 183 } 184 185 // If Src is defined by a previous copy, it cannot be eliminated. 186 for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { 187 CI = CopyMap.find(*AI); 188 if (CI != CopyMap.end()) { 189 DEBUG(dbgs() << "MCP: Copy is no longer dead: "; CI->second->dump()); 190 MaybeDeadCopies.remove(CI->second); 191 } 192 } 193 194 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 195 196 // Copy is now a candidate for deletion. 197 MaybeDeadCopies.insert(MI); 198 199 // If 'Src' is previously source of another copy, then this earlier copy's 200 // source is no longer available. e.g. 201 // %xmm9<def> = copy %xmm2 202 // ... 203 // %xmm2<def> = copy %xmm0 204 // ... 205 // %xmm2<def> = copy %xmm9 206 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 207 208 // Remember Def is defined by the copy. 209 // ... Make sure to clear the def maps of aliases first. 210 for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) { 211 CopyMap.erase(*AI); 212 AvailCopyMap.erase(*AI); 213 } 214 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); 215 ++SR) { 216 CopyMap[*SR] = MI; 217 AvailCopyMap[*SR] = MI; 218 } 219 220 // Remember source that's copied to Def. Once it's clobbered, then 221 // it's no longer available for copy propagation. 222 if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == 223 SrcMap[Src].end()) { 224 SrcMap[Src].push_back(Def); 225 } 226 227 continue; 228 } 229 230 // Not a copy. 231 SmallVector<unsigned, 2> Defs; 232 int RegMaskOpNum = -1; 233 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 234 MachineOperand &MO = MI->getOperand(i); 235 if (MO.isRegMask()) 236 RegMaskOpNum = i; 237 if (!MO.isReg()) 238 continue; 239 unsigned Reg = MO.getReg(); 240 if (!Reg) 241 continue; 242 243 if (TargetRegisterInfo::isVirtualRegister(Reg)) 244 report_fatal_error("MachineCopyPropagation should be run after" 245 " register allocation!"); 246 247 if (MO.isDef()) { 248 Defs.push_back(Reg); 249 continue; 250 } 251 252 // If 'Reg' is defined by a copy, the copy is no longer a candidate 253 // for elimination. 254 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 255 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(*AI); 256 if (CI != CopyMap.end()) { 257 DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); 258 MaybeDeadCopies.remove(CI->second); 259 } 260 } 261 // Treat undef use like defs for copy propagation but not for 262 // dead copy. We would need to do a liveness check to be sure the copy 263 // is dead for undef uses. 264 // The backends are allowed to do whatever they want with undef value 265 // and we cannot be sure this register will not be rewritten to break 266 // some false dependencies for the hardware for instance. 267 if (MO.isUndef()) 268 Defs.push_back(Reg); 269 } 270 271 // The instruction has a register mask operand which means that it clobbers 272 // a large set of registers. It is possible to use the register mask to 273 // prune the available copies, but treat it like a basic block boundary for 274 // now. 275 if (RegMaskOpNum >= 0) { 276 // Erase any MaybeDeadCopies whose destination register is clobbered. 277 const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 278 for (SmallSetVector<MachineInstr*, 8>::iterator 279 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 280 DI != DE; ++DI) { 281 unsigned Reg = (*DI)->getOperand(0).getReg(); 282 if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg)) 283 continue; 284 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 285 (*DI)->dump()); 286 (*DI)->eraseFromParent(); 287 Changed = true; 288 ++NumDeletes; 289 } 290 291 // Clear all data structures as if we were beginning a new basic block. 292 MaybeDeadCopies.clear(); 293 AvailCopyMap.clear(); 294 CopyMap.clear(); 295 SrcMap.clear(); 296 continue; 297 } 298 299 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 300 unsigned Reg = Defs[i]; 301 302 // No longer defined by a copy. 303 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 304 CopyMap.erase(*AI); 305 AvailCopyMap.erase(*AI); 306 } 307 308 // If 'Reg' is previously source of a copy, it is no longer available for 309 // copy propagation. 310 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 311 } 312 } 313 314 // If MBB doesn't have successors, delete the copies whose defs are not used. 315 // If MBB does have successors, then conservative assume the defs are live-out 316 // since we don't want to trust live-in lists. 317 if (MBB.succ_empty()) { 318 for (SmallSetVector<MachineInstr*, 8>::iterator 319 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 320 DI != DE; ++DI) { 321 if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { 322 (*DI)->eraseFromParent(); 323 Changed = true; 324 ++NumDeletes; 325 } 326 } 327 } 328 329 return Changed; 330 } 331 332 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 333 if (skipOptnoneFunction(*MF.getFunction())) 334 return false; 335 336 bool Changed = false; 337 338 TRI = MF.getSubtarget().getRegisterInfo(); 339 TII = MF.getSubtarget().getInstrInfo(); 340 MRI = &MF.getRegInfo(); 341 342 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 343 Changed |= CopyPropagateBlock(*I); 344 345 return Changed; 346 } 347