[LLVMdev] constructing 'for' statement from LLVM bitcode

[Wojciech Matyjewicz]

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