Constant pool

[apt1002]

Currently Mijit supposes that any word-sized value can be placed in an immediate constant. This is true only because we're on x86_64 (#18) and only because we're writing every constant to a register before we use it (#15). In future, we need to do something different.

64-bit ARM

64-bit ARM seems to be the most awkward target, and it will therefore drive the design. The strategy required for ARM is something like this (included for illustration only):

• If the constant is used by an arithmetic instruction, consider changing the instruction to make the constant easier to encode:
  • Swap ADD with SUB, and negate the constant.
  • Swap AND with BIC, and invert the constant.
  • Swap OR with ORN, and invert the constant.
  • Swap EOR with EON, and invert the constant.
• If the constant is zero, use the zero register.
• If the constant fits in the instruction as an immediate constant, use that form. The rules are:
  • If the constant is smaller than the precision in bits, it can be used as a shift with LSL, LSR, ASR, and ROR.
  • If the constant is an "arithmetic immediate", i.e. a 12-bit value shifted left by 0 or 12 bits, it can be used with ADD SUB, ADDS and SUBS.
  • If the constant is a "bitmask immediate", i.e. one of 2,667 special bit patterns, it can be used with AND, OR, EOR and ANDS.
  • If the constant is a signed 9-bit value, it can be used as an increment with LDR, STR, LDRB, STRB, LDRSB, LDRH, STRH, LDRSH, and LDRSW.
  • If the constant is an unsigned 12-bit value times the number of bytes transferred, it can be used as an offset with LDR, STR, LDRB, STRB, LDRSB, LDRH, STRH, LDRSH, and LDRSW.
• Otherwise, the constant needs to be written to a register before it is used. There are still more cases to distinguish:
  • If the constant is a 16-bit value shifted by a multiple of 16 bits, use a MOVZ instruction. If it is the inverse of such a value, use MOVN.
  • If the constant would be legal for an OR, or it with the zero register.
  • There are ways of loading wider constants using multiple instructions, but they are probably not appropriate.
  • Load the constant from memory using a PC-relative LDR. The offset must be a signed 21-bit number.

x86_64

Most instructions can use a signed 32-bit immediate constant. Larger constants must be written to a register first, either using a wide MOV instruction, or using an IP-relative load.

Position-independent load

Regardless of the platform, the final case (a position-independent load) is the most general. Let us say that a constant is "awkward" if it requires a position-independent load instruction. Such constants need to be held in a constant pool: a read-only area of memory that is contiguous with the executable code but that is never executed.

Because of the limitations of the position-independent load instruction, the constant pool must be within +-1MB of the instruction (on ARM). We must allow Mijit to compile more than 1MB of code in total. Therefore, more than one constant pool will be needed. It is less likely that it will compile a basic block that is more than 1MB in size, so it probably suffices to have one constant pool per basic block. If a basic block does grow too big, we can split it in two using a jump instruction.

Currently, basic blocks are represented by a Vec of Actions. I suggest we supplement this with a Vec of constants. The lowerer will need to receive the constants first, followed by the Actions. The Actions can specify constants by value. The pool for a basic block is only required to contain the awkward constants that are mentioned by the Actions in the basic block. The target abstraction layer (#18) will need to provide a way of testing whether a constant is awkward.

[apt1002]

We left x86_64 unchanged (it uses MOV instructions).

We implemented constant pools for aarch64 in an incremental way. We allocate code memory in 1MB chunks. In each chunk we assemble code forwards and collect constants backwards. When there is too little free space between the two, we allocate the next chunk and assemble a branch to it. This incremental scheme avoided any changes to Lower::action().