MachineCSE.cpp revision 05bdcbb1ae48d1d1209173d137d11c35f46abff3
193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===-- MachineCSE.cpp - Machine Common Subexpression Elimination Pass ----===// 293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// The LLVM Compiler Infrastructure 493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This file is distributed under the University of Illinois Open Source 693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// License. See LICENSE.TXT for details. 793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner//===----------------------------------------------------------------------===// 993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// This pass performs global common subexpression elimination on machine 1193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// instructions using a scoped hash table based value numbering scheme. It 1293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// must be run while the machine function is still in SSA form. 1393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner// 1484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson//===----------------------------------------------------------------------===// 1593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 1693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#define DEBUG_TYPE "machine-cse" 17cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands#include "llvm/CodeGen/Passes.h" 1884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson#include "llvm/CodeGen/MachineDominators.h" 1984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson#include "llvm/CodeGen/MachineInstr.h" 2093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 2193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/Target/TargetInstrInfo.h" 2293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner#include "llvm/ADT/ScopedHashTable.h" 234aad88d1fd88413029dd05255306b07cb19396eeBob Wilson#include "llvm/ADT/Statistic.h" 244aad88d1fd88413029dd05255306b07cb19396eeBob Wilson#include "llvm/Support/Debug.h" 2593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 2693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnerusing namespace llvm; 2784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 2893f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSTATISTIC(NumCoalesces, "Number of copies coalesced"); 2993f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerSTATISTIC(NumCSEs, "Number of common subexpression eliminated"); 3093f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 3193f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattnernamespace { 32f5a1fb6b247611b92d9dec9476202b477661dbe8Chris Lattner class MachineCSE : public MachineFunctionPass { 33fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands const TargetInstrInfo *TII; 3493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner MachineRegisterInfo *MRI; 3593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner MachineDominatorTree *DT; 3693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner public: 3793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner static char ID; // Pass identification 3893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {} 3993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 40fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands virtual bool runOnMachineFunction(MachineFunction &MF); 41fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands 4293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 4393f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AU.setPreservesCFG(); 4493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner MachineFunctionPass::getAnalysisUsage(AU); 4593f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner AU.addRequired<MachineDominatorTree>(); 46fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands AU.addPreserved<MachineDominatorTree>(); 47fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands } 4893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 4993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner private: 500bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner unsigned CurrVN; 510bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT; 520bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner SmallVector<MachineInstr*, 64> Exps; 530bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner 540bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB); 550bef562ea253878ee92a1eaf6db05b0c2edfa74cChris Lattner bool ProcessBlock(MachineDomTreeNode *Node); 5693f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner }; 5793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner} // end anonymous namespace 5893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 59fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sandschar MachineCSE::ID = 0; 60fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sandsstatic RegisterPass<MachineCSE> 6193f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerX("machine-cse", "Machine Common Subexpression Elimination"); 6293f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 6393f3bcf7f323069e40d9abb950da73d437b6f7daChris LattnerFunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 6493f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner 65e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilsonbool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI, 66e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson MachineBasicBlock *MBB) { 6784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson bool Changed = false; 68e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 69e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson MachineOperand &MO = MI->getOperand(i); 70e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (!MO.isReg() || !MO.isUse()) 71e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson continue; 72e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson unsigned Reg = MO.getReg(); 73e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) 74e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson continue; 75e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (!MRI->hasOneUse(Reg)) 76e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson // Only coalesce single use copies. This ensure the copy will be 77e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson // deleted. 78e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson continue; 79e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson MachineInstr *DefMI = MRI->getVRegDef(Reg); 80e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson if (DefMI->getParent() != MBB) 81e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson continue; 82e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && 841a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner TargetRegisterInfo::isVirtualRegister(SrcReg) && 855fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner !SrcSubIdx && !DstSubIdx) { 865fb107287fd8d35b8fc39aa3e6b084fb2871a8ffChris Lattner MO.setReg(SrcReg); 8793f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner DefMI->eraseFromParent(); 8893f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner ++NumCoalesces; 8993f3bcf7f323069e40d9abb950da73d437b6f7daChris Lattner Changed = true; 901a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 911a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 921a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 931a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return Changed; 941a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 951a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 961a8d4de397c360a76f1389d15e862eba265d71fdChris Lattnerstatic bool hasLivePhysRegDefUse(MachineInstr *MI) { 971a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 981a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MachineOperand &MO = MI->getOperand(i); 991a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!MO.isReg()) 1001a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1011a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner unsigned Reg = MO.getReg(); 1021a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!Reg) 1031a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1041a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // FIXME: This is obviously overly conservative. On x86 lots of instructions 1051a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // will def EFLAGS and they are not marked dead at this point. 1061a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 1071a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner !(MO.isDef() && MO.isDead())) 1081a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return true; 1091a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1101a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner return false; 1111a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 11284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 1131a8d4de397c360a76f1389d15e862eba265d71fdChris Lattnerbool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { 114ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands bool Changed = false; 1151a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 1161a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner ScopedHashTableScope<MachineInstr*, unsigned, 1171a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MachineInstrExpressionTrait> VNTS(VNT); 1181a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MachineBasicBlock *MBB = Node->getBlock(); 119ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { 1201a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MachineInstr *MI = &*I; 1211a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner ++I; 1221a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool SawStore = false; 1231a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!MI->isSafeToMove(TII, 0, SawStore)) 1241a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1251a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Ignore copies or instructions that read / write physical registers 1261a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // (except for dead defs of physical registers). 1271a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 128ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) || 1291a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg()) 1301a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1311a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (hasLivePhysRegDefUse(MI)) 1321a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1331a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 1341a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner bool FoundCSE = VNT.count(MI); 1351a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!FoundCSE) { 1361a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Look for trivial copy coalescing opportunities. 1371a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (PerformTrivialCoalescing(MI, MBB)) 1381a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner FoundCSE = VNT.count(MI); 1391a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1401a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 141ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands if (!FoundCSE) { 1421a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner VNT.insert(MI, CurrVN++); 1431a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner Exps.push_back(MI); 1441a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1451a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner } 1461a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 1471a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner // Found a common subexpression, eliminate it. 1481a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner unsigned CSVN = VNT.lookup(MI); 1491a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MachineInstr *CSMI = Exps[CSVN]; 150ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands DEBUG(dbgs() << "Examining: " << *MI); 1511a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); 1521a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner unsigned NumDefs = MI->getDesc().getNumDefs(); 153fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { 154ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands MachineOperand &MO = MI->getOperand(i); 1551a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner if (!MO.isReg() || !MO.isDef()) 1561a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner continue; 1571a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner unsigned OldReg = MO.getReg(); 158ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands unsigned NewReg = CSMI->getOperand(i).getReg(); 15984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson assert(OldReg != NewReg && 16084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson TargetRegisterInfo::isVirtualRegister(OldReg) && 16184bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson TargetRegisterInfo::isVirtualRegister(NewReg) && 16284bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson "Do not CSE physical register defs!"); 16384bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson MRI->replaceRegWith(OldReg, NewReg); 16484bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson --NumDefs; 16584bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 16684bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson MI->eraseFromParent(); 16784bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson ++NumCSEs; 16884bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson } 16984bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson 17084bd6b0c31f41cdd1d859dab54b6bc1177c4c6bbBob Wilson // Recursively call ProcessBlock with childred. 171e98585eb36eff3b8c7da1cf7b044da6a05973074Bob Wilson const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 1724c1e3da0cdd2fd0df5188dea1988beb8bf6a0dc6Chris Lattner for (unsigned i = 0, e = Children.size(); i != e; ++i) 173fc6e29d4ab52b7d3efd83846ed495a9ca7e51e49Duncan Sands Changed |= ProcessBlock(Children[i]); 1741a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 175ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands return Changed; 1761a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 1771a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner 1781a8d4de397c360a76f1389d15e862eba265d71fdChris Lattnerbool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 179ed90342d8ae0756305219e0f01e03e77599ebb41Duncan Sands TII = MF.getTarget().getInstrInfo(); 1801a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner MRI = &MF.getRegInfo(); 1811a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner DT = &getAnalysis<MachineDominatorTree>(); 182cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands return ProcessBlock(DT->getRootNode()); 1831a8d4de397c360a76f1389d15e862eba265d71fdChris Lattner} 184cdbd99262286e96729007ac535cd430ecb3d38acDuncan Sands