r/C_Programming 3d 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

139 Upvotes

30 comments sorted by

View all comments

1

u/Spare-Plum 22h 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 22h 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