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 schemem. 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/ADT/ScopedHashTable.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/Support/Debug.h" 23 24 using namespace llvm; 25 26 namespace llvm { 27 template<> struct DenseMapInfo<MachineInstr*> { 28 static inline MachineInstr *getEmptyKey() { 29 return 0; 30 } 31 32 static inline MachineInstr *getTombstoneKey() { 33 return reinterpret_cast<MachineInstr*>(-1); 34 } 35 36 static unsigned getHashValue(const MachineInstr* const &MI) { 37 unsigned Hash = MI->getOpcode() * 37; 38 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 39 const MachineOperand &MO = MI->getOperand(i); 40 uint64_t Key = (uint64_t)MO.getType() << 32; 41 switch (MO.getType()) { 42 default: break; 43 case MachineOperand::MO_Register: 44 Key |= MO.getReg(); 45 break; 46 case MachineOperand::MO_Immediate: 47 Key |= MO.getImm(); 48 break; 49 case MachineOperand::MO_FrameIndex: 50 case MachineOperand::MO_ConstantPoolIndex: 51 case MachineOperand::MO_JumpTableIndex: 52 Key |= MO.getIndex(); 53 break; 54 case MachineOperand::MO_MachineBasicBlock: 55 Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB()); 56 break; 57 case MachineOperand::MO_GlobalAddress: 58 Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal()); 59 break; 60 case MachineOperand::MO_BlockAddress: 61 Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress()); 62 break; 63 } 64 Key += ~(Key << 32); 65 Key ^= (Key >> 22); 66 Key += ~(Key << 13); 67 Key ^= (Key >> 8); 68 Key += (Key << 3); 69 Key ^= (Key >> 15); 70 Key += ~(Key << 27); 71 Key ^= (Key >> 31); 72 Hash = (unsigned)Key + Hash * 37; 73 } 74 return Hash; 75 } 76 77 static bool isEqual(const MachineInstr* const &LHS, 78 const MachineInstr* const &RHS) { 79 return LHS->isIdenticalTo(RHS); 80 } 81 }; 82 } // end llvm namespace 83 84 namespace { 85 class MachineCSE : public MachineFunctionPass { 86 ScopedHashTable<MachineInstr*, unsigned> VNT; 87 MachineDominatorTree *DT; 88 public: 89 static char ID; // Pass identification 90 MachineCSE() : MachineFunctionPass(&ID) {} 91 92 virtual bool runOnMachineFunction(MachineFunction &MF); 93 94 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 95 AU.setPreservesCFG(); 96 MachineFunctionPass::getAnalysisUsage(AU); 97 AU.addRequired<MachineDominatorTree>(); 98 AU.addPreserved<MachineDominatorTree>(); 99 } 100 101 private: 102 bool ProcessBlock(MachineDomTreeNode *Node); 103 }; 104 } // end anonymous namespace 105 106 char MachineCSE::ID = 0; 107 static RegisterPass<MachineCSE> 108 X("machine-cse", "Machine Common Subexpression Elimination"); 109 110 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); } 111 112 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) { 113 ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT); 114 MachineBasicBlock *MBB = Node->getBlock(); 115 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 116 ++I) { 117 } 118 return false; 119 } 120 121 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { 122 DT = &getAnalysis<MachineDominatorTree>(); 123 return ProcessBlock(DT->getRootNode()); 124 } 125