[llvm-dev] Incorrect behavior in the LLVM dependence analyzer (original) (raw)

Bardia Mahjour via llvm-dev llvm-dev at lists.llvm.org
Fri May 1 08:42:25 PDT 2020

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 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>

More information about the llvm-dev mailing list