[CVP] Process binary operations even when def is local

[anna]

Summary

This patch adds processing of binary operations when the def of operands are in
the same block (i.e. local processing).

Earlier we bailed out in such cases (the bail out was introduced in rL252032)
because LVI at that time was more precise about context at the end of basic
blocks, which implied local def and use analysis didn't benefit CVP.

Since then we've added support for LVI in presence of assumes and guards. The
test cases added show how local def processing in CVP helps adding more
information to the ashr, sdiv, srem and add operators.

Note: processCmp which suffers from the same problem will
be handled in a later patch.

[apilipenko]

Did you measure the compile time impact somehow?

The patch itself looks good to me.

[anna]

In D38766#895817, @apilipenko wrote:

Did you measure the compile time impact somehow?

Compile time results on CTMark benchmarks show compile time is not affected by this change:

Tests: 10
Metric: compile_time

Program                                        Patch   NoPatch           diff
sqlite3/sqlite3                                35.23   35.53             0.8%
tramp3d-v4/tramp3d-v4                          49.20   49.61             0.8%
lencod/lencod                                  34.92   35.09             0.5%
Bullet/bullet                                  54.23   54.02            -0.4%
mafft/pairlocalalign                           20.22   20.29             0.3%
SPASS/SPASS                                    29.78   29.87             0.3%
7zip/7zip-benchmark                            79.72   79.50            -0.3%
kimwitu++/kc                                   27.46   27.53             0.3%
ClamAV/clamscan                                32.89   32.95             0.2%
consumer-typeset/consumer-typeset              23.23   23.20            -0.1%

Also discussed offline with Philip (wrt change rL252032). LVI over time has been greatly improved to get rid of compile time bottlenecks, so the compile time reason to have the LocalDefs constraint is no longer that relevant.

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
   LLVMContext &Ctx = CS.getInstruction()->getContext();
   AS = AS.addParamAttribute(Ctx, ArgNos,
                             Attribute::get(Ctx, Attribute::NonNull));
   CS.setAttributes(AS);
 
   return true;
 }
 
-// Helper function to rewrite srem and sdiv. As a policy choice, we choose not
-// to waste compile time on anything where the operands are local defs.  While
-// LVI can sometimes reason about such cases, it's not its primary purpose.
-static bool hasLocalDefs(BinaryOperator *SDI) {
-  for (Value *O : SDI->operands()) {
-    auto *I = dyn_cast<Instruction>(O);
-    if (I && I->getParent() == SDI->getParent())
-      return true;
-  }
-  return false;
-}
-
 static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) {
   Constant *Zero = ConstantInt::get(SDI->getType(), 0);
   for (Value *O : SDI->operands()) {
     auto Result = LVI->getPredicateAt(ICmpInst::ICMP_SGE, O, Zero, SDI);
     if (Result != LazyValueInfo::True)
       return false;
   }
   return true;
 }
 
 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
-  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+  if (SDI->getType()->isVectorTy() ||
       !hasPositiveOperands(SDI, LVI))
     return false;
 
   ++NumSRems;
   auto *BO = BinaryOperator::CreateURem(SDI->getOperand(0), SDI->getOperand(1),
                                         SDI->getName(), SDI);
   SDI->replaceAllUsesWith(BO);
   SDI->eraseFromParent();
   return true;
 }
 
 /// See if LazyValueInfo's ability to exploit edge conditions or range
 /// information is sufficient to prove the both operands of this SDiv are
 /// positive.  If this is the case, replace the SDiv with a UDiv. Even for local
 /// conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
-  if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+  if (SDI->getType()->isVectorTy() ||
       !hasPositiveOperands(SDI, LVI))
     return false;
 
   ++NumSDivs;
   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))
+  if (SDI->getType()->isVectorTy())
     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))
+  if (AddOp->getType()->isVectorTy())
     return false;
 
   bool NSW = AddOp->hasNoSignedWrap();
   bool NUW = AddOp->hasNoUnsignedWrap();
   if (NSW && NUW)
     return false;
 
   BasicBlock *BB = AddOp->getParent();

test/Transforms/CorrelatedValuePropagation/add.ll

 ; CHECK: %add = add nsw i32 %a, 1
   %add = add i32 %a, 1
   br label %exit
 
 exit:
   ret void
 }
 
+; single basic block loop
+; because the loop exit condition is SLT, we can supplement the iv add
+; (iv.next def) with an nsw.
+; CHECK-LABEL: @test16(
+define i32 @test16(i32* %n, i32* %a) {
+preheader:
+  br label %loop
+
+loop:
+; CHECK: %iv.next = add nsw i32 %iv, 1
+  %iv = phi i32 [ 0, %preheader ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %preheader ], [ %acc.curr, %loop ]
+  %x = load atomic i32, i32* %a unordered, align 8
+  fence acquire
+  %acc.curr = add i32 %acc, %x
+  %iv.next = add i32 %iv, 1
+  %nval = load atomic i32, i32* %n unordered, align 8
+  %cmp = icmp slt i32 %iv.next, %nval
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret i32 %acc.curr
+}

test/Transforms/CorrelatedValuePropagation/ashr.ll

 bb:
 ; CHECK: lshr exact i32 %n, 4
   %shr = ashr exact i32 %n, 4
   br label %exit
 
 exit:
   ret void
 }
+
+; looping case where loop has exactly one block
+; at the point of ashr, we know that the operand is always greater than 0,
+; because of the guard before it, so we can transform it to lshr.
+declare void @llvm.experimental.guard(i1,...)
+; CHECK-LABEL: @test4
+define void @test4(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+; CHECK: lshr i32 %a, 1
+  %a = phi i32 [ %n, %entry ], [ %shr, %loop ]
+  %cond = icmp sgt i32 %a, 2
+  call void(i1,...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
+  %shr = ashr i32 %a, 1
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; same test as above with assume instead of guard.
+declare void @llvm.assume(i1)
+; CHECK-LABEL: @test5
+define void @test5(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+; CHECK: lshr i32 %a, 1
+  %a = phi i32 [ %n, %entry ], [ %shr, %loop ]
+  %cond = icmp sgt i32 %a, 4
+  call void @llvm.assume(i1 %cond)
+  %shr = ashr i32 %a, 1
+  %loopcond = icmp sgt i32 %shr, 8
+  br i1 %loopcond, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Transforms/CorrelatedValuePropagation/sdiv.ll

 bb:
 ; CHECK: %div1 = udiv i32 %n, 2 
   %div = sdiv i32 %n, 2
   br label %exit
 
 exit:
   ret void
 }
+
+; looping case where loop has exactly one block
+; at the point of sdiv, we know that %a is always greater than 0,
+; because of the guard before it, so we can transform it to udiv.
+declare void @llvm.experimental.guard(i1,...)
+; CHECK-LABEL: @test4
+define void @test4(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+; CHECK: udiv i32 %a, 6
+  %a = phi i32 [ %n, %entry ], [ %div, %loop ]
+  %cond = icmp sgt i32 %a, 4
+  call void(i1,...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ]
+  %div = sdiv i32 %a, 6
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; same test as above with assume instead of guard.
+declare void @llvm.assume(i1)
+; CHECK-LABEL: @test5
+define void @test5(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+; CHECK: udiv i32 %a, 6
+  %a = phi i32 [ %n, %entry ], [ %div, %loop ]
+  %cond = icmp sgt i32 %a, 4
+  call void @llvm.assume(i1 %cond)
+  %div = sdiv i32 %a, 6
+  %loopcond = icmp sgt i32 %div, 8
+  br i1 %loopcond, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Transforms/CorrelatedValuePropagation/srem.ll

 if.then:
   %rem2 = srem i32 %x, 10
   store i32 %rem2, i32* %p, align 4
   br label %if.end
 
 if.end:
   ret void
 }
+
+; looping case where loop has exactly one block
+; at the point of srem, we know that %a is always greater than 0,
+; because of the assume before it, so we can transform it to urem.
+declare void @llvm.assume(i1)
+; CHECK-LABEL: @test4
+define void @test4(i32 %n) {
+entry:
+  %cmp = icmp sgt i32 %n, 0
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+; CHECK: urem i32 %a, 6
+  %a = phi i32 [ %n, %entry ], [ %rem, %loop ]
+  %cond = icmp sgt i32 %a, 4
+  call void @llvm.assume(i1 %cond)
+  %rem = srem i32 %a, 6
+  %loopcond = icmp sgt i32 %rem, 8
+  br i1 %loopcond, label %loop, label %exit
+
+exit:
+  ret void
+}