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/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include "llvm/Target/TargetInstrInfo.h" 27 #include "llvm/Target/TargetRegisterInfo.h" 28 #include "llvm/Target/TargetSubtargetInfo.h" 29 using namespace llvm; 30 31 #define DEBUG_TYPE "codegen-cp" 32 33 STATISTIC(NumDeletes, "Number of dead copies deleted"); 34 35 namespace { 36 class MachineCopyPropagation : public MachineFunctionPass { 37 const TargetRegisterInfo *TRI; 38 const TargetInstrInfo *TII; 39 MachineRegisterInfo *MRI; 40 41 public: 42 static char ID; // Pass identification, replacement for typeid 43 MachineCopyPropagation() : MachineFunctionPass(ID) { 44 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 45 } 46 47 bool runOnMachineFunction(MachineFunction &MF) override; 48 49 private: 50 typedef SmallVector<unsigned, 4> DestList; 51 typedef DenseMap<unsigned, DestList> SourceMap; 52 53 void SourceNoLongerAvailable(unsigned Reg, 54 SourceMap &SrcMap, 55 DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 56 bool CopyPropagateBlock(MachineBasicBlock &MBB); 57 void removeCopy(MachineInstr *MI); 58 }; 59 } 60 char MachineCopyPropagation::ID = 0; 61 char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 62 63 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 64 "Machine Copy Propagation Pass", false, false) 65 66 void 67 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 68 SourceMap &SrcMap, 69 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 70 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 71 SourceMap::iterator SI = SrcMap.find(*AI); 72 if (SI != SrcMap.end()) { 73 const DestList& Defs = SI->second; 74 for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 75 I != E; ++I) { 76 unsigned MappedDef = *I; 77 // Source of copy is no longer available for propagation. 78 if (AvailCopyMap.erase(MappedDef)) { 79 for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) 80 AvailCopyMap.erase(*SR); 81 } 82 } 83 } 84 } 85 } 86 87 static bool NoInterveningSideEffect(const MachineInstr *CopyMI, 88 const MachineInstr *MI) { 89 const MachineBasicBlock *MBB = CopyMI->getParent(); 90 if (MI->getParent() != MBB) 91 return false; 92 MachineBasicBlock::const_iterator I = CopyMI; 93 MachineBasicBlock::const_iterator E = MBB->end(); 94 MachineBasicBlock::const_iterator E2 = MI; 95 96 ++I; 97 while (I != E && I != E2) { 98 if (I->hasUnmodeledSideEffects() || I->isCall() || 99 I->isTerminator()) 100 return false; 101 ++I; 102 } 103 return true; 104 } 105 106 /// isNopCopy - Return true if the specified copy is really a nop. That is 107 /// if the source of the copy is the same of the definition of the copy that 108 /// supplied the source. If the source of the copy is a sub-register than it 109 /// must check the sub-indices match. e.g. 110 /// ecx = mov eax 111 /// al = mov cl 112 /// But not 113 /// ecx = mov eax 114 /// al = mov ch 115 static bool isNopCopy(MachineInstr *CopyMI, unsigned Def, unsigned Src, 116 const TargetRegisterInfo *TRI) { 117 unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 118 if (Def == SrcSrc) 119 return true; 120 if (TRI->isSubRegister(SrcSrc, Def)) { 121 unsigned SrcDef = CopyMI->getOperand(0).getReg(); 122 unsigned SubIdx = TRI->getSubRegIndex(SrcSrc, Def); 123 if (!SubIdx) 124 return false; 125 return SubIdx == TRI->getSubRegIndex(SrcDef, Src); 126 } 127 128 return false; 129 } 130 131 // Remove MI from the function because it has been determined it is dead. 132 // Turn it into a noop KILL instruction as opposed to removing it to 133 // maintain imp-use/imp-def chains. 134 void MachineCopyPropagation::removeCopy(MachineInstr *MI) { 135 MI->setDesc(TII->get(TargetOpcode::KILL)); 136 } 137 138 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 139 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 140 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 141 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 142 SourceMap SrcMap; // Src -> Def map 143 144 DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n"); 145 146 bool Changed = false; 147 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 148 MachineInstr *MI = &*I; 149 ++I; 150 151 if (MI->isCopy()) { 152 unsigned Def = MI->getOperand(0).getReg(); 153 unsigned Src = MI->getOperand(1).getReg(); 154 155 if (TargetRegisterInfo::isVirtualRegister(Def) || 156 TargetRegisterInfo::isVirtualRegister(Src)) 157 report_fatal_error("MachineCopyPropagation should be run after" 158 " register allocation!"); 159 160 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 161 if (CI != AvailCopyMap.end()) { 162 MachineInstr *CopyMI = CI->second; 163 if (!MRI->isReserved(Def) && 164 (!MRI->isReserved(Src) || NoInterveningSideEffect(CopyMI, MI)) && 165 isNopCopy(CopyMI, Def, Src, TRI)) { 166 // The two copies cancel out and the source of the first copy 167 // hasn't been overridden, eliminate the second one. e.g. 168 // %ECX<def> = COPY %EAX<kill> 169 // ... nothing clobbered EAX. 170 // %EAX<def> = COPY %ECX 171 // => 172 // %ECX<def> = COPY %EAX 173 // 174 // Also avoid eliminating a copy from reserved registers unless the 175 // definition is proven not clobbered. e.g. 176 // %RSP<def> = COPY %RAX 177 // CALL 178 // %RAX<def> = COPY %RSP 179 180 DEBUG(dbgs() << "MCP: copy is a NOP, removing: "; MI->dump()); 181 182 // Clear any kills of Def between CopyMI and MI. This extends the 183 // live range. 184 for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 185 I->clearRegisterKills(Def, TRI); 186 187 removeCopy(MI); 188 Changed = true; 189 ++NumDeletes; 190 continue; 191 } 192 } 193 194 // If Src is defined by a previous copy, it cannot be eliminated. 195 for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { 196 CI = CopyMap.find(*AI); 197 if (CI != CopyMap.end()) { 198 DEBUG(dbgs() << "MCP: Copy is no longer dead: "; CI->second->dump()); 199 MaybeDeadCopies.remove(CI->second); 200 } 201 } 202 203 DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump()); 204 205 // Copy is now a candidate for deletion. 206 MaybeDeadCopies.insert(MI); 207 208 // If 'Src' is previously source of another copy, then this earlier copy's 209 // source is no longer available. e.g. 210 // %xmm9<def> = copy %xmm2 211 // ... 212 // %xmm2<def> = copy %xmm0 213 // ... 214 // %xmm2<def> = copy %xmm9 215 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 216 217 // Remember Def is defined by the copy. 218 // ... Make sure to clear the def maps of aliases first. 219 for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) { 220 CopyMap.erase(*AI); 221 AvailCopyMap.erase(*AI); 222 } 223 for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid(); 224 ++SR) { 225 CopyMap[*SR] = MI; 226 AvailCopyMap[*SR] = MI; 227 } 228 229 // Remember source that's copied to Def. Once it's clobbered, then 230 // it's no longer available for copy propagation. 231 if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == 232 SrcMap[Src].end()) { 233 SrcMap[Src].push_back(Def); 234 } 235 236 continue; 237 } 238 239 // Not a copy. 240 SmallVector<unsigned, 2> Defs; 241 int RegMaskOpNum = -1; 242 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 243 MachineOperand &MO = MI->getOperand(i); 244 if (MO.isRegMask()) 245 RegMaskOpNum = i; 246 if (!MO.isReg()) 247 continue; 248 unsigned Reg = MO.getReg(); 249 if (!Reg) 250 continue; 251 252 if (TargetRegisterInfo::isVirtualRegister(Reg)) 253 report_fatal_error("MachineCopyPropagation should be run after" 254 " register allocation!"); 255 256 if (MO.isDef()) { 257 Defs.push_back(Reg); 258 continue; 259 } 260 261 // If 'Reg' is defined by a copy, the copy is no longer a candidate 262 // for elimination. 263 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 264 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(*AI); 265 if (CI != CopyMap.end()) { 266 DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump()); 267 MaybeDeadCopies.remove(CI->second); 268 } 269 } 270 } 271 272 // The instruction has a register mask operand which means that it clobbers 273 // a large set of registers. It is possible to use the register mask to 274 // prune the available copies, but treat it like a basic block boundary for 275 // now. 276 if (RegMaskOpNum >= 0) { 277 // Erase any MaybeDeadCopies whose destination register is clobbered. 278 const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 279 for (SmallSetVector<MachineInstr*, 8>::iterator 280 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 281 DI != DE; ++DI) { 282 unsigned Reg = (*DI)->getOperand(0).getReg(); 283 if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg)) 284 continue; 285 DEBUG(dbgs() << "MCP: Removing copy due to regmask clobbering: "; 286 (*DI)->dump()); 287 removeCopy(*DI); 288 Changed = true; 289 ++NumDeletes; 290 } 291 292 // Clear all data structures as if we were beginning a new basic block. 293 MaybeDeadCopies.clear(); 294 AvailCopyMap.clear(); 295 CopyMap.clear(); 296 SrcMap.clear(); 297 continue; 298 } 299 300 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 301 unsigned Reg = Defs[i]; 302 303 // No longer defined by a copy. 304 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 305 CopyMap.erase(*AI); 306 AvailCopyMap.erase(*AI); 307 } 308 309 // If 'Reg' is previously source of a copy, it is no longer available for 310 // copy propagation. 311 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 312 } 313 } 314 315 // If MBB doesn't have successors, delete the copies whose defs are not used. 316 // If MBB does have successors, then conservative assume the defs are live-out 317 // since we don't want to trust live-in lists. 318 if (MBB.succ_empty()) { 319 for (SmallSetVector<MachineInstr*, 8>::iterator 320 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 321 DI != DE; ++DI) { 322 if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { 323 removeCopy(*DI); 324 Changed = true; 325 ++NumDeletes; 326 } 327 } 328 } 329 330 return Changed; 331 } 332 333 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 334 if (skipOptnoneFunction(*MF.getFunction())) 335 return false; 336 337 bool Changed = false; 338 339 TRI = MF.getSubtarget().getRegisterInfo(); 340 TII = MF.getSubtarget().getInstrInfo(); 341 MRI = &MF.getRegInfo(); 342 343 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 344 Changed |= CopyPropagateBlock(*I); 345 346 return Changed; 347 } 348