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

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>

On Feb 22, 2009, at 5:43 PM, Wesley J. Landaker wrote:
>
> 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.
Have you seen:
http://llvm.org/docs/WritingAnLLVMBackend.html

If you're targeting a stack machine, I'd strongly recommend not using  
the llvm register allocators and just run you own custom stackifier  
pass instead.

-Chris

On Sunday 22 February 2009 23:18:25 Chris Lattner wrote:
> Have you seen:
> http://llvm.org/docs/WritingAnLLVMBackend.html
I have, and it's certainly helpful. Since the Kalescope tutorial is so 
amazingly easy to work through that it makes me jealous for a similar 
tutorial on the backend. But I'm definitely not complaining. =)
> If you're targeting a stack machine, I'd strongly recommend not
using
> the llvm register allocators and just run you own custom stackifier
> pass instead.
After reading  
<http://www.llvm.org/docs/CodeGenerator.html#regAlloc_ssaDecon> is correct
to say that if I don't use an existing LLVM register allocation pass, that 
I would need to do my stackification directly on the SSA form? 

Could/should I still reuse parts like the PHIElimination pass? It sounded 
sort of like this was very coupled with the register allocators.

I'm was initial sort of thinking that for a first (unoptimized) cut I might 
be able to just use the "simple" built-in allocator that spills every 
value, then replace that afterwards with a stack-based allocator. Does that 
sound practical, or would I be painting myself into a corner in the first 
step?

Anyway, I'm just trying to make sure I'm taking the right approach
before I
run head first into any dead ends. Ultimately, I'd rather do things
"right"
than "fast", since in my experience, "right" takes less time
in the long
run. ;)

-- 
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/2fbc155e/attachment.sig>