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.

Sign up for GitHub

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

Jump to bottom

[IndVars] Incorrect comparison folding #56242

Closed
nikic opened this issue Jun 27, 2022 · 2 comments
Closed

[IndVars] Incorrect comparison folding #56242

nikic opened this issue Jun 27, 2022 · 2 comments
Assignees
@nikic
Labels
llvm:SCEV Scalar Evolution miscompilation

Comments

@nikic
Copy link
Contributor

nikic commented Jun 27, 2022 •
edited by VoltrexKeyva
Loading

In the following test (https://llvm.godbolt.org/z/rT64Yb1K6), -indvars currently folds %cmp2 to false:

declare void @use(i1)

define void @test(ptr %arr) {
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ %iv.inc, %loop.latch ], [ 0, %entry ]
  %prev = phi i32 [ %v, %loop.latch ], [ 0, %entry ]
  %ptr = getelementptr inbounds i32, ptr %arr, i64 %iv
  %v = load i32, ptr %ptr
  %cmp1 = icmp sgt i32 %v, 0
  br i1 %cmp1, label %if, label %loop.latch

if:
  %cmp2 = icmp slt i32 %prev, 0
  call void @use(i1 %cmp2)
  br label %loop.latch

loop.latch:
  %iv.inc = add nuw nsw i64 %iv, 1
  %cmp = icmp ult i64 %iv.inc, 16
  br i1 %cmp, label %loop.header, label %exit

exit:
  ret void
}

This is incorrect: While we have a guard that %v > 0, the value of %v in the %prev phi comes from the previous iteration, so the used context is incorrect.
@nikic nikic mentioned this issue Jun 27, 2022
Closed
@nikic nikic self-assigned this Jun 27, 2022
@nikic
Copy link
Contributor Author

nikic commented Jun 27, 2022

I believe https://reviews.llvm.org/D101829 previously tried to fix this issue, but the fix is incomplete. Here the incoming phi block is loop.latch, and %v does properly dominate the latch.

@nikic
Copy link
Contributor Author

nikic commented Jun 27, 2022

Candidate patch: https://reviews.llvm.org/D128640

@nikic nikic closed this as completed in e4d1d0c Jul 5, 2022
nikic added a commit to rust-lang/llvm-project that referenced this issue Jul 5, 2022
@nikic
[SCEV] Fix isImpliedViaMerge() with values from previous iteration (P…
3317cfe 
…R56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about values coming
from a backedge, as these may refer to a previous loop iteration.
A variant of this issue was fixed in D101829, but the dominance
condition used there isn't quite right: It checks that the value
dominates the incoming block, which doesn't exclude backedges
(values defined in a loop will usually dominate the loop latch,
which is the incoming block of the backedge).

Instead, we should be checking for domination of the phi block.
Any values defined inside the loop will not dominate the loop
header phi.

Fixes llvm#56242.

Differential Revision: https://reviews.llvm.org/D128640

(cherry picked from commit e4d1d0c)
Mark-Simulacrum pushed a commit to rust-lang/llvm-project that referenced this issue Jul 9, 2022
@nikic @Mark-Simulacrum
[SCEV] Fix isImpliedViaMerge() with values from previous iteration (P…
fc0ffca 
…R56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about values coming
from a backedge, as these may refer to a previous loop iteration.
A variant of this issue was fixed in D101829, but the dominance
condition used there isn't quite right: It checks that the value
dominates the incoming block, which doesn't exclude backedges
(values defined in a loop will usually dominate the loop latch,
which is the incoming block of the backedge).

Instead, we should be checking for domination of the phi block.
Any values defined inside the loop will not dominate the loop
header phi.

Fixes llvm#56242.

Differential Revision: https://reviews.llvm.org/D128640

(cherry picked from commit e4d1d0c)
sveitser added a commit to EspressoSystems/cape that referenced this issue Jul 18, 2022
@sveitser
Temporarily switch to nightly rust
e9ec202 
Version 20220717 includes a fix for
llvm/llvm-project#56242
sveitser added a commit to EspressoSystems/cape that referenced this issue Jul 19, 2022
@sveitser
Rust nightly for llvm bug (#1202)
ad21447 
* Temporarily switch to nightly rust

Version 20220717 includes a fix for
llvm/llvm-project#56242

* Make clippy happy

- Fix most lints.
- Allow a few tedious and false positive lints.

* rust latest -> 2022-07-17
bmwiedemann pushed a commit to bmwiedemann/openSUSE that referenced this issue Sep 8, 2022
@bmwiedemann
Update llvm14 to version 14.0.6 / rev 9 via SR 1001713
406f7fc 
https://build.opensuse.org/request/show/1001713
by user aaronpuchert + dimstar_suse
- Make sure we keep -DNDEBUG. At some point %{optflags} must have
  lost it, perhaps because CMake usually adds it on top. So when
  overriding CMAKE_{C,CXX}_FLAGS_RELWITHDEBINFO, we make sure to
  take over the other flags. We drop LLVM_ENABLE_ASSERTIONS=OFF,
  because that's the default anyway and hasn't helped here.
- Add llvm-scev-fix-isImpliedViaMerge.patch: fixes a miscompilation
  caused by mixing up values of the current and previous iteration.
  (See gh#llvm/llvm-project#56242.)
mem-frob pushed a commit to draperlaboratory/hope-llvm-project that referenced this issue Oct 7, 2022
@nikic
[SCEV] Fix isImpliedViaMerge() with values from previous iteration (P…
2aae94e 
…R56242)

When trying to prove an implied condition on a phi by proving it
for all incoming values, we need to be careful about values coming
from a backedge, as these may refer to a previous loop iteration.
A variant of this issue was fixed in D101829, but the dominance
condition used there isn't quite right: It checks that the value
dominates the incoming block, which doesn't exclude backedges
(values defined in a loop will usually dominate the loop latch,
which is the incoming block of the backedge).

Instead, we should be checking for domination of the phi block.
Any values defined inside the loop will not dominate the loop
header phi.

Fixes llvm/llvm-project#56242.

Differential Revision: https://reviews.llvm.org/D128640
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nikic nikic

Labels
llvm:SCEV Scalar Evolution miscompilation
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@nikic @EugeneZelenko