This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombine] Fold redundant select
ClosedPublic

Authored by samparker on Jan 25 2023, 6:09 AM.

Details

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

Diff Detail

Event Timeline

samparker created this revision.Jan 25 2023, 6:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2023, 6:09 AM
Herald added subscribers: luke, pmatos, asb and 29 others. · View Herald Transcript
samparker requested review of this revision.Jan 25 2023, 6:09 AM
samparker updated this revision to Diff 492120.Jan 25 2023, 8:10 AM
samparker edited the summary of this revision. (Show Details)

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

samparker updated this revision to Diff 492356.Jan 26 2023, 1:31 AM

Added setugt and setult support.

craig.topper added inline comments.Jan 26 2023, 10:16 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10921

Could this have ISD::SETNE too?

samparker added inline comments.Jan 30 2023, 1:23 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10921

Yeah, good shout.

samparker updated this revision to Diff 493239.Jan 30 2023, 1:39 AM

Added SETNE as well.

This revision is now accepted and ready to land.Jan 31 2023, 1:06 PM
This revision was landed with ongoing or failed builds.Feb 2 2023, 1:43 AM
This revision was automatically updated to reflect the committed changes.
bgraur added a subscriber: bgraur.Feb 6 2023, 7:40 AM
bgraur added a comment.Feb 7 2023, 2:10 AM

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.

Any update on that reproducer @bgraur?

bgraur added a comment.Feb 8 2023, 6:22 AM

Any update on that reproducer @bgraur?

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

Okay, thanks!

bgraur added a comment.Feb 8 2023, 8:27 AM

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.

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?

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)

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

bgraur added a comment.EditedFeb 10 2023, 5:58 AM

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.

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

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++

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.

I'm preparing a reduced, verified case.

Okay, great, thanks.

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

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

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

This comment was removed by 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,

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

craig.topper added inline comments.Feb 28 2023, 9:51 AM
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?

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.