llvm dev - Feb 2009 - [LLVMdev] Creating an LLVM backend for a very small stack machine

Hi folks,

I am interesting in creating an LLVM backend for a very small stack machine. 

Before I start in on the actual implementation, I'd like to make sure that 
I'm on the right track. Any comments, suggestions, warnings, tips, etc 
would be greatly appreciated.

Background
----------

There are a number of small as other embedded microprocessors that are often 
used in FPGAs such as Xilinx's Picoblaze, Lattice's Mico8, or Bernd 
Paysan's b16-small.

I am developping a very small stack machine primarily for use inside FPGAs 
and ASICs. This serves roughly the same niche as the above processors, 
however from my perpsective, my design has a number of advantages. For 
example, mine has a much smaller minimal configuration, has higher code 
density, is much more parameterizable, fully supports indirect branches, is 
FPGA-architecture independent, etc.

The main goal, however, is to not just have a shiny new architecture, but to 
have an entire optimized supporting toolchain. I am hoping to build on LLVM 
as infrastructure. I don't think I need to sell you all on the reasons why 
this would be handy.

I am already pretty "familiar" with LLVM, in that I have successfully
made
my own front-end DSL for another project by basically following the 
Kalidescope tutorial. I have a good grasp of the LLVM assembly language, 
and have a lot of notes (just a sanity-check paper excercize) about how I 
would lower just about every instruction into my architecture if I were 
doing it by hand. I've read through all the LLVM documentation available 
online, and (superficially) looked at a lot of the other backend targets. I 
have written custom assemblers and peephole optimizers outside of LLVM in 
the past. I am familiar academically with stack-machine specific "register 
allocation" optimizations. I'm basically ready to get started on an
LLVM
backend for my processor.

My main concerns are that in my searching online, I've gleaned a number of 
things that urge me to caution. I don't know how much of this is
"true",
but it's my impression after spending a lot of time googling:

  * A Picoblaze backend was apparently attempted both for LLVM and GCC, but 
apparently didn't go anywhere on either due to missing support for register 
indirect jumps, and possibly for other reasons. Of course my processor does 
support this, but ... 

  * There were a number of threads in various GCC lists and other places 
implying that, at least for GCC, targeting a stack machine would be very 
very difficult because of it's backend assumptions. Of course LLVM is not 
GCC, but TableGen seems register-biased ...

  * There seems to be a (to me) strange negative vibe whenever someone 
brings up targeting a compiler to a very small microprocessor, usually 
including an argument that it's not worth it. Of course, I'm the one
doing
the work, and I already have decided it's worth it ...

Anyway, hopefully that gives you an idea of where I'm coming from. Before I 
get too knee-deep into writing a backend, I have a few questions that I 
hope someone can help me with.

Questions
---------

  * Has anyone else out there targeted (or tried to target) a stack machine 
before? Was it successfull? What problems did you have? 

  * What parts of the LLVM backend code generator infrastructure would be 
usable for targeting a stack machine? e.g. Is it even possible to use 
TableGen to target a stack machine?

  * When/where/how do things like big integer (iXXXXX), phi nodes, llvm.* 
instrincs get lowered; e.g. does my target have to do that, or is it done 
generically?

Ultimtely, I'm wondering if targeting a stack machine with the current LLVM 
infrastructure is going to be somewhat straightforward even if it's not 
totally optimal (desirable), or if it's going to be so problematic that
I'd
be better off implementing an entire new code-generator myself 
(undesirable).

Any other comments or discussion is welcome.

All of my work (hardware design and all software) will be publicly and 
freely available.

-- 
Wesley J. Landaker <wjl at icecavern.net> <xmpp:wjl at
icecavern.net>
OpenPGP FP: 4135 2A3B 4726 ACC5 9094  0097 F0A9 8A4C 4CD6 E3D2
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090222/4db71cb1/attachment.sig>

On Sun, Feb 22, 2009 at 3:25 PM, Wesley J. Landaker <wjl at icecavern.net>
wrote:
>  * Has anyone else out there targeted (or tried to target) a stack machine
> before? Was it successfull? What problems did you have?
Haven't done that, and I don't think there are any existing backends
like this.  It should be feasible, though; the backend code is pretty
flexible.
>  * What parts of the LLVM backend code generator infrastructure would be
> usable for targeting a stack machine? e.g. Is it even possible to use
> TableGen to target a stack machine?
You should be able to use existing LLVM backend code and TableGen at
least through instruction selection; I'm not sure whether you'll want
register allocation or not, but it should be easy to choose either
way.  The whole thing is quite flexible; see
LLVMTargetMachine::addCommonCodeGenPasses in
lib/CodeGen/LLVMTargetMachine.cpp for a high-level overview of how
CodeGen works.  It might also be useful to look at LLVM handles x87
floating-point; the relevant code is in
lib/Target/X86/X86FloatingPoint.cpp.
>  * When/where/how do things like big integer (iXXXXX), phi nodes, llvm.*
> instrincs get lowered; e.g. does my target have to do that, or is it done
> generically?
Aribitrary-width integers, vectors, llvm.*, etc. are lowered
generically by the Legalize infrastructure; the backend just has to
say what it can and can't support.  See
lib/Target/X86/X86ISelLowering.cpp for an example.  I don't know the
details of PHI nodes, but that's also taken care of by instruction
selection.

-Eli

On Sunday 22 February 2009 17:06:06 Eli Friedman wrote:
> On Sun, Feb 22, 2009 at 3:25 PM, Wesley J. Landaker <wjl at
icecavern.net>
wrote:
> >  * Has anyone else out there targeted (or tried to target) a stack
> > machine before? Was it successfull? What problems did you have?
>
> Haven't done that, and I don't think there are any existing
backends
> like this.  It should be feasible, though; the backend code is pretty
> flexible.
At the very least, there isn't anything in the LLVM instruction set that I 
think I would have any trouble lowering to the architecture ... but so far 
that's just on paper. ;)

I would love to see a Kalescope-like tutorial that goes step-by-step through 
making a backend. At the very least, I'll be documenting my adventure, so 
maybe once I know what I'm doing I can turn it into a tutorial.
> You should be able to use existing LLVM backend code and TableGen at
> least through instruction selection; I'm not sure whether you'll
want
> register allocation or not, but it should be easy to choose either
> way.  The whole thing is quite flexible; see
> LLVMTargetMachine::addCommonCodeGenPasses in
> lib/CodeGen/LLVMTargetMachine.cpp for a high-level overview of how
> CodeGen works.  It might also be useful to look at LLVM handles x87
> floating-point; the relevant code is in
> lib/Target/X86/X86FloatingPoint.cpp.
Thank you for the references, I'll have a look at those.

I've read quite a few papers on stack-machine-specific "register
allocation"
algorithms, but at least for the first pass, I want to make this as 
straightforward as possible. 

One thing I was considering was pretending I had multiple registers, and 
then when they actually get emitted I would thunk in code to do stack 
manipulations, hoping that my architecture specific peephole optimizer 
would be able to clean it up (or not, for the first cut).
> Aribitrary-width integers, vectors, llvm.*, etc. are lowered
> generically by the Legalize infrastructure; the backend just has to
> say what it can and can't support.  See
> lib/Target/X86/X86ISelLowering.cpp for an example.  I don't know the
> details of PHI nodes, but that's also taken care of by instruction
> selection.
Okay, I obviously need to learn more about the infrastructure here, but this 
at least sounds promising. I was worried that if I didn't have a register 
architecture that I'd have to reinvent the wheel in more places than it 
soudns like I will have to.

I'm sure I will be back with more questions once I seriously try starting a 
target.

-- 
Wesley J. Landaker <wjl at icecavern.net> <xmpp:wjl at
icecavern.net>
OpenPGP FP: 4135 2A3B 4726 ACC5 9094  0097 F0A9 8A4C 4CD6 E3D2
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090222/051ef2c6/attachment.sig>

Hi Wesley,

I've done quite a lot of work on register allocation for stack machines.
You might want to look at my papers:
http://www.dcs.gla.ac.uk/~marks/euroforth.pdf
http://www.dcs.gla.ac.uk/~marks/thesis.pdf

Good luck,
Mark.


-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu on behalf of Wesley J. Landaker
Sent: Sun 22/02/2009 23:25
To: llvmdev at cs.uiuc.edu
Subject: [LLVMdev] Creating an LLVM backend for a very small stack
machine[MESSAGE NOT SCANNED]
 
Hi folks,

I am interesting in creating an LLVM backend for a very small stack machine. 

Before I start in on the actual implementation, I'd like to make sure that 
I'm on the right track. Any comments, suggestions, warnings, tips, etc 
would be greatly appreciated.

Background
----------

There are a number of small as other embedded microprocessors that are often 
used in FPGAs such as Xilinx's Picoblaze, Lattice's Mico8, or Bernd 
Paysan's b16-small.

I am developping a very small stack machine primarily for use inside FPGAs 
and ASICs. This serves roughly the same niche as the above processors, 
however from my perpsective, my design has a number of advantages. For 
example, mine has a much smaller minimal configuration, has higher code 
density, is much more parameterizable, fully supports indirect branches, is 
FPGA-architecture independent, etc.

The main goal, however, is to not just have a shiny new architecture, but to 
have an entire optimized supporting toolchain. I am hoping to build on LLVM 
as infrastructure. I don't think I need to sell you all on the reasons why 
this would be handy.

I am already pretty "familiar" with LLVM, in that I have successfully
made
my own front-end DSL for another project by basically following the 
Kalidescope tutorial. I have a good grasp of the LLVM assembly language, 
and have a lot of notes (just a sanity-check paper excercize) about how I 
would lower just about every instruction into my architecture if I were 
doing it by hand. I've read through all the LLVM documentation available 
online, and (superficially) looked at a lot of the other backend targets. I 
have written custom assemblers and peephole optimizers outside of LLVM in 
the past. I am familiar academically with stack-machine specific "register 
allocation" optimizations. I'm basically ready to get started on an
LLVM
backend for my processor.

My main concerns are that in my searching online, I've gleaned a number of 
things that urge me to caution. I don't know how much of this is
"true",
but it's my impression after spending a lot of time googling:

  * A Picoblaze backend was apparently attempted both for LLVM and GCC, but 
apparently didn't go anywhere on either due to missing support for register 
indirect jumps, and possibly for other reasons. Of course my processor does 
support this, but ... 

  * There were a number of threads in various GCC lists and other places 
implying that, at least for GCC, targeting a stack machine would be very 
very difficult because of it's backend assumptions. Of course LLVM is not 
GCC, but TableGen seems register-biased ...

  * There seems to be a (to me) strange negative vibe whenever someone 
brings up targeting a compiler to a very small microprocessor, usually 
including an argument that it's not worth it. Of course, I'm the one
doing
the work, and I already have decided it's worth it ...

Anyway, hopefully that gives you an idea of where I'm coming from. Before I 
get too knee-deep into writing a backend, I have a few questions that I 
hope someone can help me with.

Questions
---------

  * Has anyone else out there targeted (or tried to target) a stack machine 
before? Was it successfull? What problems did you have? 

  * What parts of the LLVM backend code generator infrastructure would be 
usable for targeting a stack machine? e.g. Is it even possible to use 
TableGen to target a stack machine?

  * When/where/how do things like big integer (iXXXXX), phi nodes, llvm.* 
instrincs get lowered; e.g. does my target have to do that, or is it done 
generically?

Ultimtely, I'm wondering if targeting a stack machine with the current LLVM 
infrastructure is going to be somewhat straightforward even if it's not 
totally optimal (desirable), or if it's going to be so problematic that
I'd
be better off implementing an entire new code-generator myself 
(undesirable).

Any other comments or discussion is welcome.

All of my work (hardware design and all software) will be publicly and 
freely available.

-- 
Wesley J. Landaker <wjl at icecavern.net> <xmpp:wjl at
icecavern.net>
OpenPGP FP: 4135 2A3B 4726 ACC5 9094  0097 F0A9 8A4C 4CD6 E3D2

-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 5354 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090223/81f5f759/attachment.bin>

On Monday 23 February 2009 03:23:59 Mark Shannon wrote:
> I've done quite a lot of work on register allocation for stack
machines.
> You might want to look at my papers:
> http://www.dcs.gla.ac.uk/~marks/euroforth.pdf
> http://www.dcs.gla.ac.uk/~marks/thesis.pdf
Hi Mark,

I've read your papers, and in fact they were part of the data that convinced
me that I really could go with a stack machine for the work I'm doing.
I'm
planning on implementing register allocation based partially on your paper.

Actually, I was wondering if any of your lcc implementation work was 
publicly available. 

-- 
Wesley J. Landaker <wjl at icecavern.net> <xmpp:wjl at
icecavern.net>
OpenPGP FP: 4135 2A3B 4726 ACC5 9094  0097 F0A9 8A4C 4CD6 E3D2
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090223/5428d77f/attachment.sig>