Use MIR provide a basis to implement fast and lightweight interpreters and JITs.

[devillove084]

Disadvantages of GCC/LLVM-based JIT
Enough about the advantages of GCC/LLVM-based JITs. Let us speak about the disadvantages:

1. GCC/LLVM-based JITs are big.
2. Their compilation speed can be slow.
3. It is hard to implement combined optimizations of code written in different programming languages.

GCC/LLVM compilation speed
Second, GCC/LLVM compilation speed is slow. It might feel like 20ms on a modern Intel CPU for a method compilation with GCC/LLVM is short, but for less powerful but widely used CPUs this value can be a half-second. For example, according to the SPEC2000 176.gcc benchmark, the Raspberry PI3 B3+ CPU is about 30 times slower than the Intel i7-9700K (score 320 vs. 8520).

We need JIT even more on slow machines, but JIT compilation becomes intolerably slow for these. Even on fast machines, GCC/LLVM-based JITs can be too slow in environments like MinGW. Faster JIT speed can also help achieve desirable JIT performance through aggressive adaptive optimization and function inlining.

What might a faster JIT compilation look like? A keynote about the Java Falcon compiler at the 2017 LLVM developers conference suggested about 100ms per method for an LLVM-based JIT compiler and one millisecond for the faster tier-one JVM compiler. Answering a question about using LLVM for a Python JIT implementation, the speaker (Philip Reems) said that you first need a tier-one compiler implementation.

The central notion of JIT is a well-defined intermediate language called Medium Internal Representation, or MIR. You can find the name in Steven Muchnik's famous book "Advanced Compiler Design and Implementation." The Rust team also uses this term for a Rust intermediate language.

MIR is strongly typed and flexible enough. MIR in different forms is capable of representing machine code for both CISC and RISC processors.

Here is a brief MIR description:

• MIR consists of modules
• Each module can contain functions and some declarations and data
• Each function has signature (parameters and return types), local variables (including function arguments) and instructions
• Each local variable has type which can be only 64-bit integer, float, double, or long double
• Each instruction has opcode and operands
• Operand can be a local variable (or a function argument), immediate, memory, label, or reference
• Immediate operand can be 64-bit integer, float, double, or long double value
• Memory operand has a type, displacement, base and index integer local variable, and integer constant as a scale for the index
• Memory type can be 8-, 16-, 32- and 64-bit signed or unsigned integer type, float type, double, or long double type
• When integer memory value is used it is expanded with sign or zero promoting to 64-bit integer value first
• Label operand has name and used for control flow instructions
• Reference operand is used to refer to functions and declarations in the current module, in other MIR modules, or for C external functions or declarations
• opcode describes what the instruction does
• There are conversion instructions for conversion between different 32- and 64-bit signed and unsigned values, float, double, and long double values
• There are arithmetic instructions (addition, subtraction, multiplication, division, modulo) working on 32- and 64-bit signed and unsigned values, float, double, and long double values
• There are logical instructions (and, or, xor, different shifts) working on 32- and 64-bit signed and unsigned values
• There are comparison instructions working on 32- and 64-bit signed and unsigned values, float, double, and long double values
• There are branch insns (unconditional jump, and jump on zero or non-zero value) which take a label as one their operand
• There are combined comparison and branch instructions taking a label as one operand and two 32- and 64-bit signed and unsigned values, float, double, and long double values
• There is switch instruction to jump to a label from labels given as operands depending on index given as the first operand
• There are function and procedural call instructions
• There are return instructions working on 32- and 64-bit integer values, float, double, and long double values

[bobcao3]

Some context here: we are only using LLVM for the CUDA and CPU backend. Something I'm more concerned about is the tooling, in LLVM we get to use C++ to write some of the device runtime and helper routines, and we can easily target different backends with very small amount of modification (not just RISC or CISC, GPU uses an extremely different instruction set and execution model). If we move to MIR, what kind of tooling can we expect to have? If we don't care about tooling, we have an existing SPIR-V backend that is a lot quicker than the LLVM backend.

[devillove084]

1. You can expect a more general IR layer that can generate code corresponding to either metal or opencl or cuda or any other backend.
2. Some C implementations ignore full-call ABI compatibility or omit long double implementation for the target ABI.You can expect a better-profile IR layer by fully supporting C-ABI.
3. We could use BBV(https://arxiv.org/abs/1411.0352),we might generate and use only general case code. If a particular call to some small function had specific type values in the majority of cases, we could improve the generated code by using code inlining. Use BBV can solve this complicated problem.

[bobcao3]

In terms of IR design, we have the frontend AST, the CHI-IR, and finally the backend IRs (LLVM ir or SPIR-V). I think CHI-IR is quite similar to MIR's position in Rust's compiler stack, however one big difference is that CHI-IR uses abstract memory operations based on SNodes (which can be sparse), while MIR directly maps to memory operations. Because the memory model in different backends are extremely different, CHI-IR can not have direct memory ops. I do not see how a MIR will help us in this case?

[devillove084]

I haven't looked at your CHI-IR in detail, so are there some designs that we can refer to?

[k-ye]

Thanks for writing this up!!

CHI IR is currently located in https://github.com/taichi-dev/taichi/blob/master/taichi/ir/ir.h (plus some other files under ir/). It's not polished to a point that can be used as a stand-alone IR, but that's fine for us for now. The problem @bobcao3 has mentioned is a result that Taichi has placed some of its first-class features into IR stmts/exprs directly, instead of having a generic type system for the IR to use. That is, you can use LLVM (I believe MIR as well) to build arbitrary composite types.

I understand that Rust uses several layers of IRs, e.g. HIR, MIR and LLVM IR in the end. From that point of view, it seems to me that the purpose MIR serves not significantly different from that of CHI IR. I believe CHI IR's redesign can borrow lots of ideas from MIR, but I don't see whether it's the optimal approach to just make MIR a drop-in replacement for CHI IR.

[k-ye]

One thing to confirm: Most of the features you've listed are available in LLVM as well. So IIUC, the biggest advantage of MIR over LLVM IR is still the JIT speed?

[devillove084]

Yep, the biggest advantage of MIR over LLVM IR is still the JIT speed.

[bobcao3]

Currently our JIT speed bottleneck even on the LLVM backends is our CHI-IR optimization passes. On a backend where we can directly codegen into target IR like vulkan with SPIR-V, about 80% of time is spent on CHI-IR optimization. We should probably focus on improving CHI-IR first