From: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>
To: "Eduard Zingerman" <eddyz87@gmail.com>, <bpf@vger.kernel.org>
Cc: <andrii@kernel.org>, <daniel@iogearbox.net>, <kernel-team@fb.com>,
<yonghong.song@linux.dev>
Subject: Re: [PATCH bpf-next v2 23/43] bpf: add a min-heap for ordered analysis worklists
Date: Tue, 06 Oct 2026 16:53:09 +0000 [thread overview]
Message-ID: <DLXWU3H4P99Q.1RJN2ALJ3JTAX@gmail.com> (raw)
In-Reply-To: <20261004-scev-minimal-rebase-v2-23-f6254e29fdf2@gmail.com>
On Sun, Oct 04, 2026 at 06:38 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> SCEV needs to process pending basic blocks in reverse postorder.
> Provide a small integer min-heap whose comparator can order instruction
> indices by their CFG ranks.
Why not include/linux/min_heap.h ?
less() there takes 'void *args'.
worklist_push() checks discovered[] first, so an insn is pushed once
per loop. prog->len ints allocated in bpf_init_scev() are enough
and the push cannot fail.
next prev parent reply other threads:[~2026-10-06 16:53 UTC|newest]
Thread overview: 69+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-10-04 13:37 [PATCH bpf-next v2 00/43] bpf: use scalar evolution to widen bounded loops Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 01/43] bpf: represent stack access effects with arg_access_info Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:37 ` [PATCH bpf-next v2 02/43] bpf: describe helper stack accesses " Eduard Zingerman
2026-10-04 14:02 ` sashiko-bot
2026-10-04 13:37 ` [PATCH bpf-next v2 03/43] bpf: describe kfunc " Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 04/43] bpf: track may_write flags in liveness Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 05/43] bpf: summarize may write stack slots in insn_aux_data Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 06/43] bpf: summarize live " Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 07/43] bpf: summarize regs that may hold a frame pointer " Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 08/43] bpf: record write effects for atomic operations in liveness.c Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 09/43] bpf: add tnum_alignment() Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 10/43] bpf: add cnum{32,64}_union() Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 11/43] bpf: add cnum64_intersect_linear() Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 12/43] bpf: expose comparison opcode transformations Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:37 ` [PATCH bpf-next v2 13/43] bpf: allow subrange relations for PTR_TO_STACK in regsafe() Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 14/43] bpf: representation for intervals with steps Eduard Zingerman
2026-10-04 14:02 ` sashiko-bot
2026-10-04 14:40 ` bot+bpf-ci
2026-10-04 13:37 ` [PATCH bpf-next v2 15/43] bpf: varying offset access support for PTR_TO_BTF_ID pointers Eduard Zingerman
2026-10-04 15:11 ` bot+bpf-ci
2026-10-04 13:37 ` [PATCH bpf-next v2 16/43] bpf: save DFS postorder numbers for program instructions Eduard Zingerman
2026-10-04 13:37 ` [PATCH bpf-next v2 17/43] bpf: move the live-register and SCC printout to a standalone function Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 18/43] bpf: compute immediate dominators Eduard Zingerman
2026-10-04 13:50 ` sashiko-bot
2026-10-04 13:38 ` [PATCH bpf-next v2 19/43] bpf: compute loop hierarchy Eduard Zingerman
2026-10-04 14:40 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 20/43] bpf: add bpf_set_reg_range() Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 21/43] bpf: add bpf_mark_reg_known_scalar() Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 22/43] bpf: add bpf_reg_union() Eduard Zingerman
2026-10-04 13:59 ` sashiko-bot
2026-10-04 13:38 ` [PATCH bpf-next v2 23/43] bpf: add a min-heap for ordered analysis worklists Eduard Zingerman
2026-10-04 13:47 ` sashiko-bot
2026-10-06 16:53 ` Alexei Starovoitov [this message]
2026-10-04 13:38 ` [PATCH bpf-next v2 24/43] bpf: record basic-block ends in insn_aux_data Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 25/43] bpf: add bpf_split_cur_state() Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 26/43] bpf: add bpf_same_memory_origin() Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 27/43] bpf: allow precision backtracking between overlapping checkpoints Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 28/43] bpf: compute scalar evolution expressions for loops Eduard Zingerman
2026-10-04 14:00 ` sashiko-bot
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 29/43] bpf: use SCEV to widen bounded loops Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 30/43] bpf: avoid widening registers that hinder exact stack-slot tracking Eduard Zingerman
2026-10-04 14:02 ` sashiko-bot
2026-10-04 13:38 ` [PATCH bpf-next v2 31/43] bpf: bpf_func_state size optimization Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 32/43] selftests/bpf: __msg_next tag for matching messages on consecutive lines Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 33/43] selftests/bpf: bound UNIX socket path loops by sun_path size Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 34/43] selftests/bpf: test for stack-pointer subrange pruning Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 35/43] selftests/bpf: tests for may_write stack-liveness tracking Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 36/43] selftests/bpf: tests for may_def marks of atomic RMW operations Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 37/43] selftests/bpf: tests for map special cases in bpf_helper_stack_access_bytes() Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 38/43] selftests/bpf: tests for register base/step arithmetic Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 39/43] selftests/bpf: tests for register base/step state pruning Eduard Zingerman
2026-10-04 13:54 ` sashiko-bot
2026-10-04 13:38 ` [PATCH bpf-next v2 40/43] selftests/bpf: tests for varying offset access to PTR_TO_BTF_ID Eduard Zingerman
2026-10-04 13:38 ` [PATCH bpf-next v2 41/43] selftests/bpf: tests for loop hierarchy computation Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 42/43] selftests/bpf: tests for immediate dominator computation Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 13:38 ` [PATCH bpf-next v2 43/43] selftests/bpf: tests for SCEV analysis and loop widening Eduard Zingerman
2026-10-04 14:24 ` bot+bpf-ci
2026-10-04 20:04 ` [syzbot ci] Re: bpf: use scalar evolution to widen bounded loops syzbot ci
2026-10-06 16:40 ` [PATCH bpf-next v2 00/43] " patchwork-bot+netdevbpf
2026-10-06 16:45 ` Alexei Starovoitov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=DLXWU3H4P99Q.1RJN2ALJ3JTAX@gmail.com \
--to=alexei.starovoitov@gmail.com \
--cc=andrii@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=kernel-team@fb.com \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox