[EarlyCSE] Fix hashing of self-compares

[JosephTremoulet]

Summary

Update compare normalization in SimpleValue hashing to break ties (when
the same value is being compared to itself) by switching to the swapped
predicate if it has a lower numerical value. This brings the hashing in
line with isEqual, which already recognizes the self-compares with
swapped predicates as equal.

Fixes PR 42280.

[nikic]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #204820)

Would it be possible to make the condition just Pred > SwappedPred, without ordering by LHS/RHS at all?

[JosephTremoulet]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #204820)

No, some predicates (eq, ne) are their own swap duals, so we need to check the operands to handle e.g. icmp eq A, B vs icmp eq B, A.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #204820)

Right you are! In that case, I'm wondering if we're missing the operand swap for equality/inequality for the select case below? We canonicalize by inverse predicate, but I don't think there's anything handling swapping of equality comparison arguments.

[JosephTremoulet]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #204820)

The swap in the select case is swapping the second and third operands on the select and using the inverse predicate (not the swapped predicate), to handle e.g. A == B ? X : Y vs A != B ? Y : X. Predicates are never their own inverse, so I think it's ok to ignore X and Y there.

Of course, there could also be a swap on the compare feeding the select, so e.g. A == B ? X : Y is also the same as B != A ? Y : X. We're not handling that case in the hashing, but we're not handling it in isEqual either, so it's a missed optimization opportunity rather than nondeterminism/assertions. E.g.:

declare void @use(i32, i32)

define void @test(i32 %a, i32 %b, i32 %x, i32 %y) {
  %c1 = icmp eq i32 %a, %b
  %t1 = select i1 %c1, i32 %x, i32 %y
  %c2 = icmp ne i32 %b, %a
  %t2 = select i1 %c2, i32 %y, i32 %x
  call void @use(i32 %t1, i32 %t2)
  ret void
}

doesn't get changed by EarlyCSE (but neither does it assert, even with -earlycse-debug-hash).

I'm not familiar enough with the composition of the optimization pipeline to have an informed decision whether or not we'd want to add the complexity to handle that to EarlyCSE or not...

[JosephTremoulet]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

185 ↗

(On Diff #204820)

Sigh, meant "to have an informed opinion", not "to have an informed decision".

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *RHS = BinOp->getOperand(1);
     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
       std::swap(LHS, RHS);
 
     return hash_combine(BinOp->getOpcode(), LHS, RHS);
   }
 
   if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
+    // Compares can be commuted by swapping the comparands and
+    // updating the predicate.  Choose the form that has the
+    // comparands in sorted order, or in the case of a tie, the
+    // one with the lower predicate.
     Value *LHS = CI->getOperand(0);
     Value *RHS = CI->getOperand(1);
     CmpInst::Predicate Pred = CI->getPredicate();
-    if (Inst->getOperand(0) > Inst->getOperand(1)) {
+    CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();
+    if (std::tie(LHS, Pred) > std::tie(RHS, SwappedPred)) {
       std::swap(LHS, RHS);
-      Pred = CI->getSwappedPredicate();
+      Pred = SwappedPred;
     }
     return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
   }
 
   // Hash general selects to allow matching commuted true/false operands.
   SelectPatternFlavor SPF;
   Value *Cond, *A, *B;
   if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, SPF)) {

llvm/trunk/test/Transforms/EarlyCSE/commute.ll

 ;
   %C = icmp sgt i32 %A, %B
   store i1 %C, i1* %PA
   %D = icmp slt i32 %B, %A
   store i1 %D, i1* %PB
   ret void
 }
 
+; Test degenerate case of commuted compare of identical comparands.
+
+define void @test6(float %f, i1* %p1, i1* %p2) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[C1:%.*]] = fcmp ult float [[F:%.*]], [[F]]
+; CHECK-NEXT:    store i1 [[C1]], i1* [[P1:%.*]]
+; CHECK-NEXT:    store i1 [[C1]], i1* [[P2:%.*]]
+; CHECK-NEXT:    ret void
+;
+  %c1 = fcmp ult float %f, %f
+  %c2 = fcmp ugt float %f, %f
+  store i1 %c1, i1* %p1
+  store i1 %c2, i1* %p2
+  ret void
+}
+
 ; Min/max operands may be commuted in the compare and select.
 
 define i8 @smin_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smin_commute(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i8 [[B]], [[A]]
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 [[A]], i8 [[B]]
 ; CHECK-NEXT:    [[R:%.*]] = mul i8 [[M1]], [[M1]]