llvm dev - Feb 2007 - [LLVMdev] Software Pipelineing

hello,

we're considering LLVM as an excellent framework for a compiler backend
for a novel dsp architecture based on vliw principles that is still  
under
development. in this context, two students at our institute are  
particularly
interested in the following projects:

I) software pipelining
    apparently [1], there has been already an remarkable amount of  
work done
    by tanya lattner for the sparc backend. however, it appears it  
did not (yet)
    make its way into llvm. are there ongoing efforts in this  
direction? most of
    the work seems to be done in an architecture dependent, very low- 
level IR. are
    there any efforts to generalize architecture independent portions  
of the code.
    any comments on this are very appreciated.

II) Embedded C Extensions [2,3]
    there's a ongoing project in gcc [4] that aims to implement  
embedded c extensions
    for gcc. it appears that the portions belonging to the frontend  
are already pretty
    stable. are there already people working on getting those bits  
into llvm?
    i see two basic approaches:
    a) implement fractional and saturated operations using  
(conditional) integer arithmetic.
       this does not require to change anything within llvm but might  
make it hard to detect
       those patterns for the instruction selector in order to  
generate efficient code
       for architectures with hardware support for those features.
    b) introduce new types for llvm that handle types such as  
__Fract, __Accum and _Sat.
    again, comments are highly appreciated.


cheers,

-
dietmar

[1] http://llvm.org/pubs/2005-06-17-LattnerMSThesis.html
[2] http://www.embedded-c.org/
[3] http://www.open-std.org/jtc1/sc22/wg14/
[4] http://gcc.gnu.org/wiki/FixedPointArithmetic

---------------------------------------------------------------------
Dietmar Ebner
CD Laboratory - Compilation Techniques for Embedded Processors
Institut fuer Computersprachen  E: ebner at complang.tuwien.ac.at
Technische Universitaet Wien    T: (+431) 58801-18598
Argentinierstrasse 8 / E1851    F: (+431) 58801-58521
1040 Wien, Austria              W: www.complang.tuwien.ac.at/cd/ebner

Dietmar Ebner wrote:
>  most of the work seems to be done in an architecture dependent, very low-
> level IR. are there any efforts to generalize architecture independent
portions
> of the code.
>     any comments on this are very appreciated.
We are in a similar situation, with an architecture in our
hands that needs software pipelining support. Since SW pipelining
is by its very nature quite architecture dependent, I don't know
how much could be generalized, but we would certainly be interested
in working on it.
-- 
Pertti

> I) software pipelining
>    apparently [1], there has been already an remarkable amount of
> work done
>    by tanya lattner for the sparc backend. however, it appears it
> did not (yet)
>    make its way into llvm. are there ongoing efforts in this
> direction? most of
Unfortunately the work was done on the previous sparc backend that did not 
use the target independent framework. It would need to be almost totally 
rewritten to be used with the new backends. The good news is that it might 
even be easier to implement now then when I did my work :)

-Tanya

On Tue, 13 Feb 2007, Dietmar Ebner wrote:
> II) Embedded C Extensions [2,3]
>    there's a ongoing project in gcc [4] that aims to implement
> embedded c extensions
>    for gcc. it appears that the portions belonging to the frontend
> are already pretty
>    stable. are there already people working on getting those bits
> into llvm?
Nope, I'm not aware of anyone doing this work.  Doing so requires at least 
three pieces of work:

1. Merging in the relevant front-end changes into llvm-gcc.
2. Creating LLVM IR operations to represent the new features.
3. Teaching the backend to 'legalize' these away for targets that
don't
    support them (i.e. to libcalls or other simple arithmetic ops).

These don't all have to be done in one step of course.  If you're 
interested in this, I'd suggest starting with #2.
>    i see two basic approaches:
>    a) implement fractional and saturated operations using
> (conditional) integer arithmetic.
>       this does not require to change anything within llvm but might
> make it hard to detect
>       those patterns for the instruction selector in order to
> generate efficient code
>       for architectures with hardware support for those features.
Ah, this would be even easier.  If you took this path, you would only need 
#1 above.  The problem is that it would be hard to reconstruct the 
operations at isel time, and the mid-level optimizers couldn't hack on 
these operations as easily.
>    b) introduce new types for llvm that handle types such as
> __Fract, __Accum and _Sat.
>    again, comments are highly appreciated.
My understanding of these operations is that they are basically integer 
data types whose operators have special semantics.  As such, I'd suggest 
treating these as just new binary operators (e.g. add_fract_sat) which 
take normal integer datatypes (e.g. i32).  LLVM 2.0 is designed to encode 
information about arithmetic ops into the operations instead of the types 
where possible: e.g. we have ashr and lshr instead of signed vs unsigned 
types.

Would this work?

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

Pertti,

On Feb 13, 2007, at 7:34 PM, Pertti Kellomäki wrote:
> Dietmar Ebner wrote:
>>  most of the work seems to be done in an architecture dependent,  
>> very low-
>> level IR. are there any efforts to generalize architecture  
>> independent portions
>> of the code.
>>     any comments on this are very appreciated.
>
> We are in a similar situation, with an architecture in our
> hands that needs software pipelining support. Since SW pipelining
> is by its very nature quite architecture dependent, I don't know
> how much could be generalized, but we would certainly be interested
> in working on it.
that's good news. in the past, we made good experiences with compiler
components generated from a high-level architecture description, i.e.,
we already generated descriptions for a graph coloring register  
allocator,
a scheduler with operation table support, and a grammar for a tree  
pattern
matcher - though not yet for llvm but for a hand-crafted backend.

so far, it appears to be reasonable to derive the architecture
dependent portions from a target resource model specification, e.g.,  
using
TableGen. however, we're at the very beginning of this project and  
i'm not
yet aware of all the details. we'll definitely come back to you once we
have more insight.


cheers

-
dietmar

Tanya,

On Feb 13, 2007, at 9:42 PM, Tanya M. Lattner wrote:
> Unfortunately the work was done on the previous sparc backend that  
> did not
> use the target independent framework. It would need to be almost  
> totally
> rewritten to be used with the new backends. The good news is that  
> it might
> even be easier to implement now then when I did my work :)
that's certainly true. there is a version of SMS in the 1.6 release.  
is this
a good starting point to look at or is there a more mature version in  
the cvs?
apart from your thesis and the online docs, is there further  
documentation that
might be helpful?

cheers,

-
dietmar

Dear Chris,

On Feb 14, 2007, at 12:33 AM, Chris Lattner wrote:
>>    b) introduce new types for llvm that handle types such as
>> __Fract, __Accum and _Sat.
>>    again, comments are highly appreciated.
>
> My understanding of these operations is that they are basically  
> integer
> data types whose operators have special semantics.  As such, I'd  
> suggest
> treating these as just new binary operators (e.g. add_fract_sat) which
> take normal integer datatypes (e.g. i32).  LLVM 2.0 is designed to  
> encode
> information about arithmetic ops into the operations instead of the  
> types
> where possible: e.g. we have ashr and lshr instead of signed vs  
> unsigned
> types.
>
> Would this work?
probably, though i'm not yet certain. we're considering splitting the  
project in two while one subtask is to catch up with the new gcc  
frontend and the other one is to extend llvm with fixed point  
operations in order to generate efficient code for dsp targets.

in the first step, we either have to backport the changes in the gcc  
frontend or port llvm-gcc to a more recent version (with the 4.2  
release on its way, this might be a good candidate). it appears,  
resources are better spent for latter. are there major concerns  
speaking against this approach? does anybody have a rough estimate of  
the required effort? this task would also include a mapping of fixed  
point operations to the existing integer infrastructure.

i doubt that it is feasible matching those complex patterns at  
instruction selection time - considering that optimization passes are  
free to transform the generated code sequences. therefore, i think  
it's best to extend the virtual machine accordingly and add  
corresponding patterns to the backend. i don't know yet how those  
extensions should look like. once we reach this point, we'll try to  
come up with a feasible proposal and ask for comments.

thanks a lot for your comments! greetings,

-
dietmar