[ValueTracking] Use assumptions in computeConstantRange.

[fhahn]

Summary

This patch updates computeConstantRange to optionally take an assumption
cache as argument and use the available assumptions to limit the range
of the result.

Currently this is limited to assumptions that are comparisons.

[nikic]

Can you please provide some context on where this is going to be used? Generally LVI should be quite good at handling these kinds of assumes.

[fhahn]

In D76193#1923412, @nikic wrote:

Can you please provide some context on where this is going to be used? Generally LVI should be quite good at handling these kinds of assumes.

Sure, I've linked D76194, which uses it in BasicAA.

[nikic]

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time. Together with the linked change, this is a 0.5% regression.

llvm/lib/Analysis/ValueTracking.cpp

6411

Should we also be passing the DT through?

Side note: https://github.com/llvm/llvm-project/blob/56aed6144a16cdd71e03e5855b19dab1fe9331e6/llvm/lib/Analysis/ValueTracking.cpp#L604-L609 needs to be updated to use the new block local dominance checks, instead of doing an instruction scan.

6419

We may need to start passing a Depth parameter through, as this is now recursive. Though, as you don't pass through AC/CtxI here, recursion is implicitly limited to two levels.

llvm/unittests/Analysis/ValueTrackingTest.cpp

1355

Possibly worth checking a contradicting assumption? Which would result in an empty range.

[fhahn]

In D76193#1923931, @nikic wrote:

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time.

Together with the linked change, this is a 0.5% regression.

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

llvm/lib/Analysis/ValueTracking.cpp

6411

Should we also be passing the DT through?

We certainly can. Maybe best done as a follow-up?

Side note: https://github.com/llvm/llvm-project/blob/56aed6144a16cdd71e03e5855b19dab1fe9331e6/llvm/lib/Analysis/ValueTracking.cpp#L604-L609 needs to be updated to use the new block local dominance checks, instead of doing an instruction scan.

Agreed, I had the same though when looking at the code for isValudAssumeForContext. I've put it up at D76228.

[fhahn]

Add depth parameter & test case with contradictions.

[nikic]

In D76193#1924399, @fhahn wrote:

In D76193#1923931, @nikic wrote:

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time.

Together with the linked change, this is a 0.5% regression.

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

If you push a branch that starts with perf/ to your fork, it should get picked up. I've also done a run with the additional patch: Individual commits and all three combined.

Turns out the change to isValidAssumeForContext() in D76228 is neutral, I guess we don't exercise that code path much. This patch itself is a slight regression (the function is called often enough that the extra params and checks make a measurable difference). The BasicAA patch is a bit larger regression. I doubt this has anything to do with the assume handling, it's probably just the cost of the extra computeConstantRange() calls in a common analysis.

Anyway, this patch looks fine to me technically, so LGTM.

[fhahn]

In D76193#1927889, @nikic wrote:

In D76193#1924399, @fhahn wrote:

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

If you push a branch that starts with perf/ to your fork, it should get picked up. I've also done a run with the additional patch: Individual commits and all three combined.

Awesome I tried with a branch and it seems to get picked up.

Did you consider open-sourcing the scripts/tooling, e.g. as part of LNT/test-suite/llvm-zorg or as standalone project? It would be great if it would be possible to spin up separate instances, to not overload lvm-compile-time-tracker.com ;)

llvm/include/llvm/Analysis/ValueTracking.h

class Value;
   /// used only along the paths control dependent on the computation
   /// not overflowing, \p WO being an <op>.with.overflow intrinsic.
   bool isOverflowIntrinsicNoWrap(const WithOverflowInst *WO,
                                  const DominatorTree &DT);
 
 
   /// Determine the possible constant range of an integer or vector of integer
   /// value. This is intended as a cheap, non-recursive check.
-  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true);
+  ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true,
+                                     AssumptionCache *AC = nullptr,
+                                     const Instruction *CtxI = nullptr,
+                                     unsigned Depth = 0);
 
   /// Return true if this function can prove that the instruction I will
   /// always transfer execution to one of its successors (including the next
   /// instruction that follows within a basic block). E.g. this is not
   /// guaranteed for function calls that could loop infinitely.
   ///
   /// In other words, this function returns false for instructions that may
   /// transfer execution or fail to transfer execution in a way that is not

llvm/lib/Analysis/ValueTracking.cpp

case SPF_SMAX:
       Lower = *C;
       Upper = APInt::getSignedMaxValue(BitWidth) + 1;
       break;
     default:
       break;
   }
 }
 
-ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) {
+ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo,
+                                         AssumptionCache *AC,
+                                         const Instruction *CtxI,
+                                         unsigned Depth) {
   assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction");
 
+  if (Depth == MaxDepth)
+    return ConstantRange::getFull(V->getType()->getScalarSizeInBits());
+
   const APInt *C;
   if (match(V, m_APInt(C)))
     return ConstantRange(*C);
 
   InstrInfoQuery IIQ(UseInstrInfo);
   unsigned BitWidth = V->getType()->getScalarSizeInBits();
   APInt Lower = APInt(BitWidth, 0);
   APInt Upper = APInt(BitWidth, 0);
   if (auto *BO = dyn_cast<BinaryOperator>(V))
     setLimitsForBinOp(*BO, Lower, Upper, IIQ);
   else if (auto *II = dyn_cast<IntrinsicInst>(V))
     setLimitsForIntrinsic(*II, Lower, Upper);
   else if (auto *SI = dyn_cast<SelectInst>(V))
     setLimitsForSelectPattern(*SI, Lower, Upper, IIQ);
 
   ConstantRange CR = ConstantRange::getNonEmpty(Lower, Upper);
 
   if (auto *I = dyn_cast<Instruction>(V))
     if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range))
       CR = CR.intersectWith(getConstantRangeFromMetadata(*Range));
 
+  if (CtxI && AC) {
+    // Try to restrict the range based on information from assumptions.
+    for (auto &AssumeVH : AC->assumptionsFor(V)) {
+      if (!AssumeVH)
+        continue;
+      CallInst *I = cast<CallInst>(AssumeVH);
+      assert(I->getParent()->getParent() == CtxI->getParent()->getParent() &&
+             "Got assumption for the wrong function!");
+      assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
+             "must be an assume intrinsic");
+
+      if (!isValidAssumeForContext(I, CtxI, nullptr))
+        continue;
+      Value *Arg = I->getArgOperand(0);
+      ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
+      // Currently we just use information from comparisons.
+      if (!Cmp || Cmp->getOperand(0) != V)
+        continue;
+      ConstantRange RHS = computeConstantRange(Cmp->getOperand(1), UseInstrInfo,
+                                               AC, I, Depth + 1);
+      CR = CR.intersectWith(
+          ConstantRange::makeSatisfyingICmpRegion(Cmp->getPredicate(), RHS));
+    }
+  }
+
   return CR;
 }
 
 static Optional<int64_t>
 getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) {
   // Skip over the first indices.
   gep_type_iterator GTI = gep_type_begin(GEP);
   for (unsigned i = 1; i != Idx; ++i, ++GTI)

llvm/unittests/Analysis/ValueTrackingTest.cpp

 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
+static Instruction &findInstructionByName(Function *F, StringRef Name) {
+  for (Instruction &I : instructions(F))
+    if (I.getName() == Name)
+      return I;
+
+  llvm_unreachable("Expected value not found");
+}
+
 class ValueTrackingTest : public testing::Test {
 protected:
   std::unique_ptr<Module> parseModule(StringRef Assembly) {
     SMDiagnostic Error;
     std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
 
     std::string errMsg;
     raw_string_ostream os(errMsg);
     Error.print("", os);
     EXPECT_TRUE(M) << os.str();
 
     return M;
   }
 
   void parseAssembly(StringRef Assembly) {
     M = parseModule(Assembly);
     ASSERT_TRUE(M);
 
     F = M->getFunction("test");
     ASSERT_TRUE(F) << "Test must have a function @test";
     if (!F)
       return;
 
-    A = nullptr;
-    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
-      if (I->hasName()) {
-        if (I->getName() == "A")
-          A = &*I;
-      }
-    }
+    A = &findInstructionByName(F, "A");
     ASSERT_TRUE(A) << "@test must have an instruction %A";
   }
 
   LLVMContext Context;
   std::unique_ptr<Module> M;
   Function *F = nullptr;
   Instruction *A = nullptr;
 };
TEST_P(IsBytewiseValueTest, IsBytewiseValue) {
   GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getNamedValue("test"));
   Value *Actual = isBytewiseValue(GV->getInitializer(), M->getDataLayout());
   std::string Buff;
   raw_string_ostream S(Buff);
   if (Actual)
     S << *Actual;
   EXPECT_EQ(GetParam().first, S.str());
 }
+
+TEST_F(ValueTrackingTest, ComputeConstantRange) {
+  {
+    // Assumptions:
+    //  * stride >= 5
+    //  * stride < 10
+    //
+    // stride = [5, 10)
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %stride) {
+    %gt = icmp uge i32 %stride, 5
+    call void @llvm.assume(i1 %gt)
+    %lt = icmp ult i32 %stride, 10
+    call void @llvm.assume(i1 %lt)
+    %stride.plus.one = add nsw nuw i32 %stride, 1
+    ret i32 %stride.plus.one
+  })");
+    Function *F = M->getFunction("test");
+
+    AssumptionCache AC(*F);
+    Value *Stride = &*F->arg_begin();
+    ConstantRange CR1 = computeConstantRange(Stride, true, &AC, nullptr);
+    EXPECT_TRUE(CR1.isFullSet());
+
+    Instruction *I = &findInstructionByName(F, "stride.plus.one");
+    ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
+    EXPECT_EQ(5, CR2.getLower());
+    EXPECT_EQ(10, CR2.getUpper());
+  }
+
+  {
+    // Assumptions:
+    //  * stride >= 5
+    //  * stride < 200
+    //  * stride == 99
+    //
+    // stride = [99, 100)
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %stride) {
+    %gt = icmp uge i32 %stride, 5
+    call void @llvm.assume(i1 %gt)
+    %lt = icmp ult i32 %stride, 200
+    call void @llvm.assume(i1 %lt)
+    %eq = icmp eq i32 %stride, 99
+    call void @llvm.assume(i1 %eq)
+    %stride.plus.one = add nsw nuw i32 %stride, 1
+    ret i32 %stride.plus.one
+  })");
+    Function *F = M->getFunction("test");
+
+    AssumptionCache AC(*F);
+    Value *Stride = &*F->arg_begin();
+    Instruction *I = &findInstructionByName(F, "stride.plus.one");
+    ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
+    EXPECT_EQ(99, *CR.getSingleElement());
+  }
+
+  {
+    // Assumptions:
+    //  * stride >= 5
+    //  * stride >= 50
+    //  * stride < 100
+    //  * stride < 200
+    //
+    // stride = [50, 100)
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %stride, i1 %cond) {
+    %gt = icmp uge i32 %stride, 5
+    call void @llvm.assume(i1 %gt)
+    %gt.2 = icmp uge i32 %stride, 50
+    call void @llvm.assume(i1 %gt.2)
+    br i1 %cond, label %bb1, label %bb2
+
+  bb1:
+    %lt = icmp ult i32 %stride, 200
+    call void @llvm.assume(i1 %lt)
+    %lt.2 = icmp ult i32 %stride, 100
+    call void @llvm.assume(i1 %lt.2)
+    %stride.plus.one = add nsw nuw i32 %stride, 1
+    ret i32 %stride.plus.one
+
+  bb2:
+    ret i32 0
+  })");
+    Function *F = M->getFunction("test");
+
+    AssumptionCache AC(*F);
+    Value *Stride = &*F->arg_begin();
+    Instruction *GT2 = &findInstructionByName(F, "gt.2");
+    ConstantRange CR = computeConstantRange(Stride, true, &AC, GT2);
+    EXPECT_EQ(5, CR.getLower());
+    EXPECT_EQ(0, CR.getUpper());
+
+    Instruction *I = &findInstructionByName(F, "stride.plus.one");
+    ConstantRange CR2 = computeConstantRange(Stride, true, &AC, I);
+    EXPECT_EQ(50, CR2.getLower());
+    EXPECT_EQ(100, CR2.getUpper());
+  }
+
+  {
+    // Assumptions:
+    //  * stride > 5
+    //  * stride < 5
+    //
+    // stride = empty range, as the assumptions contradict each other.
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %stride, i1 %cond) {
+    %gt = icmp ugt i32 %stride, 5
+    call void @llvm.assume(i1 %gt)
+    %lt = icmp ult i32 %stride, 5
+    call void @llvm.assume(i1 %lt)
+    %stride.plus.one = add nsw nuw i32 %stride, 1
+    ret i32 %stride.plus.one
+  })");
+    Function *F = M->getFunction("test");
+
+    AssumptionCache AC(*F);
+    Value *Stride = &*F->arg_begin();
+
+    Instruction *I = &findInstructionByName(F, "stride.plus.one");
+    ConstantRange CR = computeConstantRange(Stride, true, &AC, I);
+    EXPECT_TRUE(CR.isEmptySet());
+  }
+
+  {
+    // Assumptions:
+    //  * x.1 >= 5
+    //  * x.2 < x.1
+    //
+    // stride = [0, 5)
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %x.1, i32 %x.2) {
+    %gt = icmp uge i32 %x.1, 5
+    call void @llvm.assume(i1 %gt)
+    %lt = icmp ult i32 %x.2, %x.1
+    call void @llvm.assume(i1 %lt)
+    %stride.plus.one = add nsw nuw i32 %x.1, 1
+    ret i32 %stride.plus.one
+  })");
+    Function *F = M->getFunction("test");
+
+    AssumptionCache AC(*F);
+    Value *X2 = &*std::next(F->arg_begin());
+
+    Instruction *I = &findInstructionByName(F, "stride.plus.one");
+    ConstantRange CR1 = computeConstantRange(X2, true, &AC, I);
+    EXPECT_EQ(0, CR1.getLower());
+    EXPECT_EQ(5, CR1.getUpper());
+
+    // Check the depth cutoff results in a conservative result (full set) by
+    // passing Depth == MaxDepth == 6.
+    ConstantRange CR2 = computeConstantRange(X2, true, &AC, I, 6);
+    EXPECT_TRUE(CR2.isFullSet());
+  }
+}