MachineCSE.cpp revision 5196018d9cb80a1cc81b95c6365de24f33c5f6bb
1//===-- MachineCSE.cpp - Machine Common Subexpression Elimination 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 pass performs global common subexpression elimination on machine 11// instructions using a scoped hash table based value numbering scheme. It 12// must be run while the machine function is still in SSA form. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "machine-cse" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/CodeGen/MachineDominators.h" 19#include "llvm/CodeGen/MachineInstr.h" 20#include "llvm/CodeGen/MachineRegisterInfo.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/ADT/ScopedHashTable.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/Support/Debug.h" 26 27using namespace llvm; 28 29STATISTIC(NumCoalesces, "Number of copies coalesced"); 30STATISTIC(NumCSEs, "Number of common subexpression eliminated"); 31 32namespace { 33 class MachineCSE : public MachineFunctionPass { 34 const TargetInstrInfo *TII; 35 const TargetRegisterInfo *TRI; 36 MachineRegisterInfo *MRI; 37 MachineDominatorTree *DT; 38 AliasAnalysis *AA; 39 public: 40 static char ID; // Pass identification 41 MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {} 42 43 virtual bool runOnMachineFunction(MachineFunction &MF); 44 45 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 46 AU.setPreservesCFG(); 47 MachineFunctionPass::getAnalysisUsage(AU); 48 AU.addRequired<AliasAnalysis>(); 49 AU.addRequired<MachineDominatorTree>(); 50 AU.addPreserved<MachineDominatorTree>(); 51 } 52 53 private: 54 unsigned CurrVN; 55 ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT; 56 SmallVector<MachineInstr*, 64> Exps; 57 58 bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 59 bool isPhysDefTriviallyDead(unsigned Reg, 60 MachineBasicBlock::const_iterator I, 61 MachineBasicBlock::const_iterator E); 62 bool hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB); 63 bool isCSECandidate(MachineInstr *MI); 64 bool ProcessBlock(MachineDomTreeNode *Node); 65 }; 66} // end anonymous namespace 67 68char MachineCSE::ID = 0; 69static RegisterPass<MachineCSE> 70X("machine-cse", "Machine Common Subexpression Elimination"); 71 72FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 73 74bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 75 MachineBasicBlock *MBB) { 76 bool Changed = false; 77 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 78 MachineOperand &MO = MI->getOperand(i); 79 if (!MO.isReg() || !MO.isUse()) 80 continue; 81 unsigned Reg = MO.getReg(); 82 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 83 continue; 84 if (!MRI->hasOneUse(Reg)) 85 // Only coalesce single use copies. This ensure the copy will be 86 // deleted. 87 continue; 88 MachineInstr *DefMI = MRI->getVRegDef(Reg); 89 if (DefMI->getParent() != MBB) 90 continue; 91 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 92 if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 93 TargetRegisterInfo::isVirtualRegister(SrcReg) && 94 MRI->getRegClass(SrcReg) == MRI->getRegClass(Reg) && 95 !SrcSubIdx && !DstSubIdx) { 96 DEBUG(dbgs() << "Coalescing: " << *DefMI); 97 DEBUG(dbgs() << "*** to: " << *MI); 98 MO.setReg(SrcReg); 99 DefMI->eraseFromParent(); 100 ++NumCoalesces; 101 Changed = true; 102 } 103 } 104 105 return Changed; 106} 107 108bool MachineCSE::isPhysDefTriviallyDead(unsigned Reg, 109 MachineBasicBlock::const_iterator I, 110 MachineBasicBlock::const_iterator E) { 111 unsigned LookAheadLeft = 5; 112 while (LookAheadLeft--) { 113 if (I == E) 114 // Reached end of block, register is obviously dead. 115 return true; 116 117 if (I->isDebugValue()) 118 continue; 119 bool SeenDef = false; 120 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 121 const MachineOperand &MO = I->getOperand(i); 122 if (!MO.isReg() || !MO.getReg()) 123 continue; 124 if (!TRI->regsOverlap(MO.getReg(), Reg)) 125 continue; 126 if (MO.isUse()) 127 return false; 128 SeenDef = true; 129 } 130 if (SeenDef) 131 // See a def of Reg (or an alias) before encountering any use, it's 132 // trivially dead. 133 return true; 134 ++I; 135 } 136 return false; 137} 138 139bool MachineCSE::hasLivePhysRegDefUse(MachineInstr *MI, MachineBasicBlock *MBB){ 140 unsigned PhysDef = 0; 141 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 142 MachineOperand &MO = MI->getOperand(i); 143 if (!MO.isReg()) 144 continue; 145 unsigned Reg = MO.getReg(); 146 if (!Reg) 147 continue; 148 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 149 if (MO.isUse()) 150 // Can't touch anything to read a physical register. 151 return true; 152 if (MO.isDead()) 153 // If the def is dead, it's ok. 154 continue; 155 // Ok, this is a physical register def that's not marked "dead". That's 156 // common since this pass is run before livevariables. We can scan 157 // forward a few instructions and check if it is obviously dead. 158 if (PhysDef) 159 // Multiple physical register defs. These are rare, forget about it. 160 return true; 161 PhysDef = Reg; 162 } 163 } 164 165 if (PhysDef) { 166 MachineBasicBlock::iterator I = MI; I = llvm::next(I); 167 if (!isPhysDefTriviallyDead(PhysDef, I, MBB->end())) 168 return true; 169 } 170 return false; 171} 172 173bool MachineCSE::isCSECandidate(MachineInstr *MI) { 174 if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 175 MI->isKill() || MI->isInlineAsm()) 176 return false; 177 178 // Ignore copies or instructions that read / write physical registers 179 // (except for dead defs of physical registers). 180 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 181 if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || 182 MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg()) 183 return false; 184 185 // Ignore stuff that we obviously can't move. 186 const TargetInstrDesc &TID = MI->getDesc(); 187 if (TID.mayStore() || TID.isCall() || TID.isTerminator() || 188 TID.hasUnmodeledSideEffects()) 189 return false; 190 191 if (TID.mayLoad()) { 192 // Okay, this instruction does a load. As a refinement, we allow the target 193 // to decide whether the loaded value is actually a constant. If so, we can 194 // actually use it as a load. 195 if (!MI->isInvariantLoad(AA)) 196 // FIXME: we should be able to hoist loads with no other side effects if 197 // there are no other instructions which can change memory in this loop. 198 // This is a trivial form of alias analysis. 199 return false; 200 } 201 return true; 202} 203 204bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { 205 bool Changed = false; 206 207 ScopedHashTableScope<MachineInstr*, unsigned, 208 MachineInstrExpressionTrait> VNTS(VNT); 209 MachineBasicBlock *MBB = Node->getBlock(); 210 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 211 MachineInstr *MI = &*I; 212 ++I; 213 214 if (!isCSECandidate(MI)) 215 continue; 216 217 bool FoundCSE = VNT.count(MI); 218 if (!FoundCSE) { 219 // Look for trivial copy coalescing opportunities. 220 if (PerformTrivialCoalescing(MI, MBB)) 221 FoundCSE = VNT.count(MI); 222 } 223 // FIXME: commute commutable instructions? 224 225 // If the instruction defines a physical register and the value *may* be 226 // used, then it's not safe to replace it with a common subexpression. 227 if (FoundCSE && hasLivePhysRegDefUse(MI, MBB)) 228 FoundCSE = false; 229 230 if (!FoundCSE) { 231 VNT.insert(MI, CurrVN++); 232 Exps.push_back(MI); 233 continue; 234 } 235 236 // Found a common subexpression, eliminate it. 237 unsigned CSVN = VNT.lookup(MI); 238 MachineInstr *CSMI = Exps[CSVN]; 239 DEBUG(dbgs() << "Examining: " << *MI); 240 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 241 unsigned NumDefs = MI->getDesc().getNumDefs(); 242 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 243 MachineOperand &MO = MI->getOperand(i); 244 if (!MO.isReg() || !MO.isDef()) 245 continue; 246 unsigned OldReg = MO.getReg(); 247 unsigned NewReg = CSMI->getOperand(i).getReg(); 248 if (OldReg == NewReg) 249 continue; 250 assert(TargetRegisterInfo::isVirtualRegister(OldReg) && 251 TargetRegisterInfo::isVirtualRegister(NewReg) && 252 "Do not CSE physical register defs!"); 253 MRI->replaceRegWith(OldReg, NewReg); 254 --NumDefs; 255 } 256 MI->eraseFromParent(); 257 ++NumCSEs; 258 } 259 260 // Recursively call ProcessBlock with childred. 261 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 262 for (unsigned i = 0, e = Children.size(); i != e; ++i) 263 Changed |= ProcessBlock(Children[i]); 264 265 return Changed; 266} 267 268bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 269 TII = MF.getTarget().getInstrInfo(); 270 TRI = MF.getTarget().getRegisterInfo(); 271 MRI = &MF.getRegInfo(); 272 DT = &getAnalysis<MachineDominatorTree>(); 273 AA = &getAnalysis<AliasAnalysis>(); 274 return ProcessBlock(DT->getRootNode()); 275} 276