Add skeleton of a machine level cse pass.
[oota-llvm.git] / 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 }