MachineCopyPropagation.cpp revision fb9ebbf236974beac31705eaeb9f50ab585af6ab
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/CodeGen/MachineRegisterInfo.h" 20#include "llvm/Target/TargetRegisterInfo.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/ErrorHandling.h" 23#include "llvm/Support/raw_ostream.h" 24#include "llvm/ADT/BitVector.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/SetVector.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/Statistic.h" 29using namespace llvm; 30 31STATISTIC(NumDeletes, "Number of dead copies deleted"); 32 33namespace { 34 class MachineCopyPropagation : public MachineFunctionPass { 35 const TargetRegisterInfo *TRI; 36 MachineRegisterInfo *MRI; 37 38 public: 39 static char ID; // Pass identification, replacement for typeid 40 MachineCopyPropagation() : MachineFunctionPass(ID) { 41 initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry()); 42 } 43 44 virtual bool runOnMachineFunction(MachineFunction &MF); 45 46 private: 47 typedef SmallVector<unsigned, 4> DestList; 48 typedef DenseMap<unsigned, DestList> SourceMap; 49 50 void SourceNoLongerAvailable(unsigned Reg, 51 SourceMap &SrcMap, 52 DenseMap<unsigned, MachineInstr*> &AvailCopyMap); 53 bool CopyPropagateBlock(MachineBasicBlock &MBB); 54 }; 55} 56char MachineCopyPropagation::ID = 0; 57char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID; 58 59INITIALIZE_PASS(MachineCopyPropagation, "machine-cp", 60 "Machine Copy Propagation Pass", false, false) 61 62void 63MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg, 64 SourceMap &SrcMap, 65 DenseMap<unsigned, MachineInstr*> &AvailCopyMap) { 66 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 67 SourceMap::iterator SI = SrcMap.find(*AI); 68 if (SI != SrcMap.end()) { 69 const DestList& Defs = SI->second; 70 for (DestList::const_iterator I = Defs.begin(), E = Defs.end(); 71 I != E; ++I) { 72 unsigned MappedDef = *I; 73 // Source of copy is no longer available for propagation. 74 if (AvailCopyMap.erase(MappedDef)) { 75 for (MCSubRegIterator SR(MappedDef, TRI); SR.isValid(); ++SR) 76 AvailCopyMap.erase(*SR); 77 } 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 SourceMap 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 (!MRI->isReserved(Def) && 151 (!MRI->isReserved(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 for (MCRegAliasIterator AI(Src, TRI, true); AI.isValid(); ++AI) { 181 CI = CopyMap.find(*AI); 182 if (CI != CopyMap.end()) 183 MaybeDeadCopies.remove(CI->second); 184 } 185 186 // Copy is now a candidate for deletion. 187 MaybeDeadCopies.insert(MI); 188 189 // If 'Src' is previously source of another copy, then this earlier copy's 190 // source is no longer available. e.g. 191 // %xmm9<def> = copy %xmm2 192 // ... 193 // %xmm2<def> = copy %xmm0 194 // ... 195 // %xmm2<def> = copy %xmm9 196 SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap); 197 198 // Remember Def is defined by the copy. 199 // ... Make sure to clear the def maps of aliases first. 200 for (MCRegAliasIterator AI(Def, TRI, false); AI.isValid(); ++AI) { 201 CopyMap.erase(*AI); 202 AvailCopyMap.erase(*AI); 203 } 204 CopyMap[Def] = MI; 205 AvailCopyMap[Def] = MI; 206 for (MCSubRegIterator SR(Def, TRI); SR.isValid(); ++SR) { 207 CopyMap[*SR] = MI; 208 AvailCopyMap[*SR] = MI; 209 } 210 211 // Remember source that's copied to Def. Once it's clobbered, then 212 // it's no longer available for copy propagation. 213 if (std::find(SrcMap[Src].begin(), SrcMap[Src].end(), Def) == 214 SrcMap[Src].end()) { 215 SrcMap[Src].push_back(Def); 216 } 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 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 246 DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(*AI); 247 if (CI != CopyMap.end()) 248 MaybeDeadCopies.remove(CI->second); 249 } 250 } 251 252 // The instruction has a register mask operand which means that it clobbers 253 // a large set of registers. It is possible to use the register mask to 254 // prune the available copies, but treat it like a basic block boundary for 255 // now. 256 if (RegMaskOpNum >= 0) { 257 // Erase any MaybeDeadCopies whose destination register is clobbered. 258 const MachineOperand &MaskMO = MI->getOperand(RegMaskOpNum); 259 for (SmallSetVector<MachineInstr*, 8>::iterator 260 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 261 DI != DE; ++DI) { 262 unsigned Reg = (*DI)->getOperand(0).getReg(); 263 if (MRI->isReserved(Reg) || !MaskMO.clobbersPhysReg(Reg)) 264 continue; 265 (*DI)->eraseFromParent(); 266 Changed = true; 267 ++NumDeletes; 268 } 269 270 // Clear all data structures as if we were beginning a new basic block. 271 MaybeDeadCopies.clear(); 272 AvailCopyMap.clear(); 273 CopyMap.clear(); 274 SrcMap.clear(); 275 continue; 276 } 277 278 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 279 unsigned Reg = Defs[i]; 280 281 // No longer defined by a copy. 282 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 283 CopyMap.erase(*AI); 284 AvailCopyMap.erase(*AI); 285 } 286 287 // If 'Reg' is previously source of a copy, it is no longer available for 288 // copy propagation. 289 SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap); 290 } 291 } 292 293 // If MBB doesn't have successors, delete the copies whose defs are not used. 294 // If MBB does have successors, then conservative assume the defs are live-out 295 // since we don't want to trust live-in lists. 296 if (MBB.succ_empty()) { 297 for (SmallSetVector<MachineInstr*, 8>::iterator 298 DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end(); 299 DI != DE; ++DI) { 300 if (!MRI->isReserved((*DI)->getOperand(0).getReg())) { 301 (*DI)->eraseFromParent(); 302 Changed = true; 303 ++NumDeletes; 304 } 305 } 306 } 307 308 return Changed; 309} 310 311bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) { 312 bool Changed = false; 313 314 TRI = MF.getTarget().getRegisterInfo(); 315 MRI = &MF.getRegInfo(); 316 317 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 318 Changed |= CopyPropagateBlock(*I); 319 320 return Changed; 321} 322