It was overloading equal_keys and not keys and thus the hash table lookup used equal from the inerited pointer_hash ... (so pointer equality rather than operand_equal_p as desired).
This makes hash_map<tree_operand_hash, X> work as intented. Bootstrap / regtest running on x86_64-unknown-linux-gnu. Richard. 2015-11-05 Richard Biener <rguent...@suse.de> * tree-hash-traits.h (tree_operand_hash): Provide equal, not equal_keys. Index: gcc/tree-hash-traits.h =================================================================== --- gcc/tree-hash-traits.h (revision 229804) +++ gcc/tree-hash-traits.h (working copy) @@ -23,18 +23,20 @@ along with GCC; see the file COPYING3. /* Hash for trees based on operand_equal_p. */ struct tree_operand_hash : ggc_ptr_hash <tree_node> { - static inline hashval_t hash (const_tree); - static inline bool equal_keys (const_tree, const_tree); + static inline hashval_t hash (const value_type &); + static inline bool equal (const value_type &, + const compare_type &); }; inline hashval_t -tree_operand_hash::hash (const_tree t) +tree_operand_hash::hash (const value_type &t) { return iterative_hash_expr (t, 0); } inline bool -tree_operand_hash::equal_keys (const_tree t1, const_tree t2) +tree_operand_hash::equal (const value_type &t1, + const compare_type &t2) { return operand_equal_p (t1, t2, 0); }