Allow BasicBlockEdge to be used in DenseMap

[• dberlin]

Summary

Add a DenseMapInfo specialization for BasicBlockEdge

[• dberlin]

The use case for this is that anything that includes Dominators.h gets this definition of BasicBlockEdge. and it seems like an okay one at a glance, so may as well reuse it. This is what is required to use them as a DenseMap key.

The other easy option i see is to just typedef BasicBlockEdge to std::pair<const BasicBlock *, const BasicBlock *> here, and make isSingleEdge (which has 3 uses in all of llvm) a non-member function.

In fact, all the code for our DenseMapInfo is just being reused from the existing std::pair specialization DenseMapInfo has.

Not sure which we prefer, happy to do either

[hfinkel]

In D22207#479840, @dberlin wrote:

The use case for this is that anything that includes Dominators.h gets this definition of BasicBlockEdge. and it seems like an okay one at a glance, so may as well reuse it. This is what is required to use them as a DenseMap key.

The other easy option i see is to just typedef BasicBlockEdge to std::pair<const BasicBlock *, const BasicBlock *> here, and make isSingleEdge (which has 3 uses in all of llvm) a non-member function.

In fact, all the code for our DenseMapInfo is just being reused from the existing std::pair specialization DenseMapInfo has.

Not sure which we prefer, happy to do either

What would happen if you made BasicBlockEdge convertible into a std::pair<const BasicBlock *, const BasicBlock *>? Would you still need this?

[hfinkel]

In D22207#479842, @hfinkel wrote:

In D22207#479840, @dberlin wrote:

The use case for this is that anything that includes Dominators.h gets this definition of BasicBlockEdge. and it seems like an okay one at a glance, so may as well reuse it. This is what is required to use them as a DenseMap key.

The other easy option i see is to just typedef BasicBlockEdge to std::pair<const BasicBlock *, const BasicBlock *> here, and make isSingleEdge (which has 3 uses in all of llvm) a non-member function.

In fact, all the code for our DenseMapInfo is just being reused from the existing std::pair specialization DenseMapInfo has.

Not sure which we prefer, happy to do either

What would happen if you made BasicBlockEdge convertible into a std::pair<const BasicBlock *, const BasicBlock *>? Would you still need this?

Given that the conversion does not work, this LGTM. I'd rather have real names for the endpoints (not just first and second as we'd get if we use pair).

llvm/trunk/include/llvm/IR/Dominators.h

 // This file defines the DominatorTree class, which provides fast and efficient
 // dominance queries.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_DOMINATORS_H
 #define LLVM_IR_DOMINATORS_H
 
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
const BasicBlock *getStart() const {
     return Start;
   }
   const BasicBlock *getEnd() const {
     return End;
   }
   bool isSingleEdge() const;
 };
 
+template <> struct DenseMapInfo<BasicBlockEdge> {
+  static unsigned getHashValue(const BasicBlockEdge *V);
+  typedef DenseMapInfo<const BasicBlock *> BBInfo;
+  static inline BasicBlockEdge getEmptyKey() {
+    return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
+  }
+  static inline BasicBlockEdge getTombstoneKey() {
+    return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const BasicBlockEdge &Edge) {
+    return hash_combine(BBInfo::getHashValue(Edge.getStart()),
+                        BBInfo::getHashValue(Edge.getEnd()));
+  }
+  static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
+    return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
+           BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
+  }
+};
+
 /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
 /// normal dominator tree.
 ///
 /// Definition: A block is said to be forward statically reachable if there is
 /// a path from the entry of the function to the block.  A statically reachable
 /// block may become statically unreachable during optimization.
 ///
 /// A forward unreachable block may appear in the dominator tree, or it may