[EarlyCSE] Ensure equal keys have the same hash value

Summary:

The logic in EarlyCSE that looks through 'not' operations in the

predicate recognizes e.g. that `select (not (cmp sgt X, Y)), X, Y` is

equivalent to `select (cmp sgt X, Y), Y, X`. Without this change,

however, only the latter is recognized as a form of `smin X, Y`, so the

two expressions receive different hash codes. This leads to missed

optimization opportunities when the quadratic probing for the two hashes

doesn't happen to collide, and assertion failures when probing doesn't

collide on insertion but does collide on a subsequent table grow

operation.

This change inverts the order of some of the pattern matching, checking

first for the optional `not` and then for the min/max/abs patterns, so

that e.g. both expressions above are recognized as a form of `smin X, Y`.

It also adds an assertion to isEqual verifying that it implies equal

hash codes; this fires when there's a collision during insertion, not

just grow, and so will make it easier to notice if these functions fall

out of sync again. A new flag --earlycse-debug-hash is added which can

be used when changing the hash function; it forces hash collisions so

that any pair of values inserted which compare as equal but hash

differently will be caught by the isEqual assertion.

Reviewers: spatel, nikic

Reviewed By: spatel, nikic

Subscribers: lebedev.ri, arsenm, craig.topper, efriedma, hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D62644

llvm-svn: 363274