[InstCombineCompares] Added shl optimization for the instruction - icmp ugt/ult/uge/ule (shl Const2, A), Const1

[ankur29.garg]

Summary

Hi,
The following patch implements the optimization for the instructions of the type:
icmp ugt/ult/uge/ule (shl Const2, A), Const1

Such instructions can be converted to:
icmp (operator) A, (LeadingZeros(Const2) - LeadingZeros(Const1))

where (operator) is based on the initial operator and the actual values of the constants.

This handles the unsigned inequality operators. Equality operators are handled in patch D5839.
This patch is an extension of above patch where only equality operators are handled for similar instructions.

For Signed Inequality operators, such optimizations can't be made as with each left shift a signed number may keep changing the sign. So, such optimizations can't be performed.

Please help in reviewing it.

Thanks.
Ankur

[majnemer]

test/Transforms/InstCombine/icmp.ll

1549–1555

Consider when %a is 31: %shl will be 0 which will mean %cmp is actually false, not true.

1557–1588

These have similar problems to the previous test case.

1590–1597

Consider when %a is 31: %shl will be 0 which will mean %cmp should be false.

However, this transform would make %cmp true.

1599–1606

Consider when %a is 30: %shl will be 0 which will mean %cmp should be true.

However, this transform would make %cmp false.

1608–1651

I'm pretty sure these aren't correct transformations either.

[ankur29.garg]

Hi David,
Thanks for reviewing the patch.
I have made the changes to correct the error you pointed out.

There are two cases:
Const 1 < Const 2
In this case i have added separate if else for the cases you have mentioned. So, this case is correct now.
Const 1 > Const 2
In this case, if Const 2 has some trailing zeros, that means it can be made zero by left shifting by an amount less than its bit width. In such cases, after the transformation, expression will involve two comparisons. For example:

%shl = shl i32 76, %a
%cmp = icmp ugt i32 %shl, 108
ret i1 %cmp
here %a should be greater than 0 and less than 31
So, this transformation is infact increasing the number of operations required. After the transformation this would become:
and (icmp ugt i32 A, 0), (icmp ult i32 A, 31)
This involves 3 operations (greater than the earlier 2).
So, I haven't included transformations for such cases as it is not leading to optimization.
Please suggest any other way to do this, if possible.
Please review the updated revision.

Thanks.

[majnemer]

In D6131#6, @ankur29.garg wrote:

Hi David,
Thanks for reviewing the patch.
I have made the changes to correct the error you pointed out.

There are two cases:
Const 1 < Const 2
In this case i have added separate if else for the cases you have mentioned. So, this case is correct now.
Const 1 > Const 2
In this case, if Const 2 has some trailing zeros, that means it can be made zero by left shifting by an amount less than its bit width. In such cases, after the transformation, expression will involve two comparisons. For example:

%shl = shl i32 76, %a
%cmp = icmp ugt i32 %shl, 108
ret i1 %cmp
here %a should be greater than 0 and less than 31
So, this transformation is infact increasing the number of operations required. After the transformation this would become:
and (icmp ugt i32 A, 0), (icmp ult i32 A, 31)

(and (icmp ugt i32 A, 0), (icmp ult i32 A, 31)) is equivalent to (icmp ult (add i32 A, -1), 30)

This involves 3 operations (greater than the earlier 2).
So, I haven't included transformations for such cases as it is not leading to optimization.
Please suggest any other way to do this, if possible.
Please review the updated revision.

Thanks.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1172–1175

Please adhere to the coding standards: http://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

1181

Please clang-format this.

1185–1196

Can this be handled in one step as:

return new ICmpInst(I.getPredicate(), A,
                    ConstantInt::get(A->getType(), Shift));

[ankur29.garg]

Hi,
I have made the changes as per your in-line comments.

About the transformation for even const2:

"(and (icmp ugt i32 A, 0), (icmp ult i32 A, 31)) is equivalent to (icmp ult (add i32 A, -1), 30)"

This still transforms the initial two instructions into 2 instructions. I wanted to ask, is it useful to include this transformation.

[ankur29.garg]

Hi,
I found some errors in this optimization. Left-shifting an integer may cause it become lesser or greater than a constant based on the ordering of the bits.
For example,
AP1 = 01010000
AP2 = 00000101

if %a = 4, AP2 = AP1
if %a = 5, AP2 u> AP1
if %a = 6, AP2 u< AP1

I don't think this optimization is possible for 'shl'.
I will work on finding another way to do this, if possible.

Thanks.

[ankur29.garg]

This transformation is not possible for 'shl' instruction (example in the previous comment).

Thanks.

lib/Transforms/InstCombine/InstCombine.h

public:
   Instruction *FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
                               ConstantInt *DivRHS);
   Instruction *FoldICmpShrCst(ICmpInst &ICI, BinaryOperator *DivI,
                               ConstantInt *DivRHS);
   Instruction *FoldICmpCstShrCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
                                  ConstantInt *CI1, ConstantInt *CI2);
+  Instruction *FoldUICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
+                                 ConstantInt *CI1, ConstantInt *CI2);
   Instruction *FoldICmpAddOpCst(Instruction &ICI, Value *X, ConstantInt *CI,
                                 ICmpInst::Predicate Pred);
   Instruction *FoldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
                            ICmpInst::Predicate Cond, Instruction &I);
   Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
                                    BinaryOperator &I);
   Instruction *commonCastTransforms(CastInst &CI);
   Instruction *commonPointerCastTransforms(CastInst &CI);

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::FoldICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
 
   if (Shift > 0 && AP2.shl(Shift) == AP1)
     return getICmp(I.ICMP_EQ, A, ConstantInt::get(A->getType(), Shift));
 
   // Shifting const2 will never be equal to const1.
   return getConstant(false);
 }
 
+/// FoldUICmpCstShlCst - Handle "(icmp ugt/uge/ult/ule (shl const2, A), const1)"
+/// -> (icmp eq/ne A, LeadingZeros(const2) - LeadingZeros(const1)).
+Instruction *InstCombiner::FoldUICmpCstShlCst(ICmpInst &I, Value *Op, Value *A,
+                                              ConstantInt *CI1,
+                                              ConstantInt *CI2) {
+  assert(I.isUnsigned() && "Cannot fold icmp sgt/sge/slt/sle");
+
+  APInt AP1 = CI1->getValue();
+  APInt AP2 = CI2->getValue();
+
+  Instruction *Result = nullptr;
+
+  // Don't bother doing any work for cases which InstSimplify handles.
+  if (AP2 == 0 || AP1 == 0)
+    return nullptr;
+
+  if (AP1 == AP2) {
+    if (I.getPredicate() == I.ICMP_UGT) {
+      Result =
+          new ICmpInst(I.ICMP_NE, A, ConstantInt::getNullValue(A->getType()));
+    } else if (I.getPredicate() == I.ICMP_UGE) {
+      Result = ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), true));
+    } else if (I.getPredicate() == I.ICMP_ULT) {
+      Result = ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), false));
+    } else {
+      Result =
+          new ICmpInst(I.ICMP_EQ, A, ConstantInt::getNullValue(A->getType()));
+    }
+    return Result;
+  }
+
+  // Get the distance between the highest bits that are set.
+  int AP2TrailingZeros = AP2.countTrailingZeros();
+  int Shift = AP2.countLeadingZeros() - AP1.countLeadingZeros();
+
+  if (AP1.ult(AP2)) {
+    if (I.getPredicate() == I.ICMP_UGT || I.getPredicate() == I.ICMP_UGE) {
+      if (AP2TrailingZeros == 0)
+        Result = ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), true));
+      else
+        Result =
+            new ICmpInst(I.ICMP_ULT, A,
+                         ConstantInt::get(A->getType(), AP2.getBitWidth() -
+                                                            AP2TrailingZeros));
+    } else {
+      if (AP2TrailingZeros == 0)
+        Result = ReplaceInstUsesWith(I, ConstantInt::get(I.getType(), false));
+      else
+        Result =
+            new ICmpInst(I.ICMP_UGE, A,
+                         ConstantInt::get(A->getType(), AP2.getBitWidth() -
+                                                            AP2TrailingZeros));
+    }
+  } else if (Shift >= 0 && AP2TrailingZeros == 0) {
+    if (AP2.shl(Shift) == AP1) {
+      Result = new ICmpInst(I.getPredicate(), A,
+                            ConstantInt::get(A->getType(), Shift));
+    } else {
+      if (AP2.shl(Shift).ugt(AP1))
+        Shift--;
+      if (I.getPredicate() == I.ICMP_UGT || I.getPredicate() == I.ICMP_UGE)
+        Result =
+            new ICmpInst(I.ICMP_UGT, A, ConstantInt::get(A->getType(), Shift));
+      else
+        Result = new ICmpInst(I.ICMP_ULT, A,
+                              ConstantInt::get(A->getType(), Shift + 1));
+    }
+  }
+
+  return Result;
+}
+
 /// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
 ///
 Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
                                                           Instruction *LHSI,
                                                           ConstantInt *RHS) {
   const APInt &RHSV = RHS->getValue();
 
   switch (LHSI->getOpcode()) {
if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
           // are correct using an SMT solver.
           if (!ICI.isSigned())
             CanFold = true;
           else {
             ConstantInt *ShiftedAndCst =
               cast<ConstantInt>(ConstantExpr::getShl(AndCst, ShAmt));
             ConstantInt *ShiftedRHSCst =
               cast<ConstantInt>(ConstantExpr::getShl(RHS, ShAmt));
-            
             if (!ShiftedAndCst->isNegative() && !ShiftedRHSCst->isNegative())
               CanFold = true;
           }
         }
 
         if (CanFold) {
           Constant *NewCst;
           if (ShiftOpcode == Instruction::Shl)
case ICmpInst::ICMP_UGE:
       return new ICmpInst(ICmpInst::ICMP_UGT, Op0,
                           Builder->getInt(CI->getValue()-1));
     case ICmpInst::ICMP_SGE:
       assert(!CI->isMinValue(true));                  // A >=s MIN -> TRUE
       return new ICmpInst(ICmpInst::ICMP_SGT, Op0,
                           Builder->getInt(CI->getValue()-1));
     }
 
-    if (I.isEquality()) {
-      ConstantInt *CI2;
-      if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) ||
-          match(Op0, m_LShr(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isEquality()) {
         // (icmp eq/ne (ashr/lshr const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShrCst(I, Op0, A, CI, CI2))
           return Inst;
       }
-      if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+    } else if (match(Op0, m_Shl(m_ConstantInt(CI2), m_Value(A)))) {
+      if (I.isEquality()) {
         // (icmp eq/ne (shl const2, A), const1)
         if (Instruction *Inst = FoldICmpCstShlCst(I, Op0, A, CI, CI2))
           return Inst;
+      } else if (I.isUnsigned()) {
+        // (icmp ult/ule/ugt/uge (shl const2, A), const1)
+        if (Instruction *Inst = FoldUICmpCstShlCst(I, Op0, A, CI, CI2))
+          return Inst;
       }
     }
 
     // If this comparison is a normal comparison, it demands all
     // bits, if it is a sign bit comparison, it only demands the sign bit.
     bool UnusedBit;
     isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
   }

test/Transforms/InstCombine/icmp.ll

 
 ; CHECK-LABEL: @icmp_sle_zero_add_nsw
 ; CHECK-NEXT: icmp slt i32 %a, 0
 define i1 @icmp_sle_zero_add_nsw(i32 %a) {
  %add = add nsw i32 %a, 1
  %cmp = icmp sle i32 %add, 0
  ret i1 %cmp
 }
+
+define i1 @shl_ugt_both_equal(i32 %a) {
+; CHECK-LABEL: @shl_ugt_both_equal(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 4895, %a
+  %cmp = icmp ugt i32 %shl, 4895
+  ret i1 %cmp
+}
+
+define i1 @shl_uge_both_equal(i32 %a) {
+; CHECK-LABEL: @shl_uge_both_equal(
+; CHECK-NEXT: ret i1 true
+  %shl = shl i32 4895, %a
+  %cmp = icmp uge i32 %shl, 4895
+  ret i1 %cmp
+}
+
+define i1 @shl_ult_both_equal(i32 %a) {
+; CHECK-LABEL: @shl_ult_both_equal(
+; CHECK-NEXT: ret i1 false
+  %shl = shl i32 4895, %a
+  %cmp = icmp ult i32 %shl, 4895
+  ret i1 %cmp
+}
+
+define i1 @shl_ule_both_equal(i32 %a) {
+; CHECK-LABEL: @shl_ule_both_equal(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 4895, %a
+  %cmp = icmp ule i32 %shl, 4895
+  ret i1 %cmp
+}
+
+define i1 @shl_ugt_ap2_greater(i32 %a) {
+; CHECK-LABEL: @shl_ugt_ap2_greater(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 31
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 498, %a
+  %cmp = icmp ugt i32 %shl, 123
+  ret i1 %cmp
+}
+
+define i1 @shl_uge_ap2_greater(i32 %a) {
+; CHECK-LABEL: @shl_uge_ap2_greater(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 31
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 498, %a
+  %cmp = icmp uge i32 %shl, 123
+  ret i1 %cmp
+}
+
+define i1 @shl_ult_ap2_greater(i32 %a) {
+; CHECK-LABEL: @shl_ult_ap2_greater(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 30
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 498, %a
+  %cmp = icmp ult i32 %shl, 123
+  ret i1 %cmp
+}
+
+define i1 @shl_ule_ap2_greater(i32 %a) {
+; CHECK-LABEL: @shl_ule_ap2_greater(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 30
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 498, %a
+  %cmp = icmp ule i32 %shl, 123
+  ret i1 %cmp
+}
+
+define i1 @shl_ugt_ap1_greater_1(i32 %a) {
+; CHECK-LABEL: @shl_ugt_ap1_greater_1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ugt i32 %shl, 108
+  ret i1 %cmp
+}
+
+define i1 @shl_uge_ap1_greater_1(i32 %a) {
+; CHECK-LABEL: @shl_uge_ap1_greater_1(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp uge i32 %shl, 108
+  ret i1 %cmp
+}
+
+define i1 @shl_ult_ap1_greater_1(i32 %a) {
+; CHECK-LABEL: @shl_ult_ap1_greater_1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ult i32 %shl, 108
+  ret i1 %cmp
+}
+
+define i1 @shl_ule_ap1_greater_1(i32 %a) {
+; CHECK-LABEL: @shl_ule_ap1_greater_1(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ule i32 %shl, 108
+  ret i1 %cmp
+}
+
+define i1 @shl_ugt_ap1_greater_2(i32 %a) {
+; CHECK-LABEL: @shl_ugt_ap1_greater_2(
+; CHECK-NEXT: %cmp = icmp ugt i32 %a, 1
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ugt i32 %shl, 150
+  ret i1 %cmp
+}
+
+define i1 @shl_uge_ap1_greater_2(i32 %a) {
+; CHECK-LABEL: @shl_uge_ap1_greater_2(
+; CHECK-NEXT: %cmp = icmp ne i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp uge i32 %shl, 150
+  ret i1 %cmp
+}
+
+define i1 @shl_ult_ap1_greater_2(i32 %a) {
+; CHECK-LABEL: @shl_ult_ap1_greater_2(
+; CHECK-NEXT: %cmp = icmp eq i32 %a, 0
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ult i32 %shl, 150
+  ret i1 %cmp
+}
+
+define i1 @shl_ule_ap1_greater_2(i32 %a) {
+; CHECK-LABEL: @shl_ule_ap1_greater_2(
+; CHECK-NEXT: %cmp = icmp ult i32 %a, 2
+; CHECK-NEXT: ret i1 %cmp
+  %shl = shl i32 75, %a
+  %cmp = icmp ule i32 %shl, 150
+  ret i1 %cmp
+}