[CVP] Convert an AShr to a LShr if both operands are known to be nonnegative.

[mcrosier]

Summary

An arithmetic shift can be safely changed to a logical shift if the first operand is known positive. This allows ComputeKnownBits (and similar analysis) to determine the sign bit of the shifted value. In turn this allows InstCombine to canonicalize a signed comparison (a > 0) into an equality check (a != 0).

This fixes PR30577 and is the same approach taken in r263406.

Chad

[efriedma]

Whether the RHS is positive doesn't matter. (If it were negative, the result of the shift would be undef anyway.)

[mcrosier]

Address Eli's comment:
-Only check the first operand to ensure it is positive.

[mcrosier]

Ping.

[haicheng]

LGTM

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 
 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
+STATISTIC(NumAShrs,     "Number of ashr converted to lshr");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 
 static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(false));
 
 namespace {
   class CorrelatedValuePropagation : public FunctionPass {
   public:
     static char ID;
auto *BO = BinaryOperator::CreateUDiv(SDI->getOperand(0), SDI->getOperand(1),
                                         SDI->getName(), SDI);
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
   SDI->eraseFromParent();
 
   return true;
 }
 
+static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
+  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI))
+    return false;
+
+  Constant *Zero = ConstantInt::get(SDI->getType(), 0);
+  if (LVI->getPredicateAt(ICmpInst::ICMP_SGE, SDI->getOperand(0), Zero, SDI) !=
+      LazyValueInfo::True)
+    return false;
+
+  ++NumAShrs;
+  auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
+                                        SDI->getName(), SDI);
+  BO->setIsExact(SDI->isExact());
+  SDI->replaceAllUsesWith(BO);
+  SDI->eraseFromParent();
+
+  return true;
+}
+
 static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
   typedef OverflowingBinaryOperator OBO;
 
   if (DontProcessAdds)
     return false;
 
   if (AddOp->getType()->isVectorTy() || hasLocalDefs(AddOp))
     return false;
for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
         BBChanged |= processCallSite(CallSite(II), LVI);
         break;
       case Instruction::SRem:
         BBChanged |= processSRem(cast<BinaryOperator>(II), LVI);
         break;
       case Instruction::SDiv:
         BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::AShr:
+        BBChanged |= processAShr(cast<BinaryOperator>(II), LVI);
+        break;
       case Instruction::Add:
         BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
         break;
       }
     }
 
     Instruction *Term = BB.getTerminator();
     switch (Term->getOpcode()) {

llvm/trunk/test/Transforms/CorrelatedValuePropagation/ashr.ll

+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test1
+define void @test1(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %a = phi i32 [ %n, %entry ], [ %shr, %for.body ]
+  %cmp = icmp sgt i32 %a, 1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: lshr i32 %a, 5
+  %shr = ashr i32 %a, 5
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+;; Negative test to show transform doesn't happen unless n > 0.
+; CHECK-LABEL: @test2
+define void @test2(i32 %n) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %a = phi i32 [ %n, %entry ], [ %shr, %for.body ]
+  %cmp = icmp sgt i32 %a, -2
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+; CHECK: ashr i32 %a, 2
+  %shr = ashr i32 %a, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+;; Non looping test case.
+; CHECK-LABEL: @test3
+define void @test3(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: lshr exact i32 %n, 4
+  %shr = ashr exact i32 %n, 4
+  br label %exit
+
+exit:
+  ret void
+}