lib/CodeGen/MachineCSE.cpp

   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 }