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

[InstCombine] Infinite loop with select / icmp #48244

Closed
fhahn opened this issue Jan 27, 2021 · 4 comments
Closed

[InstCombine] Infinite loop with select / icmp #48244

fhahn opened this issue Jan 27, 2021 · 4 comments
Assignees
Labels
bugzilla Issues migrated from bugzilla

Comments

@fhahn
Copy link
Contributor

fhahn commented Jan 27, 2021

Bugzilla Link 48900
Resolution FIXED
Resolved on May 04, 2021 09:05
Version trunk
OS All
Blocks #46259
CC @LebedevRI,@RKSimon,@nikic,@rotateright

Extended Description

Running opt -instcombine on the function below triggers an infinite loop in instcombine and it looks like it does not get caught by the existing checks.

define i32 @​clamp_check_for_no_infinite_loop3(i32 %i) {
%i2 = icmp ugt i32 %i, 1
%i3 = select i1 %i2, i32 %i, i32 1
%i4 = icmp sgt i32 %i3, 0
br i1 %i4, label %truelabel, label %falselabel

truelabel: ; preds = %0
%i5 = icmp slt i32 %i3, 2
%i6 = select i1 %i5, i32 %i3, i32 2
%i7 = shl nuw nsw i32 %i6, 2
ret i32 %i7

falselabel: ; preds = %0
ret i32 0
}

This is a reduced version of https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29957

@fhahn
Copy link
Contributor Author

fhahn commented Jan 27, 2021

assigned to @rotateright

@fhahn
Copy link
Contributor Author

fhahn commented Jan 27, 2021

Note that this is similar to the existing @​clamp_check_for_no_infinite_loop3 in llvm/test/Transforms/InstCombine/minmax-fold.ll, but with some predicates flipped.

@rotateright
Copy link
Contributor

We could view this as a missing optimization.

The special-case of clamping to a range of only 2 values can be reduced to a single cmp+select:
https://alive2.llvm.org/ce/z/txD5Dk

I don't know why we don't hit the same inf-loop for the signed predicate example. I'll take a look.

@rotateright
Copy link
Contributor

The existing test looks similar, but it's not the same as the new problem case.

I added a test that shows we can hit the same infinite loop using a different combination of predicates here:
https://reviews.llvm.org/rGa6f79b56711e

The opposing transforms are within InstCombinerImpl::foldICmpWithDominatingICmp() and canonicalizeMinMaxWithConstant().

For intrinsics, I also added the min/max clamp optimization suggested in the previous comment::
https://reviews.llvm.org/rG025bb5290379

We could replicate that for cmp+select, but I'm not sure if that would guarantee that we don't inf-loop. Hopefully, we can switch over to the intrinsics soon and not have to deal with these conflicts as much within instcombine.

@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bugzilla Issues migrated from bugzilla
Projects
None yet
Development

No branches or pull requests

2 participants