Skip to content

[InstCombine] Miscompilation caused by incorrect ICMP predicate #123151

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

Closed
mshockwave opened this issue Jan 16, 2025 · 5 comments
Closed

[InstCombine] Miscompilation caused by incorrect ICMP predicate #123151

mshockwave opened this issue Jan 16, 2025 · 5 comments

Comments

@mshockwave
Copy link
Member

This is discovered from 445.gobmk when compiling it with RISC-V LLVM:

clang --target riscv64-linux-gnu -mcpu=sifive-p670 -O1 -mno-implicit-float ...

This is the reproducer snippet:

define dso_local i1 @gg_sort.do.body.split(i32 %gap.0, i64 %width, ptr %base, ptr %div.out, ptr %add.ptr4.out, i64 noundef %nel) {
newFuncRoot:
  %sub = add i64 %nel, -1
  %mul = mul i64 %width, %sub
  %add.ptr = getelementptr inbounds nuw i8, ptr %base, i64 %mul
  br label %do.body.split

do.body.split:                                    ; preds = %newFuncRoot
  %mul1 = mul nsw i32 %gap.0, 10
  %add = add nsw i32 %mul1, 3
  %div = sdiv i32 %add, 13
  store i32 %div, ptr %div.out, align 4
  %conv2 = sext i32 %div to i64
  %mul3 = mul i64 %conv2, %width
  %add.ptr4 = getelementptr inbounds nuw i8, ptr %base, i64 %mul3
  store ptr %add.ptr4, ptr %add.ptr4.out, align 8
  %cmp5.not21 = icmp ugt ptr %add.ptr4, %add.ptr
  br i1 %cmp5.not21, label %for.end.exitStub, label %for.body.exitStub

for.end.exitStub:                                 ; preds = %do.body.split
  ret i1 true

for.body.exitStub:                                ; preds = %do.body.split
  ret i1 false
}

With this command:

opt -p instcombine input.ll ...

The following code is generated:

define dso_local i1 @gg_sort.do.body.split(i32 %gap.0, i64 %width, ptr %base, ptr %div.out, ptr %add.ptr4.out, i64 noundef %nel) {
newFuncRoot:
  br label %do.body.split

do.body.split:                                    ; preds = %newFuncRoot
  %sub = add i64 %nel, -1
  %mul = mul i64 %width, %sub
  %mul1 = mul nsw i32 %gap.0, 10
  %add = add nsw i32 %mul1, 3
  %div = sdiv i32 %add, 13
  store i32 %div, ptr %div.out, align 4
  %conv2 = sext i32 %div to i64
  %mul3 = mul i64 %width, %conv2
  %add.ptr4 = getelementptr inbounds nuw i8, ptr %base, i64 %mul3
  store ptr %add.ptr4, ptr %add.ptr4.out, align 8
  %cmp5.not21 = icmp samesign ugt i64 %mul3, %mul
  br i1 %cmp5.not21, label %for.end.exitStub, label %for.body.exitStub

for.end.exitStub:                                 ; preds = %do.body.split
  ret i1 true

for.body.exitStub:                                ; preds = %do.body.split
  ret i1 false
}

InstCombine reduces ICMP on pointers (i.e. %add.ptr and %add.ptr4) into ICMP of their offsets (i.e. %mul3 and %mul). I think the problem here is %mul3 and %mul might have different signs.

Changing ICMP into sign comparison solves this issue: %cmp5.not21 = icmp sgt i64 %mul3, %mul

@mshockwave mshockwave added bug Indicates an unexpected problem or unintended behavior miscompilation llvm:instcombine and removed new issue labels Jan 16, 2025
@llvmbot
Copy link
Member

llvmbot commented Jan 16, 2025

@llvm/issue-subscribers-bug

Author: Min-Yih Hsu (mshockwave)

This is discovered from 445.gobmk when compiling it with RISC-V LLVM: ``` clang --target riscv64-linux-gnu -mcpu=sifive-p670 -O1 -mno-implicit-float ... ``` This is the reproducer snippet: ```llvm define dso_local i1 @gg_sort.do.body.split(i32 %gap.0, i64 %width, ptr %base, ptr %div.out, ptr %add.ptr4.out, i64 noundef %nel) { newFuncRoot: %sub = add i64 %nel, -1 %mul = mul i64 %width, %sub %add.ptr = getelementptr inbounds nuw i8, ptr %base, i64 %mul br label %do.body.split

do.body.split: ; preds = %newFuncRoot
%mul1 = mul nsw i32 %gap.0, 10
%add = add nsw i32 %mul1, 3
%div = sdiv i32 %add, 13
store i32 %div, ptr %div.out, align 4
%conv2 = sext i32 %div to i64
%mul3 = mul i64 %conv2, %width
%add.ptr4 = getelementptr inbounds nuw i8, ptr %base, i64 %mul3
store ptr %add.ptr4, ptr %add.ptr4.out, align 8
%cmp5.not21 = icmp ugt ptr %add.ptr4, %add.ptr
br i1 %cmp5.not21, label %for.end.exitStub, label %for.body.exitStub

for.end.exitStub: ; preds = %do.body.split
ret i1 true

for.body.exitStub: ; preds = %do.body.split
ret i1 false
}

With this command:

opt -p instcombine input.ll ...

The following code is generated:
```llvm
define dso_local i1 @<!-- -->gg_sort.do.body.split(i32 %gap.0, i64 %width, ptr %base, ptr %div.out, ptr %add.ptr4.out, i64 noundef %nel) {
newFuncRoot:
  br label %do.body.split

do.body.split:                                    ; preds = %newFuncRoot
  %sub = add i64 %nel, -1
  %mul = mul i64 %width, %sub
  %mul1 = mul nsw i32 %gap.0, 10
  %add = add nsw i32 %mul1, 3
  %div = sdiv i32 %add, 13
  store i32 %div, ptr %div.out, align 4
  %conv2 = sext i32 %div to i64
  %mul3 = mul i64 %width, %conv2
  %add.ptr4 = getelementptr inbounds nuw i8, ptr %base, i64 %mul3
  store ptr %add.ptr4, ptr %add.ptr4.out, align 8
  %cmp5.not21 = icmp samesign ugt i64 %mul3, %mul
  br i1 %cmp5.not21, label %for.end.exitStub, label %for.body.exitStub

for.end.exitStub:                                 ; preds = %do.body.split
  ret i1 true

for.body.exitStub:                                ; preds = %do.body.split
  ret i1 false
}

InstCombine reduces ICMP on pointers (i.e. %add.ptr and %add.ptr4) into ICMP of their offsets (i.e. %mul3 and %mul). I think the problem here is %mul3 and %mul might have different signs.

Changing ICMP into sign comparison solves this issue: %cmp5.not21 = icmp sgt i64 %mul3, %mul

@mshockwave mshockwave removed the bug Indicates an unexpected problem or unintended behavior label Jan 16, 2025
@topperc
Copy link
Collaborator

topperc commented Jan 16, 2025

Based on the nuw flags on the GEPs, I think InstCombine is correct. Is it possible nel is 0?

@dtcxzyw
Copy link
Member

dtcxzyw commented Jan 16, 2025

InstCombine is correct: https://alive2.llvm.org/ce/z/SyRCQL

I think the problem here is %mul3 and %mul might have different signs.

It is impossible. getelementptr inbounds nuw implies that the index is non-negative: https://alive2.llvm.org/ce/z/zNzhJ3

@dtcxzyw
Copy link
Member

dtcxzyw commented Jan 16, 2025

Can you rebuild 445.gobmk with -fsanitize=pointer-overflow?
See also https://clang.llvm.org/docs/ReleaseNotes.html#potentially-breaking-changes

@mshockwave
Copy link
Member Author

Can you rebuild 445.gobmk with -fsanitize=pointer-overflow? See also https://clang.llvm.org/docs/ReleaseNotes.html#potentially-breaking-changes

Yes the sanitizer did point out there is a pointer overflow. I confirmed that -fno-strict-overflow also solves this problem.

Is it possible nel is 0?

From the addresses reported by the sanitizer, it is likely that nel might indeed be zero.

@dtcxzyw dtcxzyw added invalid Resolved as invalid, i.e. not a bug undefined behaviour labels Jan 16, 2025
@dtcxzyw dtcxzyw closed this as not planned Won't fix, can't repro, duplicate, stale Jan 16, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants