[InstCombine] infinite loop with select + compare canonicalization

[clin111]

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]

select-loop.ll.txt

[nikic]

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]

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]

@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]

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]

Thanks for the quick fix! Much appreciated.