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