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