On 22/08/2018 20:00, Edward Cree wrote:
The first patch is a simplification of register liveness tracking by using
a separate parentage chain for each register and stack slot, thus avoiding
the need for logic to handle callee-saved registers when applying read
marks. In the future this idea may be extended to form use-def chains.
Interesting.
This could potentially help efficient code-gen for 32-bit architectures and I
had been thinking some implementations along this line and would like to have
a discussion.
Program description
===
It will be good if we could know one instruction is safe to operate on low
32-bit sub-register only. If this is true:
- 32-bit arches could save some code-gen.
- 64-bit arches could utilize 32-bit sub-register instructions.
Algorithm
===
Based on the current verifier code-path-walker, it looks to me we could get
32-bit safety information using the following algorithm:
1. assume all instructions operate on 32-bit sub-register initially.
2. link each insn to insns which define its use.
3. for a register use, if it is a 64-bit write back to memory, or if it is
a comparison-then-jump based on 64-bit value, or if it is a right shift,
then consider the use is a 64-bit use, then all its define insns and their
parents define insns should be marked as need full 64-bit operation.
4. currently, register read (REG_LIVE_READ) will be propagated to parent
state when path prune happened, and REG_LIVE_WRITTEN would screen off such
propagation. We need to propagate 64-bit mark in similar way, but
REG_LIVE_WRITTEN shouldn't screen off backward 64-bit mark propagation if
the written reg also used as source reg (this has raised REG_LIVE_READ
propagation but it is not necessarily indicating 64-bit read) in the same
instruction.
Implementation
===
And it seems there could be an implementation based on current liveness tracking
infrastructure without dramatic change.
1. instruction level use->def chain
- new active_defs array for each call frame to record which insn the active
define of one register comes from. callee copies active_defs from caller
for argument registers only, and copies active_def of R0 to caller when
exit.
struct bpf_func_state {
...
s16 active_defs[__MAX_BPF_REG];
- new use->def chains for each instruction. one eBPF insn could have two
uses at maximum. also one new boolean "full_ref_def" added to keep the
final 32-bit safety information. it will be true if this instruction
needs to operate on full 64-bit.
bpf_insn_aux_data {
...
struct {
s16 def[2];
bool full_ref_def;
};
2. Inside mark_reg_read, split SRC_OP to SRC0_OP/SRC1_OP/SRC_OP_64/SRC1_OP_64
to indicate one register read if from the first or second use slot of this
instruction, and to indicate whether the read is on full 64-bit which will
only be true if the read is for 64-bit write back to memory, or 64-bit
comparison-then-jump, or bit right shift means 64-bit.
Build use->def chain for any read, but do 64-bit backward propagation
for 64-bit read only. The propagation is to set full_ref_def to true for
def and parent defs of the 64-bit read.
3. Need new bpf_reg_liveness enum, REG_LIVE_READ64 to indicate there is
64-bit access to one register in the pruned path, and need
REG_LIVE_WRITTEN64 to indicate a write that is REG_LIVE_WRITTEN but should
not screen backward propagate 64-bit read info.
#define REG_LIVE_NONE 0
#define REG_LIVE_READ BIT(0)
#define REG_LIVE_READ64 BIT(1)
#define REG_LIVE_WRITTEN BIT(2)
#define REG_LIVE_WRITTEN64 BIT(3)
I might have missed something in above thoughts, would appreciate reviews and
suggestions. I will also send out some concrete patches later.
Regards,
Jiong
