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/Target/TargetInstrInfo.h" 22 #include "llvm/ADT/ScopedHashTable.h" 23 #include "llvm/ADT/Statistic.h" 24 #include "llvm/Support/Debug.h" 25 26 using namespace llvm; 27 28 STATISTIC(NumCoalesces, "Number of copies coalesced"); 29 STATISTIC(NumCSEs, "Number of common subexpression eliminated"); 30 31 namespace { 32 class MachineCSE : public MachineFunctionPass { 33 const TargetInstrInfo *TII; 34 MachineRegisterInfo *MRI; 35 MachineDominatorTree *DT; 36 public: 37 static char ID; // Pass identification 38 MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {} 39 40 virtual bool runOnMachineFunction(MachineFunction &MF); 41 42 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43 AU.setPreservesCFG(); 44 MachineFunctionPass::getAnalysisUsage(AU); 45 AU.addRequired<MachineDominatorTree>(); 46 AU.addPreserved<MachineDominatorTree>(); 47 } 48 49 private: 50 unsigned CurrVN; 51 ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT; 52 SmallVector<MachineInstr*, 64> Exps; 53 54 bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 55 bool ProcessBlock(MachineDomTreeNode *Node); 56 }; 57 } // end anonymous namespace 58 59 char MachineCSE::ID = 0; 60 static RegisterPass<MachineCSE> 61 X("machine-cse", "Machine Common Subexpression Elimination"); 62 63 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 64 65 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 66 MachineBasicBlock *MBB) { 67 bool Changed = false; 68 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 69 MachineOperand &MO = MI->getOperand(i); 70 if (!MO.isReg() || !MO.isUse()) 71 continue; 72 unsigned Reg = MO.getReg(); 73 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 74 continue; 75 if (!MRI->hasOneUse(Reg)) 76 // Only coalesce single use copies. This ensure the copy will be 77 // deleted. 78 continue; 79 MachineInstr *DefMI = MRI->getVRegDef(Reg); 80 if (DefMI->getParent() != MBB) 81 continue; 82 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 83 if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 84 TargetRegisterInfo::isVirtualRegister(SrcReg) && 85 !SrcSubIdx && !DstSubIdx) { 86 MO.setReg(SrcReg); 87 DefMI->eraseFromParent(); 88 ++NumCoalesces; 89 Changed = true; 90 } 91 } 92 93 return Changed; 94 } 95 96 static bool hasLivePhysRegDefUse(MachineInstr *MI) { 97 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 98 MachineOperand &MO = MI->getOperand(i); 99 if (!MO.isReg()) 100 continue; 101 unsigned Reg = MO.getReg(); 102 if (!Reg) 103 continue; 104 // FIXME: This is obviously overly conservative. On x86 lots of instructions 105 // will def EFLAGS and they are not marked dead at this point. 106 if (TargetRegisterInfo::isPhysicalRegister(Reg) && 107 !(MO.isDef() && MO.isDead())) 108 return true; 109 } 110 return false; 111 } 112 113 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { 114 bool Changed = false; 115 116 ScopedHashTableScope<MachineInstr*, unsigned, 117 MachineInstrExpressionTrait> VNTS(VNT); 118 MachineBasicBlock *MBB = Node->getBlock(); 119 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 120 MachineInstr *MI = &*I; 121 ++I; 122 bool SawStore = false; 123 if (!MI->isSafeToMove(TII, 0, SawStore)) 124 continue; 125 // Ignore copies or instructions that read / write physical registers 126 // (except for dead defs of physical registers). 127 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 128 if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || 129 MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg()) 130 continue; 131 132 bool FoundCSE = VNT.count(MI); 133 if (!FoundCSE) { 134 // Look for trivial copy coalescing opportunities. 135 if (PerformTrivialCoalescing(MI, MBB)) 136 FoundCSE = VNT.count(MI); 137 } 138 139 // If the instruction defines a physical register and the value *may* be 140 // used, then it's not safe to replace it with a common subexpression. 141 if (FoundCSE && hasLivePhysRegDefUse(MI)) 142 FoundCSE = false; 143 144 if (!FoundCSE) { 145 VNT.insert(MI, CurrVN++); 146 Exps.push_back(MI); 147 continue; 148 } 149 150 // Found a common subexpression, eliminate it. 151 unsigned CSVN = VNT.lookup(MI); 152 MachineInstr *CSMI = Exps[CSVN]; 153 DEBUG(dbgs() << "Examining: " << *MI); 154 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 155 unsigned NumDefs = MI->getDesc().getNumDefs(); 156 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 157 MachineOperand &MO = MI->getOperand(i); 158 if (!MO.isReg() || !MO.isDef()) 159 continue; 160 unsigned OldReg = MO.getReg(); 161 unsigned NewReg = CSMI->getOperand(i).getReg(); 162 assert(OldReg != NewReg && 163 TargetRegisterInfo::isVirtualRegister(OldReg) && 164 TargetRegisterInfo::isVirtualRegister(NewReg) && 165 "Do not CSE physical register defs!"); 166 MRI->replaceRegWith(OldReg, NewReg); 167 --NumDefs; 168 } 169 MI->eraseFromParent(); 170 ++NumCSEs; 171 } 172 173 // Recursively call ProcessBlock with childred. 174 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 175 for (unsigned i = 0, e = Children.size(); i != e; ++i) 176 Changed |= ProcessBlock(Children[i]); 177 178 return Changed; 179 } 180 181 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 182 TII = MF.getTarget().getInstrInfo(); 183 MRI = &MF.getRegInfo(); 184 DT = &getAnalysis<MachineDominatorTree>(); 185 return ProcessBlock(DT->getRootNode()); 186 } 187