Use a captable for globals sometimes

[davidchisnall]

The current ABI always materialises globals with the sequence:

auipcc {reg}, {relocation on symbol} # usually relaxed away, occasionally rewritten to auicgp
cincoffset {reg}, {reg}, {relocation on auipcc} # usually rewrites source register to cgp, displacement in integer
csetbounds {reg}, {reg}, {size relocation on symbol}

In some cases, particularly when the size is large, but also when the same global is referenced a lot of times, this sequence will be shorter:

auipcc {reg}, {relocation to captable entry} # Usually a c.auipc, because you need a very large compartment to not be able to cover all of .text with c.aupic
clc {reg}, {relocation to auipcc}({reg})

This is actually a saving if the number of references to the global multiplied by the length of this sequence plus one capability (8 bytes), is greater than the number of occurrences of the earlier sequence. In the best case, this second sequence will be 6 bytes, in the worst 8 bytes. The common case for the first sequence is 8 bytes, so this requires four references to the same global to break even, and five to be a win, but for large globals, it's always a win because cincoffset + lui + csetbounds is 12 bytes of instruction and burns a register.

In addition, if we rewrite all references to a global to the latter sequence, the global no longer has to be reachable via cgp. We can then have the linker move it to a different section. This requires a bit of work in the loader because it now has two notions of compartment globals: the full set, and only those reachable from cgp. This will reduce the size of the section that ends up reachable via cgp, which, in turn, means that auicgp is less likely to be needed.

If we can do this in the toolchain, we could potentially eliminate auicgp entirely. This would be very nice because:

• It is a big instruction (in terms of encoding space).
• It is on the critical path for Ibex (so things could go faster without it).

[resistor]

How are we envisioning this working? I suppose translation-unit-local globals we can count the number of uses at compile time, but in general we need link time knowledge to determine the number of uses of a global. I guess this bleeds into the LTO discussion, since that would enable us to internalize all of the globals...

[resistor]

In the near term, I can look into getting it to work for TU-local globals. I'll have to spend some time understanding the codegen flow here. It looks like we want to use PseudoCLGC to load the cap from the captable?

[resistor]

Trying to enable this path is exposing a number of bugs in the toolchain. #249 is the first one, but there's a linker error after that one is fixed.

[davidchisnall]

I wonder if this can be done entirely as a linker relaxation, since the linker knows how many references there are to a global and so can decide whether it makes sense. I presume we'd need to put the cap table at the end of the section (which would make the section larger, but not move any symbols within the section). So my ideal flow would be:

1. Collect all references in a text section that refer to things that will end up in a data section.
2. Extract the ones where the size is too large for an immediate in a cincoffset or where there are sufficient that it would be a size saving to rewrite them.
3. Allocate captable entries for those at the end of PCC (or, ideally, in the middle in space freed up by other relaxations, but that's harder) and rewrite them as auipcc + clc to the captable entries. Emit caprelocs to initialise these.
4. Move those globals to one end of the data section, sorted by size.
5. Split the compartment data into two sections: the captable-accessed ones and the rest.
6. Process all of the remaining relocations against the newly shrunk data section (which should result in more auicgp instructions being removed.

We could then almost certainly remove auicgp entirely and simply do this transform for any globals that didn't fit into 4 KiB, starting with the most frequently accessed (where we want to do it anyway), then the largest.

[resistor]

Recording my findings so far:

• It's not terribly hard to get LLVM to generate capable relocs for TU-local globals where it would be profitable, and it does trigger a reasonable number of times on the RTOS.
• The problem arises in the linker. We don't have CHERIoT relocations for captable entries. There are two options: we can either add a new CHERIOT_CAPTABLE_HI relocation, or we can teach the normal CHERI captable relocations to handle the CHERIoT 11-bit shift. [1]
• Either way, this doesn't play nicely with the CHERIoT relocation pre-pass, which assumes that the target of CHERIoT PC-relative low relocation can be represented as a Symbol prior to relocation, but this isn't the case for captable entries. I'm not sure of the best solution for this. We might have to add CHERIOT_CAPTABLE_LO_I and CHERIOT_CAPTABLE_LO_S entries? Or perhaps copying the RelExpr from the high reloc to the low one would suffice?

[1] Side thought: now that we have CHERIoT flags in the ELF header, could we potentially get rid of some of our own relocations by making the normal CHERI ones CHERIoT aware?

[resistor]

It looks like normal RISCV doesn't use the prepass to achieve the same effect for its paired relocations, using the RelExpr RE_RISCV_PC_INDIRECT. Maybe we can actually get rid of the preps and reconverge with the normal code path, which might ease captable adoption.