Re-apply r97667 but with a little bit of thought put into the patch. This implements a special DenseMapInfo trait for DenseMap<MachineInstr*> that compare the value of the MachineInstr rather than the pointer value. Since the hashing and equality test functions ignore defs it's useful for doing CSE kind optimization.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97678 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 68 insertions, 65 deletions

diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index 66be26c..85ad26e 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -419,6 +419,71 @@ private:
   void AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo);
 };
 
+/// MachineInstrExpressionTrait - Special DenseMapInfo traits to compare
+/// MachineInstr* by *value* of the instruction rather than by pointer value.
+/// The hashing and equality testing functions ignore definitions so this is
+/// useful for CSE, etc.
+struct MachineInstrExpressionTrait : DenseMapInfo<MachineInstr*> {
+  static inline MachineInstr *getEmptyKey() {
+    return 0;
+  }
+
+  static inline MachineInstr *getTombstoneKey() {
+    return reinterpret_cast<MachineInstr*>(-1);
+  }
+
+  static unsigned getHashValue(const MachineInstr* const &MI) {
+    unsigned Hash = MI->getOpcode() * 37;
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      const MachineOperand &MO = MI->getOperand(i);
+      uint64_t Key = (uint64_t)MO.getType() << 32;
+      switch (MO.getType()) {
+        default: break;
+        case MachineOperand::MO_Register:
+          if (MO.isDef())
+            continue;  // Skip defs.
+          Key |= MO.getReg();
+          break;
+        case MachineOperand::MO_Immediate:
+          Key |= MO.getImm();
+          break;
+        case MachineOperand::MO_FrameIndex:
+        case MachineOperand::MO_ConstantPoolIndex:
+        case MachineOperand::MO_JumpTableIndex:
+          Key |= MO.getIndex();
+          break;
+        case MachineOperand::MO_MachineBasicBlock:
+          Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
+          break;
+        case MachineOperand::MO_GlobalAddress:
+          Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
+          break;
+        case MachineOperand::MO_BlockAddress:
+          Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
+          break;
+      }
+      Key += ~(Key << 32);
+      Key ^= (Key >> 22);
+      Key += ~(Key << 13);
+      Key ^= (Key >> 8);
+      Key += (Key << 3);
+      Key ^= (Key >> 15);
+      Key += ~(Key << 27);
+      Key ^= (Key >> 31);
+      Hash = (unsigned)Key + Hash * 37;
+    }
+    return Hash;
+  }
+
+  static bool isEqual(const MachineInstr* const &LHS,
+                      const MachineInstr* const &RHS) {
+    if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
+        LHS == getEmptyKey() || LHS == getTombstoneKey())
+      return LHS == RHS;
+    return LHS->isIdenticalTo(RHS, MachineInstr::IgnoreVRegDefs);
+  }
+};
+
 //===----------------------------------------------------------------------===//
 // Debugging Support
 
diff --git a/lib/CodeGen/MachineCSE.cpp b/lib/CodeGen/MachineCSE.cpp
index c5f555b..ea11bfb 100644
--- a/lib/CodeGen/MachineCSE.cpp
+++ b/lib/CodeGen/MachineCSE.cpp
@@ -28,69 +28,6 @@ using namespace llvm;
 STATISTIC(NumCoalesces, "Number of copies coalesced");
 STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
 
-namespace llvm {
-  template<> struct DenseMapInfo<MachineInstr*> {
-    static inline MachineInstr *getEmptyKey() {
-      return 0;
-    }
-
-    static inline MachineInstr *getTombstoneKey() {
-      return reinterpret_cast<MachineInstr*>(-1);
-    }
-
-    static unsigned getHashValue(const MachineInstr* const &MI) {
-      unsigned Hash = MI->getOpcode() * 37;
-      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-        const MachineOperand &MO = MI->getOperand(i);
-        uint64_t Key = (uint64_t)MO.getType() << 32;
-        switch (MO.getType()) {
-        default: break;
-        case MachineOperand::MO_Register:
-          if (MO.isDef() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
-            continue;  // Skip virtual register defs.
-          Key |= MO.getReg();
-          break;
-        case MachineOperand::MO_Immediate:
-          Key |= MO.getImm();
-          break;
-        case MachineOperand::MO_FrameIndex:
-        case MachineOperand::MO_ConstantPoolIndex:
-        case MachineOperand::MO_JumpTableIndex:
-          Key |= MO.getIndex();
-          break;
-        case MachineOperand::MO_MachineBasicBlock:
-          Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
-          break;
-        case MachineOperand::MO_GlobalAddress:
-          Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
-          break;
-        case MachineOperand::MO_BlockAddress:
-          Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
-          break;
-        }
-        Key += ~(Key << 32);
-        Key ^= (Key >> 22);
-        Key += ~(Key << 13);
-        Key ^= (Key >> 8);
-        Key += (Key << 3);
-        Key ^= (Key >> 15);
-        Key += ~(Key << 27);
-        Key ^= (Key >> 31);
-        Hash = (unsigned)Key + Hash * 37;
-      }
-      return Hash;
-    }
-
-    static bool isEqual(const MachineInstr* const &LHS,
-                        const MachineInstr* const &RHS) {
-      if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
-          LHS == getEmptyKey() || LHS == getTombstoneKey())
-        return LHS == RHS;
-      return LHS->isIdenticalTo(RHS, MachineInstr::IgnoreVRegDefs);
-    }
-  };
-} // end llvm namespace
-
 namespace {
   class MachineCSE : public MachineFunctionPass {
     const TargetInstrInfo *TII;
@@ -111,7 +48,7 @@ namespace {
 
   private:
     unsigned CurrVN;
-    ScopedHashTable<MachineInstr*, unsigned> VNT;
+    ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT;
     SmallVector<MachineInstr*, 64> Exps;
 
     bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
@@ -176,7 +113,8 @@ static bool hasLivePhysRegDefUse(MachineInstr *MI) {
 bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
   bool Changed = false;
 
-  ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT);
+  ScopedHashTableScope<MachineInstr*, unsigned,
+    MachineInstrExpressionTrait> VNTS(VNT);
   MachineBasicBlock *MBB = Node->getBlock();
   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
     MachineInstr *MI = &*I;