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
