thr3ads.net - llvm dev - [llvm-dev] A bug in DependenceAnalysis? [Jun 2017]

If this information is useful, please help other people find it:
Share via:

Stanislav Manilov via llvm-dev

2017-Jun-22 08:59 UTC

[llvm-dev] A bug in DependenceAnalysis?

Hi Philip,

I forgot to mention that I was ignoring loop-independent dependences. If I
don't I get an inconsistent, ordered, anti, loop-independent dependence and
an inconsistent, ordered, flow, loop-carried dependence for example A. At
the same time I get just a consistent, ordered, anti, loop-independent
dependence for example B.

Here's the .ll code for example A:

*; Function Attrs: nounwind uwtable*
*define void @_Z8move_onePij(i32*, i32) #3 {*
*  br label %3*

*; <label>:3:                                      ; preds = %13, %2*
*  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
*  %4 = sub i32 %1, 1*
*  %5 = icmp ult i32 %.0, %4*
*  br i1 %5, label %6, label %15*

*; <label>:6:                                      ; preds = %3*
*  %7 = add i32 %.0, 1*
*  %8 = zext i32 %7 to i64*
*  %9 = getelementptr inbounds i32, i32* %0, i64 %8*
*  %10 = load i32, i32* %9, align 4*
*  %11 = zext i32 %.0 to i64*
*  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
*  store i32 %10, i32* %12, align 4*
*  br label %13*

*; <label>:13:                                     ; preds = %6*
*  %14 = add i32 %.0, 1*
*  br label %3*

*; <label>:15:                                     ; preds = %3*
*  ret void*
*}*

Here's the .ll code for example B:

*; Function Attrs: nounwind uwtable*
*define void @_Z12move_one_altPij(i32*, i32) #3 {*
*  %3 = getelementptr inbounds i32, i32* %0, i64 1*
*  br label %4*

*; <label>:4:                                      ; preds = %13, %2*
*  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
*  %5 = sub i32 %1, 1*
*  %6 = icmp ult i32 %.0, %5*
*  br i1 %6, label %7, label %15*

*; <label>:7:                                      ; preds = %4*
*  %8 = zext i32 %.0 to i64*
*  %9 = getelementptr inbounds i32, i32* %3, i64 %8*
*  %10 = load i32, i32* %9, align 4*
*  %11 = zext i32 %.0 to i64*
*  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
*  store i32 %10, i32* %12, align 4*
*  br label %13*

*; <label>:13:                                     ; preds = %7*
*  %14 = add i32 %.0, 1*
*  br label %4*

*; <label>:15:                                     ; preds = %4*
*  ret void*
*}*

Can you please check whether the anti dependeces that you get are
loop-carried or loop-independent?

Thanks,
 - Stan

On Wed, Jun 21, 2017 at 7:21 PM, Philip Pfaffe <philip.pfaffe at
gmail.com>
wrote:
> Hi Stan,
>
> can you share your example.bc? Can you reproduce your issue with llvm 4.0
> or, better even, trunk?
>
> Cheers,
> Philip
>
> 2017-06-21 18:58 GMT+02:00 Stanislav Manilov <stanislav.manilov at
gmail.com>
> :
>
>> Hi Philip,
>>
>> Thanks for checking!
>>
>> I'm running my own Foo pass that registers
DependenceAnalysisWrapperPass
>> as a prerequisite and then I run it like so:
>>
>> opt -load libfoo.so -foo example.bc
>>
>> This is LLVM 3.9.
>>
>> Cheers,
>>  - Stan
>>
>> On Wed, Jun 21, 2017 at 5:40 PM, Philip Pfaffe <philip.pfaffe at
gmail.com>
>> wrote:
>>
>>> Hi Stan,
>>>
>>> in both cases I get a consistent anti result. Can you show us the
>>> command lines you're using? Which version of llvm is this?
>>>
>>> Best,
>>> Philip
>>>
>>> 2017-06-21 17:56 GMT+02:00 Stanislav Manilov via llvm-dev <
>>> llvm-dev at lists.llvm.org>:
>>>
>>>> Hello llvm-dev,
>>>>
>>>> I'm running a pass that uses the result of
>>>> llvm::DependenceAnalysisWrapperPass to compute the dependencies
>>>> between all instructions of a loop. I have the following two
examples of
>>>> code I wish to analyse:
>>>>
>>>> example A:
>>>>
>>>> ```
>>>> void move_one(int *A, unsigned n) {
>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>     A[i] = A[i + 1];
>>>>   }
>>>> }
>>>> ```
>>>> and example B:
>>>> ```
>>>> void move_one_alt(int *A, unsigned n) {
>>>>   int *B = A + 1;
>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>     A[i] = B[i];
>>>>   }
>>>> }
>>>> ```
>>>>
>>>> I would expect that I get the same result for both A and B,
namely a
>>>> loop carried anti (WAR) dependence from the generated load
instruction to
>>>> the generated store instruction. This should be the case,
because on
>>>> iteration i+1 the loop is writing to the element that has been
read in the
>>>> previous iteration - iteration i.
>>>>
>>>> However, in example A I get a loop carried flow (RAW)
dependence from
>>>> the store instruction to the load instruction, while in example
B I don't
>>>> get any dependence at all.
>>>>
>>>> Am I missing something, or is the result wrong?
>>>>
>>>> Thanks,
>>>>  - Stan
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>>
>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170622/330d64f5/attachment.html>

Philip Pfaffe via llvm-dev

2017-Jun-23 10:52 UTC

head link

[llvm-dev] A bug in DependenceAnalysis?

Hi Stan,

in the first example, I get an "anti [*|<]" result. DA doesn't
look through
zext expressions, so it needs to overapproximate.

In the second example I get a "consistent anti [0|<]" result, which
is
wrong. The cause of this bug is that DA falsely ignores the base pointer,
and only looks at the indices.

Please file a bug report for this, including a reproducing example, and put
me on CC.

Cheers,
Philip

2017-06-22 10:59 GMT+02:00 Stanislav Manilov <stanislav.manilov at
gmail.com>:
> Hi Philip,
>
> I forgot to mention that I was ignoring loop-independent dependences. If I
> don't I get an inconsistent, ordered, anti, loop-independent dependence
and
> an inconsistent, ordered, flow, loop-carried dependence for example A. At
> the same time I get just a consistent, ordered, anti, loop-independent
> dependence for example B.
>
> Here's the .ll code for example A:
>
> *; Function Attrs: nounwind uwtable*
> *define void @_Z8move_onePij(i32*, i32) #3 {*
> *  br label %3*
>
> *; <label>:3:                                      ; preds = %13, %2*
> *  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
> *  %4 = sub i32 %1, 1*
> *  %5 = icmp ult i32 %.0, %4*
> *  br i1 %5, label %6, label %15*
>
> *; <label>:6:                                      ; preds = %3*
> *  %7 = add i32 %.0, 1*
> *  %8 = zext i32 %7 to i64*
> *  %9 = getelementptr inbounds i32, i32* %0, i64 %8*
> *  %10 = load i32, i32* %9, align 4*
> *  %11 = zext i32 %.0 to i64*
> *  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
> *  store i32 %10, i32* %12, align 4*
> *  br label %13*
>
> *; <label>:13:                                     ; preds = %6*
> *  %14 = add i32 %.0, 1*
> *  br label %3*
>
> *; <label>:15:                                     ; preds = %3*
> *  ret void*
> *}*
>
> Here's the .ll code for example B:
>
> *; Function Attrs: nounwind uwtable*
> *define void @_Z12move_one_altPij(i32*, i32) #3 {*
> *  %3 = getelementptr inbounds i32, i32* %0, i64 1*
> *  br label %4*
>
> *; <label>:4:                                      ; preds = %13, %2*
> *  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
> *  %5 = sub i32 %1, 1*
> *  %6 = icmp ult i32 %.0, %5*
> *  br i1 %6, label %7, label %15*
>
> *; <label>:7:                                      ; preds = %4*
> *  %8 = zext i32 %.0 to i64*
> *  %9 = getelementptr inbounds i32, i32* %3, i64 %8*
> *  %10 = load i32, i32* %9, align 4*
> *  %11 = zext i32 %.0 to i64*
> *  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
> *  store i32 %10, i32* %12, align 4*
> *  br label %13*
>
> *; <label>:13:                                     ; preds = %7*
> *  %14 = add i32 %.0, 1*
> *  br label %4*
>
> *; <label>:15:                                     ; preds = %4*
> *  ret void*
> *}*
>
> Can you please check whether the anti dependeces that you get are
> loop-carried or loop-independent?
>
> Thanks,
>  - Stan
>
> On Wed, Jun 21, 2017 at 7:21 PM, Philip Pfaffe <philip.pfaffe at
gmail.com>
> wrote:
>
>> Hi Stan,
>>
>> can you share your example.bc? Can you reproduce your issue with llvm
4.0
>> or, better even, trunk?
>>
>> Cheers,
>> Philip
>>
>> 2017-06-21 18:58 GMT+02:00 Stanislav Manilov <stanislav.manilov at
gmail.com
>> >:
>>
>>> Hi Philip,
>>>
>>> Thanks for checking!
>>>
>>> I'm running my own Foo pass that registers
DependenceAnalysisWrapperPass
>>> as a prerequisite and then I run it like so:
>>>
>>> opt -load libfoo.so -foo example.bc
>>>
>>> This is LLVM 3.9.
>>>
>>> Cheers,
>>>  - Stan
>>>
>>> On Wed, Jun 21, 2017 at 5:40 PM, Philip Pfaffe <philip.pfaffe at
gmail.com>
>>> wrote:
>>>
>>>> Hi Stan,
>>>>
>>>> in both cases I get a consistent anti result. Can you show us
the
>>>> command lines you're using? Which version of llvm is this?
>>>>
>>>> Best,
>>>> Philip
>>>>
>>>> 2017-06-21 17:56 GMT+02:00 Stanislav Manilov via llvm-dev <
>>>> llvm-dev at lists.llvm.org>:
>>>>
>>>>> Hello llvm-dev,
>>>>>
>>>>> I'm running a pass that uses the result of
>>>>> llvm::DependenceAnalysisWrapperPass to compute the
dependencies
>>>>> between all instructions of a loop. I have the following
two examples of
>>>>> code I wish to analyse:
>>>>>
>>>>> example A:
>>>>>
>>>>> ```
>>>>> void move_one(int *A, unsigned n) {
>>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>>     A[i] = A[i + 1];
>>>>>   }
>>>>> }
>>>>> ```
>>>>> and example B:
>>>>> ```
>>>>> void move_one_alt(int *A, unsigned n) {
>>>>>   int *B = A + 1;
>>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>>     A[i] = B[i];
>>>>>   }
>>>>> }
>>>>> ```
>>>>>
>>>>> I would expect that I get the same result for both A and B,
namely a
>>>>> loop carried anti (WAR) dependence from the generated load
instruction to
>>>>> the generated store instruction. This should be the case,
because on
>>>>> iteration i+1 the loop is writing to the element that has
been read in the
>>>>> previous iteration - iteration i.
>>>>>
>>>>> However, in example A I get a loop carried flow (RAW)
dependence from
>>>>> the store instruction to the load instruction, while in
example B I don't
>>>>> get any dependence at all.
>>>>>
>>>>> Am I missing something, or is the result wrong?
>>>>>
>>>>> Thanks,
>>>>>  - Stan
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> llvm-dev at lists.llvm.org
>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>
>>>>>
>>>>
>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170623/c575a891/attachment.html>

Stanislav Manilov via llvm-dev

2017-Jun-23 14:07 UTC

head link

[llvm-dev] A bug in DependenceAnalysis?

Hi Philip,

Done. See https://bugs.llvm.org/show_bug.cgi?id=33567.

Cheers,
 - Stan

On Fri, Jun 23, 2017 at 11:52 AM, Philip Pfaffe <philip.pfaffe at
gmail.com>
wrote:
> Hi Stan,
>
> in the first example, I get an "anti [*|<]" result. DA
doesn't look
> through zext expressions, so it needs to overapproximate.
>
> In the second example I get a "consistent anti [0|<]" result,
which is
> wrong. The cause of this bug is that DA falsely ignores the base pointer,
> and only looks at the indices.
>
> Please file a bug report for this, including a reproducing example, and
> put me on CC.
>
> Cheers,
> Philip
>
> 2017-06-22 10:59 GMT+02:00 Stanislav Manilov <stanislav.manilov at
gmail.com>
> :
>
>> Hi Philip,
>>
>> I forgot to mention that I was ignoring loop-independent dependences.
If
>> I don't I get an inconsistent, ordered, anti, loop-independent
dependence
>> and an inconsistent, ordered, flow, loop-carried dependence for example
A.
>> At the same time I get just a consistent, ordered, anti,
loop-independent
>> dependence for example B.
>>
>> Here's the .ll code for example A:
>>
>> *; Function Attrs: nounwind uwtable*
>> *define void @_Z8move_onePij(i32*, i32) #3 {*
>> *  br label %3*
>>
>> *; <label>:3:                                      ; preds = %13,
%2*
>> *  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
>> *  %4 = sub i32 %1, 1*
>> *  %5 = icmp ult i32 %.0, %4*
>> *  br i1 %5, label %6, label %15*
>>
>> *; <label>:6:                                      ; preds = %3*
>> *  %7 = add i32 %.0, 1*
>> *  %8 = zext i32 %7 to i64*
>> *  %9 = getelementptr inbounds i32, i32* %0, i64 %8*
>> *  %10 = load i32, i32* %9, align 4*
>> *  %11 = zext i32 %.0 to i64*
>> *  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
>> *  store i32 %10, i32* %12, align 4*
>> *  br label %13*
>>
>> *; <label>:13:                                     ; preds = %6*
>> *  %14 = add i32 %.0, 1*
>> *  br label %3*
>>
>> *; <label>:15:                                     ; preds = %3*
>> *  ret void*
>> *}*
>>
>> Here's the .ll code for example B:
>>
>> *; Function Attrs: nounwind uwtable*
>> *define void @_Z12move_one_altPij(i32*, i32) #3 {*
>> *  %3 = getelementptr inbounds i32, i32* %0, i64 1*
>> *  br label %4*
>>
>> *; <label>:4:                                      ; preds = %13,
%2*
>> *  %.0 = phi i32 [ 0, %2 ], [ %14, %13 ]*
>> *  %5 = sub i32 %1, 1*
>> *  %6 = icmp ult i32 %.0, %5*
>> *  br i1 %6, label %7, label %15*
>>
>> *; <label>:7:                                      ; preds = %4*
>> *  %8 = zext i32 %.0 to i64*
>> *  %9 = getelementptr inbounds i32, i32* %3, i64 %8*
>> *  %10 = load i32, i32* %9, align 4*
>> *  %11 = zext i32 %.0 to i64*
>> *  %12 = getelementptr inbounds i32, i32* %0, i64 %11*
>> *  store i32 %10, i32* %12, align 4*
>> *  br label %13*
>>
>> *; <label>:13:                                     ; preds = %7*
>> *  %14 = add i32 %.0, 1*
>> *  br label %4*
>>
>> *; <label>:15:                                     ; preds = %4*
>> *  ret void*
>> *}*
>>
>> Can you please check whether the anti dependeces that you get are
>> loop-carried or loop-independent?
>>
>> Thanks,
>>  - Stan
>>
>> On Wed, Jun 21, 2017 at 7:21 PM, Philip Pfaffe <philip.pfaffe at
gmail.com>
>> wrote:
>>
>>> Hi Stan,
>>>
>>> can you share your example.bc? Can you reproduce your issue with
llvm
>>> 4.0 or, better even, trunk?
>>>
>>> Cheers,
>>> Philip
>>>
>>> 2017-06-21 18:58 GMT+02:00 Stanislav Manilov <
>>> stanislav.manilov at gmail.com>:
>>>
>>>> Hi Philip,
>>>>
>>>> Thanks for checking!
>>>>
>>>> I'm running my own Foo pass that registers
>>>> DependenceAnalysisWrapperPass as a prerequisite and then I run
it like so:
>>>>
>>>> opt -load libfoo.so -foo example.bc
>>>>
>>>> This is LLVM 3.9.
>>>>
>>>> Cheers,
>>>>  - Stan
>>>>
>>>> On Wed, Jun 21, 2017 at 5:40 PM, Philip Pfaffe
<philip.pfaffe at gmail.com
>>>> > wrote:
>>>>
>>>>> Hi Stan,
>>>>>
>>>>> in both cases I get a consistent anti result. Can you show
us the
>>>>> command lines you're using? Which version of llvm is
this?
>>>>>
>>>>> Best,
>>>>> Philip
>>>>>
>>>>> 2017-06-21 17:56 GMT+02:00 Stanislav Manilov via llvm-dev
<
>>>>> llvm-dev at lists.llvm.org>:
>>>>>
>>>>>> Hello llvm-dev,
>>>>>>
>>>>>> I'm running a pass that uses the result of
>>>>>> llvm::DependenceAnalysisWrapperPass to compute the
dependencies
>>>>>> between all instructions of a loop. I have the
following two examples of
>>>>>> code I wish to analyse:
>>>>>>
>>>>>> example A:
>>>>>>
>>>>>> ```
>>>>>> void move_one(int *A, unsigned n) {
>>>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>>>     A[i] = A[i + 1];
>>>>>>   }
>>>>>> }
>>>>>> ```
>>>>>> and example B:
>>>>>> ```
>>>>>> void move_one_alt(int *A, unsigned n) {
>>>>>>   int *B = A + 1;
>>>>>>   for (unsigned i = 0; i < n-1; ++i) {
>>>>>>     A[i] = B[i];
>>>>>>   }
>>>>>> }
>>>>>> ```
>>>>>>
>>>>>> I would expect that I get the same result for both A
and B, namely a
>>>>>> loop carried anti (WAR) dependence from the generated
load instruction to
>>>>>> the generated store instruction. This should be the
case, because on
>>>>>> iteration i+1 the loop is writing to the element that
has been read in the
>>>>>> previous iteration - iteration i.
>>>>>>
>>>>>> However, in example A I get a loop carried flow (RAW)
dependence from
>>>>>> the store instruction to the load instruction, while in
example B I don't
>>>>>> get any dependence at all.
>>>>>>
>>>>>> Am I missing something, or is the result wrong?
>>>>>>
>>>>>> Thanks,
>>>>>>  - Stan
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> LLVM Developers mailing list
>>>>>> llvm-dev at lists.llvm.org
>>>>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170623/3a4ba169/attachment.html>

llvm dev - Jun 2017 - A bug in DependenceAnalysis?

[llvm-dev] A bug in DependenceAnalysis?

[llvm-dev] A bug in DependenceAnalysis?

[llvm-dev] A bug in DependenceAnalysis?