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 #define DEBUG_TYPE "codegen-cp" 15 #include "llvm/CodeGen/Passes.h" 16 #include "llvm/Pass.h" 17 #include "llvm/CodeGen/MachineFunction.h" 18 #include "llvm/CodeGen/MachineFunctionPass.h" 19 #include "llvm/Target/TargetRegisterInfo.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include "llvm/Support/raw_ostream.h" 23 #include "llvm/ADT/BitVector.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/SetVector.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/Statistic.h" 28 using namespace llvm; 29 30 STATISTIC(NumDeletes, "Number of dead copies deleted"); 31 32 namespace { 33 class MachineCopyPropagation : public MachineFunctionPass { 34 const TargetRegisterInfo *TRI; 35 BitVector ReservedRegs; 36 37 public: 38 static char ID; // Pass identification, replacement for typeid 39 MachineCopyPropagation() : MachineFunctionPass(ID) { 40 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 41 } 42 43 virtual bool runOnMachineFunction(MachineFunction &MF); 44 45 private: 46 void SourceNoLongerAvailable(unsigned Reg, 47 DenseMap<unsigned, unsigned> &SrcMap, 48 DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 49 bool CopyPropagateBlock(MachineBasicBlock &MBB); 50 }; 51 } 52 char MachineCopyPropagation::ID = 0; 53 54 INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 55 "Machine Copy Propagation Pass", false, false) 56 57 FunctionPass *llvm::createMachineCopyPropagationPass() { 58 return new MachineCopyPropagation(); 59 } 60 61 void 62 MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 63 DenseMap<unsigned, unsigned> &SrcMap, 64 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 65 DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg); 66 if (SI != SrcMap.end()) { 67 unsigned MappedDef = SI->second; 68 // Source of copy is no longer available for propagation. 69 if (AvailCopyMap.erase(MappedDef)) { 70 for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 71 AvailCopyMap.erase(*SR); 72 } 73 } 74 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 75 SI = SrcMap.find(*AS); 76 if (SI != SrcMap.end()) { 77 unsigned MappedDef = SI->second; 78 if (AvailCopyMap.erase(MappedDef)) { 79 for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR) 80 AvailCopyMap.erase(*SR); 81 } 82 } 83 } 84 } 85 86 static bool NoInterveningSideEffect(const MachineInstr *CopyMI, 87 const MachineInstr *MI) { 88 const MachineBasicBlock *MBB = CopyMI->getParent(); 89 if (MI->getParent() != MBB) 90 return false; 91 MachineBasicBlock::const_iterator I = CopyMI; 92 MachineBasicBlock::const_iterator E = MBB->end(); 93 MachineBasicBlock::const_iterator E2 = MI; 94 95 ++I; 96 while (I != E && I != E2) { 97 if (I->hasUnmodeledSideEffects() || I->isCall() || 98 I->isTerminator()) 99 return false; 100 ++I; 101 } 102 return true; 103 } 104 105 bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 106 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 107 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 108 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 109 DenseMap<unsigned, unsigned> SrcMap; // Src -> Def map 110 111 bool Changed = false; 112 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 113 MachineInstr *MI = &*I; 114 ++I; 115 116 if (MI->isCopy()) { 117 unsigned Def = MI->getOperand(0).getReg(); 118 unsigned Src = MI->getOperand(1).getReg(); 119 120 if (TargetRegisterInfo::isVirtualRegister(Def) || 121 TargetRegisterInfo::isVirtualRegister(Src)) 122 report_fatal_error("MachineCopyPropagation should be run after" 123 " register allocation!"); 124 125 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 126 if (CI != AvailCopyMap.end()) { 127 MachineInstr *CopyMI = CI->second; 128 unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 129 if (!ReservedRegs.test(Def) && 130 (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && 131 (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) { 132 // The two copies cancel out and the source of the first copy 133 // hasn't been overridden, eliminate the second one. e.g. 134 // %ECX<def> = COPY %EAX<kill> 135 // ... nothing clobbered EAX. 136 // %EAX<def> = COPY %ECX 137 // => 138 // %ECX<def> = COPY %EAX 139 // 140 // Also avoid eliminating a copy from reserved registers unless the 141 // definition is proven not clobbered. e.g. 142 // %RSP<def> = COPY %RAX 143 // CALL 144 // %RAX<def> = COPY %RSP 145 CopyMI->getOperand(1).setIsKill(false); 146 MI->eraseFromParent(); 147 Changed = true; 148 ++NumDeletes; 149 continue; 150 } 151 } 152 153 // If Src is defined by a previous copy, it cannot be eliminated. 154 CI = CopyMap.find(Src); 155 if (CI != CopyMap.end()) 156 MaybeDeadCopies.remove(CI->second); 157 for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) { 158 CI = CopyMap.find(*AS); 159 if (CI != CopyMap.end()) 160 MaybeDeadCopies.remove(CI->second); 161 } 162 163 // Copy is now a candidate for deletion. 164 MaybeDeadCopies.insert(MI); 165 166 // If 'Src' is previously source of another copy, then this earlier copy's 167 // source is no longer available. e.g. 168 // %xmm9<def> = copy %xmm2 169 // ... 170 // %xmm2<def> = copy %xmm0 171 // ... 172 // %xmm2<def> = copy %xmm9 173 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 174 175 // Remember Def is defined by the copy. 176 CopyMap[Def] = MI; 177 AvailCopyMap[Def] = MI; 178 for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 179 CopyMap[*SR] = MI; 180 AvailCopyMap[*SR] = MI; 181 } 182 183 // Remember source that's copied to Def. Once it's clobbered, then 184 // it's no longer available for copy propagation. 185 SrcMap[Src] = Def; 186 187 continue; 188 } 189 190 // Not a copy. 191 SmallVector<unsigned, 2> Defs; 192 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 193 MachineOperand &MO = MI->getOperand(i); 194 if (!MO.isReg()) 195 continue; 196 unsigned Reg = MO.getReg(); 197 if (!Reg) 198 continue; 199 200 if (TargetRegisterInfo::isVirtualRegister(Reg)) 201 report_fatal_error("MachineCopyPropagation should be run after" 202 " register allocation!"); 203 204 if (MO.isDef()) { 205 Defs.push_back(Reg); 206 continue; 207 } 208 209 // If 'Reg' is defined by a copy, the copy is no longer a candidate 210 // for elimination. 211 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 212 if (CI != CopyMap.end()) 213 MaybeDeadCopies.remove(CI->second); 214 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 215 CI = CopyMap.find(*AS); 216 if (CI != CopyMap.end()) 217 MaybeDeadCopies.remove(CI->second); 218 } 219 } 220 221 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 222 unsigned Reg = Defs[i]; 223 224 // No longer defined by a copy. 225 CopyMap.erase(Reg); 226 AvailCopyMap.erase(Reg); 227 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 228 CopyMap.erase(*AS); 229 AvailCopyMap.erase(*AS); 230 } 231 232 // If 'Reg' is previously source of a copy, it is no longer available for 233 // copy propagation. 234 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 235 } 236 } 237 238 // If MBB doesn't have successors, delete the copies whose defs are not used. 239 // If MBB does have successors, then conservative assume the defs are live-out 240 // since we don't want to trust live-in lists. 241 if (MBB.succ_empty()) { 242 for (SmallSetVector<MachineInstr*, 8>::iterator 243 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 244 DI != DE; ++DI) { 245 if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 246 (*DI)->eraseFromParent(); 247 Changed = true; 248 ++NumDeletes; 249 } 250 } 251 } 252 253 return Changed; 254 } 255 256 bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 257 bool Changed = false; 258 259 TRI = MF.getTarget().getRegisterInfo(); 260 ReservedRegs = TRI->getReservedRegs(MF); 261 262 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 263 Changed |= CopyPropagateBlock(*I); 264 265 return Changed; 266 } 267