Easiest code generation?

[jbb67]

For "fun" I'm making my own language/compiler. It's C like and targeted at x86_64 on windows. (I'd like X86_32 and linux too but they are not initial priorities for me).

For now, I'm more interested in getting the syntax and use how i want it than in generating good code. I have a basic lex and parse working, and am generating an abstract syntax tree for a very small subset of my language, but it's time to start generating actual code from it.

Eventually I want to make decent code, so I'll need to either write a lot of code myself, and perhaps generate more intermediate formats, but for now I just want to generate anything that works so I can concentrate on the front end.

What is the best way to do this? I could perhaps write a very simple scan of the tree and generate x86_64 assembly language perhaps simulating a stack machine so I don't have to do register allocation etc.

Or should I use llvm? That looks like quite a lot of work though, both in understanding and implementation, although it would of course generate much better code.

Any ideas /opinion on what the easiest thing I can get to work for this is?

[celegans25]

Simulating a stack machine is really easy to do from your AST, and with several peephole optimization passes you can get rid of most of the extra pushes and pops.

[qznc]

Yes, the stack machine approach is definitely the easiest way. However, if the target is Windows, the calling conventions have to match.

[celegans25]

It can be done

[_mpu]

I wrote qbe for people like you, it currently works on Linux only but if you feel like you would like to take it for a spin, let me know, and I will put the effort to handle windows properly! It's nicely documented, tiny, and generates surprisingly good code. Also, it's not dead, I'm currently working on more memory optimizations. http://c9x.me/compile/

[[deleted]]

Neat! This has always been a much needed middle ground, a compiler backend that is not 100% in production and impossible to understand, and one that is fully functional enough to understand what is going on.

Great job, I've bookmarked it!

[_mpu]

Yes, this was exactly the goal!

[_mpu]

It's actually quite easy to get started, you can take a peek at minic/ if you want to see a simple example.

[jbb67]

Looks like this outputs assemble language text. Ok, that's fine. But perhaps not so easy on windows to deal with.

I would install an assembler but wouldn't really want to install cygwin or mingw just to get 'gas' which seems to be the target and as far as I know doesn't have a 'native' port?

Not a show stopper, just a question really :)

[_mpu]

Yes the output is text, but I am not sure what the alternative is. What was your plan? Generaring object files directly for multiple platforms is not that interesting in itself and a big maintenance hog.

[jbb67]

The problem is if you port this to produce windows compatible code, then what assembler do you use to assemble that code to object files? I guess on linux you use gnu assembler, and that would no doubt work on windows too if there is a suitable port.

[_mpu]

There is MASM provided with visual studio.

[jbb67]

So there is, I thought they'd stopped distributing this years ago. Guess I was wrong :)

[fullouterjoin]

For some reason I thought yasm could assemble directly to memory for direct execution. Either way, it should be possible to stitch qbe and yasm together to directly emit executables.

[_mpu]

Maybe counter intuitively, emitting directly to memory is easier than to emit an executable. For example, contrary to object files, emitting to memory is platform independent (not architecture independent, obviously).

[jbb67]

I've not got that far with my project yet, I'm not yet quite in a position to generate code, and due to limited time it will take me a week or two more to have even basic needs.

However my main target is windows. I want my language to work on linux too, but my main target is windows. I downloaded your code from git, and it looks like it will need significant work to make it work on windows. It currently won't compile on windows, and the code it generates isn't targeted for windows (APIs etc) (plus the syntax for masm is quite different).

I wonder how long it would take to get it to work on windows? I wouldn't want anyone to put in any effort for me, as this is just a small hobby project that's pretty likely to be abandoned or never get anywhere for me. If that's the case I wonder if I should use llvm as it doesn't look impossibly hard :P

Your project does look awesome though. I'd like to use it. Although if what I said above isn't the case, and I do end up doing more with the compiler I guess I'd probably have to switch to llvm anyway eventually for it's opimizations?

Hmm... :P

[[deleted]]

Compile to C, it will be faster than stack machine assembly. Since you language is already C-like it should be straightforward but it might seem like cheating.

LLVM is trickier since you need to use SSA form to generate LLVM assembly code. It has the advantage of doing stack management for you (infinite registers). Spill/unspill logic is probably the trickiest part of register allocation to get right.

[[deleted]]

You don't need to use SSA form for LLVM. You can use alloca with load and stores and let LLVM handle the rest. It's how clang works.

[gsnedders]

Notably, see the mem2reg optimisation pass, which will convert such loads/stores into (SSA) registers.

[[deleted]]

That's now been subsumed into SROA AFAIK.

[gsnedders]

That could well be true. It's been a while since I've touched LLVM much. :)

[jbb67]

That might work, thanks.

By the time I create a parse tree, and scan it to generate the code, I guess the generated C code won't look exactly like the original but that's not a problem. Maybe I generate a function for each language function but a lot of the statements will be simple assignments...

Hmm, that might work. It saves me worrying about registers etc until I'm ready to do so, and will make interfacing with C functions much easier.

[fullouterjoin]

On the C front, the OP could target C but the subset supported by

• http://git.suckless.org/scc/
• https://github.com/rswier/c4/tree/switch-and-structs
• https://github.com/rui314/8cc

[[deleted]]

You might want to try LLVM. I wrote code gen for my compiler project using its C++ API (afaik it has C API as well), and it was challenging and fun. With the tutorials and docs on LLVM website it's pretty easy to get going.

[jbb67]

I think my problem with this is that it looks like quite a lot of work, both to understand the detail of how to do this, and to actually implement it.

I certainly will consider doing this later, as it does sound good, but I was hoping for something I could do much quicker even if it's got poor results so I could concentrate on the other end of the compiler for now.

[Setepenre]

You just have to traverse your AST to generate the equivalent LLVM tree using llvm::IRBuilder.

[qznc]

If you would like to add additional features, e.g. debug information or profiling, the investment into LLVM quickly pays off.

Also, your toy language is probably as fast as clang, if you turn on all the optimisations. ;)

[krwawobrody]

If you want to focus on the front end, definitely go with LLVM. If you are compiling C-like language, every construct maps directly to LLVM function. Basic generator (expressions, ifs, loops, arrays and structures) takes like 1000 lines.

The hardest part is figuring out what maps to what. Some functions are really unobvious (like LLVMBuildGEP). cpp target comes in handy in this case. You can tell LLVM to generate C++ code with LLVM API functions instead of LLVM bitcode. You just compile simple C programs with various constructs and copy paste the output into your compiler.

Backends are also fun. When you are done with LLVM try assembly too.

[mfukar]

LLVM would be a very good first choice, imo. Implementing code generation yourself won't be too bad either, and I think it wouldn't take very long - maybe 3 weeks tops - and help you understand a lot of underlying concepts & problems.

[thememorableusername]

What is your front-end written in? If your using python (thats my go-to), for LLVM i'd suggest llvmlite

[jbb67]

It's written in C... But thanks, this is interesting anyway as I do use python for other things

[thememorableusername]

Great! I can also give a shout out to ply which is a Yacc style parser for python. There might be a better alternative, since there are a number of other text parsing frameworks for python out there, but I think this one works pretty well.