[LLVMdev] Question to Chris

[Seung Jae Lee]

Thank you for this comment, Mike.
So... your suggestion is to make a valid transform for each loop like:

>for (;C;) {
>   S
>}
>
>is to transform:
>
>top:
>if (!C) goto end;
>   S
>goto top;
>end:

For now, my code is incomplete so not ready to present for audit yet but I hope it asap.

In fact, I couldn't understand what you said:

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

Forgive my poor English. What did you mean by that?

Thanks,
Seung


---- Original message ----
>Date: Sat, 2 Feb 2008 11:31:46 -0800
>From: Mike Stump <mrs at apple.com>  
>Subject: Re: [LLVMdev] Question to Chris  
>To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
>
>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.
>_______________________________________________
>LLVM Developers mailing list
>LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev