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