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