[LLVMdev] Question to Chris

[Mike Stump]

On Feb 1, 2008, at 11:51 PM, Seung Jae Lee wrote:
> As Prof.Adve mentioned, I need to explain exactly what my problem  
> is, but I have no good ability that I can explain it in this plain  
> text space.

Let me rephrase your question for you.  You can then see the right  
question, and the answer for it.

The question is, why is, why can't I change:

   bb8:
     sum_1 = i_0_pn + sum_0_pn;
     br bool %exitcond, label %bb10, label %bb3

into

   bb8:
     br bool %exitcond, label %bb10, label %bb3
     sum_1 = i_0_pn + sum_0_pn;

?

The answer is, because that is an invalid transform.

   A:
     B;
     C;

has to be transformed into:

     B;
   A:
     C;

(where the motion of B is copy it to the other side of all control  
flows into A)

When you do this, you'll notice you get:

$ cat t.c
int foo() {
   unsigned indvar_next27, indvar_next;
   int sum_1, sum_0_pn, i_0_pn;
   //entry:
   unsigned indvar26 = 0;
   int sum_0_pn_ph = 0;
   //brlabel %bb8_outer
   //bb8_outer:
   for (indvar_next27=0; indvar_next27 != 10; ){
     int i_0_0_ph = (int) indvar26;
     unsigned indvar= 0;
     int sum_0_pn = sum_0_pn_ph;
     int i_0_pn = i_0_0_ph;
     //brlabel %bb8
     //bb8:
     sum_1 = i_0_pn + sum_0_pn;                           /* LOOK HERE  
*/
     for (;indvar!=3;){
       //%exitcond= setequint%indvar, 3
       //brbool %exitcond, label %bb10, label %bb3
       //bb3:
       indvar_next= indvar+ 1;
       indvar= indvar_next;
       sum_0_pn = sum_1;
       i_0_pn = 2;
       sum_1 = i_0_pn + sum_0_pn;                         /* LOOK HERE  
*/
       //brlabel %bb8
     }
     //bb10:
     indvar_next27 = indvar26 + 1;
     //%exitcond28 = setequint%indvar_next27, 10
     indvar26 = indvar_next27;
     sum_0_pn_ph = sum_1;
     //brbool %exitcond28, label %bb16, label %bb8_outer
   }
   //bb16:
   return sum_1;
}

int main() {
   printf("%d\n", foo());
}
$ gcc t.c
t.c: In function ‘main’:
t.c:40: warning: incompatible implicit declaration of built-in  
function ‘printf’
$ ./a.out
105

The cost of the .pdf file outweighed the benefit for me.  I can see  
the pretty graphs in the straight text code.  If you want to help me  
see them further, just indent.

The short answer is you can't guess at valid transforms.  You have to  
know they are valid, or prove the are valid.

The only way to get:

for (;C;) {
   S
}

is to transform:

top:
if (!C) goto end;
   S
goto top;
end:

into it.  If you have any other form, it is wrong to transform into  
it.  You _must_transform into the form just above first, and then that  
form goes into the for statement.

At the end of the day, you have a set of valid transforms, each one of  
which you can talk about and audit separately.  If you have any bugs,  
they are never in the valid transforms, and the invalid ones stand out  
to people skilled in the art.

So, if you had written down the transform you were using, we could  
have identified it.  You didn't, so, we could not.

I didn't check your other loop for correctness, or any of the other  
implied transforms that you used for correctness. If you want to  
ensure it is correct, you can run large amount of code through it and  
check the results (I'd call that the industrial approach) and hope it  
is approximately right, or, you have to reason about each and every  
transform you're using and hopefully even prove each one.  The latter  
approach I'd call the academic approach.  :-)

You're splitting and moving phi nodes seems reasonable.

The transform of:

   top:
     S;
     goto top;

into

   for (;;) {
     S;
   }

is valid.  What isn't valid is putting the induction variable into the  
condition slot and calling it done.  You must first transform it into  
the form given above.  To do that, you have to use other transforms,  
each one of which you should write down and list and prove is valid.

If you want us to audit each transform for you, write them all down,  
one by one.