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