[EarlyCSE] Equivalent SELECTs should hash equally

[bryanpkc]

Summary

DenseMap<SimpleValue> assumes that, if its isEqual method returns true
for two elements, then its getHashValue method must return the same value
for them. This invariant is broken when one SELECT node is a min/max
operation, and the other can be transformed into an equivalent min/max by
inverting its predicate and swapping its operands. This patch adds logic
to getHashValueImpl to ensure that the same value is returned for both
elements in this case, and fixes an assertion failure that would occur
intermittently while compiling the following IR:

define i32 @t(i32 %i) {
  %cmp = icmp sle i32 0, %i
  %twin1 = select i1 %cmp, i32 %i, i32 0
  %cmpinv = icmp sgt i32 0, %i
  %twin2 = select i1 %cmpinv,  i32 0, i32 %i
  %sink = add i32 %twin1, %twin2
  ret i32 %sink
}

[bryanpkc]

Moved the fix into matchSelectWithOptionalNotCond instead of duplicating code.

[bryanpkc]

Cleaned up unused code.

[lebedev.ri]

Two comments:

1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion
2. This should be adding a test, either to a existing file, or to the new one, with -earlycse-debug-hash.

[bryanpkc]

Added a regression test using the -earlycse-debug-hash option.

[lebedev.ri]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

87

Not for this patch, but i think we clearly should change the default.

[bryanpkc]

In D86843#2246545, @lebedev.ri wrote:

1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE? That seems like overkill.

[lebedev.ri]

In D86843#2246699, @bryanpkc wrote:

In D86843#2246545, @lebedev.ri wrote:

1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE?

At least for every test that explicitly uses -early-cse.

That seems like overkill.

OTOH these bugs aren't fun, and they should be trivially caught by existing tests, since the test coverage should be good anyways.

[bryanpkc]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

87

Oh, that makes sense.

[bryanpkc]

In D86843#2246700, @lebedev.ri wrote:

In D86843#2246699, @bryanpkc wrote:

In D86843#2246545, @lebedev.ri wrote:

1. As a preparatory patch, we should adjust every test that uses EarlyCSE to also specify -earlycse-debug-hash, at least to those where it doesn't result in an assertion

Thanks for your suggestions, Roman. I have added the reproducer to the EarlyCSE tests, next to other similar test cases. Regarding your first suggestion, do you mean that we should enable -earlycse-debug-hash in all tests under llvm/test/Transforms/EarlyCSE/, or even all tests under llvm/test/ that may implicitly use EarlyCSE?

At least for every test that explicitly uses -early-cse.

That seems like overkill.

OTOH these bugs aren't fun, and they should be trivially caught by existing tests, since the test coverage should be good anyways.

OK, I will submit a second patch to do that, as well as the EXPENSIVE_CHECKS change.

[bryanpkc]

Fixed linter warning.

[bryanpkc]

Pinging reviewers.

[spatel]

LGTM

[bryanpkc]

Thanks Sanjay.

[thakis]

Looks like this broke check-llvm: http://45.33.8.238/linux/27555/step_12.txt

Ptal!

[hliao]

Basically, the logic is wrong as we only canonicalize the condition and operands in the select. But, we also need to inverse the flavor to match the original logic. The original change plus inversing flavor is committed in 41e68f7ee7b

[bryanpkc]

Apologies for the bug and thanks @hliao for the quick fix.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

DEBUG_COUNTER(CSECounter, "early-cse",
               "Controls which instructions are removed");
 
 static cl::opt<unsigned> EarlyCSEMssaOptCap(
     "earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden,
     cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange "
              "for faster compile. Caps the MemorySSA clobbering calls."));
 
 static cl::opt<bool> EarlyCSEDebugHash(
     "earlycse-debug-hash", cl::init(false), cl::Hidden,
     cl::desc("Perform extra assertion checking to verify that SimpleValue's hash "
              "function is well-behaved w.r.t. its isEqual predicate"));
 
 //===----------------------------------------------------------------------===//
 // SimpleValue
 //===----------------------------------------------------------------------===//
 
 namespace {
if (!match(Cond, m_ICmp(Pred, m_Specific(A), m_Specific(B)))) {
     // Check for commuted variants of min/max by swapping predicate.
     // If we do not match the standard or commuted patterns, this is not a
     // recognized form of min/max, but it is still a select, so return true.
     if (!match(Cond, m_ICmp(Pred, m_Specific(B), m_Specific(A))))
       return true;
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
+  // Check for inverted variants of min/max by swapping operands.
+  switch (Pred) {
+  case CmpInst::ICMP_ULE:
+  case CmpInst::ICMP_UGE:
+  case CmpInst::ICMP_SLE:
+  case CmpInst::ICMP_SGE:
+    Pred = CmpInst::getInversePredicate(Pred);
+    std::swap(A, B);
+  default:
+    break;
+  }
+
   switch (Pred) {
   case CmpInst::ICMP_UGT: Flavor = SPF_UMAX; break;
   case CmpInst::ICMP_ULT: Flavor = SPF_UMIN; break;
   case CmpInst::ICMP_SGT: Flavor = SPF_SMAX; break;
   case CmpInst::ICMP_SLT: Flavor = SPF_SMIN; break;
   default: break;
   }
 
if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, SPF)) {
 
     // Hash general selects to allow matching commuted true/false operands.
 
     // If we do not have a compare as the condition, just hash in the condition.
     CmpInst::Predicate Pred;
     Value *X, *Y;
     if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
       return hash_combine(Inst->getOpcode(), Cond, A, B);
+#if 0
+    // Prefer to hash the select as a min/max if possible.
+    CmpInst::Predicate InvPred = CmpInst::getInversePredicate(Pred);
+    if (X == B && Y == A) {
+      switch (InvPred) {
+      case CmpInst::ICMP_UGT: SPF = SPF_UMAX; break;
+      case CmpInst::ICMP_ULT: SPF = SPF_UMIN; break;
+      case CmpInst::ICMP_SGT: SPF = SPF_SMAX; break;
+      case CmpInst::ICMP_SLT: SPF = SPF_SMIN; break;
+      default: break;
+      }
+      if (SPF == SPF_SMIN || SPF == SPF_SMAX ||
+          SPF == SPF_UMIN || SPF == SPF_UMAX) {
+        if (A > B)
+          std::swap(A, B);
+        return hash_combine(Inst->getOpcode(), SPF, A, B);
+      }
+    }
+#endif
 
     // Similar to cmp normalization (above) - canonicalize the predicate value:
     // select (icmp Pred, X, Y), A, B --> select (icmp InvPred, X, Y), B, A
     if (CmpInst::getInversePredicate(Pred) < Pred) {
       Pred = CmpInst::getInversePredicate(Pred);
       std::swap(A, B);
     }
     return hash_combine(Inst->getOpcode(), Pred, X, Y, A, B);