Optimization: (x != C) comparison can utilize (x ^ C) result

[Explorer09]

This is an optimization opportunity that can benefit RISC-V, MIPS and other processors that don't use condition codes for their compare-and-branch instructions.

#include <stdlib.h>
unsigned int func1_a(unsigned int x) {
    if (x != 0x555)
        return (x ^ 0x555);
    abort();
}

unsigned int func1_c(unsigned int x) {
    unsigned int tmp = x ^ 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

unsigned int func2_a(unsigned int x) {
    if (x != 0x555)
        return (x - 0x555);
    abort();
}

unsigned int func2_c(unsigned int x) {
    unsigned int tmp = x - 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

The example code above can be tested in Compiler Explorer (godbolt.org). (The target architecture I mostly concern here is riscv32.)

func1_c() and func2_c() are the results I expected for func1_a() and func2_a() to optimize to when using the -Os option. Clang 19 is already able to recognize the func2 case (x != 0x555 and x - 0x555 != 0) but misses on the func1 case ((x ^ 0x555) != 0).

(Note: I also reported this in GCC.)

[llvmbot]

@llvm/issue-subscribers-backend-mips

Author: Kang-Che Sung (宋岡哲) (Explorer09)

This is an optimization opportunity that can benefit RISC-V, MIPS and other processors that don't use condition codes for their compare-and-branch instructions.

#include <stdlib.h>
unsigned int func1_a(unsigned int x) {
    if (x != 0x555)
        return (x ^ 0x555);
    abort();
}

unsigned int func1_c(unsigned int x) {
    unsigned int tmp = x ^ 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

unsigned int func2_a(unsigned int x) {
    if (x != 0x555)
        return (x - 0x555);
    abort();
}

unsigned int func2_c(unsigned int x) {
    unsigned int tmp = x - 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

The example code above can be tested in Compiler Explorer (godbolt.org). (The target architecture I mostly concern here is riscv32.)

func1_c() and func2_c() are the results I expected for func1_a() and func2_a() to optimize to when using the -Os option. Clang 19 is already able to recognize the func2 case (x != 0x555 and x - 0x555 != 0) but misses on the func1 case ((x ^ 0x555) != 0).

(Note: I also reported this in GCC.)

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Kang-Che Sung (宋岡哲) (Explorer09)

This is an optimization opportunity that can benefit RISC-V, MIPS and other processors that don't use condition codes for their compare-and-branch instructions.

#include <stdlib.h>
unsigned int func1_a(unsigned int x) {
    if (x != 0x555)
        return (x ^ 0x555);
    abort();
}

unsigned int func1_c(unsigned int x) {
    unsigned int tmp = x ^ 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

unsigned int func2_a(unsigned int x) {
    if (x != 0x555)
        return (x - 0x555);
    abort();
}

unsigned int func2_c(unsigned int x) {
    unsigned int tmp = x - 0x555;
    __asm__ ("" : "+r" (tmp));
    if (tmp == 0)
        abort();
    return tmp;
}

The example code above can be tested in Compiler Explorer (godbolt.org). (The target architecture I mostly concern here is riscv32.)

func1_c() and func2_c() are the results I expected for func1_a() and func2_a() to optimize to when using the -Os option. Clang 19 is already able to recognize the func2 case (x != 0x555 and x - 0x555 != 0) but misses on the func1 case ((x ^ 0x555) != 0).

(Note: I also reported this in GCC.)

[topperc]

Maybe we just need to add xor to optimizeBranch in CodeGenPrepare.cpp?

[bababuck]

@topperc could I give this a go?

[topperc]

@topperc could I give this a go?

Sure. I tried the CodeGenPrepare change, but the RISC-V backend changed the code back so it needs more work.

[bababuck]

I will have the pull request ready tomorrow morning.

Looks like the reversion occurs in the DAG->DAG Pattern Instruction Selection pass, the pattern xor(X, Y) == 0 gets folded into X == Y if Y is a constant. This transformation should only occur if the XOR result won't be re-used.

However, I don't believe that change is sufficient, if we increase the size of the constant such that it no longer fits in the immediate field, then the compiler produces the following sub-optimal code (same C code as above but the constant increased to 0x5555.

func1_a:                                # @func1_a
# %bb.0:                                # %entry
        lui     a1, 5
        addiw   a1, a1, 1365
        xor     a0, a0, a1
        beqz    a0, .LBB0_2
# %bb.1:                                # %if.then
        ret
.LBB0_2:                                # %if.end
        call    abort

In this scenario where the constant must be resident in a register for the xor, there is no reason to not compare against the imediate and shift the xor back which will save time in the branch taken case.

func1_a:                                # @func1_a
# %bb.0:                                # %entry
        lui     a1, 5
        addiw   a1, a1, 1365
        beq   a0, a1, .LBB0_2
# %bb.1:                                # %if.then
        xor     a0, a0, a1
        ret
.LBB0_2:                                # %if.end
        call    abort