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