[ValueTracking] Fix a misuse of APInt in GetPointerBaseWithConstantOffset

[mppf]

Summary

GetPointerBaseWithConstantOffset include this code, where ByteOffset
and GEPOffset are both of type llvm::APInt :

ByteOffset += GEPOffset.getSExtValue();

The problem with this line is that getSExtValue() returns an int64_t, but
the += matches an overload for uint64_t. The problem is that the resulting
APInt is no longer considered to be signed. That in turn causes assertion
failures later on if the relevant pointer type is > 64 bits in width and
the GEPOffset was negative.

Changing it to

ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth());

resolves the issue and explicitly performs the sign-extending
or truncation. Additionally, instead of asserting later if the result
is > 64 bits, it breaks out of the loop in that case.

See also
https://reviews.llvm.org/D24729
https://reviews.llvm.org/D24772

This commit must be merged after D38662 in order for the test to pass.

[aprantl]

It would be better if the test would check for an actual different result rather than "it doesn't crash".

[hfinkel]

In D38501#887149, @aprantl wrote:

It would be better if the test would check for an actual different result rather than "it doesn't crash".

I agree.

lib/Analysis/ValueTracking.cpp

3081 ↗

(On Diff #117516)

Do we need to add a check here that the offset can actually be represented in 64 bits? I don't think that a truncated return value here actually makes sense.

[mppf]

lib/Analysis/ValueTracking.cpp

3081 ↗

(On Diff #117516)

getSExtValue does make sure it can be represented in an int64_t. If you were talking about using sextOrTrunc above, I think we need that truncation so that we can handle overflow in GEP operations so that we can handle negative GEP offsets correctly. (see my recent comment in D38499).

[mppf]

• [ValueTracking] Fix a misuse of APInt in GetPointerBaseWithConstantOffset
• Improve test

[mppf]

@aprantl / @hfinkel - I improved the test, does it look better? Oddly enough the code necessary to trigger the assert is in a section that isn't meaningfully changed by GVN. I just beefed up the test to also show a related case that GVN did usefully change. I'm having trouble doing any better than that with a reasonable amount of effort.

This one needs to merge after D38499, but other than that is it ready to go? Or does something else need to happen here?

Thanks!

[aprantl]

The testcase seems fine now. I'll defer to Hal for the semantics of the actual change.

[hfinkel]

lib/Analysis/ValueTracking.cpp

3068 ↗

(On Diff #117818)

We still need to make sure that the result doesn't overflow. I think something like this would work:

APInt OrigByteOffset(ByteOffset);

ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth());
if (ByteOffset.getActiveBits() >= 64) {
  ByteOffset = OrigByteOffset;
  break;
}

[efriedma]

lib/Analysis/ValueTracking.cpp

3068 ↗

(On Diff #117818)

Why does it matter if the result overflows? GEP arithmetic is wrapping.

3081 ↗

(On Diff #117818)

Yes, you need a check to make sure the value can be represented in 64 bits. getSExtValue() will cause an assertion failure if it doesn't.

Granted, that's only relevant if you have pointers wider than 64 bits.

[hfinkel]

lib/Analysis/ValueTracking.cpp

3068 ↗

(On Diff #117818)

Why does it matter if the result overflows? GEP arithmetic is wrapping.

For large pointers (as noted below). Since you mentioned the assertion, I'll note that its condition is a bit different, and we should match it here:

APInt OrigByteOffset(ByteOffset);

ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth());
if (ByteOffset.getMinSignedBits() > 64) {
  ByteOffset = OrigByteOffset;
  break;
}

3081 ↗

(On Diff #117818)

Yes, you need a check to make sure the value can be represented in 64 bits. getSExtValue() will cause an assertion failure if it doesn't.

You're right (I had thought it would silently saturate, so the situation is better than I thought).

Granted, that's only relevant if you have pointers wider than 64 bits.

Yes. Isn't that the point of this patch?

[efriedma]

Yes. Isn't that the point of this patch?

Well, in theory there's a crash on trunk that can happen without exotic pointers (something like "gep i64, i64* %x, i128 INT128_MIN" will cause an assertion failure in getSExtValue().)

[efriedma]

Well, in theory there's a crash on trunk that can happen without exotic pointers (something like "gep i64, i64* %x, i128 INT128_MIN" will cause an assertion failure in getSExtValue().)

Err, wait, nevermind, I misread the patch; that can't happen because it's calling accumulateConstantOffset, not visiting the offsets itself.

[mppf]

• Break from loop instead of asserting if size > 64 bits

[mppf]

@hfinkel - I've made the change you requested. I think this one is good to go, but as I mentioned we need to commit it after another fix to BasicAA (such as D38499), or else the new test will fail with BasicAA assertions.

[hfinkel]

In D38501#890491, @mppf wrote:

@hfinkel - I've made the change you requested. I think this one is good to go, but as I mentioned we need to commit it after another fix to BasicAA (such as D38499), or else the new test will fail with BasicAA assertions.

LGTM

[mppf]

Now that we have D38662, I'll look at getting this patch up to date and tested.

[mppf]

Rebasing on current LLVM master

[mppf]

@hfinkel - I think this change is ready to merge. I've rebased it on current LLVM trunk and run the tests. I've also verified that the new test fails (with an assertion failure) on LLVM trunk without this change. Thanks!

[fhahn]

Thanks! Do you need someone to commit the change on your behalf?

[hfinkel]

In D38501#1346193, @fhahn wrote:

Thanks! Do you need someone to commit the change on your behalf?

He does. I'm planning to do it this morning, but if you do it first, that's fine too :-)

[fhahn]

In D38501#1346325, @hfinkel wrote:

In D38501#1346193, @fhahn wrote:

Thanks! Do you need someone to commit the change on your behalf?

He does. I'm planning to do it this morning, but if you do it first, that's fine too :-)

Right, I can commit it in a bit.

[mppf]

Thanks!

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
       // of the Ptr parameter which was passed to this function.  This
       // means when we construct GEPOffset, we need to use the size
       // of GEP's pointer type rather than the size of the original
       // pointer type.
       APInt GEPOffset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
       if (!GEP->accumulateConstantOffset(DL, GEPOffset))
         break;
 
-      ByteOffset += GEPOffset.getSExtValue();
+      APInt OrigByteOffset(ByteOffset);
+      ByteOffset += GEPOffset.sextOrTrunc(ByteOffset.getBitWidth());
+      if (ByteOffset.getMinSignedBits() > 64) {
+        // Stop traversal if the pointer offset wouldn't fit into int64_t
+        // (this should be removed if Offset is updated to an APInt)
+        ByteOffset = OrigByteOffset;
+        break;
+      }
 
       Ptr = GEP->getPointerOperand();
     } else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
                Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
       Ptr = cast<Operator>(Ptr)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
       if (GA->isInterposable())
         break;

llvm/trunk/test/Analysis/ValueTracking/gep-negative-issue.ll

+; RUN: opt -gvn -S < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-p100:128:64:64-p101:128:64:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+%ArrayImpl = type { i64, i64 addrspace(100)*, [1 x i64], [1 x i64], [1 x i64], i64, i64, double addrspace(100)*, double addrspace(100)*, i8, i64 }
+%_array = type { i64, %ArrayImpl addrspace(100)*, i8 }
+
+define void @test(i64 %n_chpl) {
+entry:
+  ; First section is some code
+  %0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1
+  %1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %0
+  %2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %1, i32 0, i32 8
+  %3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %2
+  %4 = getelementptr inbounds double, double addrspace(100)* %3, i64 -1
+  ; Second section is that code repeated
+  %x0 = getelementptr inbounds %_array, %_array* null, i32 0, i32 1
+  %x1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %x0
+  %x2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %x1, i32 0, i32 8
+  %x3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %x2
+  %x4 = getelementptr inbounds double, double addrspace(100)* %x3, i64 -1
+  ; Stores that should be to the same location
+  store double 0.000000e+00, double addrspace(100)* %4
+  store double 0.000000e+00, double addrspace(100)* %x4
+  ; Third section is the repeated code again, with a later store
+  ; This third section is necessary to trigger the crash
+  %y1 = load %ArrayImpl addrspace(100)*, %ArrayImpl addrspace(100)** %0
+  %y2 = getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)* %y1, i32 0, i32 8
+  %y3 = load double addrspace(100)*, double addrspace(100)* addrspace(100)* %y2
+  %y4 = getelementptr inbounds double, double addrspace(100)* %y3, i64 -1
+  store double 0.000000e+00, double addrspace(100)* %y4
+  ret void
+; CHECK-LABEL: define void @test
+; CHECK: getelementptr inbounds double, double addrspace(100)* {{%.*}}, i64 -1
+; CHECK-NEXT: store double 0.000000e+00, double addrspace(100)* [[DST:%.*]]
+; CHECK-NEXT: store double 0.000000e+00, double addrspace(100)* [[DST]]
+; CHECK: load
+; CHECK: getelementptr inbounds %ArrayImpl, %ArrayImpl addrspace(100)*
+; CHECK: load
+; CHECK: getelementptr inbounds double, double addrspace(100)* {{%.*}}, i64 -1
+; CHECK: store double 0.000000e+00, double addrspace(100)*
+; CHECK: ret
+}