Fix ValueTracking computeConstantRange to use "may" instead of "always" semantics for llvm.assume

[clin1]

Summary

ValueTracking should allow for value ranges that may satisfy llvm.assume, instead of restricting the ranges only to values that will always satisfy the condition.

[nikic]

LGTM

[clin1]

Thank you for the quick review! Could I request you to "press the commit button", please? I apologize, I don't have write access to the repo.

[nikic]

Sure, can you please share Your Name <your@email> to use for the commit?

[clin1]

Chang-Sun Lin, Jr <[e-mail]>

Thanks.

llvm/lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : AC->assumptionsFor(V)) {
       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));
+          ConstantRange::makeAllowedICmpRegion(Cmp->getPredicate(), RHS));
     }
   }
 
   return CR;
 }
 
 static Optional<int64_t>
 getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) {

llvm/unittests/Analysis/ValueTrackingTest.cpp

define i32 @test(i32 %stride, i1 %cond) {
     EXPECT_TRUE(CR.isEmptySet());
   }
 
   {
     // Assumptions:
     //  * x.1 >= 5
     //  * x.2 < x.1
     //
-    // stride = [0, 5)
+    // stride = [0, -1)
     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 *X1 = &*(F->arg_begin());
     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());
+    ConstantRange CR1 = computeConstantRange(X1, true, &AC, I);
+    ConstantRange CR2 = computeConstantRange(X2, true, &AC, I);
+
+    EXPECT_EQ(5, CR1.getLower());
+    EXPECT_EQ(0, CR1.getUpper());
+
+    EXPECT_EQ(0, CR2.getLower());
+    EXPECT_EQ(0xffffffff, CR2.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());
+    ConstantRange CR3 = computeConstantRange(X2, true, &AC, I, 6);
+    EXPECT_TRUE(CR3.isFullSet());
+  }
+  {
+    // Assumptions:
+    //  * x.2 <= x.1
+    auto M = parseModule(R"(
+  declare void @llvm.assume(i1)
+
+  define i32 @test(i32 %x.1, i32 %x.2) {
+    %lt = icmp ule 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);
+    // If we don't know the value of x.2, we don't know the value of x.1.
+    EXPECT_TRUE(CR1.isFullSet());
   }
 }
 
 struct FindAllocaForValueTestParams {
   const char *IR;
   bool AnyOffsetResult;
   bool ZeroOffsetResult;
 };