Page MenuHomePhabricator

[SimpleLoopUnswitch] unswitch select instructions
Needs ReviewPublic

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

Details

Reviewers
fhahn
kazu
Summary

Fixes https://github.com/llvm/llvm-project/issues/58122

The old LoopUnswitch pass unswitched selects, but the new
SimpleLoopUnswitch only unswitches branches and switches. Seems selects
were just forgotten or never implemented.

We consider select unswitching to be nontrivial. Trivial switches have
all branches except for one that exit the loop and do not increase code
size. Select unswitches will always produces two branches and always
increase code size.

As a followup, we can try removing trivial select checks in nontrivial
unswitching, and assume select unswitching will cover it. This change
modifies some existing tests that include selects. These changes all
look like an improvement.

There can be improvements in how we compute select unswitch costs. We
assume that select unswitching copies the entire loop. This is not true
when a branch in the loop uses the select, and gets folded into an
unconditional branch.

Refactorings:

  • bunch of variable renames
  • Replace the array of DomTreeUpdates with DomTreeUpdater. I think its the same thing, since we update all changes at once with the lazy strategy. This is required because ConstantFoldTerminator takes a DomTreeUpdater.

Testing:

  • copied in tests that include select from the old LoopUnswitch
  • added new @cant_unswitch test for a select with a variant condition
  • add some CHECK's for unswitched select instructions in existing tests
  • rewrite expected output of some tests that include selects
  • @test_partial_unswitch_all_conds_guaranteed_non_poison is optimized correctly, but looks awkward. If the select instruction is moved outside the loop from LICM, which always happens in default -O3 passes, the resulting IR is much smaller. I'm not changing the test because its still correct.

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
2413

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

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

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
2413

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

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

Thank you. I'll work on this.