[LLVMdev] constructing 'for' statement from LLVM bitcode

[Seung Jae Lee]

Dear Wojciech Matyjewicz:

Thank you for your advice.
I could follow what you had suggested upto 
  opt -analyze -loops bsloop-opt.bc

Therefore, I could get the prints you had showed me as follows:
--------------------------------------------------------
Printing analysis 'Natural Loop Construction' for function 'bsloop':
Loop Containing:  %bb16, %bb13, %bb8, %bb1
    Loop Containing:  %bb8, %bb1
--------------------------------------------------------

In your reply, you could re-construct the simple 'for' from the info above like this:
--------------------------------------------------------
 FOR %i.0 = 0 TO %n - 1 STEP 1:
   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
   //%indvar.next is no longer needed
--------------------------------------------------------

I'd just like to make it sure whether you did this manually.
(LLVM doesn't support any pass doing this automatically for us. Am I right?)

And there seems to be more issues, Wojciech.
What about PHI nodes?
To construct 'for' as it was, we should handle PHI nodes.
I also wonder how you treated them.

Thank you so much.
SJ Lee

---- Original message ----
>Date: Sat, 15 Sep 2007 15:07:34 +0200
>From: Wojciech Matyjewicz <wmatyjewicz at fastmail.fm>  
>Subject: Re: [LLVMdev] constructing 'for' statement from LLVM bitcode  
>To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
>
>Hi,
>
>Seung Jae Lee wrote:
>> Hello, guys.
>> I am trying to construct higher-level 'for' from the low-level LLVM bitcode(ver 1.9).
>> It's partly successful thanks to David A. Greene's advice suggested to use Control Dependence Graph(CDG). 
>> I could find which BB contributes to form which loop with CDG.
>
>I know my post comes late... Are you still interested in this subject?
>No? Just ignore it;)
>
>I have been recently dealing with a task which is somehow similar to
>yours. I was trying to reconstruct simple 'for' loops and check if it's
>possible to automatically parallelize their execution.
>
>> For example, for this simple function:
>> -----------------------------------------------------------
>> void bsloop(int n, int pM, Params* ps) {
>>    int i, sim;  
>>    for (sim=0; sim < pM; sim++) {
>>       for (i = 0; i < n; i++) {
>>          Params* p = ps + i;
>>          double eps = norm(0,1); 
>>       }
>>    }
>> }
>
>I think it would be possible to reconstruct loops like this. However, it
>might be very difficult (impossible in general?) if they contained
>'break', 'continue' or 'goto' statements.
>
>Have you tried the use LoopInfo pass for your aim? If you compile the
>example to bitcode without optimization and then choose optimizer passes
>manually:
> opt -mem2reg -instcombine -indvars -o bsloop-opt.bc bsloop.bc
>you will get the following code for bsloop() function (llvm and
>llvm-gcc-4.2 from SVN):
>--------------------------------------------------------
>define void @bsloop(i32 %n, i32 %pM, %struct.Params* %ps) {
>entry:
>	br label %bb16
>
>bb1:		; preds = %bb8
>	%tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
>	%indvar.next = add i32 %i.0, 1
>	br label %bb8
>
>bb8:		; preds = %bb16, %bb1
>	%i.0 = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb16 ]		
>	%tmp11 = icmp slt i32 %i.0, %n
>	br i1 %tmp11, label %bb1, label %bb13
>
>bb13:
>	%indvar.next1 = add i32 %sim.0, 1
>	br label %bb16
>
>bb16:
>	%sim.0 = phi i32 [ 0, %entry ], [ %indvar.next1, %bb13 ]
>	%tmp19 = icmp slt i32 %sim.0, %pM
>	br i1 %tmp19, label %bb8, label %return
>
>return:
>	ret void
>}
>--------------------------------------------------------
>
>Then, running LoopInfo pass:
> opt -analyze -loops bsloop-opt.bc
>prints:
>--------------------------------------------------------
>Printing analysis 'Natural Loop Construction' for function 'bsloop':
>Loop Containing:  %bb16, %bb13, %bb8, %bb1
>    Loop Containing:  %bb8, %bb1
>--------------------------------------------------------
>
>Using the LoopInfo interface allows you to gather much useful
>information. In the internal loop basic block bb8 is the header, %i.0 is
>the canonical induction variable (and the only induction variable). Loop
>has a trip count %n which is a loop invariant. Inspecting the header
>shows it doesn't produce any values that are used outside of it, except
>for the loop induction variable. Furthermore, it doesn't produce any
>side effects. Hence, in this simple case a 'for' loop could be
>reconstructed:
> FOR %i.0 = 0 TO %n - 1 STEP 1:
>   %tmp4 = call i32 (...)* @norm( i32 0, i32 1 )
>   //%indvar.next is no longer needed
>
>I know such a heuristic applies to very simple 'for' loops only.
>However, "very simple 'for' loops" are quite popular;)
>
>--Wojtek
>_______________________________________________
>LLVM Developers mailing list
>LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev