GVN incorrectly handling readnone parameter attribute?

Hi,

I'm investigating a bug which I have so far been able to narrow down
to the following small testcase:

======== test.c ===========

int *get_pntr(int *p) {
    return p;
}

__attribute__((noinline))
void store(int *p) {
    int *p2 = get_pntr(p);
    *p2 = 10;
}

int test() {
    int i;
    store(&i);
    return i;
}

Further to my first post, based on the definition of readnone on an
argument, this is also incorrect. After get_pntr() has been inlined
into store(), we are dereferencing %p, but it is still marked
readnone.

So we seem to have a couple of issues. First GVN seems to be making
incorrect assumptions based on argument attributes, and secondly
inlining can invalidate existing attributes?

Thanks,
Rob.

I'm not clear on the GVN issue, but looking at your example IR, the readnone attribute is definitely incorrect after inlining.

A question worth asking here: does this definition of readnone make sense? I can see where it came from, but it seems to give very unintuitive reasoning here.

p.s. Is this with TOT or an earlier version?

Philip

Hi Philip,

Thanks for the reply.

define i32* @get_pntr(i32* readnone %p) {
entry:
   ret i32* %p
}

define void @store(i32* nocapture readnone %p) {
entry:
   store i32 10, i32* %p, align 4, !tbaa !1
   ret void
}

Further to my first post, based on the definition of readnone on an
argument, this is also incorrect. After get_pntr() has been inlined
into store(), we are dereferencing %p, but it is still marked
readnone.

So we seem to have a couple of issues. First GVN seems to be making
incorrect assumptions based on argument attributes, and secondly
inlining can invalidate existing attributes?

I'm not clear on the GVN issue, but looking at your example IR, the readnone
attribute is definitely incorrect after inlining.

Yes. I haven't investigated it any further, but the parameter was
already readnone before inlining, so it looks like the attributes
aren't revisited afterwards. But that is just a guess.

A question worth asking here: does this definition of readnone make sense?
I can see where it came from, but it seems to give very unintuitive
reasoning here.

Exactly. That was my point in asking here before I went any further.
The definition in the LangRef seems odd. If it could still be
accessed by another pointer, I can't see where the information is
useful.

p.s. Is this with TOT or an earlier version?

Yes, this was with TOT as of yesterday (r209294).

Thanks,
Rob.

Confirmed, this is a bug. This

define i32* @get_pntr(i32* %p) nounwind uwtable {
entry:
ret i32* %p
}
define void @store(i32* %p) noinline nounwind uwtable {

entry:
%call = call i32* @get_pntr(i32* %p)
store i32 10, i32* %call, align 4
ret void
}

run through opt -functionattrs gets a ‘readnone’ on @store’s %p. That’s wrong, it clearly stores to it. The bug is due to incorrectly handling the copy of the pointer made by @get_pntr, because @get_pntr itself is marked ‘readnone’.

Please file a bug.

Nick

Hi Nick,

Thanks for replying. Bug filed: http://llvm.org/bugs/show_bug.cgi?id=19842

Strangely enough, my first conclusion was that %p was being marked
readnone incorrectly as it wasn't handling the copy via @get_addr.
Somebody (not here) then pointed out the readnone definition in the
LangRef (specifically the "even though it may read or write
the memory that the pointer points to if accessed through other
pointers"). I decided the copy fell within this definition and
changed my mind and decided GVN was at fault. How should the
definition be interpreted?

Thanks,
Rob.

Hi Nick,

Thanks for replying. Bug filed:
http://llvm.org/bugs/show_bug.cgi?id=19842

Thank you!

Strangely enough, my first conclusion was that %p was being marked

readnone incorrectly as it wasn't handling the copy via @get_addr.

Sorry -- saying %p alone is ambiguous because there's the %p parameter
of @get_pntr
and the %p parameter of @store. It is correct to mark %p readnone in
@get_pntr. From function entrance to exit, it does not write to the pointer
passed in. It is incorrect to mark %p readnone in @store, as it receives a
pointer then writes to it. Supposing the @get_pntr loaded a pointer from
some global variable then wrote through it, then @get_pntr could still mark
its %p as being readnone, since the write was not through %p particularly,
it just happens to be through a pointer that aliased it.

Somebody (not here) then pointed out the readnone definition in the

LangRef (specifically the "even though it may read or write
the memory that the pointer points to if accessed through other
pointers"). I decided the copy fell within this definition and
changed my mind and decided GVN was at fault. How should the
definition be interpreted?

Consider:

define void @example(i32* %p, i32* %q) {
  store i32 10, i32* %q
  %A = icmp ult i32* %p, %q
  call void @use(i1 %A) readnone
  ret void
}

@example does not modify the memory pointed to by %p, unless it does it
through a different pointer, hence it may mark that parameter readnone. A
caller may choose to pass in %p == %q in which case the memory pointed-to
may change, but @example still lives up to its contract.

The real-world implications of this are that callers may use this
information to optimize themselves, combined with other information such as
knowing that %p != %q, or better, that %p is a local alloca or freshly
malloc'd memory and the pointer %p has not yet escaped (aka. been captured).

If we read the language as permitting the function to make copies of the
pointers the this code would be valid:

define void @writes_over_everything(i32* readnone %p, i32* readnone %q) {
  %P = bitcast i32* %p to i32*
  %Q = bitcast i32* %p to i32*
  store i32 10, i32* %P
  store i32 10, i32* %Q
  ret void
}

and that's not useful for optimization.

Nick

Would it make sense to count the return value as an escape point? ie it seems (and hopefully is programmed to be) incorrect to infer a readnone attribute for a pointer that gets passed to a non-readnone function, or stored to a global variable, etc. In that sense the pointer seems to also escape if returned from the function, because the function can’t guarantee any longer that no reads or writes happen to that value. So my take would have been that get_pntr() shouldn’t get annotated with readnone…

Kevin Modzelewski wrote:

Would it make sense to count the return value as an escape point?

It is.

   ie it

seems (and hopefully is programmed to be) incorrect to infer a readnone
attribute for a pointer that gets passed to a non-readnone function, or
stored to a global variable, etc.

That's the bug. The escape analysis gets this right and doesn't mark the pointer nocapture, but the readnone sees that the callee is readnone and decides it can't be capturing, before checking anything else. Unfortunately that isn't sufficient, it's still possible for a function with no memory loads or store to capture a pointer: it may do so by returning, and it may do so by choosing whether to unwind or not.

   In that sense the pointer seems to

also escape if returned from the function, because the function can't
guarantee any longer that no reads or writes happen to that value. So
my take would have been that get_pntr() shouldn't get annotated with
readnone...

get_pntr is safe to annotate with readnone, it's up to the caller to notice the capture coming out the function return or by unwinding. This leads to correct optimization behaviour; you can hoist a load or store above or below this particular function call, but you still have to pay attention to the value it returns, which you did anyways.

Nick

Hi,

I'm investigating a bug which I have so far been able to narrow down
to the following small testcase:

======== test.c ===========

int *get_pntr(int *p) {
    return p;
}

__attribute__((noinline))
void store(int *p) {
    int *p2 = get_pntr(p);
    *p2 = 10;
}

int test() {
    int i;
    store(&i);
    return i;
}
-----------------------------

If this is compiled in two steps as follows:

clang -O1 -emit-llvm test.c -c -o test.bc
opt -basicaa -inline -functionattrs -gvn -S test.bc

We get the following IR:

--------------------------------------------------
define i32* @get_pntr(i32* readnone %p) {
entry:
  ret i32* %p
}

define void @store(i32* nocapture readnone %p) {
entry:
  store i32 10, i32* %p, align 4, !tbaa !1
  ret void
}

define i32 @test() {
entry:
  %i = alloca i32, align 4
  call void @store(i32* %i)
  ret i32 undef
}
--------------------------------------------------

As can be seen, the load of %i in test() has been eliminated, and we
have an undefined return value.

As of revision 209870 we now get:

; Function Attrs: nounwind readnone uwtable
define i32* @get_pntr(i32* readnone %p) #0 {
entry:
  ret i32* %p
}

; Function Attrs: noinline nounwind uwtable
define void @store(i32* nocapture %p) #1 {
entry:
  store i32 10, i32* %p, align 4, !tbaa !1
  ret void
}

; Function Attrs: nounwind uwtable
define i32 @test() #2 {
entry:
  %i = alloca i32, align 4
  call void @store(i32* %i)
  %0 = load i32* %i, align 4, !tbaa !1
  ret i32 %0
}

I think that's correct, let me know if there's another bug hiding in here.

Nick

Investigating this I can see that the load is removed by the GVN pass.

Hi Nick,

Thanks for fixing this. I can confirm it fixes both the reduced test
case and our original issue. I will close the bug I raised.

Rob.