[ValueTracking] Inbounds does not imply nsw

[nikic]

Summary

The more precise known bits analysis for GEPs introduced in D86364 assumes that inbounds implies nsw for the additions. This is not the case, as the base pointer is an unsigned value.

I was not able to come up with a test case where this actually makes a difference, because KnownBits::computeMul() is too imprecise (doing something like adding a non-negative base and a non-negative offset fails because multiplication by 1 loses the non-negativity information.)

[aqjune]

The change makes sense to me; inbounds doesn't guarantee that the base address + offset is less than the maximum of a signed integer value.

[lebedev.ri]

Please can you explain what problem is this solving?
Either this is missing words "however if we'd add all offsets together, and then add the final offset to the base pointer, that addition is NSW",
or this is inconsistent with langref/D68342.

[nikic]

In D90637#2369434, @lebedev.ri wrote:

Please can you explain what problem is this solving?
Either this is missing words "however if we'd add all offsets together, and then add the final offset to the base pointer, that addition is NSW",
or this is inconsistent with langref/D68342.

Other way around. The offset multiplications/additions are all nsw, but the final addition to the base is not. If %base = 0x7fffffff and %offset = 1, then gep inbounds %base, %offset is perfectly legal (assuming an allocated object at that location), despite wrapping the signed space. In terms of wrapping behavior of the base addition, "inbounds" implies "nusw" which (in the general case) implies neither nsw nor nuw.

[lebedev.ri]

After actually re-reading D68342, i agree.
Does accumulating the offset and then applying the total offset lead to precision loss?

llvm/lib/Analysis/ValueTracking.cpp

1349

Presumably NSW should be here?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1349

It would be legal to use here, yes, but this API does not accept nowrap flags.

[nlopes]

FWIW, here's a related bug (fixed already): https://bugs.llvm.org/show_bug.cgi?id=42699

[nikic]

Hm, I think we need to clarify this in LangRef. We definitely assume this interpretation (unsigned base and signed offset) in some places (e.g. https://github.com/llvm/llvm-project/blob/c938b4a1ed43f3075155e16a7c2792ca8c122258/llvm/lib/Analysis/ScalarEvolution.cpp#L5061-L5072 and I'm pretty sure I've seen it elsewhere as well), but LangRef is really not clear on this point. It's also not completely obvious where the assumption that the pointer address space is unsigned comes from. E.g. on x86-64 the canonical address space is signed (but I don't know about other architectures). We need to clarify whether having an allocated object at [0xffffffff, 0x00000001] is legal (signed address space), [0x7fffffff, 0x80000001] is legal (unsigned address space) or both.

[nlopes]

In D90637#2369842, @nikic wrote:

Hm, I think we need to clarify this in LangRef. We definitely assume this interpretation (unsigned base and signed offset) in some places (e.g. https://github.com/llvm/llvm-project/blob/c938b4a1ed43f3075155e16a7c2792ca8c122258/llvm/lib/Analysis/ScalarEvolution.cpp#L5061-L5072 and I'm pretty sure I've seen it elsewhere as well), but LangRef is really not clear on this point. It's also not completely obvious where the assumption that the pointer address space is unsigned comes from. E.g. on x86-64 the canonical address space is signed (but I don't know about other architectures). We need to clarify whether having an allocated object at [0xffffffff, 0x00000001] is legal (signed address space), [0x7fffffff, 0x80000001] is legal (unsigned address space) or both.

Agreed. One thing that seems certain (though not mentioned in LangRef) is that a single allocation can only use up to half of the address space. Otherwise can't have positive and negative offsets; we need 1 bit for the sign.
For the issue you mention, we need a little survey of the hardware out there to understand if there's commonality or not (I've no clue).

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::GetElementPtr: {
     // Analyze all of the subscripts of this getelementptr instruction
     // to determine if we can prove known low zero bits.
     computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
     // Accumulate the constant indices in a separate variable
     // to minimize the number of calls to computeForAddSub.
     APInt AccConstIndices(BitWidth, 0, /*IsSigned*/ true);
 
     gep_type_iterator GTI = gep_type_begin(I);
-    // If the inbounds keyword is not present, the offsets are added to the
-    // base address with silently-wrapping two’s complement arithmetic.
-    bool IsInBounds = cast<GEPOperator>(I)->isInBounds();
     for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
       // TrailZ can only become smaller, short-circuit if we hit zero.
       if (Known.isUnknown())
         break;
 
       Value *Index = I->getOperand(i);
 
       // Handle case when index is zero.
for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
         APInt ScalingFactor(IndexBitWidth, TypeSizeInBytes);
         IndexConst *= ScalingFactor;
         AccConstIndices += IndexConst.sextOrTrunc(BitWidth);
         continue;
       } else {
         ScalingFactor.Zero = ~TypeSizeInBytes;
         ScalingFactor.One = TypeSizeInBytes;
       }
       IndexBits = KnownBits::computeForMul(IndexBits, ScalingFactor);
 
       // If the offsets have a different width from the pointer, according
       // to the language reference we need to sign-extend or truncate them
       // to the width of the pointer.
       IndexBits = IndexBits.sextOrTrunc(BitWidth);
 
+      // Note that inbounds does *not* guarantee nsw for the addition, as only
+      // the offset is signed, while the base address is unsigned.
       Known = KnownBits::computeForAddSub(
-          /*Add=*/true,
-          /*NSW=*/IsInBounds, Known, IndexBits);
+          /*Add=*/true, /*NSW=*/false, Known, IndexBits);
     }
     if (!Known.isUnknown() && !AccConstIndices.isNullValue()) {
       KnownBits Index(BitWidth);
       Index.Zero = ~AccConstIndices;
       Index.One = AccConstIndices;
       Known = KnownBits::computeForAddSub(
-          /*Add=*/true,
-          /*NSW=*/IsInBounds, Known, Index);
+          /*Add=*/true, /*NSW=*/false, Known, Index);
     }
     break;
   }
   case Instruction::PHI: {
     const PHINode *P = cast<PHINode>(I);
     // Handle the case of a simple two-predecessor recurrence PHI.
     // There's a lot more that could theoretically be done here, but
     // this is sufficient to catch some interesting cases.