[DAGCombine] Fold redundant select

[samparker]

Summary

If a chain of two selects share a true/false value and are controlled by two setcc nodes, that are never both true, we can fold away one of the selects. So, the following

(select (setcc X, const0, eq), Y,
  (select (setcc X, const1, eq), Z, Y))

Can be combined to:

select (setcc X, const1, eq) Z, Y

[samparker]

Added support for checking against SETLT and SETGT nodes too. X86 and Arm test changes look rather noisey...

[samparker]

Added setugt and setult support.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10921

Could this have ISD::SETNE too?

[samparker]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10921

Yeah, good shout.

[samparker]

Added SETNE as well.

[craig.topper]

LGTM

[bgraur]

Heads-up: this patch is producing miscompiles in our code.
We have verified the code is correct and the test passes without this patch and crashes with it.

@samparker: we're working on a smaller reproducer, until then it would be great if you could revert.

[samparker]

Any update on that reproducer @bgraur?

[bgraur]

In D142535#4112830, @samparker wrote:

Any update on that reproducer @bgraur?

A few more steps remaining to be executed. I'll post the repro in 3h max.

[samparker]

Okay, thanks!

[bgraur]

Thanks a lot for reverting!

Here's the repro:

#include <vector>

[[clang::noinline]] int Miscompile(const std::vector<int>& l) {
  struct Dummy{int x;};
  std::vector<Dummy> d;
  for (int i = 0; i < l.size(); ++i)
    d.push_back({l[i]});
  constexpr int kMax = 10;
  if (d.size() > kMax)
    d.resize(kMax);
  return d.size();
}

int main(int argc, char** argv) {
  return Miscompile(std::vector<int>());
}

Compilation command:

clang -O3 -fno-exceptions -fsized-deallocation -o /tmp/miscompile miscompile.cc -lc++

The resulting binary will exit with 10 while a correct compiler should exit 0.

[samparker]

Hi @bgraur Thanks for the reproducer, but I'm unable to reproduce the issue on my x64 box... What platform were you targeting? Could you please confirm that the reproducer still demonstrates the bug?

[bgraur]

In D142535#4115401, @samparker wrote:

Hi @bgraur Thanks for the reproducer, but I'm unable to reproduce the issue on my x64 box... What platform were you targeting? Could you please confirm that the reproducer still demonstrates the bug?

It reproduces for me on an Intel Skylake (didn't try other architectures)

[samparker]

Hmmm, would you be able to send post the .ll file?

[bgraur]

I tried myself to reproduce the miscompile building clang from the LLVM source tree using the cmake method and found out that it is important to use the standard library headers from the LLVM sources and not the system headers which may be an older version.

Here's the steps that worked for me:

$ cd $LLVM_ROOT
$ mkdir build && cd build
$ cmake -G "Ninja" \
  -DCMAKE_INSTALL_PREFIX=$LLVM_ROOT/install \
  -DCMAKE_BUILD_TYPE=Release  \
  -DLLVM_ENABLE_PROJECTS="clang" \
  -DLLVM_ENABLE_RUNTIMES="libcxx;libcxxabi;libunwind" \
  ../llvm
$ cmake --build .
$ cmake --install .

# Check how the compiler is invoked and what include paths are used for the standard headers:
$ ./bin/clang -O3  \
   -o /tmp/miscompile \
   miscompile.cc -lc++  -Llib/x86_64-unknown-linux-gnu/ -###

# Replace the system path `/usr/lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12` with `$LLVM_ROOT/install/include/c++/v1`
# Replace the system path `/usr/lib/gcc/x86_64-linux-gnu/12/../../../../include/x86_64-linux-gnu/c++/12` with `$LLVM_ROOT/install/include/x86_64-unknown-linux-gnu/c++/v1`
# Execute the resulting command, it should look similar to:
$ "/usr/local/google/home/bgraur/work/llvm-project/install/bin/clang-17" \
   "-cc1" "-triple" "x86_64-unknown-linux-gnu" "-emit-obj" "-disable-free" \
  "-clear-ast-before-backend" "-disable-llvm-verifier" "-discard-value-names" \
  "-main-file-name" "miscompile.cc" "-mrelocation-model" "pic" "-pic-level" "2" \
  "-pic-is-pie" "-mframe-pointer=none" "-fmath-errno" "-ffp-contract=on" \
  "-fno-rounding-math" "-mconstructor-aliases" "-funwind-tables=2" \
  "-target-cpu" "x86-64" "-tune-cpu" "generic" "-mllvm" "-treat-scalable-fixed-error-as-warning" \
  "-debugger-tuning=gdb" "-fcoverage-compilation-dir=$LLVM_ROOT/install" \
  "-resource-dir" "$LLVM_ROOT/install/lib/clang/17" \
  "-internal-isystem" "$LLVM_ROOT/install/include/c++/v1" \
  "-internal-isystem" "$LLVM_ROOT/install/include/x86_64-unknown-linux-gnu/c++/v1" \
  "-internal-isystem" "/usr/lib/gcc/x86_64-linux-gnu/12/../../../../include/c++/12/backward" \
  "-internal-isystem" "$LLVM_ROOT/install/lib/clang/17/include" \
  "-internal-isystem" "/usr/local/include" "-internal-isystem" \
  "/usr/lib/gcc/x86_64-linux-gnu/12/../../../../x86_64-linux-gnu/include" \
  "-internal-externc-isystem" "/usr/include/x86_64-linux-gnu" \
  "-internal-externc-isystem" "/include" "-internal-externc-isystem" "/usr/include" \
  "-O3" "-fdeprecated-macro" "-fdebug-compilation-dir=$LLVM_ROOT/install" \
  "-ferror-limit" "19" "-fgnuc-version=4.2.1" "-fcxx-exceptions" "-fexceptions" \
  "-fcolor-diagnostics" "-vectorize-loops" "-vectorize-slp" "-faddrsig" \
  "-D__GCC_HAVE_DWARF2_CFI_ASM=1" \
  "-o" "/tmp/miscompile-c4b187.o" "-x" "c++" "../miscompile/miscompile.cc"
# Run the linker command (no changes should be necessary).

The resulting binary should show the issue.

[samparker]

Right, thanks. My next question was going to be whether you're building libc++ :) - thanks!

[bgraur]

The correct way to using a custom built libc++ is documented here: https://libcxx.llvm.org/UsingLibcxx.html#using-a-custom-built-libc

Just confirmed the miscompile reproduces with:

./bin/clang -nostdinc++ -nostdlib++ \
  -isystem $LLVM_INSTALL/include/c++/v1 \
  -isystem $LLVM_INSTALL/include/x86_64-unknown-linux-gnu/c++/v1 \
  -O3 \
  -o /tmp/miscompile \
  miscompile.cc \
 -L$LLVM_INSTALL/lib/x86_64-unknown-linux-gnu/  \
 -Wl,-rpath,$LLVM_INSTALL/lib/x86_64-unknown-linux-gnu \
 -lc++

[asmok-g]

Heads-up: We're seeing a change in the compilation of the file (https://github.com/GNOME/pango/blob/main/pango/break.c) after this commit. The file also compiles differently with different optimization levels (0 and 1). We have a different version of the file however; so I'm preparing a reduced, verified case.

[samparker]

I'm preparing a reduced, verified case.

Okay, great, thanks.

[asmok-g]

So, for the following IR, there's a difference in the machine code generated that's causing some tests to fail for us internally in google. Can you please have a look at the diff and tell us whether it's a problem with the patch ?
clang command: clang -O1 -S -o - break.ll

break.ll301 KBDownload

break.diff165 KBDownload

[samparker]

Er, I can't read X86 machine code. And I also don't consider a 4K line IR file as a reduced reproducer....

[samparker]

The patch is certainly triggering on IR though, twice. I will look into it.

[asmok-g]

This comment was removed by asmok-g.

[asmok-g]

Hello @samparker,
Thanks for reverting this. This is kind of late to say, but we were having a bit of hard time getting a reduced test case. We're still working on it, but thought of asking whether you have some interesting findings or know the problem already, leading to the revert.

Thanks,

[samparker]

Hi @asmok-g I will be leaving it reverted, I think the case I was interested in is that just generally broken :)

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10898

This is phrased as "same value" but I think the checks just check that they can't both be true at the same time. They could still both be false at the same time.

10919

If we match the second form with select on the false operand, do we need to invert the condition codes to get back to the first form?

[asmok-g]

In D142535#4158899, @samparker wrote:

Hi @asmok-g I will be leaving it reverted, I think the case I was interested in is that just generally broken :)

OK. We'll stop working on it for now. Please Let us know if we need to proceed or anything.