Software Pipelineing | Embedded C Extensions

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 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.

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 :slight_smile:

-Tanya

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

Pertti,

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

Tanya,

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 :slight_smile:

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,

Dear Chris,

   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,

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?

I finished my thesis in June 2005 and the LLVM 1.6 release came out in November 2005. So I think the version 1.6 should have my final version.

apart from your thesis and the online docs, is there further
documentation that
might be helpful?

My thesis will have referrences to many papers that you may want to look at. There are no other docs about my work than my thesis and the comments in the code.

Good luck!

-Tanya

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.

ok

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?

llvm-gcc is mostly affected by changes in the GCC trees. From my initial investigation, it looks like there are a few minor changes (e.g. CONSTRUCTOR nodes are a bit different) but nothing major. It may be possible to get a prototype 4.2-merged compiler up in a few weeks.

My group has plans to eventually merge the apple gcc 4.2 compiler work into llvm-gcc. This would sync the front-end with 4.2 and provide several other features contributed by apple (most of which may not be interesting to people on non-darwin platforms though). Unfortunately, we don't have a definite timespan for this. We'll most likely pick up this project in the next 3-4 months. This may or may not be too late for you.

this task would also include a mapping of fixed
point operations to the existing integer infrastructure.

Right. That would be new work.

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.

Sounds good. Another alternative is to add a bunch of intrinsics to represent the operations you want. This is much easier than extending the IR, and may be a good starting point for you.

-Chris

Pertti,

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.,

Are you referring to OpenIMPACT / Elcor? The pair are designed to be used in that manner. Their description languages can be used to describe low level HW details which TableGen isn't yet capable of. Nevertheless, LLVM is a production quality compiler while those are not.

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.

If you interested in describing a in-order execution architecture where details such as port constraints, exact read / write latencies, you should expect to make some extensions to TableGen. The PPC backend comes closest to that, you should take a look to determine if you need more details than its processor itinerary class data.

If your target require full predication support and / or beyond basic block scheduling. There are some work required there as well.

Evan

hi,

Are you referring to OpenIMPACT / Elcor? The pair are designed to be
used in that manner. Their description languages can be used to
describe low level HW details which TableGen isn't yet capable of.
Nevertheless, LLVM is a production quality compiler while those are not.

no. i was speaking about a handcrafted backend developed at our lab
that basically replaces the rtl backend of gcc. however, it has never
been more than a prototype so far.

If you interested in describing a in-order execution architecture
where details such as port constraints, exact read / write latencies,
you should expect to make some extensions to TableGen. The PPC
backend comes closest to that, you should take a look to determine if
you need more details than its processor itinerary class data.

thanks for the hint - we'll have a look at it.

Tanya Lattner-2 wrote

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?

I finished my thesis in June 2005 and the LLVM 1.6 release came out in
November 2005. So I think the version 1.6 should have my final version.

apart from your thesis and the online docs, is there further
documentation that
might be helpful?

My thesis will have referrences to many papers that you may want to look
at. There are no other docs about my work than my thesis and the comments
in the code.

Good luck!

-Tanya

cheers,

-
dietmar

_______________________________________________
LLVM Developers mailing list

LLVMdev@.uiuc

         http://llvm.cs.uiuc.edu

http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list

LLVMdev@.uiuc

         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi, I was wondering if there's been any progress with this? I am currently
trying to port the 1.7 SMS implementation and I was wondering, whether
there's a different, newer starting point or where else should I start
implementing this?

Thanks a lot,
Fatum