[m-dev.] for review: --delay-constructs

Zoltan Somogyi zs at cs.mu.OZ.AU
Thu Mar 8 18:10:08 AEDT 2001
Previous message: [m-dev.] for review: library/Mmakefile +=
Next message: [m-dev.] for review: --delay-constructs
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
For review by anyone. This optimization compensates for the lack of
construction delays in the eager code generator. On tests/benchmark/query,
the eager code generator used to take a lot longer than the lazy code
generator; this optimization makes them equally fast. (The constraint
propagation pass, which should optimize similar code, does not transform
that test case.)

compiler/delay_construct.m:
	A new module for delaying construction unifications past builtins in
	conjunctions that can fail. The idea is to incur the cost of memory
	allocation only if those tests succeed. This can speed up code (e.g.
	tests/benchmarks/query) by integer factors.

compiler/options.m:
doc/user_guide.texi:
	Add a new option, --delay-construct, that switches on the new
	optimization.

compiler/mercury_compile.m:
	Invoke the new optimization if the option calls for it.

Zoltan.

cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/delay_construct.m
===================================================================
RCS file: delay_construct.m
diff -N delay_construct.m
--- /dev/null	Fri Dec  1 02:25:58 2000
+++ delay_construct.m	Wed Mar  7 17:23:35 2001
@@ -0,0 +1,225 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2001 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: delay_construct.m
+%
+% Author: zs.
+%
+% This module transforms sequences of goals in procedure bodies.
+% It looks for construction unification followed by primitive goals,
+% at least one of which can fail, and none of which take the variable
+% representing the cell as their input. Such code sequences cause the
+% cell to be constructed even if the following goal would fail, which is
+% wasteful. This module therefore reorders the sequence, moving the
+% construction unification past all the semidet primitives it can.
+%
+% The reason we don't move the construction past calls or composite goals
+% is that this may require storing the input arguments of the construction on
+% the stack, which may cause a slowdown bigger than the speedup available from
+% not having to construct the cell on some execution paths.
+
+%-----------------------------------------------------------------------------%
+
+:- module delay_construct.
+
+:- interface.
+
+:- import_module hlds_module, hlds_pred.
+:- import_module io.
+
+:- pred delay_construct_proc(pred_id::in, proc_id::in, module_info::in,
+	proc_info::in, proc_info::out, io__state::di, io__state::uo) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module prog_data, hlds_data, hlds_goal, passes_aux, globals.
+:- import_module bool, list, set, std_util, require.
+
+%-----------------------------------------------------------------------------%
+
+delay_construct_proc(PredId, ProcId, ModuleInfo, ProcInfo0, ProcInfo) -->
+	write_proc_progress_message("% Delaying construction unifications in ",
+		PredId, ProcId, ModuleInfo),
+	globals__io_get_globals(Globals),
+	{ module_info_pred_info(ModuleInfo, PredId, PredInfo) },
+	{ delay_construct_proc_no_io(ProcInfo0, PredInfo, Globals,
+		ProcInfo) }.
+
+:- pred delay_construct_proc_no_io(proc_info::in, pred_info::in, globals::in,
+	proc_info::out) is det.
+
+delay_construct_proc_no_io(ProcInfo0, PredInfo, Globals, ProcInfo) :-
+	body_should_use_typeinfo_liveness(PredInfo, Globals,
+		BodyTypeinfoLiveness),
+	proc_info_vartypes(ProcInfo0, VarTypes),
+	proc_info_typeinfo_varmap(ProcInfo0, TypeInfoVarMap),
+	DelayInfo = delay_construct_info(BodyTypeinfoLiveness,
+		VarTypes, TypeInfoVarMap),
+	proc_info_goal(ProcInfo0, Goal0),
+	delay_construct_in_goal(Goal0, DelayInfo, Goal),
+	proc_info_set_goal(ProcInfo0, Goal, ProcInfo).
+
+:- type delay_construct_info
+	--->	delay_construct_info(
+			body_typeinfo_liveness	:: bool,
+			vartypes		:: vartypes,
+			type_info_varmap	:: type_info_varmap
+		).
+
+%-----------------------------------------------------------------------------%
+
+:- pred delay_construct_in_goal(hlds_goal::in, delay_construct_info::in,
+	hlds_goal::out) is det.
+
+delay_construct_in_goal(GoalExpr0 - GoalInfo0, DelayInfo, Goal) :-
+	(
+		GoalExpr0 = conj(Goals0),
+		goal_info_get_determinism(GoalInfo0, Detism),
+		( determinism_components(Detism, can_fail, _) ->
+			delay_construct_in_conj(Goals0, DelayInfo,
+				set__init, [], Goals)
+		;
+			delay_construct_in_goals(Goals0, DelayInfo, Goals)
+		),
+		conj_list_to_goal(Goals, GoalInfo0, Goal)
+	;
+		GoalExpr0 = par_conj(Goals0, SM),
+		delay_construct_in_goals(Goals0, DelayInfo, Goals),
+		Goal = par_conj(Goals, SM) - GoalInfo0
+	;
+		GoalExpr0 = disj(Goals0, SM),
+		delay_construct_in_goals(Goals0, DelayInfo, Goals),
+		Goal = disj(Goals, SM) - GoalInfo0
+	;
+		GoalExpr0 = not(NegGoal0),
+		delay_construct_in_goal(NegGoal0, DelayInfo, NegGoal),
+		Goal = not(NegGoal) - GoalInfo0
+	;
+		GoalExpr0 = switch(Var, CanFail, Cases0, SM),
+		delay_construct_in_cases(Cases0, DelayInfo, Cases),
+		Goal = switch(Var, CanFail, Cases, SM) - GoalInfo0
+	;
+		GoalExpr0 = if_then_else(Vars, Cond0, Then0, Else0, SM),
+		delay_construct_in_goal(Cond0, DelayInfo, Cond),
+		delay_construct_in_goal(Then0, DelayInfo, Then),
+		delay_construct_in_goal(Else0, DelayInfo, Else),
+		Goal = if_then_else(Vars, Cond, Then, Else, SM) - GoalInfo0
+	;
+		GoalExpr0 = some(Var, CanRemove, SubGoal0),
+		delay_construct_in_goal(SubGoal0, DelayInfo, SubGoal),
+		Goal = some(Var, CanRemove, SubGoal) - GoalInfo0
+	;
+		GoalExpr0 = generic_call(_, _, _, _),
+		Goal = GoalExpr0 - GoalInfo0
+	;
+		GoalExpr0 = call(_, _, _, _, _, _),
+		Goal = GoalExpr0 - GoalInfo0
+	;
+		GoalExpr0 = unify(_, _, _, _, _),
+		Goal = GoalExpr0 - GoalInfo0
+	;
+		GoalExpr0 = pragma_foreign_code(_, _, _, _, _, _, _),
+		Goal = GoalExpr0 - GoalInfo0
+	;
+		GoalExpr0 = bi_implication(_, _),
+		% these should have been expanded out by now
+		error("delay_construct_in_goal: unexpected bi_implication")
+	).
+
+%-----------------------------------------------------------------------------%
+
+% We maintain a list of delayed construction unifications, and the set of
+% variables they define.
+%
+% When we find other construction unifications, we add them to the list.
+% It does not matter if they depend on other delayed construction unifications;
+% when we put them back into the conjunction, we do so in the original order.
+%
+% There are several reasons why we may not be able to delay a construction
+% unification past a conjunct. The conjunct may not be a primitive goal,
+% or it may be impure; in either case, we must insert all the delayed
+% construction unifications before it. The conjunct may also require the value
+% of a variable defined by a construction unification. In such cases, we could
+% drop before that goal only the construction unifications that define the
+% variables needed by the conjunct, either directly or indirectly through 
+% the values required by some of those construction unifications. However,
+% separating out this set of delayed constructions from the others would
+% require somewhat complex code, and it is not clear that there would be any
+% significant benefit. We therefore insert *all* the delayed constructions
+% before a goal if the goal requires *any* of the variables bound by the
+% constructions.
+
+:- pred delay_construct_in_conj(list(hlds_goal)::in, delay_construct_info::in,
+	set(prog_var)::in, list(hlds_goal)::in, list(hlds_goal)::out) is det.
+
+delay_construct_in_conj([], _, _, RevDelayedGoals, DelayedGoals) :-
+	list__reverse(RevDelayedGoals, DelayedGoals).
+delay_construct_in_conj([Goal0 | Goals0], DelayInfo,
+		ConstructedVars0, RevDelayedGoals0, Goals) :-
+	(
+		Goal0 = unify(_, _, _, Unif, _) - _,
+		Unif = construct(Var, _, Args, _, _, _, _),
+		Args = [_ | _]	% We are constructing a cell, not a constant
+	->
+		set__insert(ConstructedVars0, Var, ConstructedVars1),
+		RevDelayedGoals1 = [Goal0 | RevDelayedGoals0],
+		delay_construct_in_conj(Goals0, DelayInfo,
+			ConstructedVars1, RevDelayedGoals1, Goals)
+	;
+		Goal0 = GoalExpr0 - GoalInfo0,
+		delay_construct_skippable_expr(GoalExpr0),
+		goal_info_get_nonlocals(GoalInfo0, NonLocals),
+		proc_info_maybe_complete_with_typeinfo_vars(NonLocals,
+			DelayInfo ^ body_typeinfo_liveness,
+			DelayInfo ^ vartypes,
+			DelayInfo ^ type_info_varmap, CompletedNonLocals),
+		set__intersect(CompletedNonLocals, ConstructedVars0,
+			Intersection),
+		set__empty(Intersection),
+		\+ goal_info_has_feature(GoalInfo0, impure),
+		\+ goal_info_has_feature(GoalInfo0, semipure)
+	->
+		delay_construct_in_conj(Goals0, DelayInfo, ConstructedVars0,
+			RevDelayedGoals0, Goals1),
+		Goals = [Goal0 | Goals1]
+	;
+		list__reverse(RevDelayedGoals0, DelayedGoals),
+		delay_construct_in_conj(Goals0, DelayInfo, set__init, [],
+			Goals1),
+		list__append(DelayedGoals, [Goal0 | Goals1], Goals)
+	).
+
+:- pred delay_construct_skippable_expr(hlds_goal_expr::in) is semidet.
+
+delay_construct_skippable_expr(GoalExpr) :-
+	(
+		GoalExpr = unify(_, _, _, _, _)
+	;
+		GoalExpr = call(_, _, _, inline_builtin, _, _)
+	).
+
+%-----------------------------------------------------------------------------%
+
+:- pred delay_construct_in_goals(list(hlds_goal)::in, delay_construct_info::in,
+	list(hlds_goal)::out) is det.
+
+delay_construct_in_goals([], _, []).
+delay_construct_in_goals([Goal0 | Goals0], DelayInfo, [Goal | Goals]) :-
+	delay_construct_in_goal(Goal0, DelayInfo, Goal),
+	delay_construct_in_goals(Goals0, DelayInfo, Goals).
+
+:- pred delay_construct_in_cases(list(case)::in, delay_construct_info::in,
+	list(case)::out) is det.
+
+delay_construct_in_cases([], _, []).
+delay_construct_in_cases([case(Cons, Goal0) | Cases0], DelayInfo,
+		[case(Cons, Goal) | Cases]) :-
+	delay_construct_in_goal(Goal0, DelayInfo, Goal),
+	delay_construct_in_cases(Cases0, DelayInfo, Cases).
+
+%-----------------------------------------------------------------------------%
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.197
diff -u -b -r1.197 mercury_compile.m
--- compiler/mercury_compile.m	2001/03/02 02:05:56	1.197
+++ compiler/mercury_compile.m	2001/03/07 04:57:31
@@ -38,7 +38,7 @@
 :- import_module check_typeclass, intermod, trans_opt, table_gen, (lambda).
 :- import_module type_ctor_info, termination, higher_order, accumulator.
 :- import_module inlining, deforest, dnf, magic, dead_proc_elim.
-:- import_module unused_args, unneeded_code, lco.
+:- import_module delay_construct, unused_args, unneeded_code, lco.
 
 	% the LLDS back-end
 :- import_module saved_vars, liveness.
@@ -1142,11 +1142,13 @@
 	mercury_compile__maybe_do_inlining(HLDS33, Verbose, Stats, HLDS34),
 	mercury_compile__maybe_dump_hlds(HLDS34, "34", "inlining"),
 
-	mercury_compile__maybe_deforestation(HLDS34, 
-			Verbose, Stats, HLDS36),
+	mercury_compile__maybe_deforestation(HLDS34, Verbose, Stats, HLDS36),
 	mercury_compile__maybe_dump_hlds(HLDS36, "36", "deforestation"),
 
-	mercury_compile__maybe_unused_args(HLDS36, Verbose, Stats, HLDS39),
+	mercury_compile__maybe_delay_construct(HLDS36, Verbose, Stats, HLDS37),
+	mercury_compile__maybe_dump_hlds(HLDS37, "37", "delay_construct"),
+
+	mercury_compile__maybe_unused_args(HLDS37, Verbose, Stats, HLDS39),
 	mercury_compile__maybe_dump_hlds(HLDS39, "39", "unused_args"),
 
 	mercury_compile__maybe_unneeded_code(HLDS39, Verbose, Stats, HLDS40),
@@ -2006,6 +2008,25 @@
 		list__foldl(AddProc, ProcIds, AditiPreds0, AditiPreds)
 	;
 		AditiPreds = AditiPreds0
+	).
+
+:- pred mercury_compile__maybe_delay_construct(module_info::in,
+	bool::in, bool::in, module_info::out, io__state::di, io__state::uo)
+	is det.
+
+mercury_compile__maybe_delay_construct(HLDS0, Verbose, Stats, HLDS) -->
+	globals__io_lookup_bool_option(delay_construct, DelayConstruct),
+	( { DelayConstruct = yes } ->
+		maybe_write_string(Verbose,
+			"% Delaying construction unifications ...\n"),
+		maybe_flush_output(Verbose),
+		process_all_nonimported_procs(
+			update_proc_io(delay_construct_proc),
+			HLDS0, HLDS),
+		maybe_write_string(Verbose, "% done.\n"),
+		maybe_report_stats(Stats)
+	;
+		{ HLDS0 = HLDS }
 	).
 
 :- pred mercury_compile__maybe_unused_args(module_info, bool, bool, module_info,
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.315
diff -u -b -r1.315 options.m
--- compiler/options.m	2001/03/05 03:35:26	1.315
+++ compiler/options.m	2001/03/08 07:04:11
@@ -341,6 +341,7 @@
 		;	constant_propagation
 		;	excess_assign
 		;	optimize_saved_vars
+		;	delay_construct
 		;	follow_code
 		;	prev_code
 		;	optimize_dead_procs
@@ -727,6 +728,7 @@
 	constant_propagation	-	bool(no),
 	excess_assign		-	bool(no),
 	optimize_saved_vars	-	bool(no),
+	delay_construct		-	bool(no),
 	prev_code		-	bool(no),
 	follow_code		-	bool(no),
 	optimize_unused_args	-	bool(no),
@@ -1122,6 +1124,8 @@
 long_option("optimize-constant-propagation", constant_propagation).
 long_option("optimize-saved-vars",	optimize_saved_vars).
 long_option("optimise-saved-vars",	optimize_saved_vars).
+long_option("delay-construct",		delay_construct).
+long_option("delay-constructs",		delay_construct).
 long_option("prev-code",		prev_code).
 long_option("follow-code",		follow_code).
 long_option("constraint-propagation",	constraint_propagation).
@@ -1512,6 +1516,7 @@
 opt_level(3, _, [
 %%%	optimize_copyprop	-	bool(yes),
 	optimize_saved_vars	-	bool(yes),
+	delay_construct		-	bool(yes),
 	optimize_unused_args	-	bool(yes),	
 	optimize_higher_order	-	bool(yes),
 	deforestation		-	bool(yes),
@@ -2427,6 +2432,9 @@
 		"--optimize-duplicate-calls",
 		"\tOptimize away multiple calls to a predicate",
 		"\twith the same input arguments.",
+		"--delay-constructs",
+		"\tReorder goals to move construction unifications after",
+		"\tprimitive goals that can fail.",
 		"--optimize-saved-vars",
 		"\tReorder goals to minimize the number of variables",
 		"\tthat have to be saved across calls.",
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing doc
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.245
diff -u -b -r1.245 user_guide.texi
--- doc/user_guide.texi	2001/03/05 03:35:33	1.245
+++ doc/user_guide.texi	2001/03/08 07:04:13
@@ -4127,6 +4127,11 @@
 Optimize away multiple calls to a predicate with the same input arguments.
 
 @sp 1
+ at item --delay-constructs
+Reorder goals to move construction unifications after
+primitive goals that can fail.
+
+ at sp 1
 @item --optimize-saved-vars
 Reorder goals to minimize the number of variables
 that have to be saved across calls.
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/stream
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing java
cvs diff: Diffing library
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
Previous message: [m-dev.] for review: library/Mmakefile +=
Next message: [m-dev.] for review: --delay-constructs
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the developers mailing list