Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[NewGVN] Miscompile with equal instructions modulo attributes #53218

Closed
nunoplopes opened this issue Jan 15, 2022 · 7 comments · Fixed by #67426
Closed

[NewGVN] Miscompile with equal instructions modulo attributes #53218

nunoplopes opened this issue Jan 15, 2022 · 7 comments · Fixed by #67426
Labels
llvm:GVN GVN and NewGVN stages (Global value numbering) llvm:optimizations miscompilation

Comments

@nunoplopes
Copy link
Member

NewGVN miscompiles the following function:

@glb = external global i64, align 8

define i64 @src(i64 %tmp) {
  %conv3 = shl nuw i64 %tmp, 32
  store i64 %conv3, i64* @glb, align 8
  %sext = shl i64 %tmp, 32
  %r = lshr exact i64 %sext, 32
  ret i64 %r
}

define i64 @tgt(i64 %tmp) {
  %conv3 = shl i64 %tmp, 32
  store i64 %conv3, i64* @glb, align 8
  ret i64 %tmp
}

NewGVN hashes instructions ignoring attributes like 'nuw', so it assumes that conv3 and sext above are equivalent. But then it uses %conv3 as the leader, and then it calls InstSimplify with shl nuw & lshr extract and bug!

Test case from @regehr.
cc @alinas

@nunoplopes
Copy link
Member Author

Another instance of the same bug. This one is more serious because it takes the inbounds attribute from a non-dominating BB.

define i1 @src(i32* %dst) {
entry:
  %dst.5 = getelementptr i32, i32* %dst, i64 5
  %dst.5.uge = icmp uge i32* %dst.5, %dst
  br i1 %dst.5.uge, label %then, label %else

then:
  %dst.6 = getelementptr i32, i32* %dst, i64 6
  %c.dst.6.uge = icmp uge i32* %dst.6, %dst
  ret i1 %c.dst.6.uge

else:
  %else.dst.6 = getelementptr inbounds i32, i32* %dst, i64 6
  %else.dst.6.uge = icmp uge i32* %else.dst.6, %dst
  ret i1 %else.dst.6.uge
}


define i1 @tgt(i32* %dst) {
  %dst.5 = getelementptr i32, i32* %dst, i64 5
  %dst.5.uge = icmp uge i32* %dst.5, %dst
  br i1 %dst.5.uge, label %then, label %else

then:
  ret i1 true

else:
  ret i1 true
}

https://llvm.godbolt.org/z/P79dGGszE

@nunoplopes
Copy link
Member Author

Another one:

define void @src(i8 %start, i8 %high) {
  %start1 = add nsw i8 %start, 4
  %t1 = icmp ult i8 %start1, %high
  call void @use(i1 %t1)

  %start2 = add i8 %start, 4
  %t2 = icmp ult i8 %start2, %high
  call void @use(i1 %t2)
  ret void
}


define void @tgt(i8 %start, i8 %high) {
  %start1 = add nsw i8 %start, 4
  %t1 = icmp ult i8 %start1, %high
  call void @use(i1 %t1)
  call void @use(i1 %t1)
  ret void
}

declare void @use(i1)

@fhahn
Copy link
Contributor

fhahn commented Jan 18, 2022

cc @fhahn

@nunoplopes
Copy link
Member Author

InstSimplify has most rewrites that use nsw/nuw/exact attributes guarded by Q.IIQ.UseInstrInf && .... NewGVN sets that flag to false, so those rewrites don't kick in.
I see 5 rewrites that miss that check. Fixing those would only fix the first example though (where nuw from the leader is used). But it wouldn't fix the other 2 examples.
So I propose we get rid of this hack of UseInstrInf. It doesn't solve the root cause.

I guess the v1 fix would be to simply include the nsw/nuw/exact attributes in the GVN expression. Then we can work out if some selecting merging of classes by dropping attributes makes sense. Or some other heuristic.

@nunoplopes
Copy link
Member Author

NewGVN does intercept the attributes when replacing an instruction with the leader. But it doesn't do that recursively. So it doesn't get the 3rd example, where t1/t2 are equal, except for their first operand that differs in nsw.
If we don't consider 'add' and 'add nsw' equivalent the problem is solved. Another way is to intercept attributes recursively. I would go with separate classes for v1.

@regehr
Copy link
Contributor

regehr commented May 2, 2022

here's a testcase for this bug that I like even better than the other ones:

@f = external global i64, align 8

define i64 @src(i64 %tmp) {
entry:
  %conv3 = shl nuw i64 %tmp, 32
  store i64 %conv3, i64* @f, align 8
  %sext = shl i64 %tmp, 32
  %0 = lshr i64 %sext, 32
  ret i64 %0
}

define i64 @tgt(i64 %tmp) {
entry:
  %conv3 = shl i64 %tmp, 32
  store i64 %conv3, i64* @f, align 8
  ret i64 %tmp
}

src(0x0000000100000000) -> 0
but
tgt(x0000000100000000) -> x0000000100000000

@jayfoad jayfoad added the llvm:GVN GVN and NewGVN stages (Global value numbering) label Jul 12, 2022
@nunoplopes nunoplopes reopened this Jul 26, 2023
eymay pushed a commit to eymay/llvm-project that referenced this issue Jul 28, 2023
Regenerate some test checks in  preparation for a patch that
fixes llvm#53218.
razmser pushed a commit to razmser/llvm-project that referenced this issue Sep 8, 2023
Regenerate some test checks in  preparation for a patch that
fixes llvm#53218.
nikic added a commit that referenced this issue Sep 26, 2023
nikic added a commit that referenced this issue Sep 26, 2023
Some folds using m_NUW, m_NSW style matchers were missed, make
sure they respect UseInstrInfo.

This is part of #53218, but not a complete fix for the issue.
nikic added a commit that referenced this issue Sep 26, 2023
nikic added a commit to nikic/llvm-project that referenced this issue Sep 26, 2023
When removing an instruction, we still need to merge its IR flags
into the leader, because there may have been a transitive use.

Fixes llvm#53218.
@nikic
Copy link
Contributor

nikic commented Sep 26, 2023

I've fixed the obvious UseInstrInfo holes and put up #67426 to fix the other issue that Nuno found. I think the core problem is that we end up not doing the "patch replacement instructions" if an instruction gets removed. That's why we miss up on flag updates if there is some transitive use and the intermediate instruction is dropped.

@nikic nikic closed this as completed in 8e353fb Sep 28, 2023
legrosbuffle pushed a commit to legrosbuffle/llvm-project that referenced this issue Sep 29, 2023
legrosbuffle pushed a commit to legrosbuffle/llvm-project that referenced this issue Sep 29, 2023
When removing an instruction, we still need to merge its IR flags
into the leader, because there may have been a transitive use.

Fixes llvm#53218.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
llvm:GVN GVN and NewGVN stages (Global value numbering) llvm:optimizations miscompilation
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants