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