[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