not to break 'for' statement into basic blocks

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

not to break 'for' statement into basic blocks

Seung Jae Lee
Dear LLVM guys,

Hi. I first became to be interested in the compiler work, especially LLVM, since last October, still I'm a novice on here. (My major is not CS, either. :-\)
Please forgive my ignorance.

LLVM optimization and other tools are really fantastic.
However I don't want LLVM breaks my 'for' statement in C code into basic blocks during compiling.
I'm sure this sounds really strange but there is a reason for me.

I almost made the backend for a target machine with LLVM.
But a peculiar thing is the assembly uses 'for' statement directly, not branching among basic blocks.
Furthermore, this assembly does not have the notion of 'br'instruction, phi-node and so on. Therefore, I have no choice without making 'for' in the assembly.
(Of course, equilvant 'br' instruction is used for 'if' statement. But it should be nested in 'demux' and 'mux' so I can't use this to represent 'for')

1) First, I tried to re-unite basic blocks which llvm-gcc spits out to make 'for' again.
But this is quite tricky. Generalizing it for the optimzed llvm bytecode is not easy.

2) So.. I wonder if it is possible to modify the llvm-gcc not to break 'for' but not sure about this.
I've heard 'clang' is newly released so I'm also wondering whether this can be modified for my goal.

3) A person recommended me to use GNU lightning, but still not sure about that.

4) A person also recommended me to make this assembly to "purely functional". This assembly, fortunately, supports 'call' instruction. So this can be a good choice for me, but unfortunately I don't have enough time to implementing it on the code after studying.

Could you, any body, tell me any advice, if you have?
My head is steaming.

Thanks,
Seung J. Lee
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: not to break 'for' statement into basic blocks

Anton Korobeynikov
Hello, Seung J. Lee

> LLVM optimization and other tools are really fantastic.
> However I don't want LLVM breaks my 'for' statement in C code into
> basic blocks during compiling.
> I'm sure this sounds really strange but there is a reason for me.
LLVM is 'low-level'. It doesn't contain any special instruction for
loops at all.

> Furthermore, this assembly does not have the notion of
> 'br'instruction, phi-node and so on. Therefore, I have no choice
> without making 'for' in the assembly.
Maybe you can look, how code operates on phi-nodes in C & MSIL backends.

> 1) First, I tried to re-unite basic blocks which llvm-gcc spits out to make 'for' again.
> But this is quite tricky. Generalizing it for the optimzed llvm bytecode is not easy.
I'd say 'is not possible at all'.

In general, loop contain induction variable, which is being assigned
each iteration of loop. As LLVM IR is in SSA mode, there are only two
possibilities to operate on induction variable so:

1. Use phi node
2. Use memory (memory is never in SSA form)

So, if you don't want to deal with phi-node, you have to lower
everything to memory. 'reg2mem' pass is your friend in this case. This
will eliminate all phi nodes, but you have to resolve all branches.

However, I really don't see, how you can transform C code (in general)
to your target, because C *has* explicit goto statement. Maybe you can
split the whole CFG into "cycles" and "paths" and try to "lower" them.
But this can be pretty complicated.

--
With best regards, Anton Korobeynikov.

Faculty of Mathematics & Mechanics, Saint Petersburg State University.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: not to break 'for' statement into basic blocks

Seung Jae Lee
In reply to this post by Seung Jae Lee
According to the instruction manual of this target machine, 'goto' should not be used in C code. :-/

Could you tell me a little more about your advice as to using 'reg2mem', if you're fine?

Thank you so much, Anton.

Best,
Seung J. Lee


---- Original message ----

>Date: Sun, 15 Jul 2007 02:23:27 +0400
>From: Anton Korobeynikov <[hidden email]>  
>Subject: Re: [LLVMdev] not to break 'for' statement into basic blocks  
>To: LLVM Developers Mailing List <[hidden email]>
>
>Hello, Seung J. Lee
>
>> LLVM optimization and other tools are really fantastic.
>> However I don't want LLVM breaks my 'for' statement in C code into
>> basic blocks during compiling.
>> I'm sure this sounds really strange but there is a reason for me.
>LLVM is 'low-level'. It doesn't contain any special instruction for
>loops at all.
>
>> Furthermore, this assembly does not have the notion of
>> 'br'instruction, phi-node and so on. Therefore, I have no choice
>> without making 'for' in the assembly.
>Maybe you can look, how code operates on phi-nodes in C & MSIL backends.
>
>> 1) First, I tried to re-unite basic blocks which llvm-gcc spits out to make 'for' again.
>> But this is quite tricky. Generalizing it for the optimzed llvm bytecode is not easy.
>I'd say 'is not possible at all'.
>
>In general, loop contain induction variable, which is being assigned
>each iteration of loop. As LLVM IR is in SSA mode, there are only two
>possibilities to operate on induction variable so:
>
>1. Use phi node
>2. Use memory (memory is never in SSA form)
>
>So, if you don't want to deal with phi-node, you have to lower
>everything to memory. 'reg2mem' pass is your friend in this case. This
>will eliminate all phi nodes, but you have to resolve all branches.
>
>However, I really don't see, how you can transform C code (in general)
>to your target, because C *has* explicit goto statement. Maybe you can
>split the whole CFG into "cycles" and "paths" and try to "lower" them.
>But this can be pretty complicated.
>
>--
>With best regards, Anton Korobeynikov.
>
>Faculty of Mathematics & Mechanics, Saint Petersburg State University.
>
>
>_______________________________________________
>LLVM Developers mailing list
>[hidden email]         http://llvm.cs.uiuc.edu
>http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: not to break 'for' statement into basic blocks

greened
In reply to this post by Anton Korobeynikov
On Saturday 14 July 2007 17:23, Anton Korobeynikov wrote:

> > 1) First, I tried to re-unite basic blocks which llvm-gcc spits out to
> > make 'for' again. But this is quite tricky. Generalizing it for the
> > optimzed llvm bytecode is not easy.
>
> I'd say 'is not possible at all'.

No, it certainly is possible.  One does this, for example, when constructing
a control dependence graph.  It can't be represented in llvm, so one needs
a higher-level abstraction.  A control dependence graph is one such
abstraction.

Even llvm has a notion of "loops" that it extracts from the control flow
graph.  Now, these are very low-level abstractions and probably won't work
for the purposes of this ISA.

And when you get difficult control behavior...

> However, I really don't see, how you can transform C code (in general)
> to your target, because C *has* explicit goto statement. Maybe you can
> split the whole CFG into "cycles" and "paths" and try to "lower" them.
> But this can be pretty complicated.

Again, gotos can be eliminated with some program analysis and transformation.
See, for example, http://citeseer.ist.psu.edu/22521.html.

                                           -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: not to break 'for' statement into basic blocks

Seung Jae Lee
In reply to this post by Seung Jae Lee
Thank you so much but could you tell me a little bit more in detail about that you suggested?
Sorry, I'm just a greenhorn.

Thanks,
Seung J. Lee

---- Original message ----

>Date: Sat, 14 Jul 2007 21:26:14 -0500
>From: "David A. Greene" <[hidden email]>  
>Subject: Re: [LLVMdev] not to break 'for' statement into basic blocks  
>To: [hidden email]
>
>On Saturday 14 July 2007 17:23, Anton Korobeynikov wrote:
>
>> > 1) First, I tried to re-unite basic blocks which llvm-gcc spits out to
>> > make 'for' again. But this is quite tricky. Generalizing it for the
>> > optimzed llvm bytecode is not easy.
>>
>> I'd say 'is not possible at all'.
>
>No, it certainly is possible.  One does this, for example, when constructing
>a control dependence graph.  It can't be represented in llvm, so one needs
>a higher-level abstraction.  A control dependence graph is one such
>abstraction.
>
>Even llvm has a notion of "loops" that it extracts from the control flow
>graph.  Now, these are very low-level abstractions and probably won't work
>for the purposes of this ISA.
>
>And when you get difficult control behavior...
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: not to break 'for' statement into basic blocks

dag-7
On Monday 16 July 2007 03:20, Seung Jae Lee wrote:
> Thank you so much but could you tell me a little bit more in detail about
> that you suggested? Sorry, I'm just a greenhorn.

There's far too much to cover on an e-mail list.  Use Google, Citeseer, the
ACM digital library, etc. and search for "control dependence graph."  I
provided the reference for an algorithm to remove unstructured gotos.

Everyone starts out as a greenhorn.  Compilers are complicated beasts,
as evidenced by the number of Ph.D.s still centered on "solved" problems
like register allocation.  :)

It takes a lot of reading and doing to become fluent.  I'm very happy to try
and answer specific questions.  Here are some specific references:

Compilers: Principles, Techniques and Tools (a.k.a. The Purple Dragon
Book) by Aho, Lam, Sethi and Ullman.  This is a good, if at times dense,
introductory text.

Advanced Compiler Design & Implementation by Muchnick.  A somewhat more
advanced treatment, better as a reference than a learning book.

I strongly suggest that if you're at a University, that you investigate the
compiler course offerings.  You'll only get so far just reading.  Doing is
really important.

                                              -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev