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

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

385

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

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

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

LVI.h has forward declaration only

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 *AI, LazyValueInfo *LVI) {
+  typedef OverflowingBinaryOperator OBO;
+
+  if (AI->getType()->isVectorTy() || hasLocalDefs(AI))
+    return false;
+
+  bool NSW = AI->hasNoSignedWrap();
+  bool NUW = AI->hasNoUnsignedWrap();
+  if (NSW && NUW)
+    return false;
+
+  BasicBlock *BB = AI->getParent();
+
+  Value *LHS = AI->getOperand(0);
+  Value *RHS = AI->getOperand(1);
+
+  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AI);
+  ConstantRange RRange = LVI->getConstantRange(RHS, BB, AI);
+
+  bool Changed = false;
+  if (!NUW) {
+    ConstantRange NUWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoUnsignedWrap);
+    bool NewNUW = NUWRange.contains(RRange);
+    AI->setHasNoUnsignedWrap(NewNUW);
+    Changed |= NewNUW;
+  }
+  if (!NSW) {
+    ConstantRange NSWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoSignedWrap);
+    bool NewNSW = NSWRange.contains(RRange);
+    AI->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;

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: %div1 = add nsw i32 %a, 1
+  %div = 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: %div1 = add nsw nuw i32 %a, 1
+  %div = 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: %div1 = add nuw i32 %a, 1
+  %div = 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: %div1 = add i32 %a, 1
+  %div = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}