This is an archive of the discontinued LLVM Phabricator instance.

[SimpleLoopUnswitch][reland 2] unswitch selects
ClosedPublic

Authored by caojoshua on Nov 22 2022, 2:34 PM.

Details

Summary

The old LoopUnswitch pass unswitched selects, but the changes were
never ported to the new SimpleLoopUnswitch.

We unswitch by turning:

S = select %cond, %a, %b

into:

 head: br %cond, label %then, label %tail

then: br label %tail

tail: S = phi [ %a, %then ], [ %b, %head ]

Unswitch selects are always nontrivial, since the successors do not
exit the loop and the loop body always needs to be cloned.

Unswitch selects always need to freeze the conditional if the
conditional could be poison or undef. Selects don't propagate
poison/undef, and branches on poison/undef causes UB.

Reland 1 - Fix the insertion of freeze instructions. The original
implementation inserts a dead freeze instruction that is not used by the
unswitched branch.

Reland 2 - Include https://reviews.llvm.org/D149560 in the same patch,
which was originally reverted along with this patch. The patch prevents
unswitching of selects with a vector conditional. This could have been
caught in SimpleLoopUnswitch/crash.ll if it included tests for
nontrivial unswitching. This reland also adds a run for the test file
with nontrivial unswitching.

Diff Detail

Event Timeline

caojoshua created this revision.Nov 22 2022, 2:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 22 2022, 2:34 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
caojoshua updated this revision to Diff 477304.Nov 22 2022, 2:40 PM
This comment was removed by caojoshua.
caojoshua updated this revision to Diff 477305.Nov 22 2022, 2:42 PM
caojoshua edited the summary of this revision. (Show Details)

update commit message

caojoshua updated this revision to Diff 477306.Nov 22 2022, 2:43 PM
caojoshua edited the summary of this revision. (Show Details)

Fix typo in commit message

caojoshua updated this revision to Diff 477319.Nov 22 2022, 3:12 PM

More changes before sending for review

caojoshua published this revision for review.Nov 22 2022, 3:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 22 2022, 3:14 PM
fhahn added a comment.Dec 1 2022, 2:06 AM

This seems to try to unswitch every select, but https://github.com/llvm/llvm-project/issues/58122 would only require unswitching conditions that are fed by selects with (some) constant values. Would it be possible to just unswitch such branches, rather than all selects?

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2415

Please submit an NFC patch for review that just changes that so it can be discussed separately.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-equality-undef.ll
3 ↗(On Diff #477319)

Do the tests need to be so big to just check for that? Seems like it should be possible to simplify this more. Also, please limit the test to just simple-loop-unsiwtch, if possible. And use the new PM syntax -passes=...

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-select.ll
7 ↗(On Diff #477319)

I think we definitely need to check the full generates structure of the IR. Also, this is could do with a few more test cases, .e.g including bottom tested loops, select not fed by phi, chained selects and so on.

This seems to try to unswitch every select, but https://github.com/llvm/llvm-project/issues/58122 would only require unswitching conditions that are fed by selects with (some) constant values. Would it be possible to just unswitch such branches, rather than all selects?

Yes, we could, but I think its better to unswitch all selects, like the previous LoopUnswitch did. Should I provide some evidence for this? Maybe through benchmarks?

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2415

This is not a separate patch because we are calling ConstantFoldTerminator(), which only accepts the DomTreeUpdater. I don't think we can motivate this change outside of this patch.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-equality-undef.ll
3 ↗(On Diff #477319)

Do the tests need to be so big to just check for that?

Probably not. This test is directly copied from the old LoopUnswitch. I chose not to modify copied tests.

Also, please limit the test to just simple-loop-unsiwtch, if possible. And use the new PM syntax -passes=...

sounds good. I'll change that.

llvm/test/Transforms/SimpleLoopUnswitch/unswitch-select.ll
7 ↗(On Diff #477319)

Thank you. I'll work on this.

caojoshua added a subscriber: kachkov98.

Threw away original implementation and took it from https://reviews.llvm.org/D139109. Thanks to @kachkov98 for his work on this, who is listed as a co-author in the commit.

The implementation is mostly copied with small changes and incorporates feedback from reviewers. Took out NFC's for unswitching guards.

Added a bunch of tests.

caojoshua retitled this revision from [SimpleLoopUnswitch] unswitch select instructions to [SimpleLoopUnswitch] unswitch selects.
caojoshua edited the summary of this revision. (Show Details)

update commit message in review

caojoshua edited reviewers, added: nikic, mkazantsev, kachkov98; removed: kazu.Apr 16 2023, 11:57 PM
Matt added a subscriber: Matt.Apr 17 2023, 9:40 AM

This revision seems to fix one of the largest regression we found when going to SimpleLoopUnswitch in Julia, we will likely carry this patch going forward.

kachkov98 accepted this revision.Apr 18 2023, 8:16 AM

If there is a critical regression that this patch solves, I don't see any objections to merge it (just for note, I didn't observe any noticeable performance improvements from this on SPEC2006/2017 + some internal benchmarks)

This revision is now accepted and ready to land.Apr 18 2023, 8:16 AM

I'll let this sit for a bit in case anyone else comes and reviews.

I ran this through non-SPEC llvm-test-suite and did not observe increase in compile time.

caojoshua updated this revision to Diff 518269.Apr 29 2023, 8:43 PM

Use DomTreeUpdater for SplitAndInsertIfThen

This revision was landed with ongoing or failed builds.Apr 29 2023, 9:26 PM
This revision was automatically updated to reflect the committed changes.

This triggers failed asserts for aarch64. To repro:

$ cat repro.c
typedef __attribute__((neon_vector_type(8))) unsigned char a;
a c, d, f;
char e;
void b();
void g() {
  a h;
  if (e) {
    a i = {255};
    h = i;
  } else {
    a i = {};
    h = i;
  }
  for (;;) {
    b();
    a i = __builtin_neon_vbsl_v(h, c, d, 16);
    f = i;
  }
}
$ clang -target aarch64-linux-gnu -c repro.c -O3
clang: ../lib/IR/Instructions.cpp:1383: void llvm::BranchInst::AssertOK(): Assertion `getCondition()->getType()->isIntegerTy(1) && "May only branch on boolean predicates!"' failed.

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Indeed it is, thanks, and sorry for not checking the latest git main before posting.

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

It first started failing in https://lab.llvm.org/buildbot/#/builders/237/builds/2419, which this patch is on the blamelist for. There are 11 patches on the blamelist, and this patch is the most disruptive. Looking at the error message, msan has found use-of-initialized error. Its not obvious to me how this patch can cause this.

I will try reproducing this locally.

Should be fixed by https://reviews.llvm.org/D149560, which does not unswitch vector selects.

Could this be caused by this patch?
https://lab.llvm.org/buildbot/#/builders/74/builds/18906

It first started failing in https://lab.llvm.org/buildbot/#/builders/237/builds/2419, which this patch is on the blamelist for. There are 11 patches on the blamelist, and this patch is the most disruptive. Looking at the error message, msan has found use-of-initialized error. Its not obvious to me how this patch can cause this.

I will try reproducing this locally.

My nightly bisect failed. So still guesses.
instcombine cold be related too, but this one is more likely. Msan is about branches. In case of select, it only propagates shadow, but branch reports uninitialized stuff immediatly.
So either a bug in the Interval code, this patch breaks msan.

Its too hard to reproduce this locally on my personal machine. @vitalybuka I see you submitted a build for this patch. Lets see how that goes.

msan is reporting using unitialized end iterator. The end_iterator should be initialized with the default constructor, and I'm not sure yet how my change could break that.

Its too hard to reproduce this locally on my personal machine. @vitalybuka I see you submitted a build for this patch. Lets see how that goes.

msan is reporting using unitialized end iterator. The end_iterator should be initialized with the default constructor, and I'm not sure yet how my change could break that.

Yes, it passed on the parent. Also I bisected locally and this is the patch.
Easy way to reproduce is https://github.com/google/sanitizers/wiki/SanitizerBotReproduceBuild
We need to revert as it breaks existing feature. Unless there is a prove that C++ code is invalid (I can't see that).

vitalybuka reopened this revision.May 1 2023, 9:42 PM
This revision is now accepted and ready to land.May 1 2023, 9:42 PM
vitalybuka updated this revision to Diff 518631.May 1 2023, 9:44 PM

As reverted, with D149560 fixes.

I think this patch's transformations are correct, and that the affected test has a true case of use-of-uninitialized-value. I posted a review in https://reviews.llvm.org/D149698. If that patch is merged, I would like to reland this patch.

vitalybuka requested changes to this revision.EditedMay 2 2023, 4:26 PM

I think this patch's transformations are correct, and that the affected test has a true case of use-of-uninitialized-value. I posted a review in https://reviews.llvm.org/D149698. If that patch is merged, I would like to reland this patch.

This could be correct if you ignore other features of compiler, like msan.
Msan goal is to detects UB issues in C/C++ code. So before Msan we can't run transformation which eliminate information about the program. This patch does, so it can't detect UBs correctly.
So I am strongly against landing this patch as-is.

So what can we do about the issue?
It would be nice to change the patch to preserve structure so msan works correctly.
E.g. in order of preference:

  1. if possible avoid branching on uninitalized variables, select is fine.
  2. If it's hard, the do not run such transformations before msan. Ideally for report quality sanitizers should run as earliest passes in pipeline, but it greatly reduces performance of sanitizers (times). So they benefit from the most simplification passes. But then time to time we get into situation like this. Note that early optimizations hide some bug from sanitizers. We trade false-negatives for performance. However false-positive very undesirable.
  3. If there is a reason to run the pass in exactly that point of pipeline, then don't run transformation if function has "sanitize_memory" attribute. (I don't see implication for other sanitizers from this patch).
This revision now requires changes to proceed.May 2 2023, 4:26 PM
nikic added a comment.EditedMay 3 2023, 12:30 AM

@vitalybuka This transform introduces a freeze on the select condition. msan assumes clean shadow for freeze. So I think by itself this shouldn't cause false positives in msan (at worst only false negatives, which are okay). Something more must be going on here.

if possible avoid branching on uninitalized variables, select is fine.

I might be ok with this, would be an easy change. I would not like suggestion 2, because we want passes to work correctly regardless of where its run in the pipeline. I also would avoid suggestion 3, because we want our sanitizers to validate after the transformations.

As nikic pointed out, we are inserting a freeze. Looking at the final IR, the freeze generated by loop unswitch is gone, so I agree that something else is going on. I suspect something is happening further down the optimization pipeline. I'm going to investigate further before I make a decision on where I want to take this patch.

As an exercise, I came up with an example with branch unswitching that could cause msan warnings. The freeze instruction there prevents msan warnings. However, if I manually remove the freeze instruction and run it with msan, I do see the use-of-uninitialized-value warning. This showed me its ok to hoist the invariant branch outside of the loop, as long as we insert the freeze instruction.

caojoshua updated this revision to Diff 520135.May 6 2023, 6:05 PM
caojoshua edited the summary of this revision. (Show Details)

I found that the previous implementation was completely broken on inserting freeze instructions. We were creating freeze instructions, but not inserting it as the condition for the branch instruction. In other words, we were creating a dead freeze instruction. This issue was not caught earlier because existing logic to insert freeze on branch instructions covered most cases.

I factored out the freeze logic from unswitchNontrivialInvariants to shouldInsertFreeze. This will allow the select-converted-branch get a freeze inserted just like other branches. I added some comments here which I'm not 100% sure is accurate. Would appreciate review on wording for these.

vitalybuka accepted this revision.May 8 2023, 10:16 AM

Thanks.
Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.

I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

BTW. Also this probably means that we need to switch our msan bots to -O2 or below, to catch more uninit bugs in LLVM.

Would appreciate review on wording for these.

This is beyond my expertise. I'll accept, but please set a blocking reviewer to catch attention of particular person.

This revision is now accepted and ready to land.May 8 2023, 10:16 AM
nikic added a comment.May 8 2023, 11:56 AM

freeze comments looks fine.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2658–2659
caojoshua added 1 blocking reviewer(s): nikic.May 8 2023, 12:33 PM
This revision now requires review to proceed.May 8 2023, 12:33 PM

Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.
I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

Could you share an example of a case where LoopUnswitch could hide a bug? I'm guessing its where we hoist a branch that could be undef. We insert a freeze that hides the use of undef, but maybe its actually a true undef and we get a false negative. I'm having some trouble producing this case atm.

Not sure what examples you were able to produce, but "trivial" loop unswitching is enabled in O1. It is possible that even if we switch msan builders to a lower optimization level, some bugs could still be hidden.

From my understanding, you found the pass as a whole, and not just this patch, can hide bugs. If we filter by sanitize_memory, we should probably turn it on for the entire pass, and not just this patch. I would be OK to add this change in a separate patch.

This is beyond my expertise. I'll accept, but please set a blocking reviewer to catch attention of particular person.

I added @nikic as a blocking reviewer.

Freeze is going to be false negatives, which are bad for msan, but better then false positives. Taking that this is -O3 only the patch is LGTM.
I played with existing version of compiler, looks like freeze from this pass can hide a lot of bugs.
So please consider just make this patch NOOP if function has sanitize_memory attribute. Do you see disadvantages in this?

Could you share an example of a case where LoopUnswitch could hide a bug? I'm guessing its where we hoist a branch that could be undef. We insert a freeze that hides the use of undef, but maybe its actually a true undef and we get a false negative. I'm having some trouble producing this case atm.

I mean your and similar to https://godbolt.org/z/fvP1h164s when foo (%myB.coerce) is uninitialized, freezes eliminated all checks for shadow.

nikic accepted this revision.May 9 2023, 5:45 AM

LGTM

This revision is now accepted and ready to land.May 9 2023, 5:45 AM
xbolva00 added inline comments.
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
3505

on on -> on

3506

condtional -> conditional

@vitalybuka I created https://github.com/llvm/llvm-project/issues/62633 to track the fact that LoopUnswitch can make msan miss bugs.

I think that your idea to turn off loop unswitching for functions with sanitize_memory makes the most sense.

This revision was landed with ongoing or failed builds.May 10 2023, 12:43 AM
This revision was automatically updated to reflect the committed changes.

Reverted this in a414db1d8e3173faca024d4532a4c655a1fe02c0. Test case in the commit message.

I forgot to reland together with https://reviews.llvm.org/D149560, which will fix the broken case. I'll apply that patch and do some more testing later.

caojoshua reopened this revision.May 10 2023, 11:23 PM
This revision is now accepted and ready to land.May 10 2023, 11:23 PM
caojoshua edited the summary of this revision. (Show Details)

reland 2

Include https://reviews.llvm.org/D149560 together with the patch.

I also noticed this could have been caught if SimpleLoopUnswitch/crash.ll
@test2 had nontrivial loop unswitch testing. I also added a run with nontrivial
unswitching turned on.

caojoshua retitled this revision from [SimpleLoopUnswitch] unswitch selects to [SimpleLoopUnswitch][reland 2] unswitch selects.

Update commit message to make it clear its a reland

This revision was landed with ongoing or failed builds.May 11 2023, 10:21 PM
This revision was automatically updated to reflect the committed changes.
nikic added inline comments.May 25 2023, 12:16 AM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2877

I think this also needs a check that !SI->getType()->isInteger(1). We don't want to unswitch logical and/or through this code path, we have separate handling for unswitching of complex conditions.