Regarding Dependence distance dump

Hi,

For the below test case, I need the dependence distance between the array references “a[j][i]” and “a[j-1][i-2]”.

–Snip–
int a[5][5];
int b[10];

void test()
{
for (int j=1;j<5;j++)
for (int i=2;i<5;i++)
{
a[j][i] = 3.0;
b[i]= a[j-1][i-2] ;
}
}
–Snip-

Compile steps
clang -O1 -emit-llvm -S test.c
opt -analyze -da dist.ll

I tried dumping the dependence information with LLVM trunk (2018_09_17), it shows:

Printing analysis ‘Dependence Analysis’ for function ‘test’:

da analyze - none!
da analyze - flow [< <>]! <== dumps direction vector
da analyze - none!
da analyze - none!
da analyze - none!
da analyze - consistent output [S 0]!

LLVM Release 6.0.1 dumps the expected distance.
Printing analysis ‘Dependence Analysis’ for function ‘test’:
da analyze - none!
da analyze - consistent flow [1 2]!
da analyze - none!
da analyze - none!
da analyze - none!
da analyze - consistent output [S 0]!

In trunk, it is now showing directions instead of distances.
How to get the dependence distance?

regards,
Venkat.

Hi,

I tired to see when this behavior changed in LLVM.
It seems to start from.

–snip–

commit 95e5d37d5868ebde2302bc302c1e0af407c5646d
Author: Sebastian Pop <sebpop@gmail.com>

–snip–

https://reviews.llvm.org/D35430

Review URL says “GEP” based approach was wrong for multidimensional array references. The LLVM-DA now uses SCEV representation. But why we are not getting the distance with SCEV? Current DA will not work for multidimensional arrays?

I need to get dependence distance for a transformation that I am working on. How do I get distance for such cases, esp multidimensional arrays?

Thanks and regards,
Venkat.

Hi,

I tired to see when this behavior changed in LLVM.
It seems to start from.

–snip–

commit 95e5d37d5868ebde2302bc302c1e0af407c5646d
Author: Sebastian Pop <sebpop@gmail.com>
Date: Tue Mar 6 21:55:59 2018 +0000

DA: remove uses of GEP, only ask SCEV
–snip–

https://reviews.llvm.org/D35430

Review URL says “GEP” based approach was wrong for multidimensional array references. The LLVM-DA now uses SCEV representation. But why we are not getting the distance with SCEV? Current DA will not work for multidimensional arrays?

It should work with delinearization of multi-dim arrays.

I need to get dependence distance for a transformation that I am working on. How do I get distance for such cases, esp multidimensional arrays?

Thanks and regards,
Venkat.

Hi,

For the below test case, I need the dependence distance between the array references “a[j][i]” and “a[j-1][i-2]”.

–Snip–
int a[5][5];
int b[10];

void test()
{
for (int j=1;j<5;j++)
for (int i=2;i<5;i++)
{
a[j][i] = 3.0;
b[i]= a[j-1][i-2] ;
}
}
–Snip-

Compile steps
clang -O1 -emit-llvm -S test.c
opt -analyze -da dist.ll

you are missing the -delinearize flag to opt.

Hi Sebastian ,

Hi,

I tired to see when this behavior changed in LLVM.
It seems to start from.

–snip–

commit 95e5d37d5868ebde2302bc302c1e0af407c5646d
Author: Sebastian Pop <sebpop@gmail.com>
Date: Tue Mar 6 21:55:59 2018 +0000

DA: remove uses of GEP, only ask SCEV
–snip–

https://reviews.llvm.org/D35430

Review URL says “GEP” based approach was wrong for multidimensional array references. The LLVM-DA now uses SCEV representation. But why we are not getting the distance with SCEV? Current DA will not work for multidimensional arrays?

It should work with delinearization of multi-dim arrays.

I thought “delinearization” is enabled by default on trunk now.

I need to get dependence distance for a transformation that I am working on. How do I get distance for such cases, esp multidimensional arrays?

Thanks and regards,
Venkat.

Hi,

For the below test case, I need the dependence distance between the array references “a[j][i]” and “a[j-1][i-2]”.

–Snip–
int a[5][5];
int b[10];

void test()
{
for (int j=1;j<5;j++)
for (int i=2;i<5;i++)
{
a[j][i] = 3.0;
b[i]= a[j-1][i-2] ;
}
}
–Snip-

Compile steps
clang -O1 -emit-llvm -S test.c
opt -analyze -da dist.ll

you are missing the -delinearize flag to opt.

Tried this flag and I am getting
opt -analyze -delinearize -da dist.ll

–Snip–

Delinearization on function test:
Inst: %arrayidx6 = getelementptr inbounds [5 x [5 x i32]], [5 x [5 x i32]]* @a, i64 0, i64 %indvars.iv30, i64 %indvars.iv

In Loop with Header: for.body4
AccessFunction: 0
failed to delinearize

Inst: %arrayidx6 = getelementptr inbounds [5 x [5 x i32]], [5 x [5 x i32]]* @a, i64 0, i64 %indvars.iv30, i64 %indvars.iv
In Loop with Header: for.cond1.preheader
AccessFunction: 0
failed to delinearize


–Snip–

regards.
Venkat.

Hi Sebastian,

Given that “delinerization” fails shall I file a PR in bugzilla?

regards,

Venkat,