Re: [PATCH bpf-next 18/36] bpf: compute immediate dominators

["Alexei Starovoitov" <alexei.starovoitov@gmail.com>]

On Sat, Sep 26, 2026 at 07:20 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> +static int idoms_intersect(struct bpf_verifier_env *env, int a, int b)
> +{
> +	int *postorder_nums = env->cfg.postorder_nums;
> +	int *idoms = env->idoms;
> +
> +	while (a != b) {
> +		while (postorder_nums[a] < postorder_nums[b]) {
> +			a = idoms[a];
> +		}

This walks the idom chain one insn at a time.
For a prog that is a long run of
  if (err) goto out;
'out' has N predecessors and compute_subprog_idoms() calls this
for each of them. The k-th call walks back over k branches.
That's N^2/2 steps, and the outer loop runs at least twice.
All of it before do_check(), for every prog, loops or not.
Same issue as Daniel's commit 3852e19cb954 fixed just yesterday.

SCEV needs dominators only inside loops.
Can it be computed for insns with scc != 0 only ?
and probably a bound for a big loop body.