C extensions to support JIT

[dibyendumajumdar]

Hi @vnmakarov

Your recent Redhat blogpost made me wonder if it would be beneficial to have some C extensions in c2mir that help with better performing JIT code.

Regards

[vnmakarov]

Any good JIT for a dynamic programming language requires implementation of speculated and de-optimized code generation.

For the current MIR implementation, this would require for a JIT developer to generate MIR code which collect profile information (e.g. value type profiling) by himself and then generate speculative MIR code based on this information. It is a tedious work common for all dynamic language JITs. So I'd like to implement it in a general way. First, it requires to implement speculative MIR branch insns which collect profile information about taken paths. Then using this profile information, MIR generator in a special mode would generate a speculative code assuming that only one path will be taken. If the assumption is violated, an unoptimized code could be generated.

Second, this could implemented as a C extension (something analogous to builtin_expect) informing c2mir where to generate speculative MIR branch insns.

So that is the plan. Probably I can start this work in June-July after finishing Apple Silicon port.

[dibyendumajumdar]

Above makes sense.

I don't know how feasible this is, but here is something that I would like to be able to do.

When I JIT compile a piece of Ravi code, it essentially serializes the byte code instructions. This results in duplication of code as bytecodes are generally inlined. What would be nice if the common blocks could be shared without requiring them to be converted to functions with function call overhead. Almost like some form of fast call via local jump. This would be of huge benifit (if it can be done) to bytecode JIT compilers. Don't know if it makes sense - and also this my be too hard to do.

[vnmakarov]

When I JIT compile a piece of Ravi code, it essentially serializes the byte code instructions. This results in duplication of code as bytecodes are generally inlined. What would be nice if the common blocks could be shared without requiring them to be converted to functions with function call overhead. Almost like some form of fast call via local jump. This would be of huge benifit (if it can be done) to bytecode JIT compilers. Don't know if it makes sense - and also this my be too hard to do.

Interesting, Dibyendu. Call can be expensive as in MIR it is done through thunk (usually 2 additional insns) plus stack frame allocations and saving/restoring regs.

As a call block is probably a leaf function, there are no saving/restoring regs as allocator will use call-clobbered regs. There is still pushing/popping return address on the stack but only for x86-64 architecture.

We could implement code block call through implementation and using labels as values but it will make optimizations and RA mostly local and ineffective in a function containing and calling the call blocks.

I guess what we realistically can do:

• to prevent calls of some function through thunks. Such functions can not be redefined or their redefinition will be not visible to other functions linked with this function.
• to make new fast calls which uses hard register as a return address to remove pushing/popping it on the stack

[dibyendumajumdar]

https://v8.dev/blog/sparkplug

Above article describes the type of JIT I was referring to.
Each bytecode is translated to a chunk of code, and the interpreter loop is unrolled. But essential feature is to be able to call these chunks without function call overhead - and presumably some kind of register reservation that allows the chunk to use a subset of registers. Since MIR's goals are to support JIT compilers, if somehow a C based approach could be used for this, that would be great.

I was thinking that easiest option might be have some internal fast call method - C function annotated by something - and certain assumptions - e.g local jump, maybe allow shared variables between the function and the owning function. That is the called chunk should be able to access variables in the caller.

[vnmakarov]

https://v8.dev/blog/sparkplug

I also read this blog post a few days ago. In the bogpost I found an interesting comment that it is practically a new compiler for each target. MIR supports more targets than V8 and will support even more targets in the near future.

I am not satisfied with the speed and performance of the generated code from MIR when -O0 is used. The first version of fast path in MIR-generator for -O0 was much better. But it had a problem with generation of very big stack frames. If I can solve this problem, I could restore the original code generation for -O0 and this will improve generated code performance and generation speed.

Still improving generation speed from MIR has some inherent constraints. It is in MIR flexibility designed to be used for many purposes. To achieve even faster code generation another IR should be used which I described in more details in the next my post in this discussion.

Above article describes the type of JIT I was referring to.
Each bytecode is translated to a chunk of code, and the interpreter loop is unrolled. But essential feature is to be able to call these chunks without function call overhead - and presumably some kind of register reservation that allows the chunk to use a subset of registers. Since MIR's goals are to support JIT compilers, if somehow a C based approach could be used for this, that would be great.

I was thinking that easiest option might be have some internal fast call method - C function annotated by something - and certain assumptions - e.g local jump, maybe allow shared variables between the function and the owning function. That is the called chunk should be able to access variables in the caller.

Thank you for sharing you thoughts. I will think about this too.

[dibyendumajumdar]

BTW The reason I use the C front-end to MIR is that otherwise I would have to worry about manipulating aggregate objects such as structs and arrays myself. Moreover this needs to be portable and compatible with C conventions. If MIR IR can be extended to support definition of arrays, structs and unions, then this complication would disappear, and it would be relatively easy to generate MIR IR code.

[vnmakarov]

BTW The reason I use the C front-end to MIR is that otherwise I would have to worry about manipulating aggregate objects such as structs and arrays myself. Moreover this needs to be portable and compatible with C conventions. If MIR IR can be extended to support definition of arrays, structs and unions, then this complication would disappear, and it would be relatively easy to generate MIR IR code.

I am agree that generated JIT code actually should be considered as code on language used for VM implementation.

It is hard for developers to implement the same structure layout using only MIR. It means implementing layout algorithm for different target ABIs over and over again and that MIR is not fully target independent format (but still I believe it is more target independent than LLVM IR).

Implementing layout algorithm is not easy task even for one target. I only recently achieved structure layout compatibility in c2m with GCC/Clang. The culprit is bitfields whose layout is undefined according to C standard and even undescribed in some target ABIs.

So I consider MIR mostly as an interchange format for the same target.

I thought about higher level MIR with structural data types. Using labels in generated code could be inconvenient too and it would be nice to have some if-stmts and loop-stmts. So higher level MIR could be a simplified C. But t has no sense for this as we already have C-to-MIR compiler.

Currently I think generating JIT code on C is the right way. Simply we need to improve bulk speed of c2m compiler a bit (as currently on longer code C-to-MIR translator time is close to MIR-to-machine code time with -O2 or even -O0).

MIR is pretty flexible for generation code from C and for implementing machine code generation and optimizations. But this flexibility makes MIR slow for optimizations and code generation. To speed up it, the code should be more compact and simple and have better locality (no lists for example).

So I am thinking about a new project to generate JIT code only from C with some hidden IR (less suitable for human, less machine independent and more suitable for code generation). The bulk speed should be close to tcc. But it is a different story. I don't know when I can start the new project and will it be successful. But I can say definitely MIR project development will be continued and useful for different tasks, especially as some more or less universal interchange format (e.g. I am thinking about in wasm inter-operability these days).

[dibyendumajumdar]

Hi @vnmakarov

I would suggest improving MIR rather than starting a new project. MIR is still not 1.0 so you have some freedom with regards to changing the IR to make it higher performance.

Regards

[vnmakarov]

Hi @vnmakarov

I would suggest improving MIR rather than starting a new project. MIR is still not 1.0 so you have some freedom with regards to changing the IR to make it higher performance.

Please don't worry, Dibyendu. I wrote only about thinking the new project. I usually plan for a long time (it might take 1 year or even more) and do a lot of experiments before really starting the work. In the end, depending on the results of the experiments the new project might now start at all. On the other hand all the experiments could help to improve MIR project too.

MIR is a real thing and possible new project is a just thought. I'd prefer to improve the current code too. Simply sometimes achieving desirable performance goals is not possible w/o redesigning all compiler (e.g. 1-2 pass C compiler instead of 4-pass c2m) and rewriting a big chunk of code.

[dibyendumajumdar]

I would suggest improving MIR rather than starting a new project. MIR is still not 1.0 so you have some freedom with regards to changing the IR to make it higher performance.

Please don't worry, Dibyendu. I wrote only about thinking the new project. I usually plan for a long time (it might take 1 year or even more) and do a lot of experiments before really starting the work. In the end, depending on the results of the experiments the new project might now start at all. On the other hand all the experiments could help to improve MIR project too.

MIR is a real thing and possible new project is a just thought. I'd prefer to improve the current code too. Simply sometimes achieving desirable performance goals is not possible w/o redesigning all compiler (e.g. 1-2 pass C compiler instead of 4-pass c2m) and rewriting a big chunk of code.

I am not worried as the advantage of using the C front-end is that my code is insulated from any changes below that layer. However, your time is precious and it should be used wisely. Of course the notion of what is important varies. Personally I think that the performance of the compiler can be worked around by executing it in background. However, if the generated code is not optimum for JIT use cases then that negates any benefit from fast compilation.

[dibyendumajumdar]

Another thought I have is that currently the C front-end is ISO C11. However, this may not be optimum for JIT - it maybe that a subset/superset can be more useful.

For instance, the MIR C front-end could prohibit certain C features such as pointer aliasing. Or allow fast call functions where certain limitations are imposed - e.g.. static local functions with register arguments and returns.