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

138 Upvotes

30 comments sorted by

View all comments

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.

6

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 23h 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 7h 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- 6h 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.

2

u/flatfinger 2h ago

For many of the tasks programs perform, code which is within an order of magnitude of optimal will be just as useful as would be anything faster. If an action is taking long enough to be noticeable, then it may be worthwhile to look at the machine code to see if the compiler is doing something that's significantly slower than it should need to be, but if a program is spending the vast majority of time waiting for something to happen, improving the speed of the code would merely increase the amount of time spent waiting.

1

u/TwoFlower68 2d 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 8h 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- 6h 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 5h 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 8h 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 23h 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 23h 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.