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

[InstCombine] InstCombine gets stuck when simplifying selects #83127

Closed
dtcxzyw opened this issue Feb 27, 2024 · 4 comments · Fixed by #84036
Closed

[InstCombine] InstCombine gets stuck when simplifying selects #83127

dtcxzyw opened this issue Feb 27, 2024 · 4 comments · Fixed by #84036
Assignees
@nikic @dtcxzyw
Labels
llvm:hang Compiler hang (infinite loop) llvm:instcombine

Comments

@dtcxzyw
Copy link
Member

dtcxzyw commented Feb 27, 2024

Reduced test case: https://godbolt.org/z/ds9eq96db

define i16 @func(i16 noundef %p_12) {
entry:
  %cmp1 = icmp ult i16 %p_12, 2
  %and1 = and i16 %p_12, 1
  %and2 = select i1 %cmp1, i16 %and1, i16 0
  %cmp2 = icmp eq i16 %and2, %p_12
  %and3 = select i1 %cmp2, i16 %and1, i16 0
  ret i16 %and3
}

ADD:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD DEFERRED:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Mod =   %and3 = select i1 %cmp2, i16 %and2, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %cmp2 = icmp eq i16 %and2, %p_12
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD DEFERRED:   %and1 = and i16 %p_12, 1
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Mod =   %and3 = select i1 %cmp2, i16 %and1, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and2, i16 0


ADD:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and1 = and i16 %p_12, 1
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and2, i16 0
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
ADD DEFERRED:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Mod =   %and3 = select i1 %cmp2, i16 %and2, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD:   %cmp2 = icmp eq i16 %and2, %p_12
ADD:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Visiting:   %cmp2 = icmp eq i16 %and2, %p_12
IC: Visiting:   %and3 = select i1 %cmp2, i16 %and1, i16 0
ADD DEFERRED:   %and1 = and i16 %p_12, 1
ADD DEFERRED:   %and2 = select i1 %cmp1, i16 %and1, i16 0
IC: Mod =   %and3 = select i1 %cmp2, i16 %and1, i16 0
    New =   %and3 = select i1 %cmp2, i16 %and2, i16 0

...
@dtcxzyw dtcxzyw added llvm:instcombine llvm:hang Compiler hang (infinite loop) labels Feb 27, 2024
@dtcxzyw dtcxzyw self-assigned this Feb 27, 2024
@patrick-rivos patrick-rivos mentioned this issue Feb 28, 2024
Closed
@dtcxzyw
Copy link
Member Author

dtcxzyw commented Mar 3, 2024

Another reproducer: https://godbolt.org/z/7MEYTe9cq

declare void @use(i32,i32)

define void @func(ptr %p) {
  %1 = load i32, ptr %p, align 4
  %2 = sext i32 %1 to i64
  %3 = icmp slt i64 %2, 2
  %4 = zext i1 %3 to i32
  %5 = and i32 %4, %1
  %6 = icmp eq i32 %5, %1
  %7 = zext i1 %6 to i32
  %8 = and i32 %7, %1
  call void @use(i32 %8, i32 noundef %1)
  ret void
}

@dtcxzyw
Copy link
Member Author

dtcxzyw commented Mar 3, 2024

Third reproducer: https://godbolt.org/z/8f8b4xved

define i8 @func(i32 noundef %p_38) {
entry:
  %conv393 = trunc i32 %p_38 to i8
  %0 = call i8 @llvm.bitreverse.i8(i8 %conv393)
  %conv394 = zext i8 %0 to i32
  %cmp395 = icmp eq i32 %conv394, %p_38
  %conv397 = zext i1 %cmp395 to i8
  %mul.i = mul i8 %conv393, %conv397
  ret i8 %mul.i
}

@dtcxzyw
Copy link
Member Author

dtcxzyw commented Mar 3, 2024

Third reproducer: https://godbolt.org/z/8f8b4xved

define i8 @func(i32 noundef %p_38) {
entry:
  %conv393 = trunc i32 %p_38 to i8
  %0 = call i8 @llvm.bitreverse.i8(i8 %conv393)
  %conv394 = zext i8 %0 to i32
  %cmp395 = icmp eq i32 %conv394, %p_38
  %conv397 = zext i1 %cmp395 to i8
  %mul.i = mul i8 %conv393, %conv397
  ret i8 %mul.i
}

A simpler testcase:

define i8 @func(i32 noundef %x) {
entry:
  %trunc = trunc i32 %x to i8
  %rev = call i8 @llvm.bitreverse.i8(i8 %trunc)
  %ext = zext i8 %rev to i32
  %cmp = icmp eq i32 %ext, %x
  %sel = select i1 %cmp, i8 %trunc, i8 0
  ret i8 %sel
}

@nikic I have no idea how to fix it in foldSelectValueEquivalence/simplifyWithOpReplaced. simplifyWithOpReplaced may replace the input x with a more complicated value f(x).

@dtcxzyw
Copy link
Member Author

dtcxzyw commented Mar 5, 2024

@nikic Ping.

nikic added a commit to nikic/llvm-project that referenced this issue Mar 5, 2024
@nikic
[InstCombine] Fix infinite loop in select equivalence fold
611c898 
When replacing with a non-constant, it's possible that the result
of the simplification is actually more complicated than the original,
and may result in an infinite combine loop.

Mitigate the issue by requiring that either the replacement or
simplification result is constant, which should ensure that it's
simpler. This is a very simple check that doesn't seem to cause
many regressions in our own tests, so let's see if it's good
enough.

Fixes llvm#83127.
@nikic nikic mentioned this issue Mar 5, 2024
Merged
nikic added a commit that referenced this issue Mar 6, 2024
@nikic
[InstCombine] Fix infinite loop in select equivalence fold (#84036)
9f45c5e 
When replacing with a non-constant, it's possible that the result of the
simplification is actually more complicated than the original, and may
result in an infinite combine loop.

Mitigate the issue by requiring that either the replacement or
simplification result is constant, which should ensure that it's
simpler. While this check is crude, it does not appear to cause
optimization regressions in real-world code in practice.

Fixes #83127.
llvmbot pushed a commit to llvmbot/llvm-project that referenced this issue Mar 6, 2024
@nikic @llvmbot
[InstCombine] Fix infinite loop in select equivalence fold (llvm#84036)
f91bdec 
When replacing with a non-constant, it's possible that the result of the
simplification is actually more complicated than the original, and may
result in an infinite combine loop.

Mitigate the issue by requiring that either the replacement or
simplification result is constant, which should ensure that it's
simpler. While this check is crude, it does not appear to cause
optimization regressions in real-world code in practice.

Fixes llvm#83127.

(cherry picked from commit 9f45c5e)
llvmbot pushed a commit to llvmbot/llvm-project that referenced this issue Mar 11, 2024
@nikic @tstellar
[InstCombine] Fix infinite loop in select equivalence fold (llvm#84036)
94d8f15 
When replacing with a non-constant, it's possible that the result of the
simplification is actually more complicated than the original, and may
result in an infinite combine loop.

Mitigate the issue by requiring that either the replacement or
simplification result is constant, which should ensure that it's
simpler. While this check is crude, it does not appear to cause
optimization regressions in real-world code in practice.

Fixes llvm#83127.

(cherry picked from commit 9f45c5e)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nikic nikic

@dtcxzyw dtcxzyw

Labels
llvm:hang Compiler hang (infinite loop) llvm:instcombine
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[InstCombine] Fix infinite loop in select equivalence fold nikic/llvm-project
2 participants
@nikic @dtcxzyw