This is an archive of the discontinued LLVM Phabricator instance.

[SimpleLoopUnswitch] Collect either logical ANDs/ORs but not both.
ClosedPublic

Authored by fhahn on Apr 27 2022, 6:09 AM.

Details

Summary

After D97756, collectHomogenousInstGraphLoopInvariants may collect
conditions for both logical ANDs and logical ORs in case the root is a
select that matches both logical AND & OR.

This means the function won't return invariant values of either AND/OR
chains, but both. This can result in incorrect transformations.

See llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch-logical-and-or.ll.
Without the patch, Alive2 rejects the modified tests with:

Source and target don't have the same return domain.

Note that this also applies to the test case added in D97756
(@test_partial_condition_unswitch_or_select). We can't unswitch on
%cond6, because the graph leading to it contains and AND and an OR.

This only fixes trivial unswitching for now, but a similar problem
likely exists with non-trivial unswitching.

Diff Detail

Event Timeline

fhahn created this revision.Apr 27 2022, 6:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 27 2022, 6:09 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn requested review of this revision.Apr 27 2022, 6:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 27 2022, 6:09 AM
nikic added inline comments.Apr 28 2022, 1:13 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2770–2771

Looks like this code tries to handle this special case as well.

2783

Can we also determine ExitDirection here? I think the implementation of collectHomogenousInstGraphLoopInvariants() would be a good deal cleaner if we always passed in whether we expect or/and, rather than doing a guess in some of the cases.

fhahn updated this revision to Diff 426014.Apr 29 2022, 4:31 AM
fhahn marked 2 inline comments as done.

Update with alternative approach where helper functions are used to match either AND/OR but skipping (select _, true, false). This also removes a piece of code that may modify the function even if no unswitching happens (and we would claim no changes have been made)

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2770–2771

Yeah, the code here already handles select _, true, false by skipping it and updating the branch condition before reaching collectHomogenousInstGraphLoopInvariants. But this is not ideal, as it can change the function even if we do not perform unswitching and claim we didn't change the function.

I will update the patch with an alternative approach, that replaces all instances where we use m_LogicalAnd/m_LogicalOr with helpers that skip select _, true, false.

2783

Unfortunately I don't think we can. I think here both target blocks may be in the loop and the unswitching direction is determined based on the match operation tree.

There was a similar miscompilation report (which was introduced by my patch) and a bug fix due to the existence of select cond, true, false in the past: https://reviews.llvm.org/rG5bb38e84d3d0#986154 and https://reviews.llvm.org/rG6b4b1dc6ec6f0bf0a1bb414fbe751ccab99d41a0
Also a follow-up patch to enhance an assertion condition: https://reviews.llvm.org/rG431a40e1e28f181e87dd247b91a5e6872dd64ab4

This only fixes trivial unswitching for now, but a similar problem
likely exists with non-trivial unswitching.

If the select cond, true, false is a concern, what do you think about simplifying it to cond (https://alive2.llvm.org/ce/z/p5Ahrp) in advance before loop unswitch?

fhahn added a comment.Apr 30 2022, 4:01 AM

There was a similar miscompilation report (which was introduced by my patch) and a bug fix due to the existence of select cond, true, false in the past: https://reviews.llvm.org/rG5bb38e84d3d0#986154 and https://reviews.llvm.org/rG6b4b1dc6ec6f0bf0a1bb414fbe751ccab99d41a0
Also a follow-up patch to enhance an assertion condition: https://reviews.llvm.org/rG431a40e1e28f181e87dd247b91a5e6872dd64ab4

This only fixes trivial unswitching for now, but a similar problem
likely exists with non-trivial unswitching.

If the select cond, true, false is a concern, what do you think about simplifying it to cond (https://alive2.llvm.org/ce/z/p5Ahrp) in advance before loop unswitch?

Is it possible you did not check the latest version of the patch? It uses helpers to skip select cons, true, false when trying to match logical and/or.

I don't think we really should simplify/modify the IR if we are not unswitching, which is what 6b4b1dc6ec6f0bf0a1bb414fbe751ccab99d41a0 did, but SimpleLoopUnswitch claims no changes have been made.

nikic added inline comments.Apr 30 2022, 12:21 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
124

Might make more sense to do the stripping as a separate step Cond = stripTrivialSelect(Cond), just without the bit that actually updates the condition in the branch instruction?

There was a similar miscompilation report (which was introduced by my patch) and a bug fix due to the existence of select cond, true, false in the past: https://reviews.llvm.org/rG5bb38e84d3d0#986154 and https://reviews.llvm.org/rG6b4b1dc6ec6f0bf0a1bb414fbe751ccab99d41a0
Also a follow-up patch to enhance an assertion condition: https://reviews.llvm.org/rG431a40e1e28f181e87dd247b91a5e6872dd64ab4

This only fixes trivial unswitching for now, but a similar problem
likely exists with non-trivial unswitching.

If the select cond, true, false is a concern, what do you think about simplifying it to cond (https://alive2.llvm.org/ce/z/p5Ahrp) in advance before loop unswitch?

Is it possible you did not check the latest version of the patch? It uses helpers to skip select cons, true, false when trying to match logical and/or.

I don't think we really should simplify/modify the IR if we are not unswitching, which is what 6b4b1dc6ec6f0bf0a1bb414fbe751ccab99d41a0 did, but SimpleLoopUnswitch claims no changes have been made.

Oh, I totally forgot the conclusion that were discussed in the threads; I recalled that the select form was problematic in the past, but not discussions afterwards.
Even the branch condition-changing code (line 2754~) was still there. Thank you for cleaning up the code bit.

fhahn updated this revision to Diff 427243.May 5 2022, 2:20 AM

Update to use skipTrivialSelect helper instead of separate helpers to skip select and check for and/or.

fhahn marked an inline comment as done.May 5 2022, 2:21 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
124

I updated the patch to just use such a helper. Roughly the same places need updating and I think it's fine to go either way. Unfortunately I don't think there's a good way to prevent making the same mistake when adding new code :(

nikic accepted this revision.May 5 2022, 7:49 AM

LGTM

This revision is now accepted and ready to land.May 5 2022, 7:49 AM
This revision was landed with ongoing or failed builds.May 6 2022, 1:50 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.

Hello I think that since this patch there has been a failure on the PowerPC big endian bootstrap build. I had originally thought it was D123801 because it had the words "powerpc" and "bigendian" in it.

After being able to reproduce it, I think it's from this one though. This example through -simple-loop-unswitch fails now: https://godbolt.org/z/fjWd443P3
It's quite heavily reduced. If it does not reproduce, the original came from running:

bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Target/WebAssembly -I../llvm/lib/Target/WebAssembly -Iinclude -I../llvm/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fvisibility=hidden -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -c ../llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp --target=powerpc64-linux-gnu -I/usr/powerpc-linux-gnu/include/c++/7/powerpc-linux-gnu/64
fhahn added a comment.May 6 2022, 2:42 PM

Hello I think that since this patch there has been a failure on the PowerPC big endian bootstrap build. I had originally thought it was D123801 because it had the words "powerpc" and "bigendian" in it.

After being able to reproduce it, I think it's from this one though. This example through -simple-loop-unswitch fails now: https://godbolt.org/z/fjWd443P3
It's quite heavily reduced. If it does not reproduce, the original came from running:

bin/clang++ -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Target/WebAssembly -I../llvm/lib/Target/WebAssembly -Iinclude -I../llvm/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -fvisibility=hidden -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -c ../llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp --target=powerpc64-linux-gnu -I/usr/powerpc-linux-gnu/include/c++/7/powerpc-linux-gnu/64

I've reverted the change for now, thanks!

Hi,

I wrote
https://github.com/llvm/llvm-project/issues/55526
about a crash happening after this was recommited again in 41e142fdc7