This is an archive of the discontinued LLVM Phabricator instance.

Differential D144607

[InstCombine] Add tests for transforming `(icmp (xor X, Y), X)`; NFC
ClosedPublic

Authored by goldstein.w.n on Feb 22 2023, 5:20 PM.

Details

Reviewers
nikic
spatel
majnemer
Commits
rG7c5cc22b5567: [InstCombine] Add tests for transforming `(icmp (xor X, Y), X)`; NFC

Diff Detail

Event Timeline

goldstein.w.n created this revision.Feb 22 2023, 5:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2023, 5:20 PM
goldstein.w.n requested review of this revision.Feb 22 2023, 5:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2023, 5:20 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
goldstein.w.n added a parent revision: D144606: [InstCombine] Add transforms for `(max/min (xor X, Pow2), X)` -> `(and/or X, Pow2/~Pow2)`.Feb 22 2023, 5:22 PM
goldstein.w.n added reviewers: nikic, spatel, majnemer.
Herald added a subscriber: StephenFan. · View Herald TranscriptFeb 22 2023, 5:22 PM
goldstein.w.n added a child revision: D144608: [InstCombine] Add transforms for `(icmp {u|s}ge/le (xor X, Y), X)`.Feb 22 2023, 5:22 PM
Harbormaster completed remote builds in B215386: Diff 499677.Feb 22 2023, 6:18 PM
goldstein.w.n updated this revision to Diff 499934.Feb 23 2023, 11:46 AM

Rebase

Harbormaster completed remote builds in B215573: Diff 499934.Feb 23 2023, 12:54 PM
goldstein.w.n updated this revision to Diff 502282.Mar 3 2023, 3:54 PM

Rebase

goldstein.w.n updated this revision to Diff 502297.Mar 3 2023, 4:07 PM

Rebase

Harbormaster completed remote builds in B217305: Diff 502297.Mar 3 2023, 5:54 PM
goldstein.w.n updated this revision to Diff 502458.Mar 5 2023, 12:42 PM

Rebase

Harbormaster completed remote builds in B217440: Diff 502458.Mar 5 2023, 2:28 PM
spatel added inline comments.Mar 6 2023, 6:30 AM
llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll
42

Commute x and y on this instruction, so the test is not relying on another transform to get to canonical form.

72

Commute x and y on this instruction, so the test is not relying on another transform to get to canonical form.

73

This test is covering the same pattern (although with different types and predicate) as "xor_ule_2".
We're missing a test to provide coverage for a pattern like this:
x <= (y ^ x)

We can add an instruction to make sure the operands don't get commuted, and the test provides the coverage we want:

define i1 @xor_sge(i8 %xx, i8 %yy) {
  %x = mul i8 %xx, %xx      ; thwart complexity-based canonicalization
  %y = or i8 %yy, 128
  %xor = xor i8 %y, %x      ; both ops are binops, so they won't commute
  %r = icmp sge i8 %x, %xor ; both ops are binops, so they won't commute
  ret i1 %r
}
spatel mentioned this in D144608: [InstCombine] Add transforms for `(icmp {u|s}ge/le (xor X, Y), X)`.Mar 6 2023, 6:45 AM
goldstein.w.n marked 3 inline comments as done.Mar 6 2023, 10:53 AM
goldstein.w.n updated this revision to Diff 502725.Mar 6 2023, 10:53 AM

Fixup tests to canonical form

spatel accepted this revision.Mar 6 2023, 10:56 AM

LGTM

This revision is now accepted and ready to land.Mar 6 2023, 10:56 AM
goldstein.w.n updated this revision to Diff 502795.Mar 6 2023, 2:15 PM

Rebase

Harbormaster completed remote builds in B217697: Diff 502795.Mar 6 2023, 6:43 PM
goldstein.w.n updated this revision to Diff 514065.Apr 16 2023, 5:37 PM

Rebase

Harbormaster completed remote builds in B225978: Diff 514065.Apr 16 2023, 7:52 PM
Closed by commit rG7c5cc22b5567: [InstCombine] Add tests for transforming `(icmp (xor X, Y), X)`; NFC (authored by goldstein.w.n). · Explain WhyApr 17 2023, 8:39 PM
This revision was automatically updated to reflect the committed changes.
goldstein.w.n added a commit: rG7c5cc22b5567: [InstCombine] Add tests for transforming `(icmp (xor X, Y), X)`; NFC.

Revision Contents

PathSize
llvm/
test/
Transforms/
InstCombine/
189 lines

Diff 514510

llvm/test/Transforms/InstCombine/icmp-of-xor-x.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s
declare void @llvm.assume(i1)
declare void @barrier()
define i1 @xor_uge(i8 %x, i8 %y) {
; CHECK-LABEL: @xor_uge(
; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0
; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]])
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y]]
; CHECK-NEXT: [[R:%.*]] = icmp uge i8 [[XOR]], [[X]]
; CHECK-NEXT: ret i1 [[R]]
;
%ynz = icmp ne i8 %y, 0
call void @llvm.assume(i1 %ynz)
%xor = xor i8 %x, %y
%r = icmp uge i8 %xor, %x
ret i1 %r
}
define i1 @xor_uge_fail_maybe_zero(i8 %x, i8 %y) {
; CHECK-LABEL: @xor_uge_fail_maybe_zero(
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT: [[R:%.*]] = icmp uge i8 [[XOR]], [[X]]
; CHECK-NEXT: ret i1 [[R]]
;
%xor = xor i8 %x, %y
%r = icmp uge i8 %xor, %x
ret i1 %r
}
define <2 x i1> @xor_ule_2(<2 x i8> %x, <2 x i8> %yy) {
; CHECK-LABEL: @xor_ule_2(
; CHECK-NEXT: [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 9, i8 8>
; CHECK-NEXT: [[XOR:%.*]] = xor <2 x i8> [[Y]], [[X:%.*]]
; CHECK-NEXT: [[R:%.*]] = icmp ule <2 x i8> [[XOR]], [[X]]
; CHECK-NEXT: ret <2 x i1> [[R]]
;
%y = or <2 x i8> %yy, <i8 9, i8 8>
%xor = xor <2 x i8> %y, %x
%r = icmp ule <2 x i8> %xor, %x
spatelUnsubmitted
Done
ReplyInline Actions

Commute x and y on this instruction, so the test is not relying on another transform to get to canonical form.

spatel: Commute x and y on this instruction, so the test is not relying on another transform to get to…
ret <2 x i1> %r
}
define i1 @xor_sle_2(i8 %xx, i8 %y, i8 %z) {
; CHECK-LABEL: @xor_sle_2(
; CHECK-NEXT: [[X:%.*]] = add i8 [[XX:%.*]], [[Z:%.*]]
; CHECK-NEXT: [[YNZ:%.*]] = icmp ne i8 [[Y:%.*]], 0
; CHECK-NEXT: call void @llvm.assume(i1 [[YNZ]])
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X]], [[Y]]
; CHECK-NEXT: [[R:%.*]] = icmp sle i8 [[X]], [[XOR]]
; CHECK-NEXT: ret i1 [[R]]
;
%x = add i8 %xx, %z
%ynz = icmp ne i8 %y, 0
call void @llvm.assume(i1 %ynz)
%xor = xor i8 %x, %y
%r = icmp sle i8 %x, %xor
ret i1 %r
}
define i1 @xor_sge(i8 %xx, i8 %yy) {
; CHECK-LABEL: @xor_sge(
; CHECK-NEXT: [[X:%.*]] = mul i8 [[XX:%.*]], [[XX]]
; CHECK-NEXT: [[Y:%.*]] = or i8 [[YY:%.*]], -128
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[Y]], [[X]]
; CHECK-NEXT: [[R:%.*]] = icmp sge i8 [[X]], [[XOR]]
; CHECK-NEXT: ret i1 [[R]]
;
%x = mul i8 %xx, %xx
%y = or i8 %yy, 128
spatelUnsubmitted
Done
ReplyInline Actions

Commute x and y on this instruction, so the test is not relying on another transform to get to canonical form.

spatel: Commute x and y on this instruction, so the test is not relying on another transform to get to…
%xor = xor i8 %y, %x
spatelUnsubmitted
Done
ReplyInline Actions

This test is covering the same pattern (although with different types and predicate) as "xor_ule_2".
We're missing a test to provide coverage for a pattern like this:
x <= (y ^ x)

We can add an instruction to make sure the operands don't get commuted, and the test provides the coverage we want:

define i1 @xor_sge(i8 %xx, i8 %yy) {
  %x = mul i8 %xx, %xx      ; thwart complexity-based canonicalization
  %y = or i8 %yy, 128
  %xor = xor i8 %y, %x      ; both ops are binops, so they won't commute
  %r = icmp sge i8 %x, %xor ; both ops are binops, so they won't commute
  ret i1 %r
}
spatel: This test is covering the same pattern (although with different types and predicate) as…
%r = icmp sge i8 %x, %xor
ret i1 %r
}
define i1 @xor_ugt_2(i8 %xx, i8 %y, i8 %z) {
; CHECK-LABEL: @xor_ugt_2(
; CHECK-NEXT: [[X:%.*]] = add i8 [[XX:%.*]], [[Z:%.*]]
; CHECK-NEXT: [[YZ:%.*]] = and i8 [[Y:%.*]], 63
; CHECK-NEXT: [[Y1:%.*]] = or i8 [[YZ]], 64
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X]], [[Y1]]
; CHECK-NEXT: [[R:%.*]] = icmp ugt i8 [[X]], [[XOR]]
; CHECK-NEXT: ret i1 [[R]]
;
%x = add i8 %xx, %z
%yz = and i8 %y, 63
%y1 = or i8 %yz, 64
%xor = xor i8 %x, %y1
%r = icmp ugt i8 %x, %xor
ret i1 %r
}
define i1 @xor_ult(i8 %x) {
; CHECK-LABEL: @xor_ult(
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X:%.*]], 123
; CHECK-NEXT: [[R:%.*]] = icmp ult i8 [[XOR]], [[X]]
; CHECK-NEXT: ret i1 [[R]]
;
%xor = xor i8 %x, 123
%r = icmp ult i8 %xor, %x
ret i1 %r
}
define <2 x i1> @xor_sgt(<2 x i8> %x, <2 x i8> %y) {
; CHECK-LABEL: @xor_sgt(
; CHECK-NEXT: [[YZ:%.*]] = and <2 x i8> [[Y:%.*]], <i8 31, i8 31>
; CHECK-NEXT: [[Y1:%.*]] = or <2 x i8> [[YZ]], <i8 64, i8 64>
; CHECK-NEXT: [[XOR:%.*]] = xor <2 x i8> [[Y1]], [[X:%.*]]
; CHECK-NEXT: [[R:%.*]] = icmp sgt <2 x i8> [[XOR]], [[X]]
; CHECK-NEXT: ret <2 x i1> [[R]]
;
%yz = and <2 x i8> %y, <i8 31, i8 31>
%y1 = or <2 x i8> %yz, <i8 64, i8 64>
%xor = xor <2 x i8> %x, %y1
%r = icmp sgt <2 x i8> %xor, %x
ret <2 x i1> %r
}
define <2 x i1> @xor_sgt_fail_no_known_msb(<2 x i8> %x, <2 x i8> %y) {
; CHECK-LABEL: @xor_sgt_fail_no_known_msb(
; CHECK-NEXT: [[YZ:%.*]] = and <2 x i8> [[Y:%.*]], <i8 55, i8 55>
; CHECK-NEXT: [[Y1:%.*]] = or <2 x i8> [[YZ]], <i8 8, i8 8>
; CHECK-NEXT: [[XOR:%.*]] = xor <2 x i8> [[Y1]], [[X:%.*]]
; CHECK-NEXT: [[R:%.*]] = icmp sgt <2 x i8> [[XOR]], [[X]]
; CHECK-NEXT: ret <2 x i1> [[R]]
;
%yz = and <2 x i8> %y, <i8 63, i8 63>
%y1 = or <2 x i8> %yz, <i8 8, i8 8>
%xor = xor <2 x i8> %x, %y1
%r = icmp sgt <2 x i8> %xor, %x
ret <2 x i1> %r
}
define i1 @xor_slt_2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @xor_slt_2(
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X:%.*]], 88
; CHECK-NEXT: [[R:%.*]] = icmp sgt i8 [[XOR]], [[X]]
; CHECK-NEXT: ret i1 [[R]]
;
%xor = xor i8 %x, 88
%r = icmp slt i8 %x, %xor
ret i1 %r
}
define <2 x i1> @xor_sgt_intmin_2(<2 x i8> %xx, <2 x i8> %yy, <2 x i8> %z) {
; CHECK-LABEL: @xor_sgt_intmin_2(
; CHECK-NEXT: [[X:%.*]] = add <2 x i8> [[XX:%.*]], [[Z:%.*]]
; CHECK-NEXT: [[Y:%.*]] = or <2 x i8> [[YY:%.*]], <i8 -128, i8 -128>
; CHECK-NEXT: [[XOR:%.*]] = xor <2 x i8> [[X]], [[Y]]
; CHECK-NEXT: [[R:%.*]] = icmp sgt <2 x i8> [[X]], [[XOR]]
; CHECK-NEXT: ret <2 x i1> [[R]]
;
%x = add <2 x i8> %xx, %z
%y = or <2 x i8> %yy, <i8 128, i8 128>
%xor = xor <2 x i8> %x, %y
%r = icmp sgt <2 x i8> %x, %xor
ret <2 x i1> %r
}
define i1 @or_slt_intmin_indirect(i8 %x, i8 %C) {
; CHECK-LABEL: @or_slt_intmin_indirect(
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[C:%.*]], 0
; CHECK-NEXT: br i1 [[CMP]], label [[NEG:%.*]], label [[POS:%.*]]
; CHECK: common.ret:
; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i1 [ [[R:%.*]], [[NEG]] ], [ false, [[POS]] ]
; CHECK-NEXT: ret i1 [[COMMON_RET_OP]]
; CHECK: neg:
; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[C]], [[X:%.*]]
; CHECK-NEXT: [[R]] = icmp slt i8 [[XOR]], [[X]]
; CHECK-NEXT: br label [[COMMON_RET:%.*]]
; CHECK: pos:
; CHECK-NEXT: tail call void @barrier()
; CHECK-NEXT: br label [[COMMON_RET]]
;
%cmp = icmp slt i8 %C, 0
br i1 %cmp, label %neg, label %pos
common.ret:
%common.ret.op = phi i1 [ %r, %neg ], [ false, %pos ]
ret i1 %common.ret.op
neg:
%xor = xor i8 %C, %x
%r = icmp slt i8 %xor, %x
br label %common.ret
pos:
tail call void @barrier()
br label %common.ret
}