Web Apocrypha

Among other things, one interesting advantage of dynamically generated code is that constants can be embedded into the instruction stream. Think about it: there are several constants (usually pointers), which are unknown at compile time, but behave as constant once a value is assigned to them. Those constants can be embedded into the generated code, so several load-from-memory operations can be eliminated. WebKit JIT goes one step further: you can also rewrite constants which are not even known at JIT compilation time. Those constants typically hold cached values used by some fast cases.

On x86 based machines, these features are rather easy to implement, since instructions have a 32 bit immediate field, which is enough to hold any immediate value. On ARM, we only have an 8 bit immediate field, which can be rotated by an even number. Therefore, we sometimes need 4 instructions to create a 32 bit number. Fortunately, there is another way to access constants. The program counter (pc) is a regular register on ARM, which points to the instruction address plus 8. Using the pc, we can load constants that are at most 4 kbyte away from the current instruction. The constants are grouped together to form a constant pool and its entry is protected by a jump instruction. The constant pool is aligned to 32 bytes to aid caching. The drawback of this solution is that memory loads are expensive operations, especially when they cause cache misses.

[jump after the constant pool][constant 0][constant 1]...[constant n]

In our ARM JIT implementation, the constant generator was made as smart as possible. In other words, we tried to find the right balance between speed (a slow algorithm is not suitable for a JIT compiler) and efficiency (use the least number of instructions to generate a specific constant). Furthermore, those constants, which are not known at JIT compilation time, are placed into the constant pool as well.

Finally, let me share some technical details with you. We decided to use the following algorithm:

Since one of our primary concern is speed, we tried to avoid loops: our implementation does not need any loops if the constant itself is an ARM constant. If it is not an ARM constant, we employ a single loop to find an 8 zero bit sequence (if the the instruction can be encoded as two data processing instruction, it must have 8 continual zero bits somewhere). This 8 bits are rotated to the least significant byte (bit 0-7). The search iteration took at most 16 steps. No other loops are needed for our algorithm.