-indvars does not rewrite the exit condition for a two-level loop nest

[llvmbot]

Bugzilla Link	1722
Resolution	WORKSFORME
Resolved on	Oct 03, 2007 16:21
Version	2.1
OS	Linux
Attachments	foo.bc
Reporter	LLVM Bugzilla Contributor

Extended Description

//////// C code ////////////////
void foo()
{
int i, j;
for (i = 0; i < 100; ++i)
for (j = 0; j < i; ++j)
a[i][j] = i * j;
}

;;;;;;;;;;;;;;;;; ll code piece for the loop nest ;;;;;;;;;;;;;;;;;;;;;;

bb1: ; preds = %bb10
%tmp5 = mul i32 %i.0, %j.1 ; [#uses=1]
%tmp7 = getelementptr [100 x [100 x i32]]* @​a, i32 0, i32 %i.0, i32 %j.1 ; <i32*> [#uses=1]
store i32 %tmp5, i32* %tmp7, align 4
%tmp9 = add i32 %j.1, 1 ; [#uses=1]
br label %bb10

bb10: ; preds = %bb18, %bb1
%j.1 = phi i32 [ %tmp9, %bb1 ], [ 0, %bb18 ] ; [#uses=4]
%tmp13 = icmp slt i32 %j.1, %i.0 ; [#uses=1]
br i1 %tmp13, label %bb1, label %bb15

bb15: ; preds = %bb10
%tmp17 = add i32 %i.0, 1 ; [#uses=1]
br label %bb18

bb18: ; preds = %bb15, %entry
%i.0 = phi i32 [ 0, %entry ], [ %tmp17, %bb15 ] ; [#uses=5]
%tmp20 = icmp slt i32 %i.0, 100 ; [#uses=1]
br i1 %tmp20, label %bb10, label %return

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

After "opt -indvars -simplifycfg",

;;;;;;;;;;;;;;;;; ll code piece after -indvars ;;;;;;;;;;;;;;;;;;;;;;
bb1: ; preds = %bb10
%tmp5 = mul i32 %i.0, %j.1 ; [#uses=1]
%tmp7 = getelementptr [100 x [100 x i32]]* @​a, i32 0, i32 %i.0, i32 %j.1 ; <i32*> [#uses=1]
store i32 %tmp5, i32* %tmp7, align 4
%indvar.next = add i32 %j.1, 1 ; [#uses=1]
br label %bb10

bb10: ; preds = %bb18, %bb1
%j.1 = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb18 ] ; [#uses=4]
%tmp13 = icmp slt i32 %j.1, %i.0 ; [#uses=1]
br i1 %tmp13, label %bb1, label %bb15

bb15: ; preds = %bb10
%indvar.next1 = add i32 %i.0, 1 ; [#uses=1]
br label %bb18

bb18: ; preds = %bb15, %entry
%i.0 = phi i32 [ 0, %entry ], [ %indvar.next1, %bb15 ] ; [#uses=5]
%exitcond = icmp ne i32 %i.0, 100 ; [#uses=1]
br i1 %exitcond, label %bb10, label %return
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

I was hoping that the exit condition of the inner loop "%tmp13 = icmp slt i32 %j.1, %i.0" would be turned into "%tmp13 = icmp ne i32 %j.1, %i.0".
But this didnt happen.

I didnt use tail duplicate and loop rotate to get the first bitcode (attached as foo.bc). So my loop is in a bad form?

[lattner]

llvm-gcc -O3 does this:

    %exitcond = icmp eq i32 %indvar.next, %indvar35         ; <i1> [#uses=1]
    br i1 %exitcond, label %bb17, label %bb1

[llvmbot]

I know "llvm-gcc -O3" can do it with tail duplication and loop rotation involved in the flow. Are they required for the success of -indvars? What should I do if I dont want to use these two passes.

llvm-gcc -O3 does this:

    %exitcond = icmp eq i32 %indvar.next, %indvar35         ; <i1>

[#uses=1]
br i1 %exitcond, label %bb17, label %bb1

[lattner]

I'm not certain. Every pass has prerequisites required for it to be effective. I suggest experimenting with it.