From: Alexei Starovoitov This is about the cost of scalar evolution: the work per join point. The time in scev.c goes down by a factor of 1.7, the number of expressions by 2.3. It is what pruned SSA does: no phi for a dead register. Expressions change: a register or stack slot that is dead at a join point is '?' there. Nothing reads it before it is written, but reset_scevs_at_indirect_writes() leaves '?' alone: a slot that one of two branches writes and bpf_probe_read_kernel() then overwrites was '_' after the call and is '?' now. The loop around it is unrolled by the verifier, or the slot is joined at the header. No verdict, insn count or state count changes in the selftests, Cilium, sched_ext, katran, bpfjailer and the programs in Rust. join() constructs (any a b), which stands for a phi, for each register and stack slot that has distinct expressions on the two edges. That is a traversal of both and two or three calls of add_expr(). In loops it is rare. A later patch computes expressions for whole subprogs. There every 11th insn is a join point, and 25 of the 267 registers and stack slots differ. One of them is live. The others: - Branches leave temporaries in r0 - r5 and in the slots of their spills and buffers. Where two branches join, 7 of them are dead. - A subprog that is out of budget goes to the last exit of the subprog, on an edge that the verifier adds and the CFG does not have. Nothing is known on that edge, so every jump to that exit is joined with '?' in all 267. Only r0 is live there. These are 6 % of the join points and have 72 % of the dead registers and stack slots. 56 % of all expressions would be constructed for them, by 76 % of the calls of add_expr(). Ask reg_alive_at() first. '?' is the conservative answer: liveness is used to lose precision only, never to gain it. What it would cost to compute expressions for all code of the selftests, Cilium, sched_ext, katran, bpfjailer and programs in Rust. The last two rows are against loops only: before after expressions per insn 1.79 0.78 calls of add_expr() per insn 6.4 1.5 scev.c per insn 291 ns 170 ns kernel instructions (perf stat) +4.2 % +1.9 % load time (veristat) +5.7 % +3.2 % mem_peak of veristat is 0.7 % less. An edge to a join point cost up to 267 calls of mk_any(). It costs one per live register that differs. That is a bound per edge: the time in scev.c is linear in the number of insns before and after. Progs of 100 to 1000 insns gain most, 5 % of the load time. Above 10000 insns it is less than 1 %. With loops only, as today, it makes no difference that can be measured. Signed-off-by: Alexei Starovoitov --- kernel/bpf/scev.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 8f8ca69482ca..7031ab00a22a 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -989,8 +989,10 @@ next:; return id; } -static int join(struct scev *scev, struct env *acc, struct env *cur) +/* @acc is the env before the insn at @idx */ +static int join(struct bpf_verifier_env *env, struct env *acc, struct env *cur, int idx) { + struct scev *scev = env->scev; int i, id; if (acc->empty) { @@ -1001,7 +1003,9 @@ static int join(struct scev *scev, struct env *acc, struct env *cur) for (i = 0; i < REGS_NUM; i++) { if (!same_exprs(scev, acc->reg2expr[i], cur->reg2expr[i])) { - id = mk_any(scev, acc->reg2expr[i], cur->reg2expr[i]); + /* no phi for a dead register: pruned SSA */ + id = reg_alive_at(env, i, idx) ? + mk_any(scev, acc->reg2expr[i], cur->reg2expr[i]) : UNKNOWN_EXPR_ID; if (id < 0) return id; acc->reg2expr[i] = id; @@ -1339,7 +1343,7 @@ static int join_successor(struct bpf_verifier_env *env, int cur_header, int succ return -ENOMEM; if (log_level2) memcpy(old_env, succ_env, sizeof(*old_env)); - err = join(scev, succ_env, cur_env); + err = join(env, succ_env, cur_env, succ_idx); if (err) return err; err = worklist_push(env, cur_header, succ_idx); -- 2.55.0