llvm dev - Jun 2012 - [LLVMdev] 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
===-------------------------------------------------------------------------==  
... Statistics Collected ...
===-------------------------------------------------------------------------==
11 lda - Number of dependence queries answered
11 lda - Number of distinct dependence pairs analysed
11 lda - Number of pairs with unknown accesses

Why do the " Pairwise dependence results:" and the "Statistics
Collected"
differ?  Like first we get 11 "dependent"(must) accesses and later it
says
11 "unknown" (may) accesses?  Am I doing anything wrong or the code
seems
buggy?

Thanks;
-- 
Arnamoy Bhattacharyya
Athabasca Hall 143
Department of Computing Science - University of Alberta
Edmonton, Alberta, Canada, T6G 2E8
587-710-7073
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120620/2dc31fde/attachment.html>

> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
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
===-------------------------------------------------------------------------==  
... Statistics Collected ...
===-------------------------------------------------------------------------==
11 lda - Number of dependence queries answered
11 lda - Number of distinct dependence pairs analysed
11 lda - Number of pairs with unknown accesses




On Wed, Jun 20, 2012 at 3:48 PM, Caldarale, Charles R <
Chuck.Caldarale at unisys.com> wrote:
> > From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
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.
>
>

-- 
Arnamoy Bhattacharyya
Athabasca Hall 143
Department of Computing Science - University of Alberta
Edmonton, Alberta, Canada, T6G 2E8
587-710-7073
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120620/fa0df16d/attachment.html>

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

On 20/06/12 23:33, Arnamoy Bhattacharyya wrote:
> 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
>
===-------------------------------------------------------------------------==>
... Statistics Collected ...
>
===-------------------------------------------------------------------------==>
> 11 lda - Number of dependence queries answered
> 11 lda - Number of distinct dependence pairs analysed
> 11 lda - Number of pairs with unknown accesses
>
> Why do the " Pairwise dependence results:" and the
"Statistics
> Collected" differ?  Like first we get 11 "dependent"(must)
accesses and
> later it says 11 "unknown" (may) accesses?  Am I doing anything
wrong or
> the code seems buggy?
>
> Thanks;
> --
> Arnamoy Bhattacharyya
> Athabasca Hall 143
> Department of Computing Science - University of Alberta
> Edmonton, Alberta, Canada, T6G 2E8
> 587-710-7073