My own C compiler is designed for x86-64 and outputs ELF64 binary. My plan was that if I could output code that could run on x86-64, I could run it on my home computer, and I would be able to do this for the next 10 years. However, with the emergence of various processors, it seems that x86 may not remain the mainstream.
I also experienced the ability to compile code written in Rust to WASM and run it in a browser. I was quite surprised to find out that I can run code written in a language that can do low-level things like memory manipulation with pointers in a browser. I was quite surprised.
So I thought I'd try to make it possible to output wasm from the C compiler.
Architecture of WASM
I looked up the architecture of WASM a while ago, and the features are as follows:
- Stack machine instruction set (no registers)
- Local variables can be used
- Only
i32,i64,f32,f64types are supported (not even strings) - Jumps can only be control-syntactic jumps (out of a block or back in a loop), not to a label (address)
- There is no GC.
As for the data types that can be handled, there are no useful ones such as objects or strings, only byte array that can be manipulated, but I think this is a sufficient level to bring from a language specification of the level of C.
Policy for outputting WASM binaries from a C compiler
The original compiler was designed to convert to a register machine instruction set:
- Front end (parser): C source -> Abstract Syntax Tree (AST)
- Middle end (intermediate representation): AST -> Intermediate Representation (IR)
- Backend: IR -> x86-64 binary (ELF64 format)
It would be nice to be able to switch the output target by sharing the middle end and replacing the backend, but it's a bit difficult.
In the middle end, jumps are converted to basic blocks, and finally to label jumps. However, in WASM, the jump is a control structure, and you can't place a label at an arbitrary point and make it jump. So if we want to do this, we need to recover the control structure from the label jump. It may be possible to recover the control structure by analyzing the control flow graph, but I don't think it's easy.
There are some other points that seem troublesome.
- The calculation of the expression has been converted to an operation in three-address code between virtual registers, and it needs to be converted back to the stack machine method.
Since the AST stage can be used as-is, I decided to share only the front-end and output the wasm binary directly from the AST.
A few implementation points
Handling of local variables other than numeric types
WASM can only handle 32/64 bit integer/floating-point number types as local variables, not structures or arrays. What to do is to store them in linear memory.
It is necessary to manage which part of the linear memory to use by yourself. Therefore, we need to prepare a global variable that represents the stack pointer, store it in a local variable that represents the base pointer at the beginning of a function, modify the stack pointer, and then restore it when we exit.
If a reference is taken by & even if it is a numeric type, it is necessary to be able to rewrite it via the pointer, so it cannot be a local variable and should be placed in linear memory.
Returning from the middle of a function
When exiting with a value by return from the middle of a function, a real processor such as x86 will return to the caller with a value in the rax register according to ABI. In WASM, it is also possible to exit from a function and return the top of the stack with the return instruction, but there are cases where it is necessary to restore the stack pointer as described in the previous paragraph, so I want to unify the process of exiting from a function (epilogue).
In this case, we cannot use return from the middle of the function, so we need to prepare a local variable to store the return value, store it in the variable, jump to the epilogue, process the epilogue, retrieve the return value, and return it.
Handling of assignment expressions
In C language, assignment is an expression, so it can be connected to multiple expressions or mixed with other expressions. However, in WASM, storing a value in a local variable (local.set) or in linear memory (i32.store) removes the value from the top of the stack. Since there is no instruction like dup to duplicate the value on the stack, it is not possible to keep the assigned value (although it is possible to keep the value of a local variable while storing it with the local.tee instruction).
Therefore, the assignment expression is treated as void, and the value cannot keep alive. If the value of the assignment expression is still to be used, a local variable is allocated internally and converted to a comma expression (l = r is converted to ((void)(tmp = r), (void)(l = tmp), tmp)).
Switch statement
In WASM, only structured jumps are possible, but how to implement a switch statement? I was wondering how to implement the switch statement, but it was nothing, I just had to nest as many blocks as the number of cases and br each one.
There is also an instruction called br_table, which allows you to do table jumps instead of br_if in order (I haven't tried it).
Variable Length Arguments
The number of arguments of a function and their types must be fixed in WASM. As for how to handle variable-length arguments, we'll pass them in linear memory. We can internally pass function arguments to ... Internally, convert the function argument to the argument before ... + pointer to store the variable length arguments.
Pointer length
The pointer is treated as an offset in the linear memory, but since the offset is u32, the pointer should be 32 bits long. Therefore, I decided to use sizeof(void*) == sizeof(long) == sizeof(int) == 4. The data type model is called ILP32. i64 will be handled as a long long.
It is recommended to have the __ILP32__ macro pre-defined so that the code can determine this.
Function call using function pointer
In WASM, normal function call is not by name or label, but by an index that is assigned to the function in order. In order to handle function pointer, it was not possible to do so by using the index.
You need to register the function you want to handle as a function pointer in a table, and use that index.
Old Function Prototype Declarations
In the prototype declarations of functions in the old C language, parameters can be omitted. In that case, the function is compiled assuming that the type of the argument given by the caller matches the entity, and if it does not, it will malfunction.
In WASM, if the type or number of arguments of the function to be called is not correct, a runtime error will occur, so make it an error at compile time.
Runtime Environment
One of the advantages of compiling to binary is that you don't have to write a runtime because everything is resolved at compile time. However, this does not mean that the standalone executable is truly independent, but rather depends on the OS system calls.
In the same way, the world of wasm binaries only allows computations, so if you want to communicate with the outside world, you need to prepare a call equivalent to a system call. From wasm, it can be executed as a call to an imported function. Prepare functions such as open and read that are equivalent to unistd and make them available.
Running in a browser
As usual, if you compile the source of the compiler itself, you can get a compiler that runs as WebAssembly, which is self-hosting. It's interesting to note that cross-compilation is included this time:
- C compiler source (wcc.c) → gcc on Mac → C compiler running on Mac that can emit wasm (wcc on Mac)
- C compiler source (wcc.c) → wcc on Mac → C compiler running on wasm that can emit wasm (wcc on wasm)
- Prepare a runtime and run wcc on wasm in a browser.
Just by enabling the C compiler to emit wasm, you've got a C compiler that automatically runs on your browser! This is a good deal.
After that, I'll make up a file system, and incorporate Ace editor as a text editor that runs in the browser, so that I can compile and execute with a button.
Problems
Some of the problems with WASM, not necessarily on the browser, are
- Asynchronous processing is not possible.
- You can't wait until something is done synchronously, because you can't explicitly give away the process.
- Cannot
forka process - Cannot do global escaping
In JavaScript, asynchronous processing is possible with Promise, but it is currently not possible with wasm. If I had to do it, I'd separate functions in the middle and let them sleep the process once... but that's not possible in places where function calls are nested.
If you can't do global escaping, you can't handle exceptions, which is fine in C and Rust, but how do you handle exceptions in C++?
Unimplemented features
Jumps with goto are not supported because they cannot be easily converted to structural jumps. Disabling goto is not enough, but looping over a case inside a switch breaks the structure (Duff's device), so it is not supported.
Others: passing/returning values of structs, compound literals.
Impressions
I thought it would be interesting to be able to run code written in C on a browser, but then I realized that there is no need for me to go through the trouble of coding in C on a browser... orz
jp: https://tyfkda.github.io/blog/2021/02/04/c-on-browser.html
Top comments (0)