Page MenuHomePhabricator

[Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset (PR42699)
ClosedPublic

Authored by miyuki on Oct 2 2019, 9:54 AM.

Details

Summary

Currently when computing a GEP offset using the function EmitGEPOffset
for the following instruction

getelementptr inbounds i32, i32* %p, i64 %offs

we get

mul nuw i64 %offs, 4

Unfortunately we cannot assume that unsigned wrapping won't happen
here because %offs is allowed to be negative.

Making such assumptions can lead to miscompilations: see the new test
test24_neg_offs in InstCombine/icmp.ll. Without the patch InstCombine
would generate the following comparison:

icmp eq i64 %offs, 4611686018427387902; 0x3ffffffffffffffe

Whereas the correct value to compare with is -2.

This patch replaces the NUW flag with NSW in the multiplication
instructions generated by EmitGEPOffset and adjusts the test suite.

https://bugs.llvm.org/show_bug.cgi?id=42699

Diff Detail

Event Timeline

miyuki created this revision.Oct 2 2019, 9:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 2 2019, 9:54 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

If the inbounds keyword is not present, the offsets are added to the base address with
silently-wrapping two’s complement arithmetic.

At worst NUW should be relaxed to NSW.

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

At worst NUW should be relaxed to NSW.

What about the case I mentioned, i.e. an object which is larger than half of its address space?

I'm not fully convinced this is correct, as per
https://llvm.org/docs/LangRef.html#getelementptr-instruction

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

At worst NUW should be relaxed to NSW.

What about the case I mentioned, i.e. an object which is larger than half of its address space?

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

Nothing in the code implies that buf points to a single i32 value rather than to an element in an array of i32, but Clang nevertheless adds inbounds. If InstCombine tried to get an offset from the getelementptr inbounds i32, i32* %buf, i64 -2 instruction it would generate a mul nuw i64 4, -2 instruction, which wraps.

I also thought that "in bounds address of an allocated object" has something to do with the type used in the GEP instruction, but that's not how Clang interprets it.
E.g. for the following code

int read(int *buf) {
  buf -= 2;
  return *buf;
}

It generates the following:

define dso_local i32 @_Z4readPi(i32* nocapture readonly %buf) local_unnamed_addr #0 {
entry:
  %add.ptr = getelementptr inbounds i32, i32* %buf, i64 -2
  %0 = load i32, i32* %add.ptr, align 4, !tbaa !2
  ret i32 %0
}

I do not understand this point, could you elaborate please?

Nothing in the code implies that buf points to a single i32 value rather than to an element in an array of i32, but Clang nevertheless adds inbounds.

I don't see how that follows?
Quote from http://eel.is/c++draft/expr.add#4:

4     When an expression J that has integral type is added to or subtracted
      from an expression P of pointer type, the result has the type of P.
(4.1) If P evaluates to a null pointer value and J evaluates to 0,
      the result is a null pointer value.
(4.2) Otherwise, if P points to an array element i of an array object x with n
      elements ([dcl.array]), the expressions P + J and J + P
      (where J has the value j) point to the (possibly-hypothetical) array
      element i+j of x if 0≤i+j≤n and the expression P - J points to the 
      (possibly-hypothetical) array element i−j of x if 0≤i−j≤n.
(4.3) Otherwise, the behavior is undefined.

(see also C 6.5.6p8)

Which quite precisely maps to LangRef

"If the inbounds keyword is present, the result value of the getelementptr is a poison value if the base pointer is not an in bounds address of an allocated object <...>"

So clang is perfectly correct here.

If InstCombine tried to get an offset from the getelementptr inbounds i32, i32* %buf, i64 -2 instruction it would generate a mul nuw i64 4, -2 instruction, which wraps.

miyuki added a comment.Oct 3 2019, 2:34 AM

So clang is perfectly correct here.

Yes, Clang is correct. EmitGEPOffset is doing the wrong thing.
nuw is incorrect because negative offsets are allowed. nsw would also be incorrect because of the quote you mentioned before:

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

nsw would imply that signed overflow must not occur when computing the offset in the integer type of the same width as the pointer type. But LangRef is talking about infinitely precise arithmetic.

So clang is perfectly correct here.

Yes, Clang is correct. EmitGEPOffset is doing the wrong thing.
nuw is incorrect because negative offsets are allowed. nsw would also be incorrect because of the quote you mentioned before:

If the inbounds keyword is present, the result value of the getelementptr is a poison value
if the base pointer is not an in bounds address of an allocated object, or if any of the
addresses that would be formed by successive addition of the offsets implied by the indices
to the base address with infinitely precise signed arithmetic are not an in bounds address
of that allocated object. <...>

nsw would imply that signed overflow must not occur when computing the offset in the integer type of the same width as the pointer type. But LangRef is talking about infinitely precise arithmetic.

I'll rephrase.
I don't think this case is defined for address space 0 - i don't believe you can ever have an object e.g. occupying [i8 128, i8 8] (i.e. including null pointer).
It it likely not so for other address spaces. So the likely solution is to use NSW iff address space = 0.

miyuki updated this revision to Diff 224989.Oct 15 2019, 5:07 AM
miyuki retitled this revision from [Analysis] Don't assume that overflow can't happen in EmitGEPOffset to [Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset.
miyuki edited the summary of this revision. (Show Details)

Added the NSW flag. This discussion thread also suggests that signed overflows should not occur in the inbounds GEPs: https://lists.llvm.org/pipermail/llvm-dev/2017-November/118914.html

The patch looks good to me. Actually I had reported this bug a while back as well: https://bugs.llvm.org/show_bug.cgi?id=42699
I agree we can't have objects larger than half of the address space.

My only question is : why the restriction to address space 0? LangRef doesn't have any exception for other address spaces in these matters AFAICT.

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

I wouldn't be surprised if that isn't so, i don't think it's really documented what normal assumptions do and don't apply to non-0-address-spaces.

miyuki updated this revision to Diff 225203.Oct 16 2019, 5:47 AM
miyuki edited the summary of this revision. (Show Details)

Don't treat non-zero address space specially

@lebedev.ri, do you agree that all address spaces should be treated the same way as address space 0 (i.e. no signed overflow)?

I wouldn't be surprised if that isn't so, i don't think it's really documented what normal assumptions do and don't apply to non-0-address-spaces.

OK, let's stick to what is documented for GEP (and the status quo about objects larger than half of the address space).

lebedev.ri accepted this revision.Oct 16 2019, 11:23 AM
lebedev.ri retitled this revision from [Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset to [Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset (PR42699).
lebedev.ri edited the summary of this revision. (Show Details)
lebedev.ri added a subscriber: reames.

After re-reading everything posted/linked above, SGTM.
Please wait for @nlopes / @reames / @aqjune.

This revision is now accepted and ready to land.Oct 16 2019, 11:23 AM

LGTM
(there's only a typo in the comment "singned")

I agree that the size of a block should not be larger than the half of memory size.

https://lists.llvm.org/pipermail/llvm-dev/2017-November/118914.html

This is a pretty informative link. :) Thank you for sharing this.

This revision was automatically updated to reflect the committed changes.