[RFC] Rework the executor opcodes to be position independent to improve JIT and interpreter performances

Hi

Since the decision to turn jit to off by default, I've been thinking about the possible solutions for the cases that brought us to this conclusion.

1. Issue considered

One issue had been nagging me since I started working on my own JIT compiler, and when I looked at llvmjit I noticed it suffers from this issue too.
The opcodes are designed with the interpreter performance in mind. It means they contain a lot of pointers, with the following consequences on the JIT compilers:
- it’s impossible to compare two sets of opcodes to see if they are the same,
- it’s impossible to track down constants and do some simplifications.
Regarding this second issue, to be more explicit: when a FUNCEXPR opcode is created, the corresponding FunctionCallInfo object is allocated. This object has the function arguments (a NullableDatum[N]), and the constants are immediately set in there, the variable parts being updated when another opcode write at &args[x]. The only way for a JIT compiler to know that args[x] is a constant is to check that there is no write to args[x], a tedious and error-prone process.

I thus started hacking around the opcode design to make it both easier for the JIT compilers to do their work, while maintaining the performance for the interpreter. The current patch works for basic queries (there are opcodes I had no time to fix in my first pass), and I have made llvmjit work with the new design. The interpreter impact is background noise, being a one-time pass on each opcode, while the potential benefits on the JIT compilers is immense.

2. Change proposal

Right now, an opcode has for instance a bool *isnull field. I replace this with a BoolPtr isnull (same apply for FunctionCallInfo, Datum and NullableDatum obviously).

BoolPtr is defined as:

typedef union BoolPtr {
bool *value;
struct {
ExprEvalPtrType ptrType;
uint16_t ptrInfo;
uint8_t ptrExtra;
};
} BoolPtr;

While building the opcodes or running a JIT compiler, the second structure is used, the value being meaningless.
When the interpreter starts, during its setup phase, it iterates once through each opcode and translate the struct into the matching pointer.

For instance:
{
.ptrType = STATE_RESULTNULL_PTR;
}
is going to be translated to &state->resnull.

The struct is kept to a pointer size (currently even a 32 bits pointers but I’m not sure it’s going to hold all the info required and may thus switch to 64 bits) so there is no memory lost here.

I also moved more information into the ExprState. The target of each FmgrInfo of each function call is stored there, to be able to resolve them during setup/compilation. The constant parameters of function calls are also stored there.

Note that I'm not sharing the patch yet because it is really crude. I don't use AI and iterate manually when I have some time to spare, so there are thousands of things to clean up.

3. Demo of the change in opcodes

Here is a very basic SELECT 1 = 2 to show the result (on ARM64).

WARNING: Proof of concept: dump of exprs.
WARNING: 0x0: 1D00000000000000 FB00000000000000 FA00000000000000 F400000000000000 0000000000000000 0200000000000000 0000000000000000 0000000000000000
WARNING: 0x1: 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000
WARNING: Reduced back to pointers.
WARNING: Proof of concept: re-dump of exprs.
WARNING: 0x0: 1D00000000000000 084380620C000000 054380620C000000 784E80620C000000 90266F0201000000 0200000000000000 0000000000000000 0000000000000000
WARNING: 0xc62804e78: 504480620C000000 0000000000000000 0000000000000000 0000000000000200 0100000000000000 0000000000000000 0200000000000000 0000000000000000
WARNING: 0x1: 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000

One can see the opcodes before reducing are similar to any such a call, while the "reduced" opcodes are not position independent anymore.

4. Potential benefits for llvmjit

Outside of any optimization in handling partitions or preventing useless compilations, the immediate impact I’ve had is through stack-allocating FunctionCallInfo instead of keeping them malloc-ed. This makes LLVM aware of their entire lifespan, and thus makes it possible for LLVM to go as far as getting rid of them when the function is inlined.
With an inlined int4eq, a basic select * from table where x = 2 is reduced to the following IR:

b.op.3.start: ; preds = %b.op.1.start
%24 = load i64, ptr %v_scanvalues, align 8
%25 = and i64 %24, 4294967295
%int_eq = icmp eq i64 %25, 2
%int_eq_ext = zext i1 %int_eq to i64

This makes LLVM generate a much better code, without having to fight/work around lifetime declarations to make the compiler aware of intricate behind the scene decisions. Instead of working with black boxes, we are using idiomatic IR that is easy to optimize.

5. Potential benefits for the interpreter

For some time, I've wanted to write very specialized opcodes in the interprete, but I've never been able to achieve any interesting gain there due to the opcode having direct pointers as soon as they are created. When they are built, they are moved in RAM to be kept together, but this mean you can not have an opcode writing directly to another opcode, it always have to go through a pointer redirection, thus greatly reducing the benefits you could get from specialized opcodes.
Having the opcodes built with no pointers immediately makes this possible. I will try to implement this in order to demonstrate the benefits there.

6. Conclusion

The patch is already on the heavy side of things (+1260 -720) while being vastly incomplete. It is complicated to do the change by small steps, the entire opcode generator is based on writing to pointers.
But it has a lot of potential that is left to explore. All the function call info objects can be allocated at the same time, next to each other in RAM, likely improving CPU cache. Caching even partial compilation parts in LLVM would be incredibly useful, esp. with hundreds of partitions.

I sadly lack the time to track all the developments and emails around this topic, but my research gave no previous attempt in that area.
I hence would appreciate any opinion on this. Is this worth keeping exploring? Are other ways already being developed and much closer to beta/production than this proof of concept?