[m-rev.] for review: reduce algorithmic complexity in frameopt

[Julien Fischer]

On Wed, 26 Nov 2025 at 03:09, Zoltan Somogyi <zoltan.somogyi at runbox.com>
wrote:

> Eliminate mostly-duplicate work in frameopt.m.
>
> compiler/frameopt.m:
>     The key decision in frame optimization is "which basic blocks need
>     a stack frame"?
>
>     One aspect of this decision is that if a block needs a frame,
>     then all successors of that block will get a frame. We therefore
>     unconditionally propagate the need for a frame forwards.
>
>     Another aspect is that if all the successors of a block need a frame,
>     then it is better for that block to allocate a frame than for
>     all its successors to do so, since this saves space, and does not
>     cost any time. We therefore *conditionally* propagate the need
>     for a frame backwards.
>
>     This diff speeds up conditional propagation to predecessors
>     by processing each predecessor just once, which reduces the complexity
>     of the algorithm from quadratic to linear. This speeds up the
compilation
>     of options.m by about 13%.

Has compilation of options.m always had these performance problems or have
some
of the recent changes to that module exposed them?

>     This change can change the output slightly (because the result of the
>     "do all successors of this predicate need a frame" test can change
>     as we learn more about frames), but it seems that in practice, this
>     happens only very rarely, and even then its impact on the performance
>     of the generate code is negligible.

s/generate/generated/

>     The code doing propagation to successors already had a mechanism
>     to handle each block just once. Speed up this mechanism also by
>     switching the "have we done this block already" test from using
>     plain sets (O(N) lookup) to using set_tree234s (O(log(N)) lookup).
>
>     Also improve some minor aspects of programming style.
>

That looks fine otherwise.

Julien.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20251126/62b1de5b/attachment.html>