Add micro-optimization for 'icmp slt (or A, B), A' to instsimplify.

[nlewycky]

Summary

Add optimization for 'icmp slt (or A, B), A' and some related idioms based on knowledge of the sign bit for A and B.

No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table:

A is
+, -, +/-
F  F   F   +    B is
T  F   ?   -
?  F   ?   +/-

The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate.

There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers.

[nlewycky]

Added testcase which I forgot to include the first time.

[majnemer]

lib/Analysis/InstructionSimplify.cpp

2630–2639

If I understand correctly, you are saying that x|y < x is true if x is negative and y is not negative.
At first blush, this appears to be a specific case of a more general transform: x|y < x is true if x is negative and y has any bits set which are known not to be set in x.

[majnemer]

lib/Analysis/InstructionSimplify.cpp

2620

nullptr is preferred.

2622–2623

This can be:

if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS))))

2643–2644

Ditto.

[nlewycky]

Move the m_c_Op pattern matches out of ValueTracking.cpp and into PatternMatch.h. Reuse m_c_Or to simplify the new logic in InstructionSimplify.

Swap out a 0 for nullptr when used to initialize a pointer.

[nlewycky]

lib/Analysis/InstructionSimplify.cpp

2630–2639

Counterexample "(-2|1)<-2" --> "-1<-2" --> "false".

To sanity-check, I wrote a program that enumerates A=[-128..127], B=[-128..127] and emits all the results. That's what convinced me that only the sign bit matters.

[majnemer]

LGTM

[Eugene.Zelenko]

Committed in r266939.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
 
   /// Returns true if the given value is known be positive (i.e. non-negative
   /// and non-zero).
   bool isKnownPositive(Value *V, const DataLayout &DL, unsigned Depth = 0,
                        AssumptionCache *AC = nullptr,
                        const Instruction *CxtI = nullptr,
                        const DominatorTree *DT = nullptr);
 
+  /// Returns true if the given value is known be negative (i.e. non-positive
+  /// and non-zero).
+  bool isKnownNegative(Value *V, const DataLayout &DL, unsigned Depth = 0,
+                       AssumptionCache *AC = nullptr,
+                       const Instruction *CxtI = nullptr,
+                       const DominatorTree *DT = nullptr);
+
   /// isKnownNonEqual - Return true if the given values are known to be
   /// non-equal when defined. Supports scalar integer types only.
   bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
 
   /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use

include/llvm/IR/PatternMatch.h

 /// 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);
 }
 
+//===----------------------------------------------------------------------===//
+// Matchers for two-operands operators with the operators in either order
+//
+
+/// \brief Matches an ICmp with a predicate over LHS and RHS in either order.
+/// Does not swap the predicate.
+template<typename LHS, typename RHS>
+inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
+                        CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
+m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
+  return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
+}
+
+/// \brief Matches an And with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
+                        BinaryOp_match<RHS, LHS, Instruction::And>>
+m_c_And(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_And(L, R), m_And(R, L));
+}
+
+/// \brief Matches an Or with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
+                        BinaryOp_match<RHS, LHS, Instruction::Or>>
+m_c_Or(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_Or(L, R), m_Or(R, L));
+}
+
+/// \brief Matches an Xor with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
+                        BinaryOp_match<RHS, LHS, Instruction::Xor>>
+m_c_Xor(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif

lib/Analysis/InstructionSimplify.cpp

if (A && C && (A == C || A == D || B == C || B == D) &&
         Y = A;
         Z = C;
       }
       if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1))
         return V;
     }
   }
 
+  {
+    Value *Y = nullptr;
     // icmp pred (or X, Y), X
-  if (LBO && match(LBO, m_CombineOr(m_Or(m_Value(), m_Specific(RHS)),
-                                    m_Or(m_Specific(RHS), m_Value())))) {
+    if (LBO && match(LBO, m_c_Or(m_Value(Y), m_Specific(RHS)))) {
       if (Pred == ICmpInst::ICMP_ULT)
         return getFalse(ITy);
       if (Pred == ICmpInst::ICMP_UGE)
         return getTrue(ITy);
+
+      if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGE) {
+        bool RHSKnownNonNegative, RHSKnownNegative;
+        bool YKnownNonNegative, YKnownNegative;
+        ComputeSignBit(RHS, RHSKnownNonNegative, RHSKnownNegative, Q.DL, 0,
+                       Q.AC, Q.CxtI, Q.DT);
+        ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+                       Q.CxtI, Q.DT);
+        if (RHSKnownNonNegative && YKnownNegative)
+          return Pred == ICmpInst::ICMP_SLT ? getTrue(ITy) : getFalse(ITy);
+        if (RHSKnownNegative || YKnownNonNegative)
+          return Pred == ICmpInst::ICMP_SLT ? getFalse(ITy) : getTrue(ITy);
+      }
     }
     // icmp pred X, (or X, Y)
-  if (RBO && match(RBO, m_CombineOr(m_Or(m_Value(), m_Specific(LHS)),
-                                    m_Or(m_Specific(LHS), m_Value())))) {
+    if (RBO && match(RBO, m_c_Or(m_Value(Y), m_Specific(LHS)))) {
       if (Pred == ICmpInst::ICMP_ULE)
         return getTrue(ITy);
       if (Pred == ICmpInst::ICMP_UGT)
         return getFalse(ITy);
+
+      if (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLE) {
+        bool LHSKnownNonNegative, LHSKnownNegative;
+        bool YKnownNonNegative, YKnownNegative;
+        ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL, 0,
+                       Q.AC, Q.CxtI, Q.DT);
+        ComputeSignBit(Y, YKnownNonNegative, YKnownNegative, Q.DL, 0, Q.AC,
+                       Q.CxtI, Q.DT);
+        if (LHSKnownNonNegative && YKnownNegative)
+          return Pred == ICmpInst::ICMP_SGT ? getTrue(ITy) : getFalse(ITy);
+        if (LHSKnownNegative || YKnownNonNegative)
+          return Pred == ICmpInst::ICMP_SGT ? getFalse(ITy) : getTrue(ITy);
+      }
+    }
   }
 
   // icmp pred (and X, Y), X
   if (LBO && match(LBO, m_CombineOr(m_And(m_Value(), m_Specific(RHS)),
                                     m_And(m_Specific(RHS), m_Value())))) {
     if (Pred == ICmpInst::ICMP_UGT)
       return getFalse(ITy);
     if (Pred == ICmpInst::ICMP_ULE)

lib/Analysis/ValueTracking.cpp

if (auto *CI = dyn_cast<ConstantInt>(V))
     return CI->getValue().isStrictlyPositive();
   
   // TODO: We'd doing two recursive queries here.  We should factor this such
   // that only a single query is needed.
   return isKnownNonNegative(V, DL, Depth, AC, CxtI, DT) &&
     isKnownNonZero(V, DL, Depth, AC, CxtI, DT);
 }
 
+bool llvm::isKnownNegative(Value *V, const DataLayout &DL, unsigned Depth,
+                           AssumptionCache *AC, const Instruction *CxtI,
+                           const DominatorTree *DT) {
+  bool NonNegative, Negative;
+  ComputeSignBit(V, NonNegative, Negative, DL, Depth, AC, CxtI, DT);
+  return Negative;
+}
+
 static bool isKnownNonEqual(Value *V1, Value *V2, const Query &Q);
 
 bool llvm::isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
                           AssumptionCache *AC, const Instruction *CxtI,
                           const DominatorTree *DT) {
   return ::isKnownNonEqual(V1, V2, Query(DL, AC,
                                          safeCxtI(V1, safeCxtI(V2, CxtI)),
                                          DT));

 }
 
 bool llvm::isValidAssumeForContext(const Instruction *I,
                                    const Instruction *CxtI,
                                    const DominatorTree *DT) {
   return ::isValidAssumeForContext(const_cast<Instruction *>(I), CxtI, DT);
 }
 
-template<typename LHS, typename RHS>
-inline match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>,
-                        CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate>>
-m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
-  return m_CombineOr(m_ICmp(Pred, L, R), m_ICmp(Pred, R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>,
-                        BinaryOp_match<RHS, LHS, Instruction::And>>
-m_c_And(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_And(L, R), m_And(R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>,
-                        BinaryOp_match<RHS, LHS, Instruction::Or>>
-m_c_Or(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Or(L, R), m_Or(R, L));
-}
-
-template<typename LHS, typename RHS>
-inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
-                        BinaryOp_match<RHS, LHS, Instruction::Xor>>
-m_c_Xor(const LHS &L, const RHS &R) {
-  return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
-}
-
 static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero,
                                        APInt &KnownOne, unsigned Depth,
                                        const Query &Q) {
   // Use of assumptions is context-sensitive. If we don't have a context, we
   // cannot use them!
   if (!Q.AC || !Q.CxtI)
     return;
 

test/Transforms/InstSimplify/compare.ll

 
 define i1 @tautological9(i32 %x) {
   %add = add nuw i32 %x, 13
   %cmp = icmp ne i32 %add, 12
   ret i1 %cmp
 ; CHECK-LABEL: @tautological9(
 ; CHECK: ret i1 true
 }
+
+declare void @helper_i1(i1)
+; Series of tests for icmp s[lt|ge] (or A, B), A and icmp s[gt|le] A, (or A, B)
+define void @icmp_slt_sge_or(i32 %Ax, i32 %Bx) {
+; 'p' for positive, 'n' for negative, 'x' for potentially either.
+; %D is 'icmp slt (or A, B), A'
+; %E is 'icmp sge (or A, B), A' making it the not of %D
+; %F is 'icmp sgt A, (or A, B)' making it the same as %D
+; %G is 'icmp sle A, (or A, B)' making it the not of %D
+  %Aneg = or i32 %Ax, 2147483648
+  %Apos = and i32 %Ax, 2147483647
+  %Bneg = or i32 %Bx, 2147483648
+  %Bpos = and i32 %Bx, 2147483647
+
+  %Cpp = or i32 %Apos, %Bpos
+  %Dpp = icmp slt i32 %Cpp, %Apos
+  %Epp = icmp sge i32 %Cpp, %Apos
+  %Fpp = icmp sgt i32 %Apos, %Cpp
+  %Gpp = icmp sle i32 %Apos, %Cpp
+  %Cpx = or i32 %Apos, %Bx
+  %Dpx = icmp slt i32 %Cpx, %Apos
+  %Epx = icmp sge i32 %Cpx, %Apos
+  %Fpx = icmp sgt i32 %Apos, %Cpx
+  %Gpx = icmp sle i32 %Apos, %Cpx
+  %Cpn = or i32 %Apos, %Bneg
+  %Dpn = icmp slt i32 %Cpn, %Apos
+  %Epn = icmp sge i32 %Cpn, %Apos
+  %Fpn = icmp sgt i32 %Apos, %Cpn
+  %Gpn = icmp sle i32 %Apos, %Cpn
+
+  %Cxp = or i32 %Ax, %Bpos
+  %Dxp = icmp slt i32 %Cxp, %Ax
+  %Exp = icmp sge i32 %Cxp, %Ax
+  %Fxp = icmp sgt i32 %Ax, %Cxp
+  %Gxp = icmp sle i32 %Ax, %Cxp
+  %Cxx = or i32 %Ax, %Bx
+  %Dxx = icmp slt i32 %Cxx, %Ax
+  %Exx = icmp sge i32 %Cxx, %Ax
+  %Fxx = icmp sgt i32 %Ax, %Cxx
+  %Gxx = icmp sle i32 %Ax, %Cxx
+  %Cxn = or i32 %Ax, %Bneg
+  %Dxn = icmp slt i32 %Cxn, %Ax
+  %Exn = icmp sge i32 %Cxn, %Ax
+  %Fxn = icmp sgt i32 %Ax, %Cxn
+  %Gxn = icmp sle i32 %Ax, %Cxn
+
+  %Cnp = or i32 %Aneg, %Bpos
+  %Dnp = icmp slt i32 %Cnp, %Aneg
+  %Enp = icmp sge i32 %Cnp, %Aneg
+  %Fnp = icmp sgt i32 %Aneg, %Cnp
+  %Gnp = icmp sle i32 %Aneg, %Cnp
+  %Cnx = or i32 %Aneg, %Bx
+  %Dnx = icmp slt i32 %Cnx, %Aneg
+  %Enx = icmp sge i32 %Cnx, %Aneg
+  %Fnx = icmp sgt i32 %Aneg, %Cnx
+  %Gnx = icmp sle i32 %Aneg, %Cnx
+  %Cnn = or i32 %Aneg, %Bneg
+  %Dnn = icmp slt i32 %Cnn, %Aneg
+  %Enn = icmp sge i32 %Cnn, %Aneg
+  %Fnn = icmp sgt i32 %Aneg, %Cnn
+  %Gnn = icmp sle i32 %Aneg, %Cnn
+
+  call void @helper_i1(i1 %Dpp)
+  call void @helper_i1(i1 %Epp)
+  call void @helper_i1(i1 %Fpp)
+  call void @helper_i1(i1 %Gpp)
+  call void @helper_i1(i1 %Dpx)
+  call void @helper_i1(i1 %Epx)
+  call void @helper_i1(i1 %Fpx)
+  call void @helper_i1(i1 %Gpx)
+  call void @helper_i1(i1 %Dpn)
+  call void @helper_i1(i1 %Epn)
+  call void @helper_i1(i1 %Fpn)
+  call void @helper_i1(i1 %Gpn)
+  call void @helper_i1(i1 %Dxp)
+  call void @helper_i1(i1 %Exp)
+  call void @helper_i1(i1 %Fxp)
+  call void @helper_i1(i1 %Gxp)
+  call void @helper_i1(i1 %Dxx)
+  call void @helper_i1(i1 %Exx)
+  call void @helper_i1(i1 %Fxx)
+  call void @helper_i1(i1 %Gxx)
+  call void @helper_i1(i1 %Dxn)
+  call void @helper_i1(i1 %Exn)
+  call void @helper_i1(i1 %Fxn)
+  call void @helper_i1(i1 %Gxn)
+  call void @helper_i1(i1 %Dnp)
+  call void @helper_i1(i1 %Enp)
+  call void @helper_i1(i1 %Fnp)
+  call void @helper_i1(i1 %Gnp)
+  call void @helper_i1(i1 %Dnx)
+  call void @helper_i1(i1 %Enx)
+  call void @helper_i1(i1 %Fnx)
+  call void @helper_i1(i1 %Gnx)
+  call void @helper_i1(i1 %Dnn)
+  call void @helper_i1(i1 %Enn)
+  call void @helper_i1(i1 %Fnn)
+  call void @helper_i1(i1 %Gnn)
+; CHECK-LABEL: @icmp_slt_sge_or
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 %Dpx)
+; CHECK: call void @helper_i1(i1 %Epx)
+; CHECK: call void @helper_i1(i1 %Fpx)
+; CHECK: call void @helper_i1(i1 %Gpx)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 %Dxx)
+; CHECK: call void @helper_i1(i1 %Exx)
+; CHECK: call void @helper_i1(i1 %Fxx)
+; CHECK: call void @helper_i1(i1 %Gxx)
+; CHECK: call void @helper_i1(i1 %Dxn)
+; CHECK: call void @helper_i1(i1 %Exn)
+; CHECK: call void @helper_i1(i1 %Fxn)
+; CHECK: call void @helper_i1(i1 %Gxn)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+; CHECK: call void @helper_i1(i1 false)
+; CHECK: call void @helper_i1(i1 true)
+  ret void
+}