llvm dev - May 2014 - [LLVMdev] 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;
}
-----------------------------

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.

Investigating this I can see that the load is removed by the GVN pass.
 It does this because it believes that the call to store() has no
affect on %i, and as %i has just been allocated, the loaded value is
undefined.

The reason it believes that store() has no affect is because of
store()'s parameter attributes.  Argument %p doesn't escape
(nocapture), and it doesn't access memory (readnone).  So even though
the call aliases the load, it believes it doesn't touch it (even
though it clearly does).

The nocapture attribute is added by the functionattrs pass (and is
correct).  The readnone attribute, however, is present from the first
compilation step (clang -O1):

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

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

define i32 @test() {
entry:
  %i = alloca i32, align 4
  call void @store(i32* %i)
  %0 = load i32* %i, align 4, !tbaa !1
  ret i32 %0
}
--------------------------------------------------

Looking at the definition of readnone in the LangRef we see:

"On an argument, this attribute indicates that the function does not
dereference that pointer argument, even though it may read or write
the memory that the pointer points to if accessed through other
pointers."

So this appears to be correct.  Argument %p is marked as readnone in
both get_pntr() and store() as it is not read or written to.  Store()
does write to it via a copy of %p, but this is also OK according to
the definition.

So the problem appears to be within GVN.  The assumption based on
store()'s parameter attributes is incorrect, as the load can be
affected through a different pointer.

So before I try to fix GVN, my question is, am I on the right track?
Specifically, is the definition in the LangRef correct?

Thanks,
Rob.

P.S. GVN's checking of the attributes is done in
AliasAnalysis::callCapturesBefore in lib/Analysis/AliasAnalysis.cpp

--
Robert Lougher
SN Systems - Sony Computer Entertainment Group

On 21 May 2014 21:40, Robert Lougher <rob.lougher at gmail.com>
wrote:
>
> 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?

Thanks,
Rob.

--

Robert Lougher
SN Systems - Sony Computer Entertainment Group

On 05/21/2014 02:52 PM, Robert Lougher wrote:
> On 21 May 2014 21:40, Robert Lougher <rob.lougher at gmail.com>
wrote:
>> 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.

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

On 21 May 2014 13:40, Robert Lougher <rob.lougher at gmail.com> wrote:
> 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.
>  It does this because it believes that the call to store() has no
> affect on %i, and as %i has just been allocated, the loaded value is
> undefined.
>
> The reason it believes that store() has no affect is because of
> store()'s parameter attributes.  Argument %p doesn't escape
> (nocapture), and it doesn't access memory (readnone).  So even though
> the call aliases the load, it believes it doesn't touch it (even
> though it clearly does).
>
> The nocapture attribute is added by the functionattrs pass (and is
> correct).  The readnone attribute, however, is present from the first
> compilation step (clang -O1):
>
> --------------------------------------------------
> define i32* @get_pntr(i32* readnone %p) {
> entry:
>   ret i32* %p
> }
>
> define void @store(i32* readnone %p) {
> entry:
>   %call = tail call i32* @get_pntr(i32* %p)
>   store i32 10, i32* %call, align 4, !tbaa !1
>   ret void
> }
>
> define i32 @test() {
> entry:
>   %i = alloca i32, align 4
>   call void @store(i32* %i)
>   %0 = load i32* %i, align 4, !tbaa !1
>   ret i32 %0
> }
> --------------------------------------------------
>
> Looking at the definition of readnone in the LangRef we see:
>
> "On an argument, this attribute indicates that the function does not
> dereference that pointer argument, even though it may read or write
> the memory that the pointer points to if accessed through other
> pointers."
>
> So this appears to be correct.  Argument %p is marked as readnone in
> both get_pntr() and store() as it is not read or written to.  Store()
> does write to it via a copy of %p, but this is also OK according to
> the definition.
>
> So the problem appears to be within GVN.  The assumption based on
> store()'s parameter attributes is incorrect, as the load can be
> affected through a different pointer.
>
> So before I try to fix GVN, my question is, am I on the right track?
> Specifically, is the definition in the LangRef correct?
>
> Thanks,
> Rob.
>
> P.S. GVN's checking of the attributes is done in
> AliasAnalysis::callCapturesBefore in lib/Analysis/AliasAnalysis.cpp
>
> --
> Robert Lougher
> SN Systems - Sony Computer Entertainment Group
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140529/a1e22269/attachment.html>

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.

On 30 May 2014 03:45, Nick Lewycky <nlewycky at google.com>
wrote:
> On 21 May 2014 13:40, Robert Lougher <rob.lougher at gmail.com>
wrote:
>>
>> 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.
>>  It does this because it believes that the call to store() has no
>> affect on %i, and as %i has just been allocated, the loaded value is
>> undefined.
>>
>> The reason it believes that store() has no affect is because of
>> store()'s parameter attributes.  Argument %p doesn't escape
>> (nocapture), and it doesn't access memory (readnone).  So even
though
>> the call aliases the load, it believes it doesn't touch it (even
>> though it clearly does).
>>
>> The nocapture attribute is added by the functionattrs pass (and is
>> correct).  The readnone attribute, however, is present from the first
>> compilation step (clang -O1):
>>
>> --------------------------------------------------
>> define i32* @get_pntr(i32* readnone %p) {
>> entry:
>>   ret i32* %p
>> }
>>
>> define void @store(i32* readnone %p) {
>> entry:
>>   %call = tail call i32* @get_pntr(i32* %p)
>>   store i32 10, i32* %call, align 4, !tbaa !1
>>   ret void
>> }
>>
>> define i32 @test() {
>> entry:
>>   %i = alloca i32, align 4
>>   call void @store(i32* %i)
>>   %0 = load i32* %i, align 4, !tbaa !1
>>   ret i32 %0
>> }
>> --------------------------------------------------
>>
>> Looking at the definition of readnone in the LangRef we see:
>>
>> "On an argument, this attribute indicates that the function does
not
>> dereference that pointer argument, even though it may read or write
>> the memory that the pointer points to if accessed through other
>> pointers."
>>
>> So this appears to be correct.  Argument %p is marked as readnone in
>> both get_pntr() and store() as it is not read or written to.  Store()
>> does write to it via a copy of %p, but this is also OK according to
>> the definition.
>>
>> So the problem appears to be within GVN.  The assumption based on
>> store()'s parameter attributes is incorrect, as the load can be
>> affected through a different pointer.
>>
>> So before I try to fix GVN, my question is, am I on the right track?
>> Specifically, is the definition in the LangRef correct?
>>
>> Thanks,
>> Rob.
>>
>> P.S. GVN's checking of the attributes is done in
>> AliasAnalysis::callCapturesBefore in lib/Analysis/AliasAnalysis.cpp
>>
>> --
>> Robert Lougher
>> SN Systems - Sony Computer Entertainment Group
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>