[InstCombine] Optimize icmp slt signum(x), 1 --> icmp slt x, 1.

[sanjoy]

Summary

signum(x) is sometimes implemented as (x >> 63) | (-x >>> 63) (for
an i64 x). This change adds a pattern matcher for that pattern, and
adds an instcombine rule to optimize signum(x) s< 1.

Later, we can also consider optimizing:

icmp slt signum(x), 0 --> icmp slt x, 0
icmp sle signum(x), 1 --> true

etc.

[majnemer]

include/llvm/IR/PatternMatch.h

1281–1284

Could you use getScalarSizeInBits? My thinking is that this would enable the transform to hack on vectors of integers. The only caveat is that you need to fail if it gives you back zero, this could happen if its a vector of pointers.

[sanjoy]

I changed the patternmatch to use to use getScalarSizeInBits, but
that does not work with vectors as-is since
visitICmpInstWithInstAndIntCst only looks at ConstantInts and not
ConstantVectors. I'm slightly hesitant to add untested code like
this, but given that this is at least partially tested (via the scalar
tests), I'm fine with checking this in if you are.

[sanjoy]

ping!

[majnemer]

Test cases seem a little bigger than they need to be. Why not just have the functions return the i1 result.

include/llvm/IR/PatternMatch.h

1289–1293

We don't use the terminology >>> in LLVM. I think it is more common to see >>u.

[sanjoy]

• address David's review

[majnemer]

LGTM

include/llvm/IR/PatternMatch.h

 }
 
 template <typename Opnd0, typename Opnd1>
 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
                                                         const Opnd1 &Op1) {
   return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
 }
 
+template <typename Opnd_t> struct Signum_match {
+  Opnd_t Val;
+  Signum_match(const Opnd_t &V) : Val(V) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    unsigned TypeSize = V->getType()->getScalarSizeInBits();
+    if (TypeSize == 0)
+      return false;
+
+    unsigned ShiftWidth = TypeSize - 1;
+    Value *OpL = nullptr, *OpR = nullptr;
+
+    // This is the representation of signum we match:
+    //
+    //  signum(x) == (x >> 63) | (-x >>> 63)
+    //
+    // An i1 value is its own signum, so it's correct to match
+    //
+    //  signum(x) == (x >> 0)  | (-x >>> 0)
+    //
+    // for i1 values.
+
+    auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
+    auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
+    auto Signum = m_Or(LHS, RHS);
+
+    return Signum.match(V) && OpL == OpR && Val.match(OpL);
+  }
+};
+
+/// \brief Matches a signum pattern.
+///
+/// signum(x) =
+///      x >  0  ->  1
+///      x == 0  ->  0
+///      x <  0  -> -1
+template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
+  return Signum_match<Val_t>(V);
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif

lib/Transforms/InstCombine/InstCombineCompares.cpp

 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                           Instruction *LHSI,
                                                           ConstantInt *RHS) {
   const APInt &RHSV = RHS->getValue();
 
   switch (LHSI->getOpcode()) {
   case Instruction::Trunc:
+    if (RHS->isOne() && RHSV.getBitWidth() > 1) {
+      // icmp slt trunc(signum(V)) 1 --> icmp slt V, 1
+      Value *V = nullptr;
+      if (ICI.getPredicate() == ICmpInst::ICMP_SLT &&
+          match(LHSI->getOperand(0), m_Signum(m_Value(V))))
+        return new ICmpInst(ICmpInst::ICMP_SLT, V,
+                            ConstantInt::get(V->getType(), 1));
+    }
     if (ICI.isEquality() && LHSI->hasOneUse()) {
       // Simplify icmp eq (trunc x to i8), 42 -> icmp eq x, 42|highbits if all
       // of the high bits truncated out of x are known.
       unsigned DstBits = LHSI->getType()->getPrimitiveSizeInBits(),
              SrcBits = LHSI->getOperand(0)->getType()->getPrimitiveSizeInBits();
       APInt KnownZero(SrcBits, 0), KnownOne(SrcBits, 0);
       computeKnownBits(LHSI->getOperand(0), KnownZero, KnownOne, 0, &ICI);
 
if (ICI.isEquality() && LHSI->hasOneUse() && match(RHS, m_Zero())) {
                                   : ICmpInst::ICMP_SLT,
                               Trunc, Constant::getNullValue(NTy));
         }
       }
     }
     break;
 
   case Instruction::Or: {
+    if (RHS->isOne()) {
+      // icmp slt signum(V) 1 --> icmp slt V, 1
+      Value *V = nullptr;
+      if (ICI.getPredicate() == ICmpInst::ICMP_SLT &&
+          match(LHSI, m_Signum(m_Value(V))))
+        return new ICmpInst(ICmpInst::ICMP_SLT, V,
+                            ConstantInt::get(V->getType(), 1));
+    }
+
     if (!ICI.isEquality() || !RHS->isNullValue() || !LHSI->hasOneUse())
       break;
     Value *P, *Q;
     if (match(LHSI, m_Or(m_PtrToInt(m_Value(P)), m_PtrToInt(m_Value(Q))))) {
       // Simplify icmp eq (or (ptrtoint P), (ptrtoint Q)), 0
       // -> and (icmp eq P, null), (icmp eq Q, null).
       Value *ICIP = Builder->CreateICmp(ICI.getPredicate(), P,
                                         Constant::getNullValue(P->getType()));

test/Transforms/InstCombine/compare-signs.ll

; CHECK: xor i32 %1, 1
         %3 = or i32 %1, 35
         %4 = icmp eq i32 %2, %3         ; <i1> [#uses=1]
         %5 = zext i1 %4 to i32          ; <i32> [#uses=1]
         ret i32 %5
 ; CHECK-NOT: icmp
 ; CHECK-NOT: zext
 ; CHECK: ret i32 %2
 }
+
+define i32 @test4a(i32 %a) {
+; CHECK-LABEL: @test4a(
+ entry:
+; CHECK: %c = icmp slt i32 %a, 1
+; CHECK-NEXT: br i1 %c, label %left, label %right
+  %l = ashr i32 %a, 31
+  %na = sub i32 0, %a
+  %r = lshr i32 %na, 31
+  %signum = or i32 %l, %r
+  %c = icmp slt i32 %signum, 1
+  br i1 %c, label %left, label %right
+
+ left:
+  ret i32 100
+
+ right:
+  ret i32 200
+}
+
+define i32 @test4b(i64 %a) {
+; CHECK-LABEL: @test4b(
+ entry:
+; CHECK: %c = icmp slt i64 %a, 1
+; CHECK-NEXT: br i1 %c, label %left, label %right
+  %l = ashr i64 %a, 63
+  %na = sub i64 0, %a
+  %r = lshr i64 %na, 63
+  %signum = or i64 %l, %r
+  %c = icmp slt i64 %signum, 1
+  br i1 %c, label %left, label %right
+
+ left:
+  ret i32 100
+
+ right:
+  ret i32 200
+}
+
+define i32 @test4c(i64 %a) {
+; CHECK-LABEL: @test4c(
+ entry:
+; CHECK: %c = icmp slt i64 %a, 1
+; CHECK-NEXT: br i1 %c, label %left, label %right
+  %l = ashr i64 %a, 63
+  %na = sub i64 0, %a
+  %r = lshr i64 %na, 63
+  %signum = or i64 %l, %r
+  %signum.trunc = trunc i64 %signum to i32
+  %c = icmp slt i32 %signum.trunc, 1
+  br i1 %c, label %left, label %right
+
+ left:
+  ret i32 100
+
+ right:
+  ret i32 200
+}