[InstSimplify] (a ^ b) ? (~a) ^ b : a ^ (~b)

[k-arrows]

Test code:

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

Clang 15.0.0 (and Gcc trunk)

foo(int, int):                               # @foo(int, int)
        mov     eax, edi
        xor     eax, esi
        not     eax
        ret

Clang 16.0.0 (and Clang trunk)

foo(int, int):                               # @foo(int, int)
        mov     ecx, edi
        xor     ecx, esi
        cmp     edi, esi
        not     ecx
        mov     eax, -1
        cmovne  eax, ecx
        ret

https://godbolt.org/z/qdhKnj3af

[dc03]

I'd like to fix this, but I'm not able to find the exact transform in InstCombine causing this. It appears that the newer clang is converting a ^ (~b) into 0 ^ (-1) (which then gets folded into -1), possibly because it is able to prove that a ^ b being false means that a and b are equal. The older clang appears to be converting a ^ (~b) as well as (~a) ^ b into ~(a ^ b), then coalescing them leading to the codegen you see.

[junaire]

This fold doesn't introduce new instructions so what you really should take a look is InstructionSimplify, maybe

llvm-project/llvm/lib/Analysis/InstructionSimplify.cpp

Line 4482 in 0662167

static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,

Alive proof: https://alive2.llvm.org/ce/z/KEt9R5

[nikic]

This probably needs a generalization of simplifyWithOpReplaced to look at more than one instruction.

[dc03]

This probably needs a generalization of simplifyWithOpReplaced to look at more than one instruction.

@nikic: Not entirely sure where this plays in. Stepping through the code, the transformation comes from here: a ^ ~b gets turned into a ^ (b ^ -1) which then gets reassociated by SimplifyAssociativeOrCommutative here to be (a ^ b) ^ -1, where a ^ b then gets transformed by simplifyByDomEq into 0. I don't see simplifyWithOpReplaced in the call stack at any point.

[nikic]

@dc03 The optimization regression comes from making use of dominating conditions in icmp simplification. However, we don't want to avoid that and instead make sure that the new IR can still be simplified. simplifyWithOpReplaced() is the transform that handles this kind of pattern.

[vfdff]

The regression between llvm 15 and llvm 16 , https://gcc.godbolt.org/z/Goq9ETh67

[vfdff]

maybe this is the simplify case https://alive2.llvm.org/ce/z/TGgJTq , show that the simplifyWithOpReplaced need look at more than one instruction.