llvm dev - Apr 2020 - Incorrect behavior in the LLVM dependence analyzer

Hi all,

I am trying to use the dependence analyzer in a pass that I am writing and I was
surprised to see an incorrect behavior when I try to query DependenceInfo for
dependences between instructions. Specifically, if the two instructions are
loads/stores accessing an array in a loop, the depend() method would return a
dependence regardless of the order of instructions specified. (i.e. if the two
instructions where L1 and S1, both depend(L1, S1) and depend(S1,L1) would return
a dependence), even though only one of the two dependences is valid when the
chronological order of the instructions is considered. To illustrate consider
this example:

for(int i = 0; i < n; i++) {
S0:   A[i] = …;
S1:   … = A[i+1];
}

In the example, there is an antidependence between S1 and S0 with distance 1.
However, when querying DependenceInfo it also returns a flow dependence from S0
to S1. Is this the expected behavior of DependenceInfo or Is it a known problem?
If it is the expected behavior, is there a way to check if the dependence you
are getting back is a correct one or not? Does anyone have any ideas about
possible workarounds or solutions?
Regards,
- Adel

--
Adel Ejjeh
PhD Candidate – Computer Science
University of Illinois at Urbana Champaign
201 N Goodwin Ave, Urbana, IL 61801
aejjeh at illinois.edu<mailto:aejjeh at illinois.edu> | adel.ejjeh at
gmail.com<mailto:adel.ejjeh at gmail.com>

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200423/8ecca6f0/attachment.html>

Hello Everyone,

I am still looking for some insight regarding the below issue. Please reach out
if you have any advice!

Thanks,
-Adel

From: "Ejjeh, Adel" <aejjeh at illinois.edu>
Date: Thursday, April 23, 2020 at 5:21 PM
To: LLVM Dev <llvm-dev at lists.llvm.org>
Subject: Incorrect behavior in the LLVM dependence analyzer

Hi all,

I am trying to use the dependence analyzer in a pass that I am writing and I was
surprised to see an incorrect behavior when I try to query DependenceInfo for
dependences between instructions. Specifically, if the two instructions are
loads/stores accessing an array in a loop, the depend() method would return a
dependence regardless of the order of instructions specified. (i.e. if the two
instructions where L1 and S1, both depend(L1, S1) and depend(S1,L1) would return
a dependence), even though only one of the two dependences is valid when the
chronological order of the instructions is considered. To illustrate consider
this example:

for(int i = 0; i < n; i++) {
S0:   A[i] = …;
S1:   … = A[i+1];
}

In the example, there is an antidependence between S1 and S0 with distance 1.
However, when querying DependenceInfo it also returns a flow dependence from S0
to S1. Is this the expected behavior of DependenceInfo or Is it a known problem?
If it is the expected behavior, is there a way to check if the dependence you
are getting back is a correct one or not? Does anyone have any ideas about
possible workarounds or solutions?
Regards,
- Adel

--
Adel Ejjeh
PhD Candidate – Computer Science
University of Illinois at Urbana Champaign
201 N Goodwin Ave, Urbana, IL 61801
aejjeh at illinois.edu<mailto:aejjeh at illinois.edu> | adel.ejjeh at
gmail.com<mailto:adel.ejjeh at gmail.com>

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200430/278d5685/attachment-0001.html>

Hi Adel,

The short answer is that the behaviour is expected, since the dependence
analysis is performed in a context insensitive manor.

The data dependence theory states that there is a dependence between a
statement S1 and S2 if they both access the same memory and there is a path
from S1 to S2. The chronology of two dependent statements is relative and
must be given at start in order to be able to decide on the type of
dependence (ie anti- vs true- dependence). This is why the `depends`
function takes source and destination arguments. In your example, if you
consider S0 the source of the dependence and S1 the sink of the dependence,
then you have a true-dependence with a distance of -1 (a RAW that is
backwards). On the other hand if you consider S1 to be the source and S0
the sink, then you have an anti-dependence with a distance of +1 (a WAR
that happens one iteration forward). Both these interpretations are valid
*representation* of the dependence information given their corresponding
source and destination statements, however there is a caveat.

In realty the sink of a dependence cannot happen before the source of that
dependence, so the true-dependence (with distance -1) in your example is
not real. It must instead be established as an anti-dependence (with
distance 1). In general whenever the left-most non-zero entry of a
direction vector is negative, the dependence edge must be reversed to
correct the ordering. If you use the DDG (see include/llvm/Analysis/DDG.h),
this is taken care of during its construction. In other cases you may need
to take specific measures to account for that in your transform/analysis.

Bardia Mahjour
Compiler Optimizations
IBM Toronto Software Lab
bmahjour at ca.ibm.com





From:	"Ejjeh, Adel via llvm-dev" <llvm-dev at lists.llvm.org>
To:	"Ejjeh, Adel via llvm-dev" <llvm-dev at lists.llvm.org>
Cc:	"Adve, Vikram Sadanand" <vadve at illinois.edu>
Date:	2020/04/30 06:56 PM
Subject:	[EXTERNAL] Re: [llvm-dev] Incorrect behavior in the LLVM
            dependence analyzer
Sent by:	"llvm-dev" <llvm-dev-bounces at lists.llvm.org>



Hello Everyone,

I am still looking for some insight regarding the below issue. Please reach
out if you have any advice!

Thanks,
-Adel

From: "Ejjeh, Adel" <aejjeh at illinois.edu>
Date: Thursday, April 23, 2020 at 5:21 PM
To: LLVM Dev <llvm-dev at lists.llvm.org>
Subject: Incorrect behavior in the LLVM dependence analyzer

Hi all,

I am trying to use the dependence analyzer in a pass that I am writing and
I was surprised to see an incorrect behavior when I try to query
DependenceInfo for dependences between instructions. Specifically, if the
two instructions are loads/stores accessing an array in a loop, the depend
() method would return a dependence regardless of the order of instructions
specified. (i.e. if the two instructions where L1 and S1, both depend(L1,
S1) and depend(S1,L1) would return a dependence), even though only one of
the two dependences is valid when the chronological order of the
instructions is considered. To illustrate consider this example:

for(int i = 0; i < n; i++) {
S0:   A[i] = …;
S1:   … = A[i+1];
}

In the example, there is an antidependence between S1 and S0 with distance
1. However, when querying DependenceInfo it also returns a flow dependence
from S0 to S1. Is this the expected behavior of DependenceInfo or Is it a
known problem? If it is the expected behavior, is there a way to check if
the dependence you are getting back is a correct one or not? Does anyone
have any ideas about possible workarounds or solutions?
Regards,
- Adel

--
Adel Ejjeh
PhD Candidate – Computer Science
University of Illinois at Urbana Champaign
201 N Goodwin Ave, Urbana, IL 61801
aejjeh at illinois.edu | adel.ejjeh at gmail.com
 _______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwIGaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=aihobyOnVzXW7OPSK1-NiSYQkq7oP3ZSUVc4BemvrVo&m=V4OnaRm4Q3xfMWN6WTtVEUcnoYSgLKh4q2osM8TcxVo&s=gwhw8VZw7DuR_jvqef4g3oCqK3X3YdVEt3Gf-ZBzFCc&e


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200501/2a72957d/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200501/2a72957d/attachment.gif>