llvm dev - Sep 2007 - [LLVMdev] constructing 'for' statement from LLVM bitcode

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

Hi,

Seung Jae Lee wrote:
> 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?)
You're right - there is no pass that automatically reconstructs
'for'
loops. I might have gone too far with the above example, because my
algorithm doesn't represent loops literally this way. It was only a
high-level view of information gathered about the loop.

By writing "simple for loop", I mean a loop which in C would have this
form:
 for (int i = low; i < up; i += step)
   // loop body

If it doesn't contain 'break', 'goto' nor 'continue'
statements it is
generally translated to something like this (only -mem2reg and
-instcombine passes used):
----------------------------------------------------------
bb4:		; preds = %bb, %entry
	%i.0 = phi i32 [ %low, %entry ], [ %tmp3, %bb ]; <i32> [#uses=2]
	%tmp7 = icmp slt i32 %i.0, %up		; <i1> [#uses=1]
	br i1 %tmp7, label %bb, label %bb9

bb:		; preds = %bb4
	; <loop body>
	%tmp3 = add i32 %i.0, %step		; <i32> [#uses=1]
	br label %bb4
----------------------------------------------------------

LoopInfo discovers the natural loop built from these basic blocks (with
%bb4 as a loop header). My algorithm then applies some heuristics to
check if it's a simple for loop. It finds the def. representing the
induction variable (%i.0) and operands representing lower bound (%low),
upper bound (%up), step (%step). Next, it can be proved that
instructions: %tmp7, %tmp3 and both branches are solely responsible for
making the loop iterate. The rest of instructions constitute the loop
body.

As far as I remember you are trying to compile for a virtual machine
with an explicit 'for' instruction... Unfortunatelly, I have no
experience with writing backends for LLVM. I was only trying to show
that simple for loops can be recognized. I believe the gathered
information could be used somehow in the backend.
> What about PHI nodes?
> To construct 'for' as it was, we should handle PHI nodes.
> I also wonder how you treated them.
I only change the loop iteration bounds in the code for the loop so
there is no special treatment of them.

What about 'if' instruction in your target? Is it also explicit? If your
VM doesn't support branching instructions it may be difficult, in my
opinion, to create an LLVM backend for it, as LLVM instruction set
models ordinary processors. Have you considered using higher-level
information for your aim? For example, using an abstract syntax tree,
which represents directly control flow statements of the source
language. You could take a look at clang - a new C frontend for LLVM...

Wojtek