[m-rev.] For review by Fergus: Loop Invariant Hoisting

[Fergus Henderson]

On 16-Oct-2002, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> I've just done a bootcheck on an updated tree and all is well.

I presume you bootchecked with the optimization enabled?
(E.g. -O4 or greater?)

Also, what effect does this have on performance?  (E.g. for the compiler
itself, or the benchmarks in the `bench' directory).  We don't want to
enable the optimization by default if it ends up making performance worse.
It would be a good idea to run some benchmarks to double-check that the
intended optimization really does improve things.

How much space cost does it have?
Should it be disabled if --optimize-space is specified?

> Added loop-invariant hoisting optimization.

This is worth mentioning in the NEWS file.

> options.m:
>       Added bool option --loop-invariants (default `no').
>       This optimization is set at -O4.

The new option should be documented in doc/user_guide.texi.

Also, the new file loop_inv.m should be documented in
compiler/notes/compiler_design.html.

> follow_code.m:
> 	Changed the interface to move_follow_code_in_proc to support
> 	introduction of the loop invariant hoisting optimization.
...
> passes_aux.m:
> 	Minor changes to support introduction of optmimization.

To make it clearer why adding loop invariant hoisting required
modifying follow_code, that would be better phrased as

	passes_aux.m:
		Minor changes to support introduction of the loop
		invariant hoisting optimization.

	follow_code.m:
		Update to reflect the new interface to passes_aux.m.

> Index: compiler/liveness.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/liveness.m,v
> retrieving revision 1.121
> diff -u -r1.121 liveness.m
> --- compiler/liveness.m	30 Jul 2002 08:25:02 -0000	1.121
> +++ compiler/liveness.m	16 Oct 2002 01:58:25 -0000
> @@ -212,14 +212,17 @@
>  	live_info_init(ModuleInfo, TypeInfoLiveness, VarTypes, TVarMap, VarSet,
>  		LiveInfo),
>  
> +	globals__lookup_int_option(Globals, debug_liveness, DebugLiveness),
> +	pred_id_to_int(PredId, PredIdInt),
> +	maybe_write_progress_message("\nbefore liveness",
> +		DebugLiveness, PredIdInt, Goal0, VarSet, ModuleInfo, IO0, IO0b),
> +
>  	initial_liveness(ProcInfo1, PredId, ModuleInfo, Liveness0),
>  	detect_liveness_in_goal(Goal0, Liveness0, LiveInfo,
>  		_, Goal1),
>  
> -	globals__lookup_int_option(Globals, debug_liveness, DebugLiveness),
> -	pred_id_to_int(PredId, PredIdInt),
>  	maybe_write_progress_message("\nafter liveness",
> -		DebugLiveness, PredIdInt, Goal1, VarSet, ModuleInfo, IO0, IO1),
> +		DebugLiveness, PredIdInt, Goal1, VarSet, ModuleInfo, IO0b, IO1),

Rather than using "IO0b", please renumber the IO* variables.
("IO0b" is OK for a quick hack, but for the CVS repository we
have higher standards ;-)

> Index: compiler/loop_inv.m
> ===================================================================
> RCS file: compiler/loop_inv.m
> diff -N compiler/loop_inv.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ compiler/loop_inv.m	16 Oct 2002 04:33:38 -0000
> @@ -0,0 +1,1333 @@
> +%------------------------------------------------------------------------------%
> +% loop_inv.m
> +% Ralph Becket <rbeck at microsoft.com>
> +% Thu Nov  8 12:05:29 EST 2001
> +% vim: ft=mercury ff=unix ts=4 sw=4 et tw=0 wm=0

"ff=unix" is not appropriate here.  That might do the wrong thing on
non-Unix systems.

Why "tw=0 wm=0"?

It would be nicer to spell out "et" as "expandtab", as is done in runtime/*.h.
(Do the other options have long names too?)

> +hoist_loop_invariants(PredId, ProcId, PredInfo, ProcInfo0, ProcInfo,
> +        ModuleInfo0, ModuleInfo) :-
> +
> +    ( if
> +
> +            % We only want to apply this optimization to pure preds (e.g.
> +            % benchmark_det_loop).

Did you mean "not e.g. benchmark_det_loop".
              ^^^

> +invariant_goal_candidates_handle_non_recursive_call(
> +        Goal @ (_GoalExpr - GoalInfo), IGCs) =
> +    ( if   not model_non(GoalInfo),
> +           purity__goal_info_is_pure(GoalInfo)
> +      then IGCs ^ path_candidates := [Goal | IGCs ^ path_candidates]
> +      else IGCs
> +    ).

The documentation says it handles only model_det,
but this code seems to handle model_semi as well.

> +    % A constant construction is a construction unification with no
> +    % arguments or which is constructed from a statically initialized
> +    % constant.
> +    %
> +    % NOTE: we could do better, but it's not clear it's worth it.

I don't understand the comment.  How could we do better?

> +:- pred const_construction(hlds_goal).
> +:- mode const_construction(in) is semidet.
> +
> +const_construction(GoalExpr - _GoalInfo) :-
> +    Construction = GoalExpr ^ unify_kind,
> +    (   Construction ^ construct_args = []
> +    ;   Construction ^ construct_how  = construct_statically(_)
> +    ).

The "construct_how" flag is not valid until stage 60
(and only for the MLDS back-end).  This code is running in stage 34.
So it won't have the desired effect.

As a result, this optimization may end up hoisting out invariant
terms which would get contructed statically anyway; in which case
the main effect is an increase in code size.


I don't understand why const_goals (goals without any inputs)
are not hoisted.


The change seems fine apart from the issues raised above.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------