[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

[wizardengineer]

is there any real world examples?

[yafet-a]

Hi @Ralender. I have implemented a fix (#149530) for the issue but there is a request for a stronger real-world use case. Was wondering if you had a particular reason to raise this and identify this missed optimisation?

[Ralender]

Hi @Ralender. I have implemented a fix for the issue but there is a request for a stronger real-world use case. Was wondering if you had a particular reason to raise this and identify this missed optimisation?

In my case I needed to apply a 3-bit lookup, 1-bit output to all the bits in values. So the most natural way was ((x&y&~z) | (x&~y&z) | (~x&~y&~z) | (x&y&z)) where every expression represents 1 bits in the lookup table. Maybe its a very weird case.
All the other expression are intermediates states of me progressively reorganizing and optimizing the expression by hand.

For sure putting the entire expression is not a good solution because its way too specific. but I suspect there is some small patterns, or expression re-arranging tricks. that could be useful.

An other approach could also be to do evaluation for large fully bit-wise expressions into a the table, and build and optimal expression from those tables.

[dtcxzyw]

Hi @Ralender. I have implemented a fix for the issue but there is a request for a stronger real-world use case. Was wondering if you had a particular reason to raise this and identify this missed optimisation?

In my case I needed to apply a 3-bit lookup, 1-bit output to all the bits in values. So the most natural way was ((x&y&~z) | (x&~y&z) | (~x&~y&~z) | (x&y&z)) where every expression represents 1 bits in the lookup table. Maybe its a very weird case. All the other expression are intermediates states of me progressively reorganizing and optimizing the expression by hand.

For sure putting the entire expression is not a good solution because its way too specific. but I suspect there is some small patterns, or expression re-arranging tricks. that could be useful.

An other approach could also be to do evaluation for large fully bit-wise expressions into a the table, and build and optimal expression from those tables.

I am fine to convert an expression tree with <=3 leaf nodes into a truth table, then fold it into the optimal form. We have a similar thing called createLogicFromTable in InstCombine.