Teach CorrelatedValuePropagation to mark adds as no wrap

[apilipenko]

Summary

Use LVI to prove that adds do not wrap. The change is motivated by https://llvm.org/bugs/show_bug.cgi?id=28620 bug and it's the first step to fix that problem.

[sanjoy]

lgtm modulo comments inline

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

21 ↗

(On Diff #66465)

Interesting that you had to add this. Doesn't LVI include this?

385 ↗

(On Diff #66465)

Why AI as the variable name? I'd have gone with BO or something like that.

edit: I suppose you mean AddInst? In that case, I'd suggest calling it AddInst or AddOp. I've seen AI be normally used for alloca instructions.

409 ↗

(On Diff #66465)

There is an optimization we can do here: we only need RRange if NUWRange (resp. NSWRange) is not empty. What do you think about changing RRange to an Optional<ConstantRange> and lazily initializing it? My intuition is that calling getConstantRange on a value that LVI hasn't seen before can be expensive (since it will have to do a CFG-walk).

test/Transforms/CorrelatedValuePropagation/add.ll

51 ↗

(On Diff #66465)

For completeness, can you please add a few tests like @test3 and @test4 with signed integer min and signed integer max?

[apilipenko]

lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

21 ↗

(On Diff #66465)

LVI.h has forward declaration only

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

 
 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Local.h"
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 processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
+  typedef OverflowingBinaryOperator OBO;
+
+  if (AddOp->getType()->isVectorTy() || hasLocalDefs(AddOp))
+    return false;
+
+  bool NSW = AddOp->hasNoSignedWrap();
+  bool NUW = AddOp->hasNoUnsignedWrap();
+  if (NSW && NUW)
+    return false;
+
+  BasicBlock *BB = AddOp->getParent();
+
+  Value *LHS = AddOp->getOperand(0);
+  Value *RHS = AddOp->getOperand(1);
+
+  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AddOp);
+
+  // Initialize RRange only if we need it. If we know that guaranteed no wrap
+  // range for the given LHS range is empty don't spend time calculating the
+  // range for the RHS.
+  Optional<ConstantRange> RRange;
+  auto LazyRRange = [&] () {
+      if (!RRange)
+        RRange = LVI->getConstantRange(RHS, BB, AddOp);
+      return RRange.getValue();
+  };
+
+  bool Changed = false;
+  if (!NUW) {
+    ConstantRange NUWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoUnsignedWrap);
+    if (!NUWRange.isEmptySet()) {
+      bool NewNUW = NUWRange.contains(LazyRRange());
+      AddOp->setHasNoUnsignedWrap(NewNUW);
+      Changed |= NewNUW;
+    }
+  }
+  if (!NSW) {
+    ConstantRange NSWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoSignedWrap);
+    if (!NSWRange.isEmptySet()) {
+      bool NewNSW = NSWRange.contains(LazyRRange());
+      AddOp->setHasNoSignedWrap(NewNSW);
+      Changed |= NewNSW;
+    }
+  }
+
+  return Changed;
+}
+
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
 
   // TODO: The following really should be sunk inside LVI's core algorithm, or
   // at least the outer shims around such.
   auto *C = dyn_cast<CmpInst>(V);
   if (!C) return nullptr;
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::Add:
+        BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
+        break;
       }
     }
 
     Instruction *Term = BB.getTerminator();
     switch (Term->getOpcode()) {
     case Instruction::Switch:
       BBChanged |= processSwitch(cast<SwitchInst>(Term), LVI);
       break;

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

+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test0(
+define void @test0(i32 %a) {
+entry:
+  %cmp = icmp slt i32 %a, 100
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test1(
+define void @test1(i32 %a) {
+entry:
+  %cmp = icmp ult i32 %a, 100
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nuw nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i32 %a) {
+entry:
+  %cmp = icmp ult i32 %a, -1
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nuw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test3(
+define void @test3(i32 %a) {
+entry:
+  %cmp = icmp ule i32 %a, -1
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test4(
+define void @test4(i32 %a) {
+entry:
+  %cmp = icmp slt i32 %a, 2147483647
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test5(
+define void @test5(i32 %a) {
+entry:
+  %cmp = icmp sle i32 %a, 2147483647
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}