optimizer returning wrong variable?

Project Infrastructure LLVM Dev List Archives
#1

I’m having some trouble trying to workout how to form functions from the c interface
I thought I had it sorted but I guess I’m missing something or haven’t understood
the requirements, a case of trial and error and not really having a clue to start with!

I’ve got binary ops, cmps, for loops, while loops working but then it hit the
wall with a tail cmp loop.

looking at the output from the c interface it looks ok to me
but the optimizer is returning the wrong variable
I don’t know what to do to avoid it?

source language input

Procedure TRU(a,b)
Protected x,y,c
Repeat
y=0
Repeat
c+x+y
y+1
Until y >= b
x+1
Until x >= a
ProcedureReturn c
EndProcedure

output generated via the c Interface

define i32 @TRU(i32 %a, i32 %b) {
Entry:
%a1 = alloca i32
store i32 %a, i32* %a1
%b2 = alloca i32
store i32 %b, i32* %b2
%c = alloca i32
store i32 0, i32* %c
%x = alloca i32
store i32 0, i32* %x
%y = alloca i32
store i32 0, i32* %y
br label %Repeat1

Repeat1: ; preds = %Until1, %Entry
store i32 0, i32* %y
br label %Repeat2

Repeat2: ; preds = %Until2, %Repeat1
%x3 = load i32* %x
%y4 = load i32* %y
%add = add i32 %x3, %y4
%c5 = load i32* %c
%add6 = add i32 %c5, %add
store i32 %add6, i32* %c
%y7 = load i32* %y
%add8 = add i32 %y7, 1
store i32 %add8, i32* %y
br label %Until2

Until2: ; preds = %Repeat2
%y9 = load i32* %y
%b10 = load i32* %b2
%cond = icmp sge i32 %y9, %b10
br i1 %cond, label %Repeat2, label %Untilcmp2

Untilcmp2: ; preds = %Until2
%x11 = load i32* %x
%add12 = add i32 %x11, 1
store i32 %add12, i32* %x
br label %Until1

Until1: ; preds = %Untilcmp2
%x13 = load i32* %x
%a14 = load i32* %a1
%cond15 = icmp sge i32 %x13, %a14
br i1 %cond15, label %Repeat1, label %Untilcmp1

Untilcmp1: ; preds = %Until1
%c16 = load i32* %c
ret i32 %c16
}

verifying module
Optimize Function
Run in JIT
Jit Result: = 0
should = 325

dump the optimized module

define i32 @TRU(i32 %a, i32 %b) {
Entry:
br label %Repeat1

Repeat1: ; preds = %Untilcmp2, %Entry
%c.0 = phi i32 [ 0, %Entry ], [ %add6, %Untilcmp2 ]
%x.0 = phi i32 [ 0, %Entry ], [ %add12, %Untilcmp2 ]
br label %Repeat2

Repeat2: ; preds = %Repeat2, %Repeat1
%c.1 = phi i32 [ %c.0, %Repeat1 ], [ %add6, %Repeat2 ]
%y.0 = phi i32 [ 0, %Repeat1 ], [ %add8, %Repeat2 ]
%add = add i32 %c.1, %x.0
%add6 = add i32 %add, %y.0
%add8 = add i32 %y.0, 1
%cond = icmp slt i32 %add8, %b
br i1 %cond, label %Untilcmp2, label %Repeat2

Untilcmp2: ; preds = %Repeat2
%add12 = add i32 %x.0, 1
%cond15 = icmp slt i32 %add12, %a
br i1 %cond15, label %Untilcmp1, label %Repeat1

Untilcmp1: ; preds = %Untilcmp2
ret i32 %add6
}

#2

Andrew Ferguson wrote:

  I'm having some trouble trying to workout how to form functions from
the c interface
I thought I had it sorted but I guess I'm missing something or haven't
understood
the requirements, a case of trial and error and not really having a clue
to start with!

I've got binary ops, cmps, for loops, while loops working but then it
hit the
wall with a tail cmp loop.

looking at the output from the c interface it looks ok to me
but the optimizer is returning the wrong variable
I don't know what to do to avoid it?

I don't see the problem. In your input .ll, the function's return is:

   %c16 = load i32* %c
   ret i32 %c16

The last store to %c is the one in Repeat2

   %add6 = add i32 %c, %add
   store i32 %add6, i32* %c

which postdominates (ie., all routes from entry to exit must encounter that store). Therefore we conclude that the return value is in fact %add6.

Are you actually seeing different behaviour for any particular set of inputs on some target?

Nick

#3

Andrew Ferguson wrote:
> I'm having some trouble trying to workout how to form functions from
> the c interface
> I thought I had it sorted but I guess I'm missing something or haven't
> understood
> the requirements, a case of trial and error and not really having a clue
> to start with!
>
> I've got binary ops, cmps, for loops, while loops working but then it
> hit the
> wall with a tail cmp loop.
>
> looking at the output from the c interface it looks ok to me
> but the optimizer is returning the wrong variable
> I don't know what to do to avoid it?

I don't see the problem. In your input .ll, the function's return is:

   %c16 = load i32* %c
   ret i32 %c16

The last store to %c is the one in Repeat2

   %add6 = add i32 %c, %add
   store i32 %add6, i32* %c

which postdominates (ie., all routes from entry to exit must encounter
that store). Therefore we conclude that the return value is in fact %add6.

Are you actually seeing different behaviour for any particular set of
inputs on some target?

Nick

Thanks, that make sense, it's just that the returned value from the
example is coming out as zero, when it should be 325
Should or does the optimized code return the correct value?
Or should I be looking at the JIT?

I've only been able to test what I'm doing on (32 bit Ubuntu 11.04)
I did try to build a dll on windows with MinGW, 2.9 failed, 2.8 built ok
but was broken, so I deferred it to a later date. I couldn't satisfy the
linker with the static libs. So I'm using the shared object if that
makes any difference.

Regarding the JIT none of the .ll I'm generating runs without having
been optimized first. I assumed it would run if it's been validated but
apparently it doesn't, so I concluded that the JIT only accepts the
proper SSA representation, I don't know if that's supposed to be the
case or not.
     
Cheers Andrew

#4

Sorry people, actually it looks like there's a problem with my logic!
And even the raw .ll is running in the JIT (which is a first)
Perhaps once I've got over the teething problems, I'll contribute some
documentation for using the c interface.
Thanks for the help.