MachineCopyPropagation.cpp revision f56ce5312448e5876ee1822facab48385ea5c0c0
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 unsigned *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 102bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) { 103 SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion 104 DenseMap<unsigned, MachineInstr*> AvailCopyMap; // Def -> available copies map 105 DenseMap<unsigned, MachineInstr*> CopyMap; // Def -> copies map 106 DenseMap<unsigned, unsigned> SrcMap; // Src -> Def map 107 108 bool Changed = false; 109 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) { 110 MachineInstr *MI = &*I; 111 ++I; 112 113 if (MI->isCopy()) { 114 unsigned Def = MI->getOperand(0).getReg(); 115 unsigned Src = MI->getOperand(1).getReg(); 116 117 if (TargetRegisterInfo::isVirtualRegister(Def) || 118 TargetRegisterInfo::isVirtualRegister(Src)) 119 report_fatal_error("MachineCopyPropagation should be run after" 120 " register allocation!"); 121 122 DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src); 123 if (CI != AvailCopyMap.end()) { 124 MachineInstr *CopyMI = CI->second; 125 unsigned SrcSrc = CopyMI->getOperand(1).getReg(); 126 if (!ReservedRegs.test(Def) && 127 (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) && 128 (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) { 129 // The two copies cancel out and the source of the first copy 130 // hasn't been overridden, eliminate the second one. e.g. 131 // %ECX<def> = COPY %EAX<kill> 132 // ... nothing clobbered EAX. 133 // %EAX<def> = COPY %ECX 134 // => 135 // %ECX<def> = COPY %EAX 136 // 137 // Also avoid eliminating a copy from reserved registers unless the 138 // definition is proven not clobbered. e.g. 139 // %RSP<def> = COPY %RAX 140 // CALL 141 // %RAX<def> = COPY %RSP 142 143 // Clear any kills of Def between CopyMI and MI. This extends the 144 // live range. 145 for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I) 146 I->clearRegisterKills(Def, TRI); 147 148 MI->eraseFromParent(); 149 Changed = true; 150 ++NumDeletes; 151 continue; 152 } 153 } 154 155 // If Src is defined by a previous copy, it cannot be eliminated. 156 CI = CopyMap.find(Src); 157 if (CI != CopyMap.end()) 158 MaybeDeadCopies.remove(CI->second); 159 for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) { 160 CI = CopyMap.find(*AS); 161 if (CI != CopyMap.end()) 162 MaybeDeadCopies.remove(CI->second); 163 } 164 165 // Copy is now a candidate for deletion. 166 MaybeDeadCopies.insert(MI); 167 168 // If 'Src' is previously source of another copy, then this earlier copy's 169 // source is no longer available. e.g. 170 // %xmm9<def> = copy %xmm2 171 // ... 172 // %xmm2<def> = copy %xmm0 173 // ... 174 // %xmm2<def> = copy %xmm9 175 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 176 177 // Remember Def is defined by the copy. 178 CopyMap[Def] = MI; 179 AvailCopyMap[Def] = MI; 180 for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) { 181 CopyMap[*SR] = MI; 182 AvailCopyMap[*SR] = MI; 183 } 184 185 // Remember source that's copied to Def. Once it's clobbered, then 186 // it's no longer available for copy propagation. 187 SrcMap[Src] = Def; 188 189 continue; 190 } 191 192 // Not a copy. 193 SmallVector<unsigned, 2> Defs; 194 int RegMaskOpNum = -1; 195 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 196 MachineOperand &MO = MI->getOperand(i); 197 if (MO.isRegMask()) 198 RegMaskOpNum = i; 199 if (!MO.isReg()) 200 continue; 201 unsigned Reg = MO.getReg(); 202 if (!Reg) 203 continue; 204 205 if (TargetRegisterInfo::isVirtualRegister(Reg)) 206 report_fatal_error("MachineCopyPropagation should be run after" 207 " register allocation!"); 208 209 if (MO.isDef()) { 210 Defs.push_back(Reg); 211 continue; 212 } 213 214 // If 'Reg' is defined by a copy, the copy is no longer a candidate 215 // for elimination. 216 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg); 217 if (CI != CopyMap.end()) 218 MaybeDeadCopies.remove(CI->second); 219 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 220 CI = CopyMap.find(*AS); 221 if (CI != CopyMap.end()) 222 MaybeDeadCopies.remove(CI->second); 223 } 224 } 225 226 // The instruction has a register mask operand which means that it clobbers 227 // a large set of registers. It is possible to use the register mask to 228 // prune the available copies, but treat it like a basic block boundary for 229 // now. 230 if (RegMaskOpNum >= 0) { 231 // Erase any MaybeDeadCopies whose destination register is clobbered. 232 const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 233 for (SmallSetVector<MachineInstr*, 8>::iterator 234 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 235 DI != DE; ++DI) { 236 unsigned Reg = (*DI)->getOperand(0).getReg(); 237 if (ReservedRegs.test(Reg) || !MaskMO.clobbersPhysReg(Reg)) 238 continue; 239 (*DI)->eraseFromParent(); 240 Changed = true; 241 ++NumDeletes; 242 } 243 244 // Clear all data structures as if we were beginning a new basic block. 245 MaybeDeadCopies.clear(); 246 AvailCopyMap.clear(); 247 CopyMap.clear(); 248 SrcMap.clear(); 249 continue; 250 } 251 252 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 253 unsigned Reg = Defs[i]; 254 255 // No longer defined by a copy. 256 CopyMap.erase(Reg); 257 AvailCopyMap.erase(Reg); 258 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 259 CopyMap.erase(*AS); 260 AvailCopyMap.erase(*AS); 261 } 262 263 // If 'Reg' is previously source of a copy, it is no longer available for 264 // copy propagation. 265 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 266 } 267 } 268 269 // If MBB doesn't have successors, delete the copies whose defs are not used. 270 // If MBB does have successors, then conservative assume the defs are live-out 271 // since we don't want to trust live-in lists. 272 if (MBB.succ_empty()) { 273 for (SmallSetVector<MachineInstr*, 8>::iterator 274 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 275 DI != DE; ++DI) { 276 if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) { 277 (*DI)->eraseFromParent(); 278 Changed = true; 279 ++NumDeletes; 280 } 281 } 282 } 283 284 return Changed; 285} 286 287bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 288 bool Changed = false; 289 290 TRI = MF.getTarget().getRegisterInfo(); 291 ReservedRegs = TRI->getReservedRegs(MF); 292 293 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 294 Changed |= CopyPropagateBlock(*I); 295 296 return Changed; 297} 298