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 + compare canonicalization #52684

Closed
clin111 opened this issue Dec 14, 2021 · 6 comments
Closed

[InstCombine] infinite loop with select + compare canonicalization #52684

clin111 opened this issue Dec 14, 2021 · 6 comments

Comments

@clin111
Copy link
Contributor

clin111 commented Dec 14, 2021

The attached test case is causing instcombine to infinite loop. The two transformations that are going back and forth are:

InstCombineSelect.cpp:

static Instruction * tryToReuseConstantFromSelectInComparison(....)

and:

InstCombineCompares.cpp:

Instruction *InstCombinerImpl::foldICmpAddConstant(...)
....
  // The range test idiom can use either ult or ugt. Arbitrarily canonicalize
  // to the ult form.
  // X+C2 >u C -> X+(C2-C-1) <u ~C
  if (Pred == ICmpInst::ICMP_UGT)

The select transformation is doing this:

  %1 = icmp ult i32 %0, 2
  %spec.select = select i1 %1, i32 1, i32 -3

=>

  %.inv = icmp ugt i32 %0, 1
  %spec.select = select i1 %.inv, i32 -3, i32 1

It is flipping the compare so that the constant becomes the same as one of the
select operands.

The compare canonicalization then undoes this transformation, as it changes "ugt" back to ult". It looks like
one of these transformations should be prevented, but it is not immediately clear which way is "better".

@clin111
Copy link
Contributor Author

clin111 commented Dec 14, 2021

select-loop.ll.txt

@nikic
Copy link
Contributor

nikic commented Dec 14, 2021

Slightly reduced:

define i32 @test(i32 %x) {
  %add = add i32 %x, -3
  %cmp = icmp ult i32 %add, 2
  %select = select i1 %cmp, i32 1, i32 -3
  ret i32 %select
}

@spatel-gh Any recommendation for the best way to resolve this?

@rotateright
Copy link
Contributor

Note: this is Sanjay, and I am @spatel-gh too, but I think all of my llvm work is credited to my @rotateright ID, so I'm posting from that.

We should decide if that select transform still has enough value to keep it alive vs. adapting it into codegen.

But as a fast fix, we can go with one more strategic exception (this patch solves the loop and doesn't change any existing tests - let me know if I should push it):

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
index 518d3952dce5..dd769bb73554 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -1482,7 +1482,13 @@ tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
   if (C0->getType() != Sel.getType())
     return nullptr;
 

-  // FIXME: are there any magic icmp predicate+constant pairs we must not touch?
+  // ULT with 'not' of an offset is canonical. See foldICmpAddConstant().
+  Constant *NotC0 = ConstantExpr::getNot(C0);
+  if (Pred == CmpInst::ICMP_ULT &&
+      match(X, m_Add(m_Value(), m_Specific(NotC0))))
+    return nullptr;
+
+  // FIXME: are there more magic icmp predicate+constant pairs we must avoid?
 
   Value *SelVal0, *SelVal1; // We do not care which one is from where.
   match(&Sel, m_Select(m_Value(), m_Value(SelVal0), m_Value(SelVal1)));

@nikic
Copy link
Contributor

nikic commented Dec 14, 2021

@rotateright I think it generally makes sense to exclude the pattern there (it's a hack, but a familiar hack...) but I don't really get where you are taking the ~C0 limitation from. Can't this occur with other constants in the add as well?

@rotateright
Copy link
Contributor

Ah, yes you're correct. I was looking at the infinite loop example instead of the code for the fold. I'll create a couple of tests, so we know the bailout works more generally.

@clin111
Copy link
Contributor Author

clin111 commented Dec 14, 2021

Thanks for the quick fix! Much appreciated.

@mkurdej mkurdej removed the new issue label Dec 28, 2021
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

5 participants