LLVM Bugzilla is read-only and represents the historical archive of all LLVM issues filled before November 26, 2021. Use github to submit LLVM bugs

Bug 49832 - InstCombine incorrectly folds select of vector
Summary: InstCombine incorrectly folds select of vector
Status: RESOLVED FIXED
Alias: None
Product: libraries
Classification: Unclassified
Component: Scalar Optimizations (show other bugs)
Version: trunk
Hardware: PC All
: P enhancement
Assignee: Sanjay Patel
URL:
Keywords:
Depends on:
Blocks: release-12.0.0 release-12.0.1
  Show dependency tree
 
Reported: 2021-04-04 06:45 PDT by Juneyoung Lee
Modified: 2021-05-29 08:41 PDT (History)
6 users (show)

See Also:
Fixed By Commit(s): c0b0da468490 c590a9880d7a 78e5cf66fec5 e2a0f512eaca c89d50033228 4a12f51ad009 266c82f94da2 8e2ff387d30d


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Juneyoung Lee 2021-04-04 06:45:04 PDT
```
$ cat src.ll
define void @src(<2 x i32> %input) {
    %cond = icmp eq <2 x i32> %input, zeroinitializer
    %.14 = extractelement <2 x i32> %input, i32 1
    %.15 = insertelement <2 x i32> poison, i32 %.14, i32 0
    %.16 = extractelement <2 x i32> %input, i32 0
    %.17 = insertelement <2 x i32> %.15, i32 %.16, i32 1
    %.18 = select <2 x i1> %cond, <2 x i32> %.17, <2 x i32> %input
    %x = extractelement <2 x i32> %.18, i32 0
    %y = extractelement <2 x i32> %.18, i32 1
    call void @f(i32 %x, i32 %y)
    ret void
}

declare void @f(i32, i32)
$ opt -instcombine -S -o - src.ll
define void @src(<2 x i32> %input) {
  %x = extractelement <2 x i32> %input, i32 0
  %y = extractelement <2 x i32> %input, i32 1
  call void @f(i32 %x, i32 %y)
  ret void
}

declare void @f(i32, i32)
```

This is incorrect: https://alive2.llvm.org/ce/z/8X-4kR
If input is <0, 2>, (%x, %y) is (2, 2) in src, but it becomes (0, 2) in tgt.
Comment 1 Sanjay Patel 2021-04-05 08:30:05 PDT
I'll look at this.

Reduced (don't need the initial insert/extract):

define void @src(<2 x i32> %x) {
  %r = shufflevector <2 x i32> %x, <2 x i32> undef, <2 x i32> <i32 1, i32 0>
  %cond = icmp eq <2 x i32> %x, zeroinitializer
  %s = select <2 x i1> %cond, <2 x i32> %r, <2 x i32> %x
  %s0 = extractelement <2 x i32> %s, i32 0
  %s1 = extractelement <2 x i32> %s, i32 1
  call void @f(i32 %s0, i32 %s1)
  ret void
}
Comment 2 Sanjay Patel 2021-04-05 09:42:08 PDT
We already had a regression test that Alive2 flags as a potential miscompile.

I think we just overlooked a basic requirement of select value equivalence substitution:
https://reviews.llvm.org/rGc0b0da468490
https://reviews.llvm.org/rGc590a9880d7a

Godbolt shows that this would be a new miscompile for release 12.0:
https://godbolt.org/z/qqbbxhe6z

I'm not sure what changed to make that visible, but let's see if we can still get this into the release. Marking as release blocker.
Comment 3 Nikita Popov 2021-04-05 10:34:55 PDT
It would be good to check that the same problem doesn't exist in InstSimplify (see simplifySelectWithICmpCond).
Comment 4 Sanjay Patel 2021-04-05 10:54:04 PDT
(In reply to Sanjay Patel from comment #2)
> I'm not sure what changed to make that visible, but let's see if we can
> still get this into the release. Marking as release blocker.

Aha - I'm losing track of reviews:
https://reviews.llvm.org/D96945

If that change is required to expose the bug, then it's not in the 12.0 release AFAIK.
Comment 5 Sanjay Patel 2021-04-05 11:16:35 PDT
(In reply to Nikita Popov from comment #3)
> It would be good to check that the same problem doesn't exist in
> InstSimplify (see simplifySelectWithICmpCond).

Yes, good point. Looks like we can still hit the bug there too.

https://alive2.llvm.org/ce/z/HGETc3

Not sure if it's just me, but the online instance of Alive2 is acting strange, so for reference that should show:
define <2 x i32> @src(<2 x i32> %x) {
%0:
  %x10 = shufflevector <2 x i32> %x, <2 x i32> undef, 1, 0
  %cond = icmp eq <2 x i32> %x, { 0, 0 }
  %s = select <2 x i1> %cond, <2 x i32> %x10, <2 x i32> { 0, 0 }
  ret <2 x i32> %s
}

=>

define <2 x i32> @tgt(<2 x i32> %x) {
%0:
  ret <2 x i32> { 0, 0 }
}

Transformation doesn't verify!
ERROR: Value mismatch

Example:
<2 x i32> %x = < #x00000000 (0), #xffffffff (4294967295, -1) >

Source:
<2 x i32> %x10 = < #xffffffff (4294967295, -1), #x00000000 (0) >
<2 x i1> %cond = < #x1 (1), #x0 (0) >
<2 x i32> %s = < #xffffffff (4294967295, -1), #x00000000 (0) >

Target:
Source value: < #xffffffff (4294967295, -1), #x00000000 (0) >
Target value: < #x00000000 (0), #x00000000 (0) >
Comment 6 Sanjay Patel 2021-04-05 14:11:44 PDT
InstSimplify patches:
https://reviews.llvm.org/rG78e5cf66fec5
https://reviews.llvm.org/rGe2a0f512eaca
Comment 7 Juneyoung Lee 2021-04-05 19:56:33 PDT
Thank you for the swift fix!
I also see that online Alive2 is a bit strange; since I am not familiar with the interaction between online Alive2 and the Alive2 binary, I have no idea what's happening.. I shared the issue with other Alive2 people.
Whenever there is a problem, feel free to send us (Nuno,John,me) mails. You can leave a thread at Alive2 repo's discussion forum as well. :)
Comment 8 Tom Stellard 2021-04-30 23:38:56 PDT
So all 4 commits listed in "Fixed By Commits" need to be backported?
Comment 9 Sanjay Patel 2021-05-03 07:12:21 PDT
(In reply to Tom Stellard from comment #8)
> So all 4 commits listed in "Fixed By Commits" need to be backported?

Yes, please.

Technically, we could fix this bug with the 1st two (instcombine) patches alone. But backporting all 4 (two patches are just adding tests / NFC) would be the best way to be sure we don't hit the problem in any code.
Comment 10 Tom Stellard 2021-05-03 16:39:29 PDT
(In reply to Sanjay Patel from comment #9)
> (In reply to Tom Stellard from comment #8)
> > So all 4 commits listed in "Fixed By Commits" need to be backported?
> 
> Yes, please.
> 
> Technically, we could fix this bug with the 1st two (instcombine) patches
> alone. But backporting all 4 (two patches are just adding tests / NFC) would
> be the best way to be sure we don't hit the problem in any code.

Can you double check that the list of commits is correct. 2a0f512eaca does not exist in the git tree.
Comment 11 Sanjay Patel 2021-05-03 16:54:16 PDT
(In reply to Tom Stellard from comment #10) 
> Can you double check that the list of commits is correct. 2a0f512eaca does
> not exist in the git tree.

Sorry lost a digit - that should be:
e2a0f512eaca
Comment 12 Shoaib Meenai 2021-05-10 12:51:33 PDT
Looks like 78e5cf66fec5 and e2a0f512eaca were cherry-picked to 12.x, and I'm now seeing llvm/test/Transforms/InstSimplify/select.ll fail on that branch:

/data/users/smeenai/llvm-project/llvm/test/Transforms/InstSimplify/select.ll:974:15: error: CHECK-NEXT: is not on the line after the previous match
; CHECK-NEXT: [[T1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]])
              ^
<stdin>:457:2: note: 'next' match was here
 %t1 = call i32 @llvm.ctpop.i32(i32 %x)
 ^
<stdin>:455:31: note: previous match ended here
define i32 @select_ctpop_zero(i32 %x) {
                              ^
<stdin>:456:1: note: non-matching line after previous match is here
 %t0 = icmp eq i32 %x, 0
^
Comment 13 Sanjay Patel 2021-05-10 13:07:33 PDT
(In reply to Shoaib Meenai from comment #12)
> Looks like 78e5cf66fec5 and e2a0f512eaca were cherry-picked to 12.x, and I'm
> now seeing llvm/test/Transforms/InstSimplify/select.ll fail on that branch:

Yes - this is my fault for letting a formatting change slip into the commit. 

I think the cherry-pick is over-reaching as described here (we picked up an extra test for the branch unintentionally):
https://github.com/llvm/llvm-project/commit/266c82f94da232d
Comment 14 Tom Stellard 2021-05-10 14:21:08 PDT
I committed a patch that should fix this: 
https://github.com/llvm/llvm-project/commit/2db5d42193abefcb41b10bd70b7ab536cb03f1cc
Comment 15 Tom Stellard 2021-05-10 14:27:21 PDT
Merged: 8e2ff387d30d