Is Loop Dependence Analysis Printing Correct Stats?

Hi;

I was playing with the -lda pass of LLVM on the following program-

#include <stdio.h>
void main()
{
int a[10];
int i;
for(i = 0; i < 4; i ++)
{
a[i] = a[i-1]+1;
}
}

I run the following commands -

clang a.c -emit-llvm -S

opt -analyze -stats -lda a.s

The output is -

Printing analysis ‘Loop Dependence Analysis’:
Loop at depth 1, header block: %for.cond
Load/store instructions: 7
0: %0 = load i32* %i, align 4
1: %4 = load i32* %i, align 4
2: store i32 %inc, i32* %i, align 4
3: %1 = load i32* %i, align 4
4: %2 = load i32* %arrayidx, align 4
5: %3 = load i32* %i, align 4
6: store i32 %add, i32* %arrayidx1, align 4
Pairwise dependence results:
0,2: dependent
0,6: dependent
1,2: dependent
1,6: dependent
2,3: dependent
2,4: dependent
2,5: dependent
2,6: dependent
3,6: dependent
4,6: dependent
5,6: dependent

From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] On Behalf Of Arnamoy Bhattacharyya
Subject: [LLVMdev] Is Loop Dependence Analysis Printing Correct Stats?

for(i = 0; i < 4; i ++)
{
  a[i] = a[i-1]+1;
}

Am I doing anything wrong or the code seems buggy?

Your code is buggy. The first time through the loop, you're referencing a[-1], which is undefined.

- Chuck

THIS COMMUNICATION MAY CONTAIN CONFIDENTIAL AND/OR OTHERWISE PROPRIETARY MATERIAL and is thus for use only by the intended recipient. If you received this in error, please contact the sender and delete the e-mail and its attachments from all computers.

Thanks for the pointer Charles. Now I do:

Code:

#include <stdio.h>
void main()
{
int a[20]={0};
int i;
for(i = 0; i < 10; i ++)
{
a[i] = a[i+1]+1;
}
}

Output:

Printing analysis ‘Loop Dependence Analysis’:
Loop at depth 1, header block: %for.cond
Load/store instructions: 7
0: %1 = load i32* %i, align 4
1: %5 = load i32* %i, align 4
2: store i32 %inc, i32* %i, align 4
3: %2 = load i32* %i, align 4
4: %3 = load i32* %arrayidx, align 4
5: %4 = load i32* %i, align 4
6: store i32 %add1, i32* %arrayidx2, align 4
Pairwise dependence results:
0,2: dependent
0,6: dependent
1,2: dependent
1,6: dependent
2,3: dependent
2,4: dependent
2,5: dependent
2,6: dependent
3,6: dependent
4,6: dependent
5,6: dependent

Hi,

Looking at the code in lib/Analysis/LoopDependenceAnalysis.cpp, the 'dependent' in your output should be interpreted more like 'possibly not independent'.

Only 'dependent' and 'independent' are considered as outputs and 'dependent' is the general, 'better safe than sorry' response here.

One other point here is that the -lda pass uses results from alias analysis. By default opt uses the '-noaa' pass which always provides a 'may alias' response. To get more sensible results you will have to add a more effective alias analysis to your list of passes (e.g. -basic-aa)

Cheers,
  Roel