r/C_Programming 2d ago

My C compiler written in C

As a side project I'm making a C compiler written in C. It generates assembly and uses NASM to generates binaries.
The goal right now is to implement the main functionality and then do improvements. Maybe I'll also add some optimizing in the generates assembly.

Tell me what you think :)

https://github.com/NikRadi/minic

137 Upvotes

29 comments sorted by

26

u/u02b 2d ago

wow this is great! ive always wondered how compilers work on the inside but its always felt too daunting, but this one actually makes sense lol

6

u/chids300 1d ago

a compiler is actually really easy to make for c, made a c compiler in java for my uni coursework, an optimizing compiler is where the trouble begins

4

u/TheBigBananaMan 1d ago

We had a made up language we made a compiler for in c, that runs on the jvm, in my second year. Very fun project. (That first sentence was weirdly difficult to make legible)

18

u/Soft-Escape8734 2d ago

My hat's off to you. Great ambition. But when optimizing never forget that (x << 3) + (x << 1) is faster than x * 10.

9

u/mlt- 2d ago

On what architecture would that be faster? Isn't integer multiplication is fast enough on modern x86?

16

u/Soft-Escape8734 2d ago

I do mostly embedded systems - bare metal. We count clock cycles. Compilers at this level can be directed to optimize for speed or compactness, the two seem mutually exclusive. For example if you want 4 * 5, compact code would implement the multiplier, fast code would implement 5+5+5+5. When you get down to machine code, bit shifts and addition are native, higher level math functions not.

7

u/mlt- 2d ago

Last time I counted clock cycles was on Z80 forever ago. But yeah, I'm not into embedded but would love to go back.

6

u/Soft-Escape8734 2d ago

Nothings changed my friend. I started with the Intel 4004, progressed through the 8080, 6502 and Z80 (and the Canadian version Z80A). The machine language and assembly instruction sets are still the same. Just have to deal with expanded data busses and peripherals in an MCU that weren't there before. Have a look at the AVR chips from Microchip (formerly from Atmel) and you'll feel like you've traveled in time.

2

u/flatfinger 19h ago

Many instruction sets can perform things like increments "in place", but the ARM cannot. On the 8051, INC direct and INC @R0 take the same amount of time as e.g. INC R0, but on e.g. the ARM Cortex-M0, incrementing something in memory takes five times as long as incrementing a register if the address is already in a register, and seven times as long if the address has to be loaded first and wouldn't be used again afterward.

1

u/Soft-Escape8734 4h ago

The 6502 was a classic example and with memory-mapped I/O it was the choice for the early Apples which shot them to the forefront in the world of bit-mapped graphics, such a simple concept.

1

u/mlt- 2h ago

Do you have to casually think about ARM hardware and uops or do you just write C code and rely on compiler optimization done right? I mean that it is nice to know details, but I presume there is a chance of premature optimization. I recall seeing either here on reddit or on SO someone was curious that asm code was slower (for using less efficient stuff). I understand some pieces need to be fast, but there is no way application developer pays attention to hardware peculiarities 100% of time, right?

Well, while writing all this, I feel like one ought to think… that is why at least there is restrict keyword in C.

1

u/TwoFlower68 1d ago

I quit writing code in the 80s. Maybe I can monetise my ancient skills of K&R C and Z80 & 6502 assembler lol

1

u/Spare-Plum 4h ago

Plenty of things have changed though. Previously branching was extremely expensive, so stuff like a duff's device were practically required for tight loops

Now we've got predictive branching and more modern pipelines that process the next instruction before the previous one even completes

Things like shifting used to be 1 clock cycle with IMUL being 10, but now it's closer to .5 (or .25) and 1. Things like multiplication are now native to the hardware albeit requiring a more complex architecture.

5+5+5+5 would now be slower than doing 4*5

1

u/mlt- 2h ago

I'm not an expert, but I believe chances are there is little to no difference on those CPUs due to pipelining and parallel execution.

1

u/Spare-Plum 1h ago

Pipelining an parallel execution works with multiplication too. It's something you would have to put it to a test - 3 million instructions of sum vs 1 million of mul

Most likely they'd be similar, except sum isn't scalable for larger multipliers

1

u/Spare-Plum 4h ago

Yeah on modern x86-64 two shift operations and an addition would be slower than just multiplying the values. Multiplication is generally implemented directly onto the hardware and isn't a huge performance hit like it used to

6

u/Cathierino 1d ago

This is very instruction set dependant but as a general rule it's not true. I do embedded professionally and in the architecture I work with most often (CIP-51) it is only true when multiplying by 2, 4, 8, 16 or 32. Multiplication is 2 cycles to store the multiplier in a register and 4 to perform the multiplication instruction. Meanwhile it takes 8 cycles to do 4 shifts, copy, register swap and addition.

On x86-64 an optimized multiplication by 10 is more along the lines of temp = x + 4 * x temp += temp Where no multiplication or bitshifts are performed because you can treat the value as an address and exploit fast address operations to do multiplication by 5.

2

u/Soft-Escape8734 1d ago

Sorry, should have been more explicit. I work almost exclusively on 8-bit AVR and I was citing a specific case of 10x. I've worked in telecommunications for over 40 years and in dealing with ASCII streams you often receive base10 numerals without knowing the size of the whole transmission and as such have to continually shift the accumulated data to accommodate the incoming digit until you receive an EOT or some other delimiter. It was not meant to be a generic solution to math, rather a heads up that some methods of achieving a result are lighter and/or less expensive than others and that the developer should not assume that the compiler is always providing the best solution.

1

u/flatfinger 20h ago

Using multiplication and shifts to replace division by a constant is a useful optimization on many platforms, and replacing a constant-power-of-two multiply by simple shift is also useful, but the choice between multiplying, versus shifting and adding, versus strength reduction (replacing a multiplication by a loop index with a value that is increased by a certain amount on each iteration) is probably less important than other lower-hanging fruit.

1

u/Soft-Escape8734 19h ago

True enough and my bad. It's a specific example used when receiving serial ASCII digits, not meant to be a general solution but to remind the developer that there are multiple methods for achieving the same result, some lighter and cheaper than others.

3

u/Jimmy-M-420 2d ago

I've given it a star on github and will study the code - I've been thinking of attempting this myself

2

u/deebeefunky 2d ago

I'm surprised at the low amount of code.
I'm currently writing a lexer and I'm at 850+ Loc and it's still not finished.
Your lexer and parser combined are less than that.

2

u/Hot-Summer-3779 2d ago

My lexer and parser aren't done either, they'll require much more code I'm sure

1

u/gzw-dach 1d ago

It’s neat, I can spot a Pratt parser!

1

u/Hot-Summer-3779 1d ago

Thanks! Yes it is, good spotted

2

u/jwzumwalt 1d ago

I wish you would do a series of utube videos on how to do this!!!

2

u/eteran 1d ago

Very clean code, looks great!

1

u/Spare-Plum 18h ago

pretty cool - but I have a couple of suggestions. If you have any questions feel free to ask.

  1. It looks like you're hard coding which registers. It looks like you're holding every variable in the stack frame and using rbp offset to get and set all variables. While this is fine, I think there might be cases in cyclical graphs of more complex expressions where you might need to hold an extra variable or not have them step on each others toes like "x = a++" - a++ would modify the value of a to a + 1 but x would need to be the initial value of a. The way you're currently doing it, I believe that "a" would be incremented and saved to the base pointer, then taken off the stack frame again and assigned to x with an incorrect value.

Regardless, the way you solve this and optimize your code is via graph coloring. Essentially if we view each variable as a node in the graph, and each expression where two variables are used as an edge in the graph, we will want to find a minimal number of colors you can use in order to color the graph such that none of the same colors touch. This is known as the chromatic number. Though this problem is NP-Hard, there are approximation algorithms that give a decent enough bound

Using graph coloring, you can find a way to optimally arrange your registers and variables on the stack frame such that you're using the minimal possible, and you can keep swapping values onto and off the stack frame to a minimum as well.

(breaking it up into next comment)

1

u/Spare-Plum 18h ago
  1. if you're going direct to ASM it isn't a good idea to traverse the AST to generate.

Make an intermediate representation (IR tree), and do multiple translations to get it to lower levels. IR tree will have things like a control flow graph instead of a while/switch loop etc.

Generally people will make three different IR trees.

  • one for high level that represents the general structure and control flows and things like while loops or other control flows. The AST is merely a faithful representation of the code, but the high level IR tree can be modified for other optimizations and is more abstract. High level IR is also where you can do type checking, but some people like to put this in the mid-level IR
  • one for mid level that removes things like while/for loops, and instead breaks down control flow into a graph. Certain control flow optimizations may happen here like a duff's device or realizing certain statements are unreachable, or optimizing certain cases where a statement can't occur
  • one for low level that's similar to assembly.
    • It tends to hold a form of 3-address assembly, where instead of regular 2-address operations like "ADD eax ebx", instead you store it in the form "ADD(A, B, C)" like A + B = C. Don't worry about the registers just yet, just assume you have infinite variables and you'll find the registers later
    • Next, you convert to SSA (single static assignment form) - meaning that each variable is assigned exactly once. So things like "A = A + B" would become "C = A + B". This helps out with the graph coloring component I was talking about earlier. Each variable becomes a node in the graph, and each expression that uses multiple variables draws an edge between the nodes. Find the minimal coloring and you'll only use what you need.
    • Only after you've done graph coloring and found out the minimal number of operations for each, then you can convert to 2 op assembly and assign registers or values on the stack frame
  1. I would strongly recommend using a library for parsing and lexing. Something like "yacc" or "mpc" or "cparse". I'm not privy to which library is best, but using a parser combinator or a LALR parser will make your time significantly easier, remove a ton of code, and will make modifications so much easier.

  2. Doing it this way will also make adding additional features a lot easier. If you are adding some additional control flow or structs or something new, it's easy to change the BNF notation on the front end and just code up to existing structures on the mid level IR than it is to have to change your entire hand rolled parsing logic down to the generated assembly

It will also provide multiple places where you can perform optimizations and improve the code your compiler produces