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

[Zoltan Somogyi]

On Wed, 26 Nov 2025 13:46:14 +1100, Julien Fischer <jfischer at opturion.com> wrote:
> 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?

options.m has always been one of the largest modules in the compiler, so
its compilation time was always among the slowest. And the switch to
a single optdb table, and the addition of the new options to control the
warnings that used to be always switched on, made the module bigger,
raising its size from 5x00 lines to 7x00.

I think the performance problems I have been fixing (of which this diff is the last,
since the profile now pretty flat) have always been there. The change to using
optdb just made them a bit worse.

Note that replacing the old help text, which was just lists of strings, with more
structured data did NOT slow down compilation significantly, because of
the introduction of from-ground-term scopes more than a decade ago.
Before the introduction of those scopes, it would have led to a *major*
slowdown.

> >     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/

Done.

> >     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.

Thanks.

Zoltan.