Login
You're viewing the functional.cafe public feed.

Replies

  • Oct 30, 2026, 5:32 PM

    @giomasce Less snarky: I think they end up being pretty similar algorithms at the end of the day, just different formulations. We do the same sort of topological sorting, etc. I think the primary difference is in how you reason about the blocks and about the path variables.

    I’ve considered switching Mesa to a tag that’s just the next block index. Right now, it’s a series of Booleans for which of the subsequent branches need to be taken. This saves you having to do a comparison against block indices before branching but means you have a bunch of Booleans live. It’s a trade off.

    💬 1🔄 0⭐ 0
  • Oct 30, 2026, 6:09 PM

    @gfxstrand I don't see why they'd end up being similar algorithms, but there is a good chance the problem is just me not understanding enough Hans-Kristian's algorithm.

    💬 1🔄 0⭐ 0
  • Oct 30, 2026, 6:22 PM

    @giomasce I think Hans-Kristian's blog post does a better job of explaining the frustration than the algorithm. 😅 (Which makes for a fine blog post, too!) The Mesa one ends up making a lot of similar choices. We just don't use a switch.

    I think the biggest difference is how the algorithms reason about the CFG. The Mesa algorithm (and I think HK's as well) do so from more of a graph/dominance perspective while the blog post you linked seems to be reasoning more from structure and trying find it in the node mess.

    But that may also be me not understanding the stackifier algorithm.

    But at the end of the day, there are a lot of common principals:

    1. back-edges mean loops
    2. topological sort to order blocks and group them into which things might come next.
    3. If irreducible, add a dummy loop to sort it out.
    💬 0🔄 0⭐ 0