[m-dev.] for review: --dead-code

[Fergus Henderson]

On 19-Jul-2000, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> For review by anyone, but I would like Fergus to look at the code of the
> predicate dead_code__adjust_where_needed.
> 
> Add a new optimization, enabled by the option --dead-code. This optimization
> removes goals whose outputs are not used at all, and moves goals whose outputs
> are only used on some computation branches to the starts of those branches,
> so they do not need to be executed on other branches.

I don't think "dead code" is a good name for that optimization (both
for the option name and the module name).  The term "dead code"
normally refers to code that cannot be reached, whereas in this case
you're talking about code which can be reached, but which doesn't do
anything useful.  And that term really doesn't cover the part of the
optimization where you move code rather than removing it.

This transformation is more like a static version of lazy evaluation.
Perhaps `--semi-lazy-code'?

One potential problem with this optimization as written is that it can
increase code size, by duplicating the same goal in more than one
branch.  It would be a good idea to have a version of it which only
did the transformation if the code was used in at most one branch.
This would be particularly appropriate in the case when `--opt-space'
is enabled.

It might also be useful to have a version which only does the
transformation if the code is used in zero branches, i.e. only does
code elimination rather than moving code; that version could be
allowed for the case where the user specifies `--no-fully-strict
--no-reorder-conj', whereas the other versions would require
both `--no-fully-strict' and `--reorder-conj'.

> compiler/options.m:
> 	Define the --dead-code option.

The new option should be documented, both here and in doc/user_guide.texi.

(If there is some reason why the documentation should not be
exposed to users yet, the documentation should still be added,
commented out, together with an explanation of why it is commented out.)

> +dead_code__process_proc_msg(PredId, ProcId, ProcInfo0, ProcInfo,
> +		ModuleInfo0, ModuleInfo) -->
> +	globals__io_lookup_bool_option(very_verbose, VeryVerbose),
> +	globals__io_lookup_int_option(vn_fudge, Levels),

This undocumented `vn_fudge' option is very mysterious,
and the use of it here (rather than in value numbering)
is even more mysterious.

At very least you ought to document what is going on here.

> +dead_code__process_proc(ProcInfo0, ProcInfo, ModuleInfo0, ModuleInfo,
> +		Levels, Successful) :-
...
> +	module_info_globals(ModuleInfo0, Globals),
> +	globals__lookup_bool_option(Globals, reorder_conj, ReorderConj),
> +	globals__lookup_bool_option(Globals, fully_strict, FullyStrict),
> +	(
> +		( ReorderConj = yes
> +		; FullyStrict = yes
> +		)
> +	->
> +		MoveAny = no

Shouldn't you be checking `ReorderConj = no' there
rather than `ReorderConj = yes'?

> +% This is the predicate responsible for ensuring that the act of optimizing
> +% away the execution of a goal on some or all computation paths changes the
> +% operational semantics only in ways that are explicitly permitted by the
> +% programmer.
> +
> +:- pred dead_code__adjust_where_needed(hlds_goal::in, bool::in,
> +	where_needed::in, where_needed::out) is det.
> +
> +dead_code__adjust_where_needed(Goal, MoveAny, WhereInfo0, WhereInfo) :-
> +	(
> +		Goal = GoalExpr - GoalInfo,
> +		(
> +				% Do not move goals that can fail, since
> +				% doing so can cause execution to reach goals
> +				% it shouldn't, and those goals may have
> +				% undesirable behavior (e.g. infinite loops).
> +			goal_info_get_determinism(GoalInfo, Detism),
> +			dead_code__detism_is_moveable(Detism, no)
> +		;
> +				% Do not move impure or semipure goals,
> +				% since their ordering wrt other such goals
> +				% must be preserved.
> +			goal_info_get_features(GoalInfo, Features),
> +			( set__member((impure), Features)
> +			; set__member((semipure), Features)
> +			)

I don't think this is sufficient.
Here you check that you don't move an impure goal across a pure goal.
But doing the converse, i.e. moving a pure goal across an impure goal,
is equally bad, and this test won't prevent that.

> +:- pred dead_code__cannot_diverge(hlds_goal::in) is semidet.

There's already a predicate code_aux__goal_cannot_loop
which does the same thing as this one, so you should
use that rather than duplicating the logic here.

> +dead_code__cannot_diverge(unify(_, _, _, _, _) - _).

Complicated unifications can diverge.
I guess at this point complicated unifications have already been
eliminated, but it would be nicer to check for that case here anyway,
IMHO.

goal_path.m:
> +fill_expr_slots(switch(Var, B, Cases0, D), Path0, SlotInfo,
> +		switch(Var, B, Cases, D)) :-
> +	SlotInfo = slot_info(VarTypes, ModuleInfo),
> +	module_info_types(ModuleInfo, TypeTable),
> +	map__lookup(VarTypes, Var, Type),
> +	(
> +		type_to_type_id(Type, TypeId, _),
> +		( map__search(TypeTable, TypeId, TypeDefn) ->
> +			hlds_data__get_type_defn_body(TypeDefn, Body),
> +			Body = du_type(_, ConsTable, _, _),
> +			map__count(ConsTable, Count)
> +		; TypeId = unqualified("character") - 0 ->
> +			char__max_char_value(MaxCharValue),
> +			char__min_char_value(MinCharValue),
> +			Count = MaxCharValue - MinCharValue + 1
> +		;
> +			Count = -1
> +		)

There should be an XXX comment here like the one in
`switch_covers_all_cases' in switch_detection.m.  In fact a lot
of the code here is doing the same thing as code in
`switch_covers_all_cases'; it would be much better to factor out
the common code into a separate subroutine, called e.g.
`num_alternatives_in_type'.

> +++ compiler/hlds_pred.m	2000/07/18 05:54:06
> @@ -20,7 +20,7 @@
>  :- implementation.
>  
>  :- import_module code_aux, goal_util, make_hlds, prog_util.
> -:- import_module mode_util, type_util, options.
> +:- import_module inst_match, mode_util, type_util, options.
>  :- import_module int, string, require, assoc_list.
>  
>  %-----------------------------------------------------------------------------%
> @@ -1408,6 +1408,18 @@
>  		list(type), list(prog_var), proc_info).
>  :- mode proc_info_create_vars_from_types(in, in, out, out) is det.
>  
> +	% Given a procedure, return a list of all its headvars whose inst
> +	% is changed by the procedure.
> +:- pred proc_info_changed_inst_head_vars(module_info, proc_info,
> +		list(prog_var)).
> +:- mode proc_info_changed_inst_head_vars(in, in, out) is det.
> +
> +	% Given a procedure, return a list of all its headvars whose inst
> +	% is not changed by the procedure.
> +:- pred proc_info_unchanged_inst_head_vars(module_info, proc_info,
> +		list(prog_var)).
> +:- mode proc_info_unchanged_inst_head_vars(in, in, out) is det.

The comments here are misleading...

> +proc_info_changed_inst_head_vars(ModuleInfo, ProcInfo, ChangedInstHeadVars) :-
> +	proc_info_headvars(ProcInfo, HeadVars),
> +	proc_info_argmodes(ProcInfo, ArgModes),
> +	assoc_list__from_corresponding_lists(HeadVars, ArgModes, HeadVarModes),
> +	IsInstChanged = lambda([VarMode::in, Var::out] is semidet, (
> +		VarMode = Var - Mode,
> +		mode_get_insts(ModuleInfo, Mode, Inst1, Inst2),
> +		\+ inst_matches_binding(Inst1, Inst2, ModuleInfo)

... since the implementation uses `inst_matches_binding',
which ignores uniqueness, and which fails for `any' insts.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------