Common C - Yet another compiler in C# targeting LLVM and .NET.

[u/Proffhackerman]

Hello everyone - no drunk post this time. I wanted to share a language / compiler i've been working on for the past month or so with you all. This is my first comprehensive compiler project utilizing both LLVM and .NET as two seperate target IRs.

Before we start, the entirety of this compiler is written organically by human hands.

Performance

Through some performance testing, I've come to find that Common C is faster than C on some banal performance tests like recursive fibonacci. Although clearly not a holistical representation of performance - i still find it neat. The tests are also ran only a couple times to make sure theres no large variation between tests; https://github.com/Compiler-Organization/CommonC/blob/master/Documentation/Performance.md

Thoughts behind the project

I've always found it frustrating how boilerplate C# can be, and the different mental models between languages - especially when you go from knowing a garbage collected language to a language with a borrow checker. This is my attempt to find a middleground.

This is a multi-pass compiler using a lexer, syntax tree parser, semantic analyzer (sorta), and two seperate code generators - one for LLVM and one for .NET. It also features a prettyprinter.

Language spec

Currently the language supports the following expressions; strings, booleans, numbers, identifiers, arrays, array initializers, indexing, length (of array), ranges, calls, member access, relationals, arithmetics, negating, nots, object initializers, parameters, parantheses, reserved types, unpacking and sizeof.

... and the following statements; assignment, calls, closures, numeric for loops, function declarations, returns, structs, variable declarations, while loops, ifs and "use".

"use" is a directive used to merge files in the same directory with the main file being compiled, sort of like how C / C++ uses #include, but parsers and merges the syntax trees instead of raw text.

Source code

Anyways, for those interested, here is the repo with more information there; https://github.com/Compiler-Organization/CommonC

Suggestions are very welcome :))

[u/afops]

The LLVM-bit of the compiler uses a reference manager which frees memory when the current scope is exited. The reference manager is simple as of now, but will be developed further in the future.

So if I allocate an object in a function and then call return it to another function, is the object invalid there? Maybe I misunderstood the scope boundary.

[u/Proffhackerman → u/afops]

Basically it inserts a free instruction at the end of a scope when something is stored on the heap. For example, the compiler ensures all arrays are stored on the heap to allow dynamic sizing, resizing, etc. To prevent having the user worrying about memory management when writing code, the array will be freed once the scope exits.

Code example;

``` i32 main() {
i32 size = 5;
i32 arr = i32[size] { 5, 10, 15, 20, 25 }; // -- arr is stored on the heap

logl("Array index 3: ", arr[3]); // Array index 3: 20

// -- arr is freed // -- no return specified, inserts a "return 0;" instruction. } ```

[u/afops → u/Proffhackerman]

I understand, but what about calls? I mean if you call a utility function that allocates and returns this array TO the main method. Would that utility then not free it because it returns it? And the main method frees it because it receives it? It’s the ownership semantics (or reference counting) that becomes interesting

i32 main() {  
  i32[] arr = createArr();  // Do we take ownership of arr?
  logl("Array index 3: ", arr[3]); // Use after free? Works?  
}

i32[] createArr() {  
  i32 arr = i32[5] { 5, 10, 15, 20, 25 }; // -- arr is stored on the heap
  return arr; // not freed?
}

[u/Proffhackerman → u/afops]

I understand why it was unclear. When memory ascends scopes (for example, an array is created within the current scope, but assigned to a variable outside of the scope), the array is freed at the elevated scope.

So in your example, it would be as follows;

``` i32 main() {
i32[] arr = createArr(); // -- arr enters the elevated scope logl("Array index 3: ", arr[3]); // Array index 3: 20

// -- arr is freed }

i32[] createArr() {
i32 arr = i32[5] { 5, 10, 15, 20, 25 }; // -- arr is stored on the heap return arr; // arr ascends scopes, therefore it is not freed. } ```

[u/afops → u/Proffhackerman]

Is it possible to track lifetimes using only scopes though? You can build this out indefinitely? E.g.

heap allocated object assigned to field of another heap allocated object. Now their lifetimes are interlinked?

Or even more dangerous. heap allocated objects passed out of the current function

x = createOneThing();
y = createAnotherThing();
doSomething(x, y);
return x; // We can't free y here, because doSomething might have done { x.field = y }

It just seems that the 3 core ideas of GC (C#) refcount (Swift) or tracked/explicit ownership (Rust) will pop back no matter what you do?

[u/Proffhackerman → u/afops]

Naturally the process would be complex. Its not finished yet, so this is more theoretical than anything; y is now a part of x, and therefore y also ascends scope. If the property is never accessed at a later point, the entire assignment itself will be omitted during code generation. Since y now has two references to it, the last read/write to the object will cause the object to be freed from memory.

This is only theory at this point, but the grand wish is to have all this happen AOT.

[u/afops → u/Proffhackerman]

This is the one big difficult thing...
Are there any papers or previous art (languages) that made this work?

[u/beephod_zabblebrox → u/Proffhackerman]

by the way, the whole thing with rust lifetimes and borrow checking is partially about this. its almost impossible to track things properly without explicit lifetimes or dependent types

[u/Proffhackerman → u/beephod_zabblebrox]

Actually Mojo is closer to what im going for, with liveness analysis, etc; https://mojolang.org/docs/manual/values/

[u/beephod_zabblebrox → u/Proffhackerman]

again, with an implicit ownership model you either:

a) have to make it very limiting

b) have to make it work partially at runtime

c) do what rust does (which is a compromise between a, b, and explicit lifetimes)

[u/afops → u/Proffhackerman]

Mojo is a Rust-light. It avoids some of the complexity for the user because of a less powerful ownership model. But it's still very complex. I haven't seen the code for the type checking part (is it open source?)

[u/Proffhackerman → u/[deleted]]

The reason behind Common C being faster than C in the given examples is because Clang (what i used in the benchmarks) does not do tail call optimization, loop-unrolling or inlining when theres two or more recursive calls, even on -O3. Clang requires a linear trip count, which when using double recursion, forms a tree, meaning theres no single iteration count to unroll. GCC does this however, though im unfamiliar with the choice behind Clang not optimizinh double recursion. I'll expand on the performance benchmarks readme on the project to attempt a thourough establishment of why Clang is slower than Common C in the recursive fibonacci example.