1 //===-- MachineCSE.cpp - Machine Common Subexpression Elimination Pass ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
27 template<> struct DenseMapInfo<MachineInstr*> {
28 static inline MachineInstr *getEmptyKey() {
32 static inline MachineInstr *getTombstoneKey() {
33 return reinterpret_cast<MachineInstr*>(-1);
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()) {
43 case MachineOperand::MO_Register:
46 case MachineOperand::MO_Immediate:
49 case MachineOperand::MO_FrameIndex:
50 case MachineOperand::MO_ConstantPoolIndex:
51 case MachineOperand::MO_JumpTableIndex:
54 case MachineOperand::MO_MachineBasicBlock:
55 Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
57 case MachineOperand::MO_GlobalAddress:
58 Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
60 case MachineOperand::MO_BlockAddress:
61 Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
72 Hash = (unsigned)Key + Hash * 37;
77 static bool isEqual(const MachineInstr* const &LHS,
78 const MachineInstr* const &RHS) {
79 return LHS->isIdenticalTo(RHS);
82 } // end llvm namespace
85 class MachineCSE : public MachineFunctionPass {
86 ScopedHashTable<MachineInstr*, unsigned> VNT;
87 MachineDominatorTree *DT;
89 static char ID; // Pass identification
90 MachineCSE() : MachineFunctionPass(&ID) {}
92 virtual bool runOnMachineFunction(MachineFunction &MF);
94 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
96 MachineFunctionPass::getAnalysisUsage(AU);
97 AU.addRequired<MachineDominatorTree>();
98 AU.addPreserved<MachineDominatorTree>();
102 bool ProcessBlock(MachineDomTreeNode *Node);
104 } // end anonymous namespace
106 char MachineCSE::ID = 0;
107 static RegisterPass<MachineCSE>
108 X("machine-cse", "Machine Common Subexpression Elimination");
110 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
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;
121 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
122 DT = &getAnalysis<MachineDominatorTree>();
123 return ProcessBlock(DT->getRootNode());