[m-rev.] for review: --split-switch-arms

[Julien Fischer]

On Mon, 24 Jul 2023, Zoltan Somogyi wrote:

> Add new optimization option --split-switch-arms.

...

> diff --git a/compiler/notes/compiler_design.html b/compiler/notes/compiler_design.html
> index 4f725ee5e..cefe0acdb 100644
> --- a/compiler/notes/compiler_design.html
> +++ b/compiler/notes/compiler_design.html
> @@ -1376,6 +1376,13 @@ simplify.m is a package of submodules.
>      It also attempts to partially evaluate the correct calls,
>      essentially interpreting the format string at compile time, not runtime.
>      <li>
> +    split_switch_arms.m optimizes code in which one or more switches
> +    on a variable are nested inside one arm of a larger switch on the same
> +    variable. It does so by making all the distinctions between the cons_id
> +    of that outermost arm that any of the switches nested inside of it do.
> +    By splitting up that arm according to those distintions, it effectively

s/distintions/distinctions/

> +    replaces several switches with just one switch.
> +    <li>
>      simplify_proc.m handles the top-level processing of procedures
>      and their bodies.
>      <li>

...

> diff --git a/compiler/options.m b/compiler/options.m
> index 284a50b35..3b2663678 100644
> --- a/compiler/options.m
> +++ b/compiler/options.m

...

> @@ -5951,6 +5964,11 @@ options_help_hlds_hlds_optimization(Stream, !IO) :-
>          "\tDo not attempt to interpret the format string in calls to",
>          "\tstring.format and related predicates at compile time;",
>          "\talways leave this to be done at runtime.",
> +        "--split-switch-arms",
> +        "\tWhen a switch on a variable has an inner switch on that",
> +        "\tsame variable inside one of its arm, split up that arm of the",

its arms

> +        "\touter switch along the same lines, effectively inlining",
> +        "\tthe inner switch.",
>          "--optimize-duplicate-calls",
>          "\tOptimize away multiple calls to a predicate",
>          "\twith the same input arguments.",

...

> --- a/compiler/simplify_proc.m
> +++ b/compiler/simplify_proc.m
> diff --git a/compiler/simplify_tasks.m b/compiler/simplify_tasks.m
> index 1eafd6a11..85179b52f 100644
> --- a/compiler/simplify_tasks.m
> +++ b/compiler/simplify_tasks.m
> @@ -98,9 +98,17 @@
>              % on a data structure that the code *does* refer to using
>              % state variable notation.
> 
> -    ;       simptask_warn_no_solution_disjunct.
> +    ;       simptask_warn_no_solution_disjunct
>              % Warn about disjuncts that can have no solution.
> 
> +    ;       simptask_split_switch_arms.
> +            % Invoke split_switch_arms.m to perform its transformation,
> +            % if the main part of simplification discovers that has some

that it has some

> +            % redundant switches to optimize.
> +            %
> +            % For the details of the transformation done by
> +            % split_switch_arms.m, see its top-of-module comment.
> +
>  %---------------------%
>
>  :- type maybe_warn_simple_code

...

> diff --git a/compiler/split_switch_arms.m b/compiler/split_switch_arms.m
> index e69de29bb..a1c9ed783 100644
> --- a/compiler/split_switch_arms.m
> +++ b/compiler/split_switch_arms.m
> @@ -0,0 +1,579 @@
> +%----------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sw=4 et
> +%----------------------------------------------------------------------------%
> +% Copyright (C) 2023 The Mercury team.
> +% This file may only be copied under the terms of the GNU General
> +% Public License - see the file COPYING in the Mercury distribution.
> +%----------------------------------------------------------------------------%
> +%
> +% File: split_switch_arms.m.
> +%
> +% This module implements a program transformation that replaces code like this:
> +%
> +%   (
> +%       ( X = f1
> +%       ; X = f2
> +%       ; X = f3
> +%       ; X = f4
> +%       ),
> +%       <initial code to handle f1,f2,f3,f4>,
> +%       (
> +%           X = f1,
> +%           <code to handle f1>
> +%       ;
> +%           ( X = f2
> +%           ; X = f3
> +%           ),
> +%           <code to handle f2,f3>
> +%       ;
> +%           X = f4,
> +%           <code to handle f4>
> +%       ),
> +%       <final code to handle f1,f2,f3,f4>
> +%   ;
> +%       X = f5,
> +%       <code to handle f5>
> +%   )
> +%
> +% with code like this:
> +%   (
> +%       X = f1,
> +%       <initial code to handle f1,f2,f3,f4>,
> +%       <code to handle f1>,
> +%       <final code to handle f1,f2,f3,f4>
> +%   ;
> +%       ( X = f2
> +%       ; X = f3
> +%       ),
> +%       <initial code to handle f1,f2,f3,f4>,
> +%       <code to handle f2,f3>,
> +%       <final code to handle f1,f2,f3,f4>
> +%   ;
> +%       X = f4,
> +%       <initial code to handle f1,f2,f3,f4>,
> +%       <code to handle f4>,
> +%       <final code to handle f1,f2,f3,f4>
> +%   ;
> +%       X = f5,
> +%       <code to handle f5>
> +%   )
> +%
> +% The idea is that if inside a switch on a variable, there are other switches
> +% on that same variable that subdivide the set of cons_ids even further, then
> +% we do the following.
> +%
> +% - We partition the cons_ids of the top-level switch arm to make all the
> +%   distinctions between its cons_ids that any of the (one or more) switches
> +%   on the same variable inside the top-level switch arm make,
> +%
> +%   In this case, we would partition {f1,f2,f3,f4} into three sets:
> +%   {f1}, {f2,f3} and {f4}.
> +%
> +% - We replace the original switch arm with a separate switch arm for each
> +%   partition.
> +%
> +%   In this case, this would replace the arm for {f1,f2,f3,f4}
> +%   with three arms for {f1}, {f2,f3} and {f4} respectively.
> +%   The three arms would initially contain the same code as the original
> +%   switch arm. This would mean that each would contain the whole of
> +%   nested switch on X with the three arms for {f1}, {f2,f3} and {f4}.
> +%
> +% - We restrict the goal in each of the resulting switch arms to refer to
> +%   only the cons_ids of its own partion in any nested switches on the
> +%   original switched-on variable, and we then simplify away any trivial
> +%   switches generated by this process.
> +%
> +%   In this case, in the new {f1}-only arm of the top switch, would replace
> +%   the inner switch on X with the arms for {f1}, {f2,f3} and {f4}
> +%   with just the arm for {f1}, and then optimize away the now-unnecessary
> +%   switch wrapper around the goal inside that arm. We would do the same
> +%   with the other two arms.

I suggest adding the rationale for performing this transformation here
(i.e. from the log message).

That looks fine otherwise.

Julien.