A question about induction variables

Project Infrastructure LLVM Dev List Archives
1

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

2

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

-Chris

3

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

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

4

The code I get is somewhat different:
but still there's a loop.

Yeah that should be fine.

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

Okay, I think this is due to some code that I have had in my tree for a
long time that I forgot about. I'll get it into CVS and then let you
know.

-Chris