This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Combine no-wrap sub and icmp w/ constant.
ClosedPublic

Authored by luqmana on Mar 27 2019, 10:53 PM.

Details

Summary

Originally reported in Rust: https://github.com/rust-lang/rust/issues/58602

llvm
define i64 @test_icmp_sub_elide(i64 %offset) {
start:
  %0 = icmp ult i64 %offset, 8
  br i1 %0, label %body, label %end

body:
  %1 = sub i64 10, %offset
  %2 = icmp ult i64 %1, 3
  br i1 %2, label %dead_branch, label %end

dead_branch:
  ret i64 %1

end:
  ret i64 0
}

In the above snippet, we already check that offset < 8 in the first block but can't figure out that 10-offset < 3 is redundant. This changes fixes it in 2 parts:

  1. Teach CorrelatedValuePropagation to also handle sub instructions in addition to add. Relatively simple since makeGuaranteedNoWrapRegion already understood sub instructions. Only subtle change is which range is passed as "Other" to that function, since sub isn't commutative. Moved to separate revision: D60036
  2. Teach InstCombine the transformation (icmp P (sub nuw|nsw C2, Y), C) -> (icmp swap(P) Y, C2-C)

Diff Detail

Event Timeline

luqmana created this revision.Mar 27 2019, 10:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 27 2019, 10:53 PM
nikic added a subscriber: nikic.Mar 28 2019, 1:20 AM

Can you please split off the InstCombine change into a separate revision?

llvm/test/Transforms/InstCombine/icmp-sub.ll
4

For the instcombine tests it's enough to just check the sub+icmp folding to true/false, such as:

define i1 @test(i64 %x) {
  %y = sub nuw i64 10, %x
  %z = icmp ult i64 %y, 3
  ret i1 %z
}

Instead we'd want to test more variations here, in particular: Both nuw and nsw should be covered. Cases where the subtraction overflows should be covered. And I believe this transform also needs to be guarded based on the signedness of the predicate -- i.e. you can't do it if you have sub nsw and ult, so we'd want to test such combinations as well.

Test checks can be generated using utils/update_test_checks.py.

luqmana updated this revision to Diff 192993.Mar 30 2019, 2:40 PM
luqmana retitled this revision from [CorrelatedValuePropagation][InstCombine] Teach CorrelatedValuePropagation to also mark sub as no wrap and use that in InstCombine to fold icmp+sub. to [InstCombine] Combine no-wrap sub and icmp w/ constant..
luqmana edited the summary of this revision. (Show Details)

Split off CorrelatedValuePropagation changes to new revision: D60036

Can you please split off the InstCombine change into a separate revision?

Left the InstCombine changes on this revision as you already commented on its test here.

lebedev.ri added inline comments.
llvm/test/Transforms/InstCombine/icmp-sub.ll
66

Would be good to give tests more meaningful names.
Is this a negative test?

83–85

This is identical to the previous test.

luqmana updated this revision to Diff 193000.Mar 31 2019, 1:06 AM
luqmana marked 3 inline comments as done.

Give tests more descriptive names and add one more negative test.

llvm/test/Transforms/InstCombine/icmp-sub.ll
66

Good point, updated the names. And yup, that is a negative test. I've made it more clear.

83–85

Good catch, meant to be a different negative test.

This comment was removed by lebedev.ri.

Tests look good, please precommit them and rebase the differential (so that the test changes are visible).

luqmana updated this revision to Diff 193001.Mar 31 2019, 2:01 AM

Rebased on committed tests.

This revision is now accepted and ready to land.Mar 31 2019, 2:29 AM
dmgreen added a subscriber: dmgreen.Apr 1 2019, 2:00 AM
This revision was automatically updated to reflect the committed changes.