[InstCombine] Constant comparison involving "lshr exact"

[rahul.jain]

Summary

Hi all,

This is a follow up patch for http://llvm.org/viewvc/llvm-project?view=revision&revision=209903.
Added support to optimize comparisons with "lshr exact" of a constant
similar to "ashr exact".

I could have merged the code for both, but didnt seem to make much of a difference,
so handled after the code to handle "ashr exact".

Please help in reviewing the same.

Thanks,
Rahul

[• rafael]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2473–2474

This is not necessary, is it? match will have initialized CI2, so there is no uninitialized access.

2482

Can this share code with the above case? Use a helper function if needed. It looks like it could look something like

APInt Quotient;
if (...)

Quotient = CI2->getValue().sdiv(CI->getValue());

else if (...)

Quotient = CI2->getValue().udiv(CI->getValue());

else

// no transform.

[rahul.jain]

Hi Rafael,

Thanks for the review.
Refactored code accordingly! I dont feel the need to use
a helper function here.

Please help review the same.

Thanks,
Rahul

[• rafael]

There is still quiet a bit of duplicated code. For example

shift = Quotient.logBase2();
return new ICmpInst(I.getPredicate(), A,

ConstantInt::get(A->getType(), shift));
 ConstantInt::get(A->getType(), shift));

With a helper function it looks like you can return a boolean for "found optimization opportunity" and set the Quotient variable. That way the shif and the construction of the ICmpInst are shared.

[rahul.jain]

Hi Rafael,

Thanks for your valuable comments.
As per your suggestion, I implemented a helper function.

Please help review the same.

Thanks,
Rahul

[• rafael]

LGTM with two nits.

lib/Transforms/InstCombine/InstCombineCompares.cpp

2327

Start function name with a lowercase letter.

2338

No else needed after a return.

[rahul.jain]

Thanks Rafael, updated patch.

Please if you could commit the same for me.

Thanks a lot for your help!

Rahul

[• rafael]

r210040

[rahul.jain]

Thanks,
Rahul

lib/Transforms/InstCombine/InstCombineCompares.cpp

for (const User *U : Op0->users()) {
     }
     if (BinOp->getOperand(Op1Idx) != Op1)
       continue;
     GlobalSwapBenefits += LocalSwapBenefits;
   }
   return GlobalSwapBenefits > 0;
 }
 
+// Helper function to check whether Op represents a lshr/ashr exact
+// instruction. For example:
+// (icmp (ashr exact const2, A), const1) -> icmp A, Log2(const2/const1)
+// Here if Op represents -> (ashr exact const2, A), and CI represents
+// const1, we compute Quotient as const2/const1.
+
+static bool checkShrExact(Value *Op, APInt &Quotient, const ConstantInt *CI,
+                          Value *&A) {
+
+  ConstantInt *CI2;
+  if (match(Op, m_AShr(m_ConstantInt(CI2), m_Value(A))) &&
+      (cast<BinaryOperator>(Op)->isExact())) {
+    Quotient = CI2->getValue().sdiv(CI->getValue());
+    return true;
+  }
+
+  // Handle the case for lhsr.
+  if (match(Op, m_LShr(m_ConstantInt(CI2), m_Value(A))) &&
+      (cast<BinaryOperator>(Op)->isExact())) {
+    Quotient = CI2->getValue().udiv(CI->getValue());
+    return true;
+  }
+
+  return false;
+}
+
 Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   bool Changed = false;
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
if (I.isEquality() && CI->isZero() &&
       // (icmp cond A B) if cond is equality
       return new ICmpInst(I.getPredicate(), A, B);
     }
 
     // PR19753:
     // (icmp (ashr exact const2, A), const1) -> icmp A, Log2(const2/const1)
     // Cases where const1 doesn't divide const2 exactly or Quotient is not
     // exact of log2 are handled by SimplifyICmpInst call above where we
-    // return false.
-    // TODO: Handle this for lshr exact with udiv.
+    // return false. Similar for lshr.
     {
-      ConstantInt *CI2;
-      if (match(Op0, m_AShr(m_ConstantInt(CI2), m_Value(A))) &&
-          (cast<BinaryOperator>(Op0)->isExact())) {
-        APInt Quotient = CI2->getValue().sdiv(CI->getValue());
+      APInt Quotient;
+      if (checkShrExact(Op0, Quotient, CI, A)) {
         unsigned shift = Quotient.logBase2();
         return new ICmpInst(I.getPredicate(), A,
                             ConstantInt::get(A->getType(), shift));
       }
     }
 
     // If we have an icmp le or icmp ge instruction, turn it into the
     // appropriate icmp lt or icmp gt instruction.  This allows us to rely on
     // them being folded in the code below.  The SimplifyICmpInst code has
     // already handled the edge cases for us, so we just assert on them.
     switch (I.getPredicate()) {
     default: break;
     case ICmpInst::ICMP_ULE:
       assert(!CI->isMaxValue(false));                 // A <=u MAX -> TRUE
       return new ICmpInst(ICmpInst::ICMP_ULT, Op0,

test/Transforms/InstCombine/icmp.ll

 
 ; CHECK-LABEL: @exact_ashr_eq_false
 ; CHECK-NEXT: icmp eq i32 %a, 1
 define i1 @exact_ashr_eq_false(i32 %a) {
   %shr = ashr exact i32 -30, %a
   %cmp = icmp eq i32 %shr, -15
   ret i1 %cmp
 }
+
+; CHECK-LABEL: @exact_lhsr
+; CHECK-NEXT: icmp eq i32 %a, 3
+define i1 @exact_lhsr(i32 %a) {
+  %shr = lshr exact i32 80, %a
+  %cmp = icmp eq i32 %shr, 10
+  ret i1 %cmp
+}