clang is suboptimal for `(~a ^ b) < ~a`

[k-arrows]

Consider the following two functions:

int foo(int a, int b)
{
   return (~a ^ b) < ~a;
}

int bar(int a, int b)
{
   return (a ^ b) > a;
}

Clang vs GCC:
https://godbolt.org/z/rxK1nr794

Alive2:
https://alive2.llvm.org/ce/z/aUhKRe

define i32 @src(i32 %0, i32 %1) {
2:
  %3 = xor i32 %0, 4294967295
  %4 = xor i32 %3, %1
  %5 = icmp slt i32 %4, %3
  %6 = zext i1 %5 to i32
  ret i32 %6
}
=>
define i32 @tgt(i32 %0, i32 %1) {
2:
  %3 = xor i32 %1, %0
  %4 = icmp sgt i32 %3, %0
  %5 = zext i1 %4 to i32
  ret i32 %5
}
Transformation seems to be correct!

[elhewaty]

I am working on this.
but I have a question, How can I reach the code responsible for this?
I think the function foldXorOfICmps in InstCombineAndOrXor.cpp.

[dtcxzyw]

I am working on this. but I have a question, How can I reach the code responsible for this? I think the function foldXorOfICmps in InstCombineAndOrXor.cpp.

That is incorrect. In summary:

• If the simplification is similar to an existing one, it is likely to be related to ValueTracking. You should handle more patterns to expose more information.
• If the simplification doesn't create new instructions (fold into a constant or an existing inst), it is related to InstSimplify. You should find the root of the pattern and look through simplifyXXXInst.
• If the simplification creates new instructions, it falls into the InstCombine part. You should find the root of the pattern and look through InstCombinerImpl::visitXXXInst.

In this case, you should start with InstCombinerImpl::visitICmpInst in InstCombineCompares.cpp since we want to fold icmp slt (~X ^ Y), ~X into icmp sgt (X ^ Y), X.

[elhewaty]

@nikic @goldsteinn @arsenm @dtcxzyw candidate pull: #69882

[pinskia]

The way GCC handles this is a Canonicalization of (~a ^ b) into ~(a ^ b) and then ~a < ~b is what is optimized to a > b.

[dtcxzyw]

The way GCC handles this is a Canonicalization of (~a ^ b) into ~(a ^ b) and then ~a < ~b is what is optimized to a > b.

LLVM doesn't canonicalize (~a ^ b) into ~(a ^ b) due to multi-use of ~a.