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/MC/MCRegisterInfo.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include "llvm/Target/TargetInstrInfo.h" 31 #include "llvm/Target/TargetRegisterInfo.h" 32 #include "llvm/Target/TargetSubtargetInfo.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 (!isNopCopy(PrevCopy, Src, Def, TRI)) 191 return false; 192 193 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump()); 194 195 // Copy was redundantly redefining either Src or Def. Remove earlier kill 196 // flags between Copy and PrevCopy because the value will be reused now. 197 assert(Copy.isCopy()); 198 unsigned CopyDef = Copy.getOperand(0).getReg(); 199 assert(CopyDef == Src || CopyDef == Def); 200 for (MachineInstr &MI : 201 make_range(PrevCopy.getIterator(), Copy.getIterator())) 202 MI.clearRegisterKills(CopyDef, TRI); 203 204 Copy.eraseFromParent(); 205 Changed = true; 206 ++NumDeletes; 207 return true; 208 } 209 210 void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 211 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); 212 213 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 214 MachineInstr *MI = &*I; 215 ++I; 216 217 if (MI->isCopy()) { 218 unsigned Def = MI->getOperand(0).getReg(); 219 unsigned Src = MI->getOperand(1).getReg(); 220 221 assert(!TargetRegisterInfo::isVirtualRegister(Def) && 222 !TargetRegisterInfo::isVirtualRegister(Src) && 223 "MachineCopyPropagation should be run after register allocation!"); 224 225 // The two copies cancel out and the source of the first copy 226 // hasn't been overridden, eliminate the second one. e.g. 227 // %ECX<def> = COPY %EAX 228 // ... nothing clobbered EAX. 229 // %EAX<def> = COPY %ECX 230 // => 231 // %ECX<def> = COPY %EAX 232 // 233 // or 234 // 235 // %ECX<def> = COPY %EAX 236 // ... nothing clobbered EAX. 237 // %ECX<def> = COPY %EAX 238 // => 239 // %ECX<def> = COPY %EAX 240 if (eraseIfRedundant(*MI, Def, Src) || eraseIfRedundant(*MI, Src, Def)) 241 continue; 242 243 // If Src is defined by a previous copy, the previous copy cannot be 244 // eliminated. 245 ReadRegister(Src); 246 for (const MachineOperand &MO : MI->implicit_operands()) { 247 if (!MO.isReg() || !MO.readsReg()) 248 continue; 249 unsigned Reg = MO.getReg(); 250 if (!Reg) 251 continue; 252 ReadRegister(Reg); 253 } 254 255 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 256 257 // Copy is now a candidate for deletion. 258 if (!MRI->isReserved(Def)) 259 MaybeDeadCopies.insert(MI); 260 261 // If 'Def' is previously source of another copy, then this earlier copy's 262 // source is no longer available. e.g. 263 // %xmm9<def> = copy %xmm2 264 // ... 265 // %xmm2<def> = copy %xmm0 266 // ... 267 // %xmm2<def> = copy %xmm9 268 ClobberRegister(Def); 269 for (const MachineOperand &MO : MI->implicit_operands()) { 270 if (!MO.isReg() || !MO.isDef()) 271 continue; 272 unsigned Reg = MO.getReg(); 273 if (!Reg) 274 continue; 275 ClobberRegister(Reg); 276 } 277 278 // Remember Def is defined by the copy. 279 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); 280 ++SR) { 281 CopyMap[*SR] = MI; 282 AvailCopyMap[*SR] = MI; 283 } 284 285 // Remember source that's copied to Def. Once it's clobbered, then 286 // it's no longer available for copy propagation. 287 RegList &DestList = SrcMap[Src]; 288 if (!is_contained(DestList, Def)) 289 DestList.push_back(Def); 290 291 continue; 292 } 293 294 // Not a copy. 295 SmallVector<unsigned, 2> Defs; 296 const MachineOperand *RegMask = nullptr; 297 for (const MachineOperand &MO : MI->operands()) { 298 if (MO.isRegMask()) 299 RegMask = &MO; 300 if (!MO.isReg()) 301 continue; 302 unsigned Reg = MO.getReg(); 303 if (!Reg) 304 continue; 305 306 assert(!TargetRegisterInfo::isVirtualRegister(Reg) && 307 "MachineCopyPropagation should be run after register allocation!"); 308 309 if (MO.isDef()) { 310 Defs.push_back(Reg); 311 continue; 312 } else if (MO.readsReg()) 313 ReadRegister(Reg); 314 } 315 316 // The instruction has a register mask operand which means that it clobbers 317 // a large set of registers. Treat clobbered registers the same way as 318 // defined registers. 319 if (RegMask) { 320 // Erase any MaybeDeadCopies whose destination register is clobbered. 321 for (SmallSetVector<MachineInstr *, 8>::iterator DI = 322 MaybeDeadCopies.begin(); 323 DI != MaybeDeadCopies.end();) { 324 MachineInstr *MaybeDead = *DI; 325 unsigned Reg = MaybeDead->getOperand(0).getReg(); 326 assert(!MRI->isReserved(Reg)); 327 328 if (!RegMask->clobbersPhysReg(Reg)) { 329 ++DI; 330 continue; 331 } 332 333 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 334 MaybeDead->dump()); 335 336 // erase() will return the next valid iterator pointing to the next 337 // element after the erased one. 338 DI = MaybeDeadCopies.erase(DI); 339 MaybeDead->eraseFromParent(); 340 Changed = true; 341 ++NumDeletes; 342 } 343 344 removeClobberedRegsFromMap(AvailCopyMap, *RegMask); 345 removeClobberedRegsFromMap(CopyMap, *RegMask); 346 for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next; 347 I != E; I = Next) { 348 Next = std::next(I); 349 if (RegMask->clobbersPhysReg(I->first)) { 350 removeRegsFromMap(AvailCopyMap, I->second, *TRI); 351 SrcMap.erase(I); 352 } 353 } 354 } 355 356 // Any previous copy definition or reading the Defs is no longer available. 357 for (unsigned Reg : Defs) 358 ClobberRegister(Reg); 359 } 360 361 // If MBB doesn't have successors, delete the copies whose defs are not used. 362 // If MBB does have successors, then conservative assume the defs are live-out 363 // since we don't want to trust live-in lists. 364 if (MBB.succ_empty()) { 365 for (MachineInstr *MaybeDead : MaybeDeadCopies) { 366 assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg())); 367 MaybeDead->eraseFromParent(); 368 Changed = true; 369 ++NumDeletes; 370 } 371 } 372 373 MaybeDeadCopies.clear(); 374 AvailCopyMap.clear(); 375 CopyMap.clear(); 376 SrcMap.clear(); 377 } 378 379 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 380 if (skipFunction(*MF.getFunction())) 381 return false; 382 383 Changed = false; 384 385 TRI = MF.getSubtarget().getRegisterInfo(); 386 TII = MF.getSubtarget().getInstrInfo(); 387 MRI = &MF.getRegInfo(); 388 389 for (MachineBasicBlock &MBB : MF) 390 CopyPropagateBlock(MBB); 391 392 return Changed; 393 } 394