[ValueTracking] Fix computeKnownBits() with bitwidth-changing ptrtoint

[nikic]

Summary

computeKnownBitsFromAssume() currently asserts if m_V matches a ptrtoint that changes the bitwidth. Because InstCombine canonicalizes ptrtoint instructions to use explicit zext/trunc, we never ran into the issue in practice. I'm adding unit tests, as I don't know if this can be triggered via IR anywhere.

Fix this by calling anyextOrTrunc(BitWidth) on the computed KnownBits. Note that we are going from the KnownBits of the ptrtoint result to the KnownBits of the ptrtoint operand, so we need to truncate if the ptrtoint zexted and anyext if the ptrtoint truncated.

[lebedev.ri]

Is this fixing some bug? Is there an observable behavior change?
Can a (currently-crashing) test be added for some pass?
Or can this only be triggered via a specially-crafted unit test?

[nikic]

In D79234#2022052, @lebedev.ri wrote:

Is this fixing some bug? Is there an observable behavior change?
Can a (currently-crashing) test be added for some pass?
Or can this only be triggered via a specially-crafted unit test?

This fixes a bug. There is no behavior change. It can be observed in IR by moving known bits alignment calculation from InstCombine into AlignmentFromAssumptions. It cannot be observed in InstCombine because InstCombine canonicalizes ptrtoint casts to explicit zext/trunc. Maybe it can be observed in some other pass, but it's not easy (we need both non-trivial context instruction for assumes, and known bits query on a pointer value, which is unusual).

Maybe the better way of "fixing" this issue is to change IR definition of ptrtoint/inttoptr to forbid bitwidth change and always require zext/trunc? I have no idea why the current semantics exist. Maybe @efriedma knows?

[efriedma]

Historically, we allowed IR without a datalayout, so we didn't actually know what the pointer width would be when the IR was eventually compiled. Given that, allowing arbitrary casts was the least-bad alternative: otherwise, we wouldn't be able to verify a module.

Now that datalayout is required, we could maybe restrict the legal ptrtoint casts? Not sure what we would do about ptrtoint constant expressions; constant expressions that don't reference globals aren't associated with a particular module.

[nikic]

In D79234#2023197, @efriedma wrote:

Historically, we allowed IR without a datalayout, so we didn't actually know what the pointer width would be when the IR was eventually compiled. Given that, allowing arbitrary casts was the least-bad alternative: otherwise, we wouldn't be able to verify a module.

Now that datalayout is required, we could maybe restrict the legal ptrtoint casts? Not sure what we would do about ptrtoint constant expressions; constant expressions that don't reference globals aren't associated with a particular module.

Thanks for the context! Would anything speak against making the validity of constant expressions dependent on which module they are used in? That is, the same constant expression could be valid in one module and invalid in another, depending on data layout. As the validator works by recursively checking constants referenced in the module, I think that should work.

I may look into adding this requirement as a longer term change. I'd prefer to land this patch in the meantime though.

[efriedma]

Would anything speak against making the validity of constant expressions dependent on which module they are used in? That is, the same constant expression could be valid in one module and invalid in another, depending on data layout.

That's not something we've ever done, but I guess it's possible.

lib/Analysis/ValueTracking.cpp

794 ↗

(On Diff #261458)

LangRef says ptrtoint zero-extends.

[nikic]

In D79234#2039337, @nikic wrote:

In D79234#2023197, @efriedma wrote:

Historically, we allowed IR without a datalayout, so we didn't actually know what the pointer width would be when the IR was eventually compiled. Given that, allowing arbitrary casts was the least-bad alternative: otherwise, we wouldn't be able to verify a module.

Now that datalayout is required, we could maybe restrict the legal ptrtoint casts? Not sure what we would do about ptrtoint constant expressions; constant expressions that don't reference globals aren't associated with a particular module.

Thanks for the context! Would anything speak against making the validity of constant expressions dependent on which module they are used in? That is, the same constant expression could be valid in one module and invalid in another, depending on data layout. As the validator works by recursively checking constants referenced in the module, I think that should work.

I may look into adding this requirement as a longer term change. I'd prefer to land this patch in the meantime though.

I poked at this a bit, and ran into the first snag in https://github.com/llvm/llvm-project/blob/a63eedd049bfde97f1d73caa61d27df600501c54/llvm/lib/IR/BasicBlock.cpp#L79. This is creating an inttoptr cast in the BasicBlock destructor, so we have no data layout to ensure the correct integer size is used. That may make it infeasible to enforce this restriction...

lib/Analysis/ValueTracking.cpp

794 ↗

(On Diff #261458)

Here we have the knownbits of the ptrtoint result and want to reason backwards to the knownbits of the ptrtoint operand. If the ptrtoint zexted, that means we need to trunc. If the ptrtoint truncated, that means we need to anyext.

Here anyextOrTrunc is used as the inverse operation to zextOrTrunc.

[efriedma]

LGTM

lib/Analysis/ValueTracking.cpp

794 ↗

(On Diff #261458)

Oh, right.

llvm/lib/Analysis/ValueTracking.cpp

for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
     // The remaining tests are all recursive, so bail out if we hit the limit.
     if (Depth == MaxDepth)
       continue;
 
     ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
     if (!Cmp)
       continue;
 
+    // Note that ptrtoint may change the bitwidth.
     Value *A, *B;
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     CmpInst::Predicate Pred;
     uint64_t C;
     switch (Cmp->getPredicate()) {
     default:
       break;
     case ICmpInst::ICMP_EQ:
       // assume(v = a)
       if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
         Known.Zero |= RHSKnown.Zero;
         Known.One  |= RHSKnown.One;
       // assume(v & b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits MaskKnown(BitWidth);
-        computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits MaskKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // known bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & MaskKnown.One;
         Known.One  |= RHSKnown.One  & MaskKnown.One;
       // assume(~(v & b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_And(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits MaskKnown(BitWidth);
-        computeKnownBits(B, MaskKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits MaskKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in the mask that are known to be one, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & MaskKnown.One;
         Known.One  |= RHSKnown.Zero & MaskKnown.One;
       // assume(v | b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_Or(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits BKnown(BitWidth);
-        computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits BKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate known
         // bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         Known.One  |= RHSKnown.One  & BKnown.Zero;
       // assume(~(v | b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Or(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits BKnown(BitWidth);
-        computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits BKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate
         // inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
       // assume(v ^ b = a)
       } else if (match(Cmp,
                        m_c_ICmp(Pred, m_c_Xor(m_V, m_Value(B)), m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits BKnown(BitWidth);
-        computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits BKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate known
         // bits from the RHS to V. For those bits in B that are known to be one,
         // we can propagate inverted known bits from the RHS to V.
         Known.Zero |= RHSKnown.Zero & BKnown.Zero;
         Known.One  |= RHSKnown.One  & BKnown.Zero;
         Known.Zero |= RHSKnown.One  & BKnown.One;
         Known.One  |= RHSKnown.Zero & BKnown.One;
       // assume(~(v ^ b) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_c_Xor(m_V, m_Value(B))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
-        KnownBits BKnown(BitWidth);
-        computeKnownBits(B, BKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+        KnownBits BKnown =
+            computeKnownBits(B, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // For those bits in B that are known to be zero, we can propagate
         // inverted known bits from the RHS to V. For those bits in B that are
         // known to be one, we can propagate known bits from the RHS to V.
         Known.Zero |= RHSKnown.One  & BKnown.Zero;
         Known.One  |= RHSKnown.Zero & BKnown.Zero;
         Known.Zero |= RHSKnown.Zero & BKnown.One;
         Known.One  |= RHSKnown.One  & BKnown.One;
       // assume(v << c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shl(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
+
         // For those bits in RHS that are known, we can propagate them to known
         // bits in V shifted to the right by C.
         RHSKnown.Zero.lshrInPlace(C);
         Known.Zero |= RHSKnown.Zero;
         RHSKnown.One.lshrInPlace(C);
         Known.One  |= RHSKnown.One;
       // assume(~(v << c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
         // to known bits in V shifted to the right by C.
         RHSKnown.One.lshrInPlace(C);
         Known.Zero |= RHSKnown.One;
         RHSKnown.Zero.lshrInPlace(C);
         Known.One  |= RHSKnown.Zero;
       // assume(v >> c = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Shr(m_V, m_ConstantInt(C)),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them to known
         // bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.Zero << C;
         Known.One  |= RHSKnown.One  << C;
       // assume(~(v >> c) = a)
       } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shr(m_V, m_ConstantInt(C))),
                                      m_Value(A))) &&
                  isValidAssumeForContext(I, Q.CxtI, Q.DT) && C < BitWidth) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
         // For those bits in RHS that are known, we can propagate them inverted
         // to known bits in V shifted to the right by C.
         Known.Zero |= RHSKnown.One  << C;
         Known.One  |= RHSKnown.Zero << C;
       }
       break;
     case ICmpInst::ICMP_SGE:
       // assume(v >=_s c) where c is non-negative
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SGT:
       // assume(v >_s c) where c is at least -1.
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isAllOnes() || RHSKnown.isNonNegative()) {
           // We know that the sign bit is zero.
           Known.makeNonNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SLE:
       // assume(v <=_s c) where c is negative
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth + 1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth + 1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       break;
     case ICmpInst::ICMP_SLT:
       // assume(v <_s c) where c is non-positive
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         if (RHSKnown.isZero() || RHSKnown.isNegative()) {
           // We know that the sign bit is one.
           Known.makeNegative();
         }
       }
       break;
     case ICmpInst::ICMP_ULE:
       // assume(v <=_u c)
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // Whatever high bits in c are zero are known to be zero.
         Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros());
       }
       break;
     case ICmpInst::ICMP_ULT:
       // assume(v <_u c)
       if (match(Cmp, m_ICmp(Pred, m_V, m_Value(A))) &&
           isValidAssumeForContext(I, Q.CxtI, Q.DT)) {
-        KnownBits RHSKnown(BitWidth);
-        computeKnownBits(A, RHSKnown, Depth+1, Query(Q, I));
+        KnownBits RHSKnown =
+            computeKnownBits(A, Depth+1, Query(Q, I)).anyextOrTrunc(BitWidth);
 
         // If the RHS is known zero, then this assumption must be wrong (nothing
         // is unsigned less than zero). Signal a conflict and get out of here.
         if (RHSKnown.isZero()) {
           Known.Zero.setAllBits();
           Known.One.setAllBits();
           break;
         }

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/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"
std::unique_ptr<Module> parseModule(StringRef Assembly) {
 
     return M;
   }
 
   void parseAssembly(StringRef Assembly) {
     M = parseModule(Assembly);
     ASSERT_TRUE(M);
 
-    Function *F = M->getFunction("test");
+    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;
       }
     }
     ASSERT_TRUE(A) << "@test must have an instruction %A";
   }
 
   LLVMContext Context;
   std::unique_ptr<Module> M;
+  Function *F = nullptr;
   Instruction *A = nullptr;
 };
 
 class MatchSelectPatternTest : public ValueTrackingTest {
 protected:
   void expectPattern(const SelectPatternResult &P) {
     Value *LHS, *RHS;
     Instruction::CastOps CastOp;
parseAssembly(
       "  %bbb = and i8 %bb, 254\n"
       "  %A = call i8 @llvm.usub.sat.i8(i8 %aaa, i8 %bbb)\n"
       "  ret i8 %A\n"
       "}\n"
       "declare i8 @llvm.usub.sat.i8(i8, i8)\n");
   expectKnownBits(/*zero*/ 2u, /*one*/ 0u);
 }
 
+TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntTrunc) {
+  // ptrtoint truncates the pointer type.
+  parseAssembly(
+      "define void @test(i8** %p) {\n"
+      "  %A = load i8*, i8** %p\n"
+      "  %i = ptrtoint i8* %A to i32\n"
+      "  %m = and i32 %i, 31\n"
+      "  %c = icmp eq i32 %m, 0\n"
+      "  call void @llvm.assume(i1 %c)\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @llvm.assume(i1)\n");
+  AssumptionCache AC(*F);
+  KnownBits Known = computeKnownBits(
+      A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
+  EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
+  EXPECT_EQ(Known.One.getZExtValue(), 0u);
+}
+
+TEST_F(ComputeKnownBitsTest, ComputeKnownBitsPtrToIntZext) {
+  // ptrtoint zero extends the pointer type.
+  parseAssembly(
+      "define void @test(i8** %p) {\n"
+      "  %A = load i8*, i8** %p\n"
+      "  %i = ptrtoint i8* %A to i128\n"
+      "  %m = and i128 %i, 31\n"
+      "  %c = icmp eq i128 %m, 0\n"
+      "  call void @llvm.assume(i1 %c)\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @llvm.assume(i1)\n");
+  AssumptionCache AC(*F);
+  KnownBits Known = computeKnownBits(
+      A, M->getDataLayout(), /* Depth */ 0, &AC, F->front().getTerminator());
+  EXPECT_EQ(Known.Zero.getZExtValue(), 31u);
+  EXPECT_EQ(Known.One.getZExtValue(), 0u);
+}
+
 class IsBytewiseValueTest : public ValueTrackingTest,
                             public ::testing::WithParamInterface<
                                 std::pair<const char *, const char *>> {
 protected:
 };
 
 const std::pair<const char *, const char *> IsBytewiseValueTests[] = {
     {