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/raw_ostream.h" 25 #include "llvm/Target/TargetInstrInfo.h" 26 #include "llvm/Target/TargetRegisterInfo.h" 27 #include "llvm/Target/TargetSubtargetInfo.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "machine-cp" 31 32 STATISTIC(NumDeletes, "Number of dead copies deleted"); 33 34 namespace { 35 typedef SmallVector<unsigned, 4> RegList; 36 typedef DenseMap<unsigned, RegList> SourceMap; 37 typedef DenseMap<unsigned, MachineInstr*> Reg2MIMap; 38 39 class MachineCopyPropagation : public MachineFunctionPass { 40 const TargetRegisterInfo *TRI; 41 const TargetInstrInfo *TII; 42 const MachineRegisterInfo *MRI; 43 44 public: 45 static char ID; // Pass identification, replacement for typeid 46 MachineCopyPropagation() : MachineFunctionPass(ID) { 47 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 48 } 49 50 void getAnalysisUsage(AnalysisUsage &AU) const override { 51 AU.setPreservesCFG(); 52 MachineFunctionPass::getAnalysisUsage(AU); 53 } 54 55 bool runOnMachineFunction(MachineFunction &MF) override; 56 57 MachineFunctionProperties getRequiredProperties() const override { 58 return MachineFunctionProperties().set( 59 MachineFunctionProperties::Property::NoVRegs); 60 } 61 62 private: 63 void ClobberRegister(unsigned Reg); 64 void ReadRegister(unsigned Reg); 65 void CopyPropagateBlock(MachineBasicBlock &MBB); 66 bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def); 67 68 /// Candidates for deletion. 69 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; 70 /// Def -> available copies map. 71 Reg2MIMap AvailCopyMap; 72 /// Def -> copies map. 73 Reg2MIMap CopyMap; 74 /// Src -> Def map 75 SourceMap SrcMap; 76 bool Changed; 77 }; 78 } 79 char MachineCopyPropagation::ID = 0; 80 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 81 82 INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE, 83 "Machine Copy Propagation Pass", false, false) 84 85 /// Remove any entry in \p Map where the register is a subregister or equal to 86 /// a register contained in \p Regs. 87 static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs, 88 const TargetRegisterInfo &TRI) { 89 for (unsigned Reg : Regs) { 90 // Source of copy is no longer available for propagation. 91 for (MCSubRegIterator SR(Reg, &TRI, true); SR.isValid(); ++SR) 92 Map.erase(*SR); 93 } 94 } 95 96 /// Remove any entry in \p Map that is marked clobbered in \p RegMask. 97 /// The map will typically have a lot fewer entries than the regmask clobbers, 98 /// so this is more efficient than iterating the clobbered registers and calling 99 /// ClobberRegister() on them. 100 static void removeClobberedRegsFromMap(Reg2MIMap &Map, 101 const MachineOperand &RegMask) { 102 for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E; 103 I = Next) { 104 Next = std::next(I); 105 unsigned Reg = I->first; 106 if (RegMask.clobbersPhysReg(Reg)) 107 Map.erase(I); 108 } 109 } 110 111 void MachineCopyPropagation::ClobberRegister(unsigned Reg) { 112 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 113 CopyMap.erase(*AI); 114 AvailCopyMap.erase(*AI); 115 116 SourceMap::iterator SI = SrcMap.find(*AI); 117 if (SI != SrcMap.end()) { 118 removeRegsFromMap(AvailCopyMap, SI->second, *TRI); 119 SrcMap.erase(SI); 120 } 121 } 122 } 123 124 void MachineCopyPropagation::ReadRegister(unsigned Reg) { 125 // If 'Reg' is defined by a copy, the copy is no longer a candidate 126 // for elimination. 127 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 128 Reg2MIMap::iterator CI = CopyMap.find(*AI); 129 if (CI != CopyMap.end()) { 130 DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); 131 MaybeDeadCopies.remove(CI->second); 132 } 133 } 134 } 135 136 /// Return true if \p PreviousCopy did copy register \p Src to register \p Def. 137 /// This fact may have been obscured by sub register usage or may not be true at 138 /// all even though Src and Def are subregisters of the registers used in 139 /// PreviousCopy. e.g. 140 /// isNopCopy("ecx = COPY eax", AX, CX) == true 141 /// isNopCopy("ecx = COPY eax", AH, CL) == false 142 static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src, 143 unsigned Def, const TargetRegisterInfo *TRI) { 144 unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg(); 145 unsigned PreviousDef = PreviousCopy.getOperand(0).getReg(); 146 if (Src == PreviousSrc) { 147 assert(Def == PreviousDef); 148 return true; 149 } 150 if (!TRI->isSubRegister(PreviousSrc, Src)) 151 return false; 152 unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src); 153 return SubIdx == TRI->getSubRegIndex(PreviousDef, Def); 154 } 155 156 /// Remove instruction \p Copy if there exists a previous copy that copies the 157 /// register \p Src to the register \p Def; This may happen indirectly by 158 /// copying the super registers. 159 bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src, 160 unsigned Def) { 161 // Avoid eliminating a copy from/to a reserved registers as we cannot predict 162 // the value (Example: The sparc zero register is writable but stays zero). 163 if (MRI->isReserved(Src) || MRI->isReserved(Def)) 164 return false; 165 166 // Search for an existing copy. 167 Reg2MIMap::iterator CI = AvailCopyMap.find(Def); 168 if (CI == AvailCopyMap.end()) 169 return false; 170 171 // Check that the existing copy uses the correct sub registers. 172 MachineInstr &PrevCopy = *CI->second; 173 if (!isNopCopy(PrevCopy, Src, Def, TRI)) 174 return false; 175 176 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); 177 178 // Copy was redundantly redefining either Src or Def. Remove earlier kill 179 // flags between Copy and PrevCopy because the value will be reused now. 180 assert(Copy.isCopy()); 181 unsigned CopyDef = Copy.getOperand(0).getReg(); 182 assert(CopyDef == Src || CopyDef == Def); 183 for (MachineInstr &MI : 184 make_range(PrevCopy.getIterator(), Copy.getIterator())) 185 MI.clearRegisterKills(CopyDef, TRI); 186 187 Copy.eraseFromParent(); 188 Changed = true; 189 ++NumDeletes; 190 return true; 191 } 192 193 void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 194 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); 195 196 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 197 MachineInstr *MI = &*I; 198 ++I; 199 200 if (MI->isCopy()) { 201 unsigned Def = MI->getOperand(0).getReg(); 202 unsigned Src = MI->getOperand(1).getReg(); 203 204 assert(!TargetRegisterInfo::isVirtualRegister(Def) && 205 !TargetRegisterInfo::isVirtualRegister(Src) && 206 "MachineCopyPropagation should be run after register allocation!"); 207 208 // The two copies cancel out and the source of the first copy 209 // hasn't been overridden, eliminate the second one. e.g. 210 // %ECX<def> = COPY %EAX 211 // ... nothing clobbered EAX. 212 // %EAX<def> = COPY %ECX 213 // => 214 // %ECX<def> = COPY %EAX 215 // 216 // or 217 // 218 // %ECX<def> = COPY %EAX 219 // ... nothing clobbered EAX. 220 // %ECX<def> = COPY %EAX 221 // => 222 // %ECX<def> = COPY %EAX 223 if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def)) 224 continue; 225 226 // If Src is defined by a previous copy, the previous copy cannot be 227 // eliminated. 228 ReadRegister(Src); 229 for (const MachineOperand &MO : MI->implicit_operands()) { 230 if (!MO.isReg() || !MO.readsReg()) 231 continue; 232 unsigned Reg = MO.getReg(); 233 if (!Reg) 234 continue; 235 ReadRegister(Reg); 236 } 237 238 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 239 240 // Copy is now a candidate for deletion. 241 if (!MRI->isReserved(Def)) 242 MaybeDeadCopies.insert(MI); 243 244 // If 'Def' is previously source of another copy, then this earlier copy's 245 // source is no longer available. e.g. 246 // %xmm9<def> = copy %xmm2 247 // ... 248 // %xmm2<def> = copy %xmm0 249 // ... 250 // %xmm2<def> = copy %xmm9 251 ClobberRegister(Def); 252 for (const MachineOperand &MO : MI->implicit_operands()) { 253 if (!MO.isReg() || !MO.isDef()) 254 continue; 255 unsigned Reg = MO.getReg(); 256 if (!Reg) 257 continue; 258 ClobberRegister(Reg); 259 } 260 261 // Remember Def is defined by the copy. 262 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); 263 ++SR) { 264 CopyMap[*SR] = MI; 265 AvailCopyMap[*SR] = MI; 266 } 267 268 // Remember source that's copied to Def. Once it's clobbered, then 269 // it's no longer available for copy propagation. 270 RegList &DestList = SrcMap[Src]; 271 if (!is_contained(DestList, Def)) 272 DestList.push_back(Def); 273 274 continue; 275 } 276 277 // Not a copy. 278 SmallVector<unsigned, 2> Defs; 279 const MachineOperand *RegMask = nullptr; 280 for (const MachineOperand &MO : MI->operands()) { 281 if (MO.isRegMask()) 282 RegMask = &MO; 283 if (!MO.isReg()) 284 continue; 285 unsigned Reg = MO.getReg(); 286 if (!Reg) 287 continue; 288 289 assert(!TargetRegisterInfo::isVirtualRegister(Reg) && 290 "MachineCopyPropagation should be run after register allocation!"); 291 292 if (MO.isDef()) { 293 Defs.push_back(Reg); 294 continue; 295 } else if (MO.readsReg()) 296 ReadRegister(Reg); 297 } 298 299 // The instruction has a register mask operand which means that it clobbers 300 // a large set of registers. Treat clobbered registers the same way as 301 // defined registers. 302 if (RegMask) { 303 // Erase any MaybeDeadCopies whose destination register is clobbered. 304 for (SmallSetVector<MachineInstr *, 8>::iterator DI = 305 MaybeDeadCopies.begin(); 306 DI != MaybeDeadCopies.end();) { 307 MachineInstr *MaybeDead = *DI; 308 unsigned Reg = MaybeDead->getOperand(0).getReg(); 309 assert(!MRI->isReserved(Reg)); 310 311 if (!RegMask->clobbersPhysReg(Reg)) { 312 ++DI; 313 continue; 314 } 315 316 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 317 MaybeDead->dump()); 318 319 // erase() will return the next valid iterator pointing to the next 320 // element after the erased one. 321 DI = MaybeDeadCopies.erase(DI); 322 MaybeDead->eraseFromParent(); 323 Changed = true; 324 ++NumDeletes; 325 } 326 327 removeClobberedRegsFromMap(AvailCopyMap, *RegMask); 328 removeClobberedRegsFromMap(CopyMap, *RegMask); 329 for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next; 330 I != E; I = Next) { 331 Next = std::next(I); 332 if (RegMask->clobbersPhysReg(I->first)) { 333 removeRegsFromMap(AvailCopyMap, I->second, *TRI); 334 SrcMap.erase(I); 335 } 336 } 337 } 338 339 // Any previous copy definition or reading the Defs is no longer available. 340 for (unsigned Reg : Defs) 341 ClobberRegister(Reg); 342 } 343 344 // If MBB doesn't have successors, delete the copies whose defs are not used. 345 // If MBB does have successors, then conservative assume the defs are live-out 346 // since we don't want to trust live-in lists. 347 if (MBB.succ_empty()) { 348 for (MachineInstr *MaybeDead : MaybeDeadCopies) { 349 assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg())); 350 MaybeDead->eraseFromParent(); 351 Changed = true; 352 ++NumDeletes; 353 } 354 } 355 356 MaybeDeadCopies.clear(); 357 AvailCopyMap.clear(); 358 CopyMap.clear(); 359 SrcMap.clear(); 360 } 361 362 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 363 if (skipFunction(*MF.getFunction())) 364 return false; 365 366 Changed = false; 367 368 TRI = MF.getSubtarget().getRegisterInfo(); 369 TII = MF.getSubtarget().getInstrInfo(); 370 MRI = &MF.getRegInfo(); 371 372 for (MachineBasicBlock &MBB : MF) 373 CopyPropagateBlock(MBB); 374 375 return Changed; 376 } 377 378