[InstCombine] (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0)

[reames]

Summary

When checking whether an smin is positive, we can move the comparison to one of the inputs if the other is known positive. If the known positive one is the min, then the other can't be negative. If the other is the min, then we compute the min.

[sanjoy]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3180 ↗

(On Diff #49789)

Why not just use an if here?

3183 ↗

(On Diff #49789)

I think this needs to be isKnownPositive, since (sgt (smin 0 1) 0) == false but (sgt 1 0) == true.

[reames]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3183 ↗

(On Diff #49789)

You are correct.

[reames]

Updated patch which fixed bug Sanjoy pointed out

[sanjoy]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3181 ↗

(On Diff #49846)

This is more work for you, but I think the right thing to do here is introduce an isKnownPositive helper in ValueTracking.h -- doing two recursive walks on the same expression seems wasteful.

I'd say lets start with a simple isKnownPositive implementation (maybe one that just looks at !range metadata and computeKnownBits), which we can evolve in the future.

[reames]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3181 ↗

(On Diff #49846)

I disagree that introducing yet another independent implementation is a good idea.

To be blunt, the extra work to make the approach you're requesting work isn't worth it for this patch. I'll just abandon the patch instead because it turns out not to address the case I actually care about.

[sanjoy]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3181 ↗

(On Diff #49846)

I disagree that introducing yet another independent implementation is a good idea.

I grepped around in the codebase, and it looks like SimplifyICmpInst already has this idiom (i.e. isKnownNonNegative(X) followed by isKnownNonZero(X)), so I suppose one more instance of it can't hurt. The avoidable 6-deep traversal still irks me though -- maybe we can leave a FIXME here?

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
     {
     ConstantInt *CI2;    // I = icmp ugt (add (add A, B), CI2), CI
     if (I.getPredicate() == ICmpInst::ICMP_UGT &&
         match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
       if (Instruction *Res = ProcessUGT_ADDCST_ADD(I, A, B, CI2, CI, *this))
         return Res;
     }
 
+    // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0)
+    if (CI->isZero() && I.getPredicate() == ICmpInst::ICMP_SGT)
+      if (auto *SI = dyn_cast<SelectInst>(Op0)) {
+        SelectPatternResult SPR = matchSelectPattern(SI, A, B);
+        if (SPR.Flavor == SPF_SMIN) {
+          if (isKnownNonNegative(A, DL) && isKnownNonZero(A, DL))
+            return new ICmpInst(I.getPredicate(), B, CI);
+          if (isKnownNonNegative(B, DL) && isKnownNonZero(B, DL))
+            return new ICmpInst(I.getPredicate(), A, CI);
+        }
+      }
+    
+
     // The following transforms are only 'worth it' if the only user of the
     // subtraction is the icmp.
     if (Op0->hasOneUse()) {
       // (icmp ne/eq (sub A B) 0) -> (icmp ne/eq A, B)
       if (I.isEquality() && CI->isZero() &&
           match(Op0, m_Sub(m_Value(A), m_Value(B))))
         return new ICmpInst(I.getPredicate(), A, B);
 

llvm/trunk/test/Transforms/InstCombine/min-positive.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+@g = external global i32
+
+define i1 @test(i32 %other) {
+; CHECK-LABEL: @test
+; CHECK: %test = icmp sgt i32 %other, 0
+  %positive = load i32, i32* @g, !range !{i32 1, i32 2048}
+  %cmp = icmp slt i32 %positive, %other
+  %sel = select i1 %cmp, i32 %positive, i32 %other
+  %test = icmp sgt i32 %sel, 0
+  ret i1 %test
+}
+
+define i1 @test2(i32 %other) {
+; CHECK-LABEL: @test2
+; CHECK: %test = icmp sgt i32 %other, 0
+  %positive = load i32, i32* @g, !range !{i32 1, i32 2048}
+  %cmp = icmp slt i32 %other, %positive
+  %sel = select i1 %cmp, i32 %other, i32 %positive
+  %test = icmp sgt i32 %sel, 0
+  ret i1 %test
+}
+
+; %positive might be zero
+define i1 @test3(i32 %other) {
+; CHECK-LABEL: @test3
+; CHECK: %test = icmp sgt i32 %sel, 0
+  %positive = load i32, i32* @g, !range !{i32 0, i32 2048}
+  %cmp = icmp slt i32 %positive, %other
+  %sel = select i1 %cmp, i32 %positive, i32 %other
+  %test = icmp sgt i32 %sel, 0
+  ret i1 %test
+}