[m-dev.] for review: convert MLDS assignments into initializers

Fergus Henderson fjh at cs.mu.OZ.AU
Thu Feb 8 22:40:25 AEDT 2001


For review by Julien.

----------

Estimated hours taken: 1.5

Add an MLDS optimization to convert assignments into
initializers.

compiler/options.m:
doc/user_guide.texi:
	Add new option `--optimize-initializations'.
	
compiler/ml_optimize.m:
	Implement the new optimization.

compiler/ml_elim_nested.m:
compiler/ml_util.m:
	Move initializer_contains_var, rval_contains_var and related
	predicates from ml_elim_nested.m to ml_util.m, for use by
	ml_optimize.m.

Workspace: /home/hg/fjh/mercury
Index: compiler/ml_elim_nested.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_elim_nested.m,v
retrieving revision 1.20
diff -u -d -r1.20 ml_elim_nested.m
--- compiler/ml_elim_nested.m	2000/12/21 03:10:10	1.20
+++ compiler/ml_elim_nested.m	2001/02/08 09:41:48
@@ -134,7 +134,7 @@
 :- implementation.
 :- import_module bool, int, list, std_util, string, require.
 
-:- import_module ml_code_util.
+:- import_module ml_code_util, ml_util.
 
 % the following imports are needed for mangling pred names
 :- import_module hlds_pred, prog_data, prog_out.
@@ -1247,13 +1247,8 @@
 % maybe_statement_contains_var:
 % statements_contains_var:
 % statement_contains_var:
-% atomic_stmt_contains_var:
-% rvals_contains_var:
-% maybe_rval_contains_var:
-% rval_contains_var:
 % trail_op_contains_var:
-% lvals_contains_var:
-% lval_contains_var:
+% atomic_stmt_contains_var:
 %	Succeeds iff the specified construct contains a reference to
 %	the specified variable.
 %
@@ -1284,19 +1279,6 @@
 		FieldDefns),
 	defns_contains_var(FieldDefns, Name).
 
-:- pred initializer_contains_var(mlds__initializer, mlds__var).
-:- mode initializer_contains_var(in, in) is semidet.
-
-% initializer_contains_var(no_initializer, _) :- fail.
-initializer_contains_var(init_obj(Rval), Name) :-
-	rval_contains_var(Rval, Name).
-initializer_contains_var(init_struct(Inits), Name) :-
-	list__member(Init, Inits),
-	initializer_contains_var(Init, Name).
-initializer_contains_var(init_array(Inits), Name) :-
-	list__member(Init, Inits),
-	initializer_contains_var(Init, Name).
-
 :- pred maybe_statement_contains_var(maybe(mlds__statement), mlds__var).
 :- mode maybe_statement_contains_var(in, in) is semidet.
 
@@ -1444,53 +1426,6 @@
 target_code_component_contains_var(name(EntityName), VarName) :-
 	EntityName = qual(ModuleName, data(var(UnqualVarName))),
 	VarName = qual(ModuleName, UnqualVarName).
-
-:- pred rvals_contains_var(list(mlds__rval), mlds__var).
-:- mode rvals_contains_var(in, in) is semidet.
-
-rvals_contains_var(Rvals, Name) :-
-	list__member(Rval, Rvals),
-	rval_contains_var(Rval, Name).
-
-:- pred maybe_rval_contains_var(maybe(mlds__rval), mlds__var).
-:- mode maybe_rval_contains_var(in, in) is semidet.
-
-% maybe_rval_contains_var(no, _Name) :- fail.
-maybe_rval_contains_var(yes(Rval), Name) :-
-	rval_contains_var(Rval, Name).
-
-:- pred rval_contains_var(mlds__rval, mlds__var).
-:- mode rval_contains_var(in, in) is semidet.
-
-rval_contains_var(lval(Lval), Name) :-
-	lval_contains_var(Lval, Name).
-rval_contains_var(mkword(_Tag, Rval), Name) :-
-	rval_contains_var(Rval, Name).
-% rval_contains_var(const(_Const), _Name) :- fail.
-rval_contains_var(unop(_Op, Rval), Name) :-
-	rval_contains_var(Rval, Name).
-rval_contains_var(binop(_Op, X, Y), Name) :-
-	( rval_contains_var(X, Name)
-	; rval_contains_var(Y, Name)
-	).
-rval_contains_var(mem_addr(Lval), Name) :-
-	lval_contains_var(Lval, Name).
-
-:- pred lvals_contains_var(list(mlds__lval), mlds__var).
-:- mode lvals_contains_var(in, in) is semidet.
-
-lvals_contains_var(Lvals, Name) :-
-	list__member(Lval, Lvals),
-	lval_contains_var(Lval, Name).
-
-:- pred lval_contains_var(mlds__lval, mlds__var).
-:- mode lval_contains_var(in, in) is semidet.
-
-lval_contains_var(field(_MaybeTag, Rval, _FieldId, _, _), Name) :-
-	rval_contains_var(Rval, Name).
-lval_contains_var(mem_ref(Rval, _Type), Name) :-
-	rval_contains_var(Rval, Name).
-lval_contains_var(var(Name), Name).  /* this is where we can succeed! */
 
 %-----------------------------------------------------------------------------%
 
Index: compiler/ml_optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_optimize.m,v
retrieving revision 1.4
diff -u -d -r1.4 ml_optimize.m
--- compiler/ml_optimize.m	2000/11/21 13:37:43	1.4
+++ compiler/ml_optimize.m	2001/02/08 09:45:15
@@ -9,7 +9,9 @@
 
 % This module runs various optimizations on the MLDS.
 %
-% Currently the only optimization is turning tailcalls into loops.
+% Currently the optimization we do here are
+%	- turning tailcalls into loops.
+%	- converting assignments to local variables into variable initializers
 %
 % Note that tailcall detection is done in ml_tailcall.m.
 % It might be nice to move the detection here, and do both the
@@ -37,9 +39,10 @@
 
 :- implementation.
 
-:- import_module bool, list, require, std_util, string.
-:- import_module builtin_ops, globals.
 :- import_module ml_util, ml_code_util.
+:- import_module builtin_ops, globals, options, error_util.
+
+:- import_module bool, list, require, std_util, string.
 
 :- type opt_info --->
 	opt_info(
@@ -121,9 +124,11 @@
 		Stmt0 = call(_, _, _, _, _, _),
 		Stmt = optimize_in_call_stmt(OptInfo, Stmt0)
 	;
-		Stmt0 = block(Defns, Statements0),
-		Stmt = block(Defns, optimize_in_statements(OptInfo, 
-			Statements0))
+		Stmt0 = block(Defns0, Statements0),
+		convert_assignments_into_initializers(Defns0, Statements0,
+			OptInfo, Defns, Statements1),
+		Statements = optimize_in_statements(OptInfo, Statements1),
+		Stmt = block(Defns, Statements)
 	;
 		Stmt0 = while(Rval, Statement0, Once),
 		Stmt = while(Rval, optimize_in_statement(OptInfo, 
@@ -315,10 +320,182 @@
 
 %-----------------------------------------------------------------------------%
 
+%
+% This code implements the --optimize-initializations option.
+% It converts MLDS code using assignments, e.g.
+%
+%	{
+%		int v1;	 // or any other type -- it doesn't have to be int
+%		int v2;
+%		int v3;
+%		int v4;
+%		int v5;
+%
+%		v1 = 1;
+%		v2 = 2;
+%		v3 = 3;
+%		foo();
+%		v4 = 4;
+%		...
+%	}
+%
+% into code that instead uses initializers, e.g.
+%
+%	{
+%		int v1 = 1;
+%		int v2 = 2;
+%		int v3 = 3;
+%		int v4;
+%	
+%		foo();
+%		v4 = 4;
+%		...
+%	}
+%
+% Note that if there are multiple initializations of the same
+% variable, then we'll apply the optimization successively,
+% replacing the existing initializers as we go, and keeping
+% only the last, e.g.
+%
+%		int v = 1;
+%		v = 2;
+%		v = 3;
+%		...
+%
+% will get replaced with
+%
+%		int v = 3;
+%		...
+%
+% We need to watch out for some tricky cases that can't be safely optimized.
+% If the RHS of the assignment refers to a variable which was declared after
+% the variable whose initialization we're optimizing, e.g.
+%
+%		int v1 = 1;
+%		int v2 = 0;
+%		v1 = v2 + 1;	// RHS refers to variable declared after v1
+%
+% then we can't do the optimization because it would cause a forward reference
+%
+%		int v1 = v2 + 1;	// error -- v2 not declared yet!
+%		int v2 = 0;
+%
+% Likewise if the RHS refers to the variable itself
+%
+%		int v1 = 1;
+%		v1 = v1 + 1;
+%
+% then we can't optimize it, because that would be bogus:
+%
+%		int v1 = v1 + 1;	// error -- v1 not initialized yet!
+%
+% Similarly, if the initializers of the variables that follow
+% the one we're trying to optimize refer to it, e.g.
+%
+%		int v1 = 1;
+%		int v2 = v1 + 1;	// here v2 == 2
+%		v1 = 0;
+%		...
+%
+% then we can't eliminate the assignment, because that would produce
+% different results:
+%
+%		int v1 = 0;
+%		int v2 = v1 + 1;	// wrong -- v2 == 1
+%		...
+
+:- pred convert_assignments_into_initializers(mlds__defns, mlds__statements,
+		opt_info, mlds__defns, mlds__statements).
+:- mode convert_assignments_into_initializers(in, in, in, out, out) is det.
+
+convert_assignments_into_initializers(Defns0, Statements0, OptInfo,
+		Defns, Statements) :-
+	(
+		% Check if --optimize-initializations is enabled
+		globals__lookup_bool_option(OptInfo ^ globals,
+			optimize_initializations, yes),
+
+		% Check if the first statement in the block is
+		% an assignment to one of the variables declared in
+		% the block.
+		Statements0 = [AssignStatement | Statements1],
+		AssignStatement = statement(atomic(assign(LHS, RHS)), _),
+		LHS = var(ThisVar),
+		ThisVar = qual(Qualifier, VarName),
+		Qualifier = OptInfo ^ module_name,
+		list__takewhile(isnt(var_defn(VarName)), Defns0, 
+			_PrecedingDefns, [_VarDefn | FollowingDefns]),
+
+		% We must check that the value being assigned
+		% doesn't refer to the variable itself, or to any
+		% of the variables which are declared after this one.
+		% We must also check that the initializers (if any)
+		% of the variables that follow this one don't
+		% refer to this variable.
+		\+ rval_contains_var(RHS, ThisVar),
+		\+ (
+			list__member(OtherDefn, FollowingDefns),
+			OtherDefn = mlds__defn(data(var(OtherVarName)),
+				_, _, data(_Type, OtherInitializer)),
+			( rval_contains_var(RHS, qual(Qualifier, OtherVarName))
+			; initializer_contains_var(OtherInitializer, ThisVar)
+			)
+		)
+	->
+		% Replace the assignment statement with an initializer
+		% on the variable declaration.
+		set_initializer(Defns0, VarName, RHS, Defns1),
+
+		% Now try to apply the same optimization again
+		convert_assignments_into_initializers(Defns1, Statements1,
+			OptInfo, Defns, Statements)
+	;
+		% No optimization possible -- leave the block unchanged.
+		Defns = Defns0,
+		Statements = Statements0
+	).
+
+:- pred var_defn(var_name::in, mlds__defn::in) is semidet.
+var_defn(VarName, Defn) :-
+	Defn = mlds__defn(data(var(VarName)), _, _, _).
+
+	% set_initializer(Defns0, VarName, Rval, Defns):
+	%	Finds the first definition of the specified variable
+	%	in Defns0, and replaces the initializer of that
+	%	definition with init_obj(Rval).
+	%
+:- pred set_initializer(mlds__defns, mlds__var_name, mlds__rval, mlds__defns).
+:- mode set_initializer(in, in, in, out) is det.
+
+set_initializer([], _, _, _) :-
+	unexpected(this_file, "set_initializer: var not found!").
+set_initializer([Defn0 | Defns0], VarName, Rval, [Defn | Defns]) :-
+	Defn0 = mlds__defn(Name, Context, Flags, DefnBody0),
+	(
+		Name = data(var(VarName)), 
+		DefnBody0 = mlds__data(Type, _OldInitializer)
+	->
+		DefnBody = mlds__data(Type, init_obj(Rval)),
+		Defn = mlds__defn(Name, Context, Flags, DefnBody),
+		Defns = Defns0
+	;
+		Defn = Defn0,
+		set_initializer(Defns0, VarName, Rval, Defns)
+	).
+
+%-----------------------------------------------------------------------------%
+
         % Maps T into V, inside a maybe .  
 :- func maybe_apply(func(T) = V, maybe(T)) = maybe(V).
 
 maybe_apply(_, no) = no.
 maybe_apply(F, yes(T)) = yes(F(T)).
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+this_file = "ml_optimize.m".
+
+:- end_module ml_optimize.
 
 %-----------------------------------------------------------------------------%
Index: compiler/ml_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_util.m,v
retrieving revision 1.5
diff -u -d -r1.5 ml_util.m
--- compiler/ml_util.m	2001/01/11 14:25:39	1.5
+++ compiler/ml_util.m	2001/02/08 09:42:51
@@ -15,11 +15,9 @@
 :- interface.
 
 :- import_module mlds.
+:- import_module list, std_util.
 
 %-----------------------------------------------------------------------------%
-%
-% Various utility routines used for MLDS manipulation.
-%
 
 	% return `true' if the statement is a tail call which
 	% can be optimized into a jump back to the start of the
@@ -27,6 +25,10 @@
 :- pred can_optimize_tailcall(mlds__qualified_entity_name, mlds__stmt).
 :- mode can_optimize_tailcall(in, in) is semidet.
 
+%-----------------------------------------------------------------------------%
+%
+% routines that deal with statements
+%
 
 	% nondeterministically generates sub-statements from statements.
 :- pred statements_contains_statement(mlds__statements, mlds__statement).
@@ -38,6 +40,11 @@
 :- pred stmt_contains_statement(mlds__stmt, mlds__statement).
 :- mode stmt_contains_statement(in, out) is nondet.
 
+%-----------------------------------------------------------------------------%
+%
+% routines that deal with definitions
+%
+
 	% defn_contains_foreign_code(NativeTargetLang, Defn):
 	%	Succeeds iff this definition contains target_code
 	%	statements in a target language other than the
@@ -69,12 +76,49 @@
 :- mode defn_is_public(in) is semidet.
 
 %-----------------------------------------------------------------------------%
+%
+% routines that deal with lvals/rvals
+%
+
+	%
+	% initializer_contains_var:
+	% rvals_contains_var:
+	% maybe_rval_contains_var:
+	% rval_contains_var:
+	% lvals_contains_var:
+	% lval_contains_var:
+	%	Succeeds iff the specified construct contains a reference to
+	%	the specified variable.
+	%
 
+:- pred initializer_contains_var(mlds__initializer, mlds__var).
+:- mode initializer_contains_var(in, in) is semidet.
+
+:- pred rvals_contains_var(list(mlds__rval), mlds__var).
+:- mode rvals_contains_var(in, in) is semidet.
+
+:- pred maybe_rval_contains_var(maybe(mlds__rval), mlds__var).
+:- mode maybe_rval_contains_var(in, in) is semidet.
+
+:- pred rval_contains_var(mlds__rval, mlds__var).
+:- mode rval_contains_var(in, in) is semidet.
+
+:- pred lvals_contains_var(list(mlds__lval), mlds__var).
+:- mode lvals_contains_var(in, in) is semidet.
+
+:- pred lval_contains_var(mlds__lval, mlds__var).
+:- mode lval_contains_var(in, in) is semidet.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
 :- implementation.
 
 :- import_module rtti.
 :- import_module bool, list, std_util.
 
+%-----------------------------------------------------------------------------%
+
 can_optimize_tailcall(Name, Call) :-
 	Call = call(_Signature, FuncRval, MaybeObject, _CallArgs,
 		_Results, IsTailCall),
@@ -110,6 +154,9 @@
 	MaybeObject = no.
 
 %-----------------------------------------------------------------------------%
+%
+% routines that deal with statements
+%
 
 statements_contains_statement(Statements, SubStatement) :-
 	list__member(Statement, Statements),
@@ -192,6 +239,9 @@
 	statement_contains_statement(Statement, SubStatement).
 
 %-----------------------------------------------------------------------------%
+%
+% routines that deal with definitions
+%
 
 defn_contains_foreign_code(NativeTargetLang, Defn) :-
 	Defn = mlds__defn(_Name, _Context, _Flags, Body),
@@ -223,5 +273,63 @@
 defn_is_public(Defn) :-
 	Defn = mlds__defn(_Name, _Context, Flags, _Body),
 	access(Flags) \= private.
+
+%-----------------------------------------------------------------------------%
+%
+% routines that deal with lvals/rvals
+%
+
+%
+% initializer_contains_var:
+% rvals_contains_var:
+% maybe_rval_contains_var:
+% rval_contains_var:
+% lvals_contains_var:
+% lval_contains_var:
+%	Succeeds iff the specified construct contains a reference to
+%	the specified variable.
+%
+
+% initializer_contains_var(no_initializer, _) :- fail.
+initializer_contains_var(init_obj(Rval), Name) :-
+	rval_contains_var(Rval, Name).
+initializer_contains_var(init_struct(Inits), Name) :-
+	list__member(Init, Inits),
+	initializer_contains_var(Init, Name).
+initializer_contains_var(init_array(Inits), Name) :-
+	list__member(Init, Inits),
+	initializer_contains_var(Init, Name).
+
+rvals_contains_var(Rvals, Name) :-
+	list__member(Rval, Rvals),
+	rval_contains_var(Rval, Name).
+
+% maybe_rval_contains_var(no, _Name) :- fail.
+maybe_rval_contains_var(yes(Rval), Name) :-
+	rval_contains_var(Rval, Name).
+
+rval_contains_var(lval(Lval), Name) :-
+	lval_contains_var(Lval, Name).
+rval_contains_var(mkword(_Tag, Rval), Name) :-
+	rval_contains_var(Rval, Name).
+% rval_contains_var(const(_Const), _Name) :- fail.
+rval_contains_var(unop(_Op, Rval), Name) :-
+	rval_contains_var(Rval, Name).
+rval_contains_var(binop(_Op, X, Y), Name) :-
+	( rval_contains_var(X, Name)
+	; rval_contains_var(Y, Name)
+	).
+rval_contains_var(mem_addr(Lval), Name) :-
+	lval_contains_var(Lval, Name).
+
+lvals_contains_var(Lvals, Name) :-
+	list__member(Lval, Lvals),
+	lval_contains_var(Lval, Name).
+
+lval_contains_var(field(_MaybeTag, Rval, _FieldId, _, _), Name) :-
+	rval_contains_var(Rval, Name).
+lval_contains_var(mem_ref(Rval, _Type), Name) :-
+	rval_contains_var(Rval, Name).
+lval_contains_var(var(Name), Name).  /* this is where we can succeed! */
 
 %-----------------------------------------------------------------------------%
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.308
diff -u -d -r1.308 options.m
--- compiler/options.m	2001/02/05 06:55:33	1.308
+++ compiler/options.m	2001/02/08 11:38:28
@@ -370,6 +370,7 @@
 		;	allow_hijacks
 	%	- MLDS
 		;	optimize_tailcalls
+		;	optimize_initializations
 	%	- LLDS
 		;	common_data
 		;	optimize	% also used for MLDS->MLDS optimizations
@@ -762,6 +763,7 @@
 	allow_hijacks		-	bool(yes),
 % MLDS
 	optimize_tailcalls	- 	bool(no),
+	optimize_initializations - 	bool(no),
 % LLDS
 	common_data		-	bool(no),
 	optimize		-	bool(no),
@@ -1189,6 +1191,8 @@
 long_option("mlds-optimise",		optimize).
 long_option("optimize-tailcalls",	optimize_tailcalls).
 long_option("optimise-tailcalls",	optimize_tailcalls).
+long_option("optimize-initializations",	optimize_initializations).
+long_option("optimise-initializations",	optimize_initializations).
 
 % LLDS optimizations
 long_option("common-data",		common_data).
@@ -1493,7 +1497,9 @@
 
 	optimize_rl		-	bool(yes),
 	optimize_rl_index	-	bool(yes),
-	detect_rl_streams	-	bool(yes)
+	detect_rl_streams	-	bool(yes),
+
+	optimize_initializations -	bool(yes)
 ]).
 
 % Optimization level 3: apply optimizations which usually have a good
@@ -2539,7 +2545,10 @@
 		"\tDisable the MLDS->MLDS optimization passes.",
 		"--no-optimize-tailcalls",
 		"\tTreat tailcalls as ordinary calls, rather than optimizing",
-		"\tby turning self-tailcalls into loops."
+		"\tby turning self-tailcalls into loops.",
+		"--no-optimize-initializations",
+		"\tLeave initializations of local variables as assignment statements,",
+		"\trather converting such assignments statements into initializers."
 	]).
 
 
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.237
diff -u -d -r1.237 user_guide.texi
--- doc/user_guide.texi	2001/02/06 07:11:41	1.237
+++ doc/user_guide.texi	2001/02/08 11:38:36
@@ -4105,6 +4105,10 @@
 Treat tailcalls as ordinary calls rather than optimizing
 by turning self-tailcalls into loops.
 
+ at item --no-optimize-initializations
+Leave initializations of local variables as assignment statements,
+rather converting such assignments statements into initializers.
+
 @end table
 
 @node Medium-level (HLDS -> LLDS) optimization options

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- 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
--------------------------------------------------------------------------



More information about the developers mailing list