[LLVM] Missed optimization on boolean instructions.

[Ralender]

All the following expression are the equivalent. and should be optimized into ~((y | z) ^ x)

int test0(int x, int y, int z) {
    return ((x&y&~z) | (x&~y&z) | (~x&~y&~z) | (x&y&z));
}

int test1(int x, int y, int z) {
    return ((~z) & ((x&y) | (~x&~y))) ^ (z & ((x&y) | (x&~y)));
}

int test2(int x, int y, int z) {
    return ((x&y) | (~x&~y)) ^ (z & (((x&y) | (~x&~y)) ^ ((x&y) | (x&~y))));
}

int test3(int x, int y, int z) {
    return ~((y | z) ^ x);
}

but clang -O3 is far from optimizing into into the optimal form.

define dso_local noundef i32 @_Z5test0iii(i32 noundef %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = xor i32 %2, -1
  %5 = and i32 %4, %0
  %6 = and i32 %5, %1
  %7 = or i32 %1, %0
  %8 = or i32 %7, %2
  %9 = xor i32 %8, -1
  %10 = and i32 %0, %2
  %11 = or i32 %6, %10
  %12 = or i32 %11, %9
  ret i32 %12
}

define dso_local noundef i32 @_Z5test1iii(i32 noundef %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = xor i32 %1, %0
  %5 = or i32 %4, %2
  %6 = and i32 %2, %0
  %7 = xor i32 %5, -1
  %8 = or i32 %6, %7
  ret i32 %8
}

define dso_local noundef i32 @_Z5test2iii(i32 noundef %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = xor i32 %1, -1
  %5 = and i32 %4, %2
  %6 = xor i32 %5, %0
  %7 = xor i32 %6, %1
  %8 = xor i32 %7, -1
  ret i32 %8
}

define dso_local noundef i32 @_Z5test3iii(i32 noundef %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = or i32 %2, %1
  %5 = xor i32 %4, %0
  %6 = xor i32 %5, -1
  ret i32 %6
}

gcc is much closer to generating the optimal code than clang. https://godbolt.org/z/x6aeWxjYG

[HazemAbdelhafez]

Any ideas on where to start in the code base if I want to look further into this?

[wangbyby]

Any ideas on where to start in the code base if I want to look further into this?

llvm\lib\Transforms\InstCombine\InstCombineAndOrXor.cpp

[medievalghoul]

is there any real world examples?