This is an archive of the discontinued LLVM Phabricator instance.

Fix for bug 26465
ClosedPublic

Authored by twoh on Feb 4 2016, 11:08 PM.

Details

Summary

For some cases, InstCombine replaces the sequence of xor/sub instruction followed by cmp instruction into a single cmp instruction. However, this replacement may result suboptimal result especially when the xor/sub has more than one use, as discussed in bug 26465 (https://llvm.org/bugs/show_bug.cgi?id=26465). This patch make the replacement happen only when xor/sub has only one use. Below are test codes for each case that addressed by this patch. For all cases below, instcombine pass does not change the original code at all when the fix is applied.

Case 1: ((xor A, ConstB) == ConstC) -> (A == (ConstB xor ConstC))

  • test case
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, 5
  %cmp1 = icmp eq i32 %xor, 10
  %cmp2 = icmp eq i32 %xor, %rhs
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}
  • Output after instcombine without fix
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, 5
  %cmp1 = icmp eq i32 %lhs, 15
  %cmp2 = icmp eq i32 %xor, %rhs
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

Case 2: ((xor A, B) == 0) with (A == B)

  • test case
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %xor, 0
  %cmp2 = icmp eq i32 %xor, 32
  %sel = xor i1 %cmp1, %cmp2
  ret i1 %sel
}
  • Output after instcombine without fix
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %xor = xor i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %lhs, %rhs
  %cmp2 = icmp eq i32 %xor, 32
  %sel = xor i1 %cmp1, %cmp2
  ret i1 %sel
}

Case 3: ((sub A, B) == 0) -> (A == B)

  • test case
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %sub = sub nsw i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %sub, 0
  %cmp2 = icmp eq i32 %sub, 31
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}
  • Output after instcombine without fix
define zeroext i1 @foo(i32 %lhs, i32 %rhs) {
  %sub = sub nsw i32 %lhs, %rhs
  %cmp1 = icmp eq i32 %lhs, %rhs
  %cmp2 = icmp eq i32 %sub, 31
  %sel = or i1 %cmp1, %cmp2
  ret i1 %sel
}

Diff Detail

Event Timeline

twoh updated this revision to Diff 46994.Feb 4 2016, 11:08 PM
twoh retitled this revision from to Fix for bug 26465 .
twoh updated this object.
twoh added reviewers: hfinkel, majnemer, spatel.
twoh set the repository for this revision to rL LLVM.
twoh updated this object.
twoh added a subscriber: llvm-commits.
majnemer requested changes to this revision.Feb 4 2016, 11:12 PM
majnemer edited edge metadata.

Please add a FileCheck test.

This revision now requires changes to proceed.Feb 4 2016, 11:12 PM
twoh updated this revision to Diff 47033.Feb 5 2016, 11:24 AM
twoh updated this object.
twoh edited edge metadata.

FileCheck test added.

spatel edited edge metadata.Feb 5 2016, 2:37 PM

We need a test case for this path too?
// Replace ((sub A, B) != C) with (B != A-C) if A & C are constants.

Doesn't affect this patch, but in case you intend to continue working near this code: this function spans ~800 lines; I think it should be broken up at this point. :)

lib/Transforms/InstCombine/InstCombineCompares.cpp
2229

I think this comment should be inside the 'if' clause to match the structure of the comment within the 'else if' clause.

twoh updated this revision to Diff 47053.Feb 5 2016, 2:53 PM
twoh edited edge metadata.
twoh removed rL LLVM as the repository for this revision.

Move the comment inside the 'if' clause.

@spatel, I don't think we need a test case for "Replace ((sub A, B) != C) with (B != A-C) if A & C are constants." in this diff, because only the order of if statements is changed for that case. Totally agree on you that the function is too long. Maybe a separate diff for that?

spatel accepted this revision.Feb 5 2016, 3:18 PM
spatel edited edge metadata.
In D16915#345405, @twoh wrote:

@spatel, I don't think we need a test case for "Replace ((sub A, B) != C) with (B != A-C) if A & C are constants." in this diff, because only the order of if statements is changed for that case.

Ah, yes. I missed that the check for that case already exists.

Totally agree on you that the function is too long. Maybe a separate diff for that?

Certainly - that was just a suggestion to make future changes easier.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2215–2217

Sorry - I missed this comment too. Please move it lower to match the format of the other cases.

twoh updated this revision to Diff 47060.Feb 5 2016, 3:25 PM
twoh edited edge metadata.

Move the comment.

lib/Transforms/InstCombine/InstCombineCompares.cpp
2214–2225

Not at all. I should have checked this as well.

spatel added a comment.Feb 5 2016, 3:40 PM

It must be Friday afternoon - I forgot to write 'LGTM' after accepting the revision.

twoh added a comment.Feb 12 2016, 8:50 AM

Hello, how can I move forward with this bug? @hfinkel @majnemer Could you please take a look?

It's not explicit here:
http://llvm.org/docs/DeveloperPolicy.html#code-reviews
...but I think the generally accepted behavior is that you can commit after any one reviewer has accepted the patch.

So you can wait if you'd like further review, or you can commit now.

twoh added a comment.Feb 12 2016, 10:16 AM

@spatel. Thank you for the reply. When I tried 'arc commit --revision D16915', it is said "Revision D16915 has not been accepted. Commit this revision anyway [y/N]?" so I though I need approvals from all assigned reviewers (The revision is marked as 'Needs review' on the Phabricator as well).

BTW, http://llvm.org/docs/DeveloperPolicy.html#code-reviews says only granted contributors can make a commit. As I have not been granted, not sure if it is okay for me to commit this diff directly.

majnemer accepted this revision.Feb 12 2016, 10:18 AM
majnemer edited edge metadata.
This revision is now accepted and ready to land.Feb 12 2016, 10:18 AM
majnemer closed this revision.Feb 12 2016, 10:19 AM

Committed in rL260695