<html><body><p><font size="2">Hi Adel,</font><br><br><font size="2">The short answer is that the behaviour is expected, since the dependence analysis is performed in a context insensitive manor.</font><br><br><font size="2">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. </font><br><br><font size="2">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.</font><br><br><font size="2">Bardia Mahjour<br>Compiler Optimizations<br>IBM Toronto Software Lab<br>bmahjour@ca.ibm.com<br><br></font><br><br><img width="16" height="16" src="cid:1__=8FBB0FC8DFC2A2098f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for "Ejjeh, Adel via llvm-dev" ---2020/04/30 06:56:15 PM---Hello Everyone, I am still looking for some in"><font size="2" color="#424282">"Ejjeh, Adel via llvm-dev" ---2020/04/30 06:56:15 PM---Hello Everyone, I am still looking for some insight regarding the below issue. Please reach out if y</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">"Ejjeh, Adel via llvm-dev" <llvm-dev@lists.llvm.org></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">"Ejjeh, Adel via llvm-dev" <llvm-dev@lists.llvm.org></font><br><font size="2" color="#5F5F5F">Cc: </font><font size="2">"Adve, Vikram Sadanand" <vadve@illinois.edu></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">2020/04/30 06:56 PM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">[EXTERNAL] Re: [llvm-dev] Incorrect behavior in the LLVM dependence analyzer</font><br><font size="2" color="#5F5F5F">Sent by: </font><font size="2">"llvm-dev" <llvm-dev-bounces@lists.llvm.org></font><br><hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br><br><br>Hello Everyone, <br> <br>I am still looking for some insight regarding the below issue. Please reach out if you have any advice!<br> <br>Thanks,<br>-Adel<br> <br><b>From: </b>"Ejjeh, Adel" <aejjeh@illinois.edu><b><br>Date: </b>Thursday, April 23, 2020 at 5:21 PM<b><br>To: </b>LLVM Dev <llvm-dev@lists.llvm.org><b><br>Subject: </b>Incorrect behavior in the LLVM dependence analyzer<br> <br>Hi all,<br> <br>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:<br> <br>for(int i = 0; i < n; i++) {<br>S0: A[i] = …;<br>S1: … = A[i+1];<br>}<br> <br>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?<br>Regards,<br>- Adel<br> <br>-- <br><font size="6" color="#203864" face="Apple Chancery">Adel Ejjeh</font><br>PhD Candidate – Computer Science<br>University of Illinois at Urbana Champaign<br>201 N Goodwin Ave, Urbana, IL 61801<br><a href="mailto:aejjeh@illinois.edu"><u><font color="#0563C1">aejjeh@illinois.edu</font></u></a> | <a href="mailto:adel.ejjeh@gmail.com"><u><font color="#0563C1">adel.ejjeh@gmail.com</font></u></a><br> <tt><font size="2">_______________________________________________<br>LLVM Developers mailing list<br>llvm-dev@lists.llvm.org<br></font></tt><tt><font size="2"><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></font></tt><tt><font size="2"> <br></font></tt><br><br><BR>
</body></html>