Page MenuHomePhabricator

[InstCombine] Add simplification of two logical and/ors
ClosedPublic

Authored by aqjune on Feb 18 2021, 1:48 AM.

Details

Summary

This is a patch that adds folding of two logical and/ors that share one variable:

a && (a && b) -> a && b
a && (a & b) -> a && b
...

This is towards removing the poison-unsafe select optimization (D93065 has more context).

Diff Detail

Event Timeline

aqjune created this revision.Feb 18 2021, 1:48 AM
aqjune requested review of this revision.Feb 18 2021, 1:48 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 18 2021, 1:48 AM
aqjune added inline comments.Feb 19 2021, 9:54 PM
llvm/lib/Analysis/ValueTracking.cpp
4889 ↗(On Diff #325153)

This update was necessary to add transformations for pattern
merge_two_logical_ands3: (X && Y) && X -> X && Y
merge_two_logical_ors3: (X || Y) || X -> X || Y

The remaining patterns are supported by the updates in InstCombineSelect.cpp.

aqjune updated this revision to Diff 326885.Feb 27 2021, 3:25 AM

Rebase & ping

aqjune added inline comments.Feb 27 2021, 3:27 AM
llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll
332–333

It is correct for this to be select; or i1 propagates poison which is unsafe.

lebedev.ri added inline comments.Feb 27 2021, 3:32 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2641–2648

Why does this only deal with select form in the cond operand, unlike the two folds above?

aqjune added inline comments.Feb 27 2021, 4:13 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2641–2648

It's because the non-select cond cases are dealt with the existing transformations (line 2593, 2598).
They fold select (or a, b), true, b into or (or a, b), b which becomes or a, b by visitOr.
This is sound: https://alive2.llvm.org/ce/z/UgMbNq
Similarly, select (and a, b), b, false is folded into and (and a, b), b which becomes and a, b.
This is also okay (https://alive2.llvm.org/ce/z/AWoJK6).

RKSimon resigned from this revision.Mar 1 2021, 8:36 AM
nikic added inline comments.Mar 4 2021, 2:32 PM
llvm/lib/Analysis/ValueTracking.cpp
4889 ↗(On Diff #325153)

Just as a side-note, I think the right way to handle this is to replace propagatesPoison() with getPoisonPropagatingOperands() or similar, which allows handling cases like these, where poison is only partially propagated. For now this is fine, though I think it would be better to write it as:

if (const auto *SI = dyn_cast<SelectInst>(I))
  return directlyImpliesPoison(ValAssumedPoison, SI->getCondition(), Depth + 1);

This will keep the same recursion as for the propagatesPoison() case.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2631

Please use && and || instead of /\ and \/.

2639

What currently happens for something like a ? (a | b) : false? I assume it doesn't get folded?

aqjune updated this revision to Diff 328857.Mar 7 2021, 3:49 AM

Address comments

aqjune marked 2 inline comments as done.Mar 7 2021, 3:51 AM
aqjune added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2639

No, it doesn't get folded.
That being said, I think it is better to simply propagate true/false to select operands, e.g.
a ? (a | b) : false -> a ? (true | b) : false -> a ? b : false. I'll update this patch to do so.

aqjune added inline comments.Mar 7 2021, 4:05 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2639

Nevermind, since the replacement needs to take care of # uses but the current version doesn't need it, I think it does not completely cover the foldings in this patch.

nikic added inline comments.Mar 7 2021, 4:11 AM
llvm/lib/Analysis/ValueTracking.cpp
4858 ↗(On Diff #328857)

Feel free to already land this part separately.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2639

What I had in mind here is that this is basically the foldSelectValueEquivalence() fold, just that instead of x == C ? y : z we have x == true ? y : z, with the == true comparison being implicit. If we generalize that fold to handle this special case, this should work automatically (either via SimplifyWithOpReplaced, or by direct operand replacement for single use).

nikic added inline comments.Mar 7 2021, 4:19 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2639

Ignoring the case of actual operand replacement, I think doing something like this should do:

if (Value *S = SimplifyWithOpReplaced(TrueVal, CondVal, True, SQ, /* AllowRefinement */ true))
  return replaceOperand(SI, 1, S);
if (Value *S = SimplifyWithOpReplaced(FalseVal, CondVal, False, SQ, /* AllowRefinement */ true))
  return replaceOperand(SI, 2, S);

Though probably SimplifyWithOpReplaced needs to be strengthened a bit to also handle selects.

aqjune updated this revision to Diff 328862.Mar 7 2021, 7:32 AM

Update & use SimplifyWithOpReplaced

aqjune updated this revision to Diff 328864.Mar 7 2021, 7:32 AM

clang-format

aqjune marked an inline comment as done.Mar 7 2021, 7:35 AM
aqjune added inline comments.
llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll
53

There are a few suboptimal patterns left; Since they are just simple syntactic patterns, I'll write them and push directly.

aqjune updated this revision to Diff 328866.Mar 7 2021, 8:04 AM

Update changes in llvm/test/Transforms/SimplifyCFG/merge-cond-stores.ll

aqjune edited the summary of this revision. (Show Details)Mar 7 2021, 8:09 AM
nikic added inline comments.Mar 7 2021, 8:49 AM
llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll
266

The previous output here was wrong. Do you know what caused that fold? Maybe there is something more we need to disable.

430

Same here, previous output was wrong.

aqjune added inline comments.Mar 7 2021, 9:02 AM
llvm/test/Transforms/InstCombine/select-safe-bool-transforms.ll
266

It is here: https://github.com/llvm/llvm-project/blob/99108c791de0285ee726a10e8274772b18cee73c/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L2893
I'll push a commit that fixes this by using CreateLogicalAnd if -instcombine-unsafe-select-transform is zero.
Similarly for the or one.

nikic accepted this revision.Mar 7 2021, 9:24 AM

LGTM

This revision is now accepted and ready to land.Mar 7 2021, 9:24 AM
This revision was landed with ongoing or failed builds.Mar 7 2021, 9:39 AM
This revision was automatically updated to reflect the committed changes.

HI,

A bisect seems to show this patch causing the test failures we see on our two-stage clang builders (https://luci-milo.appspot.com/p/fuchsia/builders/prod/clang-linux-x64/b8853364937280028160?):

********************
  LLVM :: Transforms/InstCombine/2011-05-28-swapmulsub.ll
  LLVM :: Transforms/InstCombine/bitcast-bigendian.ll
  LLVM :: Transforms/InstCombine/bitcast-inseltpoison.ll
  LLVM :: Transforms/InstCombine/bitcast.ll
  LLVM :: Transforms/InstCombine/icmp-custom-dl.ll
  LLVM :: Transforms/InstCombine/icmp.ll
  LLVM :: Transforms/InstCombine/shift-amount-reassociation-in-bittest-with-truncation-shl.ll
  LLVM :: Transforms/InstCombine/shift-amount-reassociation-with-truncation-shl.ll
  LLVM :: Transforms/InstCombine/sub-gep.ll
  LLVM :: Transforms/InstCombine/sub.ll
  LLVM :: Transforms/InstCombine/trunc-inseltpoison.ll
  LLVM :: Transforms/InstCombine/trunc.ll

Would you mind taking a look and sending out a fix or reverting? Thanks.

aqjune added a comment.Mar 9 2021, 1:00 PM

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

Thanks for the followup. Can do. Let me see if I can minimize the reproducer/reduce the number of cmake flags needed for ease first since the two-stage build has dependencies on libxml2 and zlib.

While I'm doing that, if you already have a fix, what I can do is patch it locally and get back to you on if it also fixes the issues we see.

Yep, I reverted this patch. Could you post the commandline options that is used to build LLVM?
There was a similar failure reported (D95026) which is due to an existing bug in InstructionSimplify; maybe I can check whether its prospective fix resolves this issue as well.

Thanks for the followup. Can do. Let me see if I can minimize the reproducer/reduce the number of cmake flags needed for ease first since the two-stage build has dependencies on libxml2 and zlib.

While I'm doing that, if you already have a fix, what I can do is patch it locally and get back to you on if it also fixes the issues we see.

Ok, so the cmake invocation for the second stage build is:

cmake "-DCMAKE_EXE_LINKER_FLAGS=-ldl -lpthread" "-DCMAKE_MODULE_LINKER_FLAGS=-ldl -lpthread" "-DCMAKE_SHARED_LINKER_FLAGS=-ldl -lpthread" -DCMAKE_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-amd64 -DLLVM_ENABLE_LLD=ON -DLLVM_ENABLE_LTO=ON -DLLVM_EXTERNAL_CLANG_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../clang -DLLVM_EXTERNAL_CLANG_TOOLS_EXTRA_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../clang-tools-extra -DLLVM_EXTERNAL_LLD_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../lld -DLLVM_EXTERNAL_POLLY_SOURCE_DIR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm/../polly -DPACKAGE_VERSION=13.0.0git -DPACKAGE_VENDOR=Fuchsia -DLLVM_VERSION_MAJOR=13 -DLLVM_VERSION_MINOR=0 -DLLVM_VERSION_PATCH=0 -DCLANG_VERSION_MAJOR=13 -DCLANG_VERSION_MINOR=0 -DCLANG_VERSION_PATCHLEVEL=0 -DCLANG_VENDOR=Fuchsia -DLLVM_VERSION_SUFFIX=git -DLLVM_BINUTILS_INCDIR= -DCLANG_REPOSITORY_STRING= -DCMAKE_MAKE_PROGRAM=/usr/bin/ninja "-DLLVM_ENABLE_PROJECTS=clang;clang-tools-extra;lld;llvm;polly" "-DLLVM_ENABLE_RUNTIMES=compiler-rt;libcxx;libcxxabi;libunwind" -DLINUX_aarch64-unknown-linux-gnu_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-arm64 -DLINUX_x86_64-unknown-linux-gnu_SYSROOT=/usr/local/google/home/leonardchan/sysroot/linux-amd64 -C /usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/clang/cmake/caches/Fuchsia-stage2.cmake -DCLANG_STAGE=stage2 -DCMAKE_CXX_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang++ -DCMAKE_C_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang -DCMAKE_ASM_COMPILER=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/clang -DCMAKE_ASM_COMPILER_ID=Clang -DCMAKE_AR=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/llvm-ar -DCMAKE_RANLIB=/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain/./bin/llvm-ranlib -GNinja /usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1/llvm

/usr/local/google/home/leonardchan/llvm-monorepo/llvm-project-1 can be replaced with whatever the path pointing to your llvm-project repository is.
/usr/local/google/home/leonardchan/llvm-monorepo/llvm-build-1-master-fuchsia-toolchain is the path to your existing clang toolchain made on this revision.

After this, I'm able to reproduce the failures with ninja check-llvm in my second-stage build.

Let me know if I can help more/clarify on some things.

I could reproduce the failures, thanks :)

We're still seeing some *very* strange miscompiles as a result of this patch (maybe not really this patch's fault, it could be some bad optimization that this unblocks). I'm working on a reduction right now.

Here's a repro for the issue we're seeing. It only seems to be happening with msan enabled, so I'm not sure if this is just an msan bug, or a general miscompile that *happens* to trigger in this test when msan is enabled.

The source:

#include <string>
#include <variant>

struct a {
  double b;
  double c;
  std::string d;
};

std::variant<std::pair<int, int>, std::string> e(a f) {
  double g = f.b, h = f.c;
  if (f.d == "y") {
    g *= 2.0;
    h *= 2.0;
  }
  int i(g);
  int k(h);
  if (i == 0) i = h;
  if (k == 0) k = i;
  if (k < i || i < 0) {
    std::string j;
    return j;
  }
  return std::make_pair(i, k);
}

int main() {
  auto j = e({1, 0, "x"});
  std::get<0>(j);
}

To build/run it:

$ clang++ \
  -O2 \
  -msse4.2 \
  -fsanitize=memory \
  -std=gnu++17 \
  -stdlib=libc++ \
  repro.cc \
  -o bug
$ ./bug
terminating with uncaught exception of type std::bad_variant_access: bad_variant_access

Thoughts on this example? If I follow correctly, at the if (k < i || i < 0) { check, both k and i should be 1, and that check should not trigger. Instead, it evaluates to true: the std::get<0>(j) triggers an exception, because the method return a std::string, not a std::pair after this patch.

aqjune added a comment.Thu, Apr 1, 7:47 AM

It indeed seems tricky to find out the root cause for this; this optimization enabled vectorization which led to the error for some reason.
I'll have more time to investigate this tomorrow and weekends.

aqjune added a comment.Sun, Apr 4, 6:43 AM

This turns out to be a bug in InstCombine. I reported it as https://llvm.org/pr49832 .

spatel added a comment.Tue, Apr 6, 5:06 AM

@spatel c590a9880d7a660a1c911fce07f3d01ea18be2df fixes the unreduced test case. Thanks!

Great! We also have essentially the same bug inside of InstSimplify, and that should be fixed with:
e2a0f512eaca

I'm not sure exactly where we stand with respect to exposure/timing for the 12.0 release, but I've marked the patches as blockers for now.
That is tracked at:
https://llvm.org/PR49832