Optimization: If (x & y) == y then (x - y) == (x xor y) == (x & ~y)

[Explorer09]

This is an optimization feature request.

For unsigned integers x and y, if it's checked in a conditional that (x & y) == y, then the three expressions (x - y), (x xor y) and (x & ~y) should equal to each other. The compiler should be able to emit any of the three forms in assembly, looking at which takes the least clock cycles or which is the smallest in code size.

Note that Clang is already able to optimize the condition (x & y) == y to (~x & y) == 0.

#include <stdlib.h>
unsigned int test1(unsigned int x, unsigned int y) {
    if ((x & y) == y)
        return x - y;
    abort();
}
unsigned int test2(unsigned int x, unsigned int y) {
    if ((x & y) == y)
        return x ^ y;
    abort();
}
unsigned int test3(unsigned int x, unsigned int y) {
    if ((x & y) == y)
        return x & ~y;
    abort();
}

Update: The same bug report in GCC

[nikic]

Can you please provide more context on where this is useful?

[Explorer09]

@nikic I thought such pattern should be common, such as when the bitfields represent sets, and the programmer needs to remove some elements from the set (x & ~y) but didn't notice that y is a subset of x and things can be optimized a bit.

I accidentally encountered this pattern when I wrote a pull request for the htop program (the actual line in code), although it was not about implementing sets.

In GCC, such an optimization is performed for ARM64 target (so that BIC instruction can be used in place of EOR or SUB). The optimization is not performed for x86-64 yet (and I am about to report that issue to GCC).

For RISC-V target, there is a chance where this optimization can be useful: xori rd, rs1, 4096 would sign-extend the immediate value, but to XOR the bit 12 or to clear the bit 12, addi rd, rs1, -4096 can be use instead for a shorter code when x is under this (x & y) == y constraint (specifically (x & 4096) != 0).

[Explorer09]

I think this information can be helpful for developers who try to implement this optimization.

For unsigned integers x and y...

1. The three bitwise comparisons (x & y) == y, (x | y) == x, and (~x & y) == 0 are all equivalent. This represents when the 1-bits in y are a subset of the 1-bits in x. (Clang can detect and optimize this already.)
2. (x xor y) == (x & ~y) if and only if (~x & y) == 0. So sometimes the (~x & y) == 0 conditional can be replaced with the former if sometimes the client code needs the results of both (x xor y) and (x & ~y) (although I assume such case would be rare).
3. If (~x & y) == 0, then (x - y) == (x xor y) but the conditional doesn't work in the opposite direction. There is one exception case that (x - y) == (x xor y) but (x & y) != y when x is 0 and y is ((~0 >> 1) + 1) (i.e. the MSB is 1 and all other bits 0).

Points 1 and 2 can be proven with truth tables. I'm not certain with point 3 yet, so I disclaim the accuracy on that one, but I've done my best.