llvm dev - Mar 2004 - [LLVMdev] A question about induction variables

Hello,
I've just downloaded the latest release of LLVM, and playing with the 
following simple example:

int main()
{
    int r(0);
    for (int i = 0; i < 100; ++i)
        r += i;
        ;
    return r;
}

I compile it and then run:

   analyze -indvars x.bc

which prints:

   Printing analysis 'Induction Variable Analysis' for function
'main':

and nothing else. It is a bit strange -- since 'i' is clearly an
induction
variable and the resulting loop in assembler should have some induction 
variable too. Does this mean that induction variable analysis is not fully 
implemented, or there's some error on my part?

If I don't use the 'r' variable, but just loop with empty body, the
entire
loop seems to be optimized out, but in this example the loop is still there 
in assembler.

Thanks in advance,
Volodya

On Wed, 31 Mar 2004, Vladimir Prus wrote:
> I've just downloaded the latest release of LLVM, and playing with the
> following simple example:
>
> int main()
> {
>     int r(0);
>     for (int i = 0; i < 100; ++i)
>         r += i;
>         ;
>     return r;
> }
When I compiled it, I got the following LLVM code:

int %main() {
entry:
	call void %__main( )
	br label %no_exit

no_exit:		; preds = %entry, %no_exit
	%i.0.0 = phi int [ 0, %entry ], [ %inc, %no_exit ]
	%r.0.0 = phi int [ 0, %entry ], [ %tmp.4, %no_exit ]
	%tmp.4 = add int %r.0.0, %i.0.0		; <int> [#uses=2]
	%inc = add int %i.0.0, 1		; <int> [#uses=2]
	%tmp.1 = setgt int %inc, 99		; <bool> [#uses=1]
	br bool %tmp.1, label %loopexit, label %no_exit

loopexit:		; preds = %no_exit
	ret int %tmp.4
}
> I compile it and then run:
>    analyze -indvars x.bc
> which prints:
>    Printing analysis 'Induction Variable Analysis' for function
'main':
When I did this, I got the following:

$ analyze -indvars t.ll
Printing analysis 'Induction Variable Analysis' for function
'main':
Canonical Induction Variable: int %i.0.0:
        %i.0.0 = phi int [ 0, %entry ], [ %inc, %no_exit ]              ;
<int> [#uses=2]
  Start = int 0  Step = int 1

... so it seems to work.  Are you sure that your x.bc file contains the
correct LLVM code?  This example certainly should work.
> and nothing else. It is a bit strange -- since 'i' is clearly an
induction
> variable and the resulting loop in assembler should have some induction
> variable too. Does this mean that induction variable analysis is not fully
> implemented, or there's some error on my part?
The induction variable analysis in 1.2 is not the most powerful, but it
should certainly catch this case!
> If I don't use the 'r' variable, but just loop with empty body,
the entire
> loop seems to be optimized out, but in this example the loop is still there
> in assembler.
Hrm, I'm really not sure.  It works for me :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Chris Lattner wrote:
> > int main()
> > {
> >     int r(0);
> >     for (int i = 0; i < 100; ++i)
> >         r += i;
> >         ;
> >     return r;
> > }
>
> When I compiled it, I got the following LLVM code:
The code I get is somewhat different:

int %main() {
entry:
	%tmp.1.i = load bool* %Initialized.0__		; <bool> [#uses=1]
	br bool %tmp.1.i, label %no_exit, label %endif.0.i

endif.0.i:		; preds = %entry
	store bool true, bool* %Initialized.0__
	br label %no_exit

no_exit:		; preds = %entry, %endif.0.i, %no_exit
	%i.0.0 = phi int [ %inc, %no_exit ], [ 0, %endif.0.i ], [ 0, %entry ]		; 
<int> [#uses=2]
	%r.0.0 = phi int [ %tmp.4, %no_exit ], [ 0, %endif.0.i ], [ 0, %entry ]		; 
<int> [#uses=1]
	%tmp.4 = add int %r.0.0, %i.0.0		; <int> [#uses=2]
	%inc = add int %i.0.0, 1		; <int> [#uses=2]
	%tmp.1 = setgt int %inc, 99		; <bool> [#uses=1]
	br bool %tmp.1, label %loopexit, label %no_exit

loopexit:		; preds = %no_exit
	ret int %tmp.4
}

but still there's a loop.
> > I compile it and then run:
> >    analyze -indvars x.bc
> > which prints:
> >    Printing analysis 'Induction Variable Analysis' for
function 'main':
>
> When I did this, I got the following:
>
> $ analyze -indvars t.ll
> Printing analysis 'Induction Variable Analysis' for function
'main':
> Canonical Induction Variable: int %i.0.0:
>         %i.0.0 = phi int [ 0, %entry ], [ %inc, %no_exit ]              ;
> <int> [#uses=2] Start = int 0  Step = int 1
>
> ... so it seems to work.  Are you sure that your x.bc file contains the
> correct LLVM code?  
Yes, I've just tried again, with the same results.
> Hrm, I'm really not sure.  It works for me :)
Well, I guess I'll just try the CVS version... the version built from the 
trunk has the same behaviour.

I'm using the prebuilt frontend which is part of 1.2 release, though. Maybe 
this can explain the difference in output.

- Volodya


>
> -Chris