llvm dev - Jul 2016 - load instruction erroneously removed by GVN v2

Hello to whom this may concern,

Versioned this as I saw identical title before. I'm compiling a clang
project where I'm seeing GVN mess up and replace a load with a wrong def
value. I am using LLVM-3.5, but the problem has been observed upto 3.8.
To illustrate the problem,

define i32 @main
scalar.ph:
    <initialize [80 x i16] %dest>
...
preheader:
%index=0
br test, loop1, bb2
loop1:
  ... write to %dest in increasing index // ptr-based while loop
  %ptr++;
  br test, loop1, bb2
bb2:
  %lcssa = phi [%ptr, loop1], [%ptr, preheader]
  store i16 0, i16* %lcssa !dbg !20094 !tbaa 20030  // write null byte at
end
  %76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg !20095
// load addr of null byte (7th index)
  %77 = load i16* %76, align 2, !dbg !20095, !tbaa !20010
  %78 = icmp eq i16 %77, 0, !dbg !20095
  br i1 %78, label %80, label %79, !dbg !20095

GVN calls processNonLocalLoad() on "%77 = load..." and replaces it
with
init value from scalar.ph.

bb2:
%lcssa = phi [%ptr, loop1], [%ptr, preheader]
store i16 0, i16* %lcssa, !dbg !20094, !tbaa !20030
%76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg !20095
br i1 icmp eq (i16 trunc (i128 lshr (i128 bitcast (<8 x i16> <i16 120,
i16
120, i16 120, i16 120, i16 120, i16 120, i16 120, i16 120> to i128), i128
96) to i16), i16 0), label %78, label %77, !dbg !20095  // simplifies to
"icmp eq (i16 120, i16 0) --> false"

I first suspected problem might be TBAA; invoking clang with
-fno-strict-aliasing makes the test pass (similarly, opt with -basicaa does
not make GVN transform the load). When I look at the C/C++ source code, I
cannot find any type-based aliasing violations from eyeballing.

I started looking at the aliasing and landed at
getNonLocalPointerDepFromBB(), in which the worklist algorithm to find
MemDep reported the result from the init block, ignoring all the kills
after it. I did see one of the parm was SkipFirstBlock and this appears to
ignore the store %ptr above the load. Is there a reason why it skips first
block? Shouldn't it look at the preceding instructions in the same block as
they could contain kill points? I am still unfamiliar with the algorithm
used here and would very much appreciate if someone could educate or point
me towards right direction.

Regards,
Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160720/8d497ed2/attachment.html>

On Wed, Jul 20, 2016 at 9:56 AM, Kevin Choi via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello to whom this may concern,
>
> Versioned this as I saw identical title before. I'm compiling a clang
> project where I'm seeing GVN mess up and replace a load with a wrong
def
> value.
>

Do you have a c testcase or a .ll file i can actually compile?

> I am using LLVM-3.5, but the problem has been observed upto 3.8.
> To illustrate the problem,
>
> define i32 @main
> scalar.ph:
>     <initialize [80 x i16] %dest>
> ...
> preheader:
> %index=0
> br test, loop1, bb2
> loop1:
>   ... write to %dest in increasing index // ptr-based while loop
>   %ptr++;
>   br test, loop1, bb2
> bb2:
>   %lcssa = phi [%ptr, loop1], [%ptr, preheader]
>   store i16 0, i16* %lcssa !dbg !20094 !tbaa 20030  // write null byte at
> end
>   %76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg
> !20095 // load addr of null byte (7th index)
>   %77 = load i16* %76, align 2, !dbg !20095, !tbaa !20010
>   %78 = icmp eq i16 %77, 0, !dbg !20095
>   br i1 %78, label %80, label %79, !dbg !20095
>
> GVN calls processNonLocalLoad() on "%77 = load..." and replaces
it with
> init value from scalar.ph.
>
>
> bb2:
> %lcssa = phi [%ptr, loop1], [%ptr, preheader]
> store i16 0, i16* %lcssa, !dbg !20094, !tbaa !20030
> %76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg !20095
> br i1 icmp eq (i16 trunc (i128 lshr (i128 bitcast (<8 x i16> <i16
120, i16
> 120, i16 120, i16 120, i16 120, i16 120, i16 120, i16 120> to i128),
i128
> 96) to i16), i16 0), label %78, label %77, !dbg !20095  // simplifies to
> "icmp eq (i16 120, i16 0) --> false"
>
> I first suspected problem might be TBAA; invoking clang with
> -fno-strict-aliasing makes the test pass (similarly, opt with -basicaa does
> not make GVN transform the load). When I look at the C/C++ source code, I
> cannot find any type-based aliasing violations from eyeballing.
>
Can you excerpt the actual source code?
>
> I started looking at the aliasing and landed at
> getNonLocalPointerDepFromBB(), in which the worklist algorithm to find
> MemDep reported the result from the init block, ignoring all the kills
> after it. I did see one of the parm was SkipFirstBlock and this appears to
> ignore the store %ptr above the load. Is there a reason why it skips first
> block?
>

Yes. It is looking for *non-local* dependences.  The block it should skip
is bb2, not loop1.
There is another call for local dependences.  If you ask for local
dependences, then non-local ones, as GVN does, there is no point in having
it go and look at the local ones again :)

Look at how GVN calls this:
MemDepResult Dep = MD->getDependency(L);

   // If it is defined in another block, try harder.
   if (Dep.isNonLocal())
     return processNonLocalLoad(L);

(IE get local dependence, if there is none, go looking at non-local
dependences).


The list of non-local dependences it includes should definitely include the
one from block "loop1", and if it is ignoring it, it is most likely
thinks
it does not alias for some reason.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160720/5e79a231/attachment.html>

Thanks for quick reply Daniel,

I tried to make a simple C testcase, but could not reproduce the same
condition with output from Clang. I suppose I could modify the C code to
make it look similar with TBAA's; I may be able to provide this by eod.
> store %ptr above the load.
My mistake; I was referring to the store $lcssa in bb2. Looking at the C
source code, it should definitely alias with %dest. I will try and see if I
can find out why it thinks there is no local dependence.

Thanks,
Kevin

On 20 July 2016 at 11:06, Daniel Berlin <dberlin at dberlin.org> wrote:
>
>
> On Wed, Jul 20, 2016 at 9:56 AM, Kevin Choi via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hello to whom this may concern,
>>
>> Versioned this as I saw identical title before. I'm compiling a
clang
>> project where I'm seeing GVN mess up and replace a load with a
wrong def
>> value.
>>
>
>
> Do you have a c testcase or a .ll file i can actually compile?
>
>
>> I am using LLVM-3.5, but the problem has been observed upto 3.8.
>> To illustrate the problem,
>>
>> define i32 @main
>> scalar.ph:
>>     <initialize [80 x i16] %dest>
>> ...
>> preheader:
>> %index=0
>> br test, loop1, bb2
>> loop1:
>>   ... write to %dest in increasing index // ptr-based while loop
>>   %ptr++;
>>   br test, loop1, bb2
>> bb2:
>>   %lcssa = phi [%ptr, loop1], [%ptr, preheader]
>>   store i16 0, i16* %lcssa !dbg !20094 !tbaa 20030  // write null byte
at
>> end
>>   %76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg
>> !20095 // load addr of null byte (7th index)
>>   %77 = load i16* %76, align 2, !dbg !20095, !tbaa !20010
>>   %78 = icmp eq i16 %77, 0, !dbg !20095
>>   br i1 %78, label %80, label %79, !dbg !20095
>>
>> GVN calls processNonLocalLoad() on "%77 = load..." and
replaces it with
>> init value from scalar.ph.
>>
>>
>
>
>> bb2:
>> %lcssa = phi [%ptr, loop1], [%ptr, preheader]
>> store i16 0, i16* %lcssa, !dbg !20094, !tbaa !20030
>> %76 = getelementptr inbounds [80 x i16]* %dest, i64 0, i64 7, !dbg
!20095
>> br i1 icmp eq (i16 trunc (i128 lshr (i128 bitcast (<8 x i16>
<i16 120,
>> i16 120, i16 120, i16 120, i16 120, i16 120, i16 120, i16 120> to
i128),
>> i128 96) to i16), i16 0), label %78, label %77, !dbg !20095  //
simplifies
>> to "icmp eq (i16 120, i16 0) --> false"
>>
>> I first suspected problem might be TBAA; invoking clang with
>> -fno-strict-aliasing makes the test pass (similarly, opt with -basicaa
does
>> not make GVN transform the load). When I look at the C/C++ source code,
I
>> cannot find any type-based aliasing violations from eyeballing.
>>
>
> Can you excerpt the actual source code?
>
>>
>> I started looking at the aliasing and landed at
>> getNonLocalPointerDepFromBB(), in which the worklist algorithm to find
>> MemDep reported the result from the init block, ignoring all the kills
>> after it. I did see one of the parm was SkipFirstBlock and this appears
to
>> ignore the store %ptr above the load. Is there a reason why it skips
first
>> block?
>>
>
>
> Yes. It is looking for *non-local* dependences.  The block it should skip
> is bb2, not loop1.
> There is another call for local dependences.  If you ask for local
> dependences, then non-local ones, as GVN does, there is no point in having
> it go and look at the local ones again :)
>
> Look at how GVN calls this:
> MemDepResult Dep = MD->getDependency(L);
>
>    // If it is defined in another block, try harder.
>    if (Dep.isNonLocal())
>      return processNonLocalLoad(L);
>
> (IE get local dependence, if there is none, go looking at non-local
> dependences).
>
>
> The list of non-local dependences it includes should definitely include
> the one from block "loop1", and if it is ignoring it, it is most
likely
> thinks it does not alias for some reason.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160720/0e1418d9/attachment.html>