[m-rev.] for review: --eliminate-local-vars
Fergus Henderson
fjh at cs.mu.OZ.AU
Thu Feb 7 04:34:16 AEDT 2002
Estimated hours taken: 12
Branches: main
Add a new MLDS->MLDS optimization option, --eliminate-local-variables.
The aim of this pass is to improve performance in cases where local
variables are costly -- for nondeterministic procedures,
for MLDS->C accurate GC, and for the .NET back-end.
compiler/ml_optimize.m:
Add a pass to eliminate local variables.
Also, don't optimize tail calls unless --optimize-tailcalls is set.
compiler/mercury_compile.m:
Invoke the ml_optimize pass once before ml_elim_nested
(with --optimize-tailcalls disabled), as well as once after it.
compiler/options.m:
doc/user_guide.texi:
Add an option --eliminate-local-variables to enable the new
optimization.
compiler/ml_elim_nested.m:
compiler/ml_util.m:
Move statement_contains_var and definition_contains_var
from ml_elim_nested.m to ml_util.m, for use by ml_optimize.m.
compiler/ml_elim_nested.m:
- Handle local variables with initializers; this is neccessary
now that ml_optimize gets run before ml_elim_nested.
- Don't allocate a stack frame struct and link it into the chain
if there are no local variables that contain pointers.
- In fixup_atomic_statement, handle foreign_proc_code more consistently.
- Add some comments.
XXX remember to check that this diff includes all
the relevant files that have been changed!
Workspace: /home/earth/fjh/ws-earth4/mercury
Index: compiler/mercury_compile.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mercury_compile.m,v
retrieving revision 1.229
diff -u -d -r1.229 mercury_compile.m
--- compiler/mercury_compile.m 11 Jan 2002 07:41:20 -0000 1.229
+++ compiler/mercury_compile.m 6 Feb 2002 16:03:21 -0000
@@ -3247,6 +3247,10 @@
maybe_report_stats(Stats),
mercury_compile__maybe_dump_mlds(MLDS10, "10", "rtti"),
+ % Detection of tail calls needs to occur before the
+ % chain_gc_stack_frame pass of ml_elim_nested,
+ % because we need to unlink the stack frame from the
+ % stack chain before tail calls.
globals__io_lookup_bool_option(optimize_tailcalls, OptimizeTailCalls),
( { OptimizeTailCalls = yes } ->
maybe_write_string(Verbose,
@@ -3259,6 +3263,29 @@
maybe_report_stats(Stats),
mercury_compile__maybe_dump_mlds(MLDS20, "20", "tailcalls"),
+ % run the ml_optimize pass before ml_elim_nested,
+ % so that we eliminate as many local variables as possible
+ % before the ml_elim_nested transformations.
+ % However, we don't want to do tail call elimination at
+ % this point, because that would result in loops
+ % with no call to MR_GC_check().
+ % So we explicitly disable that here.
+ globals__io_lookup_bool_option(optimize, Optimize),
+ ( { Optimize = yes } ->
+ globals__io_set_option(optimize_tailcalls, bool(no)),
+
+ maybe_write_string(Verbose, "% Optimizing MLDS...\n"),
+ ml_optimize__optimize(MLDS20, MLDS25),
+ maybe_write_string(Verbose, "% done.\n"),
+
+ globals__io_set_option(optimize_tailcalls,
+ bool(OptimizeTailCalls))
+ ;
+ { MLDS25 = MLDS20 }
+ ),
+ maybe_report_stats(Stats),
+ mercury_compile__maybe_dump_mlds(MLDS25, "25", "optimize1"),
+
%
% Note that we call ml_elim_nested twice --
% the first time to chain the stack frames together, for accurate GC,
@@ -3275,10 +3302,10 @@
( { GC = accurate } ->
maybe_write_string(Verbose,
"% Threading GC stack frames...\n"),
- ml_elim_nested(chain_gc_stack_frames, MLDS20, MLDS30),
+ ml_elim_nested(chain_gc_stack_frames, MLDS25, MLDS30),
maybe_write_string(Verbose, "% done.\n")
;
- { MLDS30 = MLDS20 }
+ { MLDS30 = MLDS25 }
),
maybe_report_stats(Stats),
mercury_compile__maybe_dump_mlds(MLDS30, "30", "gc_frames"),
@@ -3295,16 +3322,19 @@
maybe_report_stats(Stats),
mercury_compile__maybe_dump_mlds(MLDS35, "35", "nested_funcs"),
- globals__io_lookup_bool_option(optimize, Optimize),
+ % run the ml_optimize pass again after ml_elim_nested,
+ % to do tail call elimination. (It may also help pick
+ % up some additional optimization opportunities for the
+ % other optimizations in this pass.)
( { Optimize = yes } ->
- maybe_write_string(Verbose, "% Optimizing MLDS...\n"),
+ maybe_write_string(Verbose, "% Optimizing MLDS again...\n"),
ml_optimize__optimize(MLDS35, MLDS40),
maybe_write_string(Verbose, "% done.\n")
;
{ MLDS40 = MLDS35 }
),
maybe_report_stats(Stats),
- mercury_compile__maybe_dump_mlds(MLDS40, "40", "optimize"),
+ mercury_compile__maybe_dump_mlds(MLDS40, "40", "optimize2"),
{ MLDS = MLDS40 },
mercury_compile__maybe_dump_mlds(MLDS, "99", "final").
Index: compiler/ml_elim_nested.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_elim_nested.m,v
retrieving revision 1.49
diff -u -d -r1.49 ml_elim_nested.m
--- compiler/ml_elim_nested.m 4 Feb 2002 07:01:25 -0000 1.49
+++ compiler/ml_elim_nested.m 6 Feb 2002 17:14:09 -0000
@@ -167,7 +167,8 @@
% e.g.
% - optimize away temporary variables
% - put stack_chain and/or heap pointer in global register variables
-% - avoid linking stack chain unnecessarily?
+% - move termination conditions (check for base case)
+% outside of stack frame setup & GC check where possible
%
%-----------------------------------------------------------------------------%
%
@@ -442,12 +443,12 @@
LocalStatics),
- %
- % When hoisting nested functions,
- % if there were no nested functions, then we just
- % hoist the local static constants
- %
(
+ %
+ % When hoisting nested functions,
+ % if there were no nested functions, then we just
+ % hoist the local static constants
+ %
Action = hoist_nested_funcs,
NestedFuncs0 = []
->
@@ -455,6 +456,18 @@
HoistedDefns = HoistedStatics
;
%
+ % Likewise, when doing accurate GC,
+ % if there were no local variables (or arguments)
+ % that contained pointers, then we don't need to
+ % chain a stack frame for this function.
+ %
+ Action = chain_gc_stack_frames,
+ Locals = []
+ ->
+ FuncBody = FuncBody1,
+ HoistedDefns = HoistedStatics
+ ;
+ %
% Create a struct to hold the local variables,
% and initialize the environment pointers for
% both the containing function and the nested
@@ -718,6 +731,19 @@
% struct <EnvClassName> *env_ptr;
% env_ptr = &env;
%
+ % For accurate GC, we do something similar, but with a few differences:
+ %
+ % struct <EnvClassName> {
+ % /* these fixed fields match `struct MR_StackChain' */
+ % void *prev;
+ % void (*trace)(...);
+ % <LocalVars>
+ % };
+ % struct <EnvClassName> env = { stack_chain, foo_trace };
+ % struct <EnvClassName> *env_ptr;
+ % env_ptr = &env;
+ % stack_chain = env_ptr;
+ %
:- pred ml_create_env(action, mlds__class_name, mlds__type, list(mlds__defn),
mlds__context, mlds_module_name, mlds__entity_name, globals,
mlds__defn, list(mlds__defn), list(mlds__statement),
@@ -1341,8 +1367,9 @@
flatten_stmt(Stmt0, Stmt) -->
(
{ Stmt0 = block(Defns0, Statements0) },
- flatten_nested_defns(Defns0, Statements0, Defns),
- flatten_statements(Statements0, Statements),
+ flatten_nested_defns(Defns0, Statements0, Defns,
+ InitStatements),
+ flatten_statements(InitStatements ++ Statements0, Statements),
{ Stmt = block(Defns, Statements) }
;
{ Stmt0 = while(Rval0, Statement0, Once) },
@@ -1481,23 +1508,32 @@
% Hoist out nested function definitions, and any local variables
% that need to go in the environment struct (e.g. because they are
% referenced by nested functions), storing them both in the elim_info.
+% Convert initializers for local variables that need to go in the
+% environment struct into assignment statements.
+% Return the remaining (non-hoisted) definitions,
+% the list of assignment statements, and the updated elim_info.
%
:- pred flatten_nested_defns(mlds__defns, mlds__statements, mlds__defns,
- elim_info, elim_info).
-:- mode flatten_nested_defns(in, in, out, in, out) is det.
+ mlds__statements, elim_info, elim_info).
+:- mode flatten_nested_defns(in, in, out, out, in, out) is det.
-flatten_nested_defns([], _, []) --> [].
-flatten_nested_defns([Defn0 | Defns0], FollowingStatements, Defns) -->
- flatten_nested_defn(Defn0, Defns0, FollowingStatements, Defns1),
- flatten_nested_defns(Defns0, FollowingStatements, Defns2),
- { Defns = list__append(Defns1, Defns2) }.
+flatten_nested_defns([], _, [], []) --> [].
+flatten_nested_defns([Defn0 | Defns0], FollowingStatements, Defns,
+ InitStatements) -->
+ flatten_nested_defn(Defn0, Defns0, FollowingStatements,
+ Defns1, InitStatements1),
+ flatten_nested_defns(Defns0, FollowingStatements,
+ Defns2, InitStatements2),
+ { Defns = Defns1 ++ Defns2 },
+ { InitStatements = InitStatements1 ++ InitStatements2 }.
:- pred flatten_nested_defn(mlds__defn, mlds__defns, mlds__statements,
- mlds__defns, elim_info, elim_info).
-:- mode flatten_nested_defn(in, in, in, out, in, out) is det.
+ mlds__defns, mlds__statements, elim_info, elim_info).
+:- mode flatten_nested_defn(in, in, in, out, out, in, out) is det.
-flatten_nested_defn(Defn0, FollowingDefns, FollowingStatements, Defns) -->
+flatten_nested_defn(Defn0, FollowingDefns, FollowingStatements,
+ Defns, InitStatements) -->
{ Defn0 = mlds__defn(Name, Context, Flags0, DefnBody0) },
(
{ DefnBody0 = mlds__function(PredProcId, Params, FuncBody0,
@@ -1579,9 +1615,10 @@
{ Defns = [] }
;
{ Defns = [Defn] }
- )
+ ),
+ { InitStatements = [] }
;
- { DefnBody0 = mlds__data(Type, Init, MaybeGCTraceCode0) },
+ { DefnBody0 = mlds__data(Type, Init0, MaybeGCTraceCode0) },
%
% for local variable definitions, if they are
% referenced by any nested functions, then
@@ -1589,31 +1626,54 @@
%
=(ElimInfo),
(
- (
- % For IL and Java, we need to hoist all
- % static constants out to the top level,
- % so that they can be initialized in the
- % class constructor.
- % To keep things consistent (and reduce
- % the testing burden), we do the same for
- % the other back-ends too.
- { ml_decl_is_static_const(Defn0) }
- ;
- { Name = data(var(VarName)) },
- { ml_should_add_local_data(ElimInfo,
- VarName, MaybeGCTraceCode0,
- FollowingDefns, FollowingStatements) }
- )
+ % For IL and Java, we need to hoist all
+ % static constants out to the top level,
+ % so that they can be initialized in the
+ % class constructor.
+ % To keep things consistent (and reduce
+ % the testing burden), we do the same for
+ % the other back-ends too.
+ { ml_decl_is_static_const(Defn0) }
->
elim_info_add_and_flatten_local_data(Defn0),
+ { Defns = [] },
+ { InitStatements = [] }
+ ;
+ % Hoist ordinary local variables
+ { Name = data(var(VarName)) },
+ { ml_should_add_local_data(ElimInfo,
+ VarName, MaybeGCTraceCode0,
+ FollowingDefns, FollowingStatements) }
+ ->
+ % we need to strip out the initializer (if any)
+ % and convert it into an assignment statement,
+ % since this local variable is going to become
+ % a field, and fields can have initializers.
+ ( { Init0 = init_obj(Rval) } ->
+ { Init1 = no_initializer },
+ { DefnBody1 = mlds__data(Type, Init1,
+ MaybeGCTraceCode0) },
+ { Defn1 = mlds__defn(Name, Context, Flags0,
+ DefnBody1) },
+ { VarLval = var(qual(ElimInfo ^ module_name,
+ VarName), Type) },
+ { InitStatements = [mlds__statement(
+ atomic(assign(VarLval, Rval)),
+ Context)] }
+ ;
+ { Defn1 = Defn0 },
+ { InitStatements = [] }
+ ),
+ elim_info_add_and_flatten_local_data(Defn1),
{ Defns = [] }
;
+ fixup_initializer(Init0, Init),
flatten_maybe_statement(MaybeGCTraceCode0,
MaybeGCTraceCode),
{ DefnBody = mlds__data(Type, Init, MaybeGCTraceCode) },
{ Defn = mlds__defn(Name, Context, Flags0, DefnBody) },
-
- { Defns = [Defn] }
+ { Defns = [Defn] },
+ { InitStatements = [] }
)
;
{ DefnBody0 = mlds__class(_) },
@@ -1624,7 +1684,8 @@
% but currently ml_code_gen.m doesn't generate
% any of these, so it doesn't matter what we do
%
- { Defns = [Defn0] }
+ { Defns = [Defn0] },
+ { InitStatements = [] }
).
%
@@ -1723,6 +1784,7 @@
%-----------------------------------------------------------------------------%
%
+% fixup_initializer:
% fixup_atomic_stmt:
% fixup_case_cond:
% fixup_trail_op:
@@ -1735,6 +1797,18 @@
% every variable inside it.
%
+:- pred fixup_initializer(mlds__initializer, mlds__initializer,
+ elim_info, elim_info).
+:- mode fixup_initializer(in, out, in, out) is det.
+
+fixup_initializer(no_initializer, no_initializer) --> [].
+fixup_initializer(init_obj(Rval0), init_obj(Rval)) -->
+ fixup_rval(Rval0, Rval).
+fixup_initializer(init_struct(Members0), init_struct(Members)) -->
+ list__map_foldl(fixup_initializer, Members0, Members).
+fixup_initializer(init_array(Elements0), init_array(Elements)) -->
+ list__map_foldl(fixup_initializer, Elements0, Elements).
+
:- pred fixup_atomic_stmt(mlds__atomic_statement, mlds__atomic_statement,
elim_info, elim_info).
:- mode fixup_atomic_stmt(in, out, in, out) is det.
@@ -1762,8 +1836,9 @@
inline_target_code(Lang, Components)) -->
list__map_foldl(fixup_target_code_component,
Components0, Components).
-fixup_atomic_stmt(outline_foreign_proc(Lang, Lvals, Code),
- outline_foreign_proc(Lang, Lvals, Code)) --> [].
+fixup_atomic_stmt(outline_foreign_proc(Lang, Lvals0, Code),
+ outline_foreign_proc(Lang, Lvals, Code)) -->
+ list__map_foldl(fixup_lval, Lvals0, Lvals).
:- pred fixup_case_cond(mlds__case_match_cond, mlds__case_match_cond,
elim_info, elim_info).
@@ -2129,206 +2204,6 @@
% default_contains_defn(default_is_unreachable, _) :- fail.
default_contains_defn(default_case(Statement), Defn) :-
statement_contains_defn(Statement, Defn).
-
-%-----------------------------------------------------------------------------%
-
-%
-% defns_contains_var:
-% defn_contains_var:
-% defn_body_contains_var:
-% function_body_contains_var:
-% statements_contains_var:
-% statement_contains_var:
-% trail_op_contains_var:
-% atomic_stmt_contains_var:
-% Succeeds iff the specified construct contains a reference to
-% the specified variable.
-%
-
-:- pred defns_contains_var(mlds__defns, mlds__var).
-:- mode defns_contains_var(in, in) is semidet.
-
-defns_contains_var(Defns, Name) :-
- list__member(Defn, Defns),
- defn_contains_var(Defn, Name).
-
-:- pred defn_contains_var(mlds__defn, mlds__var).
-:- mode defn_contains_var(in, in) is semidet.
-
-defn_contains_var(mlds__defn(_Name, _Context, _Flags, DefnBody), Name) :-
- defn_body_contains_var(DefnBody, Name).
-
-:- pred defn_body_contains_var(mlds__entity_defn, mlds__var).
-:- mode defn_body_contains_var(in, in) is semidet.
-
- % XXX Should we include variables in the GC_TraceCode field here?
-defn_body_contains_var(mlds__data(_Type, Initializer, _GC_TraceCode), Name) :-
- initializer_contains_var(Initializer, Name).
-defn_body_contains_var(mlds__function(_PredProcId, _Params, FunctionBody,
- _Attrs), Name) :-
- function_body_contains_var(FunctionBody, Name).
-defn_body_contains_var(mlds__class(ClassDefn), Name) :-
- ClassDefn = mlds__class_defn(_Kind, _Imports, _Inherits, _Implements,
- CtorDefns, FieldDefns),
- ( defns_contains_var(FieldDefns, Name)
- ; defns_contains_var(CtorDefns, Name)
- ).
-
-:- pred maybe_statement_contains_var(maybe(mlds__statement), mlds__var).
-:- mode maybe_statement_contains_var(in, in) is semidet.
-
-% maybe_statement_contains_var(no, _) :- fail.
-maybe_statement_contains_var(yes(Statement), Name) :-
- statement_contains_var(Statement, Name).
-
-:- pred function_body_contains_var(function_body, mlds__var).
-:- mode function_body_contains_var(in, in) is semidet.
-
-% function_body_contains_var(external, _) :- fail.
-function_body_contains_var(defined_here(Statement), Name) :-
- statement_contains_var(Statement, Name).
-
-:- pred statements_contains_var(mlds__statements, mlds__var).
-:- mode statements_contains_var(in, in) is semidet.
-
-statements_contains_var(Statements, Name) :-
- list__member(Statement, Statements),
- statement_contains_var(Statement, Name).
-
-:- pred statement_contains_var(mlds__statement, mlds__var).
-:- mode statement_contains_var(in, in) is semidet.
-
-statement_contains_var(Statement, Name) :-
- Statement = mlds__statement(Stmt, _Context),
- stmt_contains_var(Stmt, Name).
-
-:- pred stmt_contains_var(mlds__stmt, mlds__var).
-:- mode stmt_contains_var(in, in) is semidet.
-
-stmt_contains_var(Stmt, Name) :-
- (
- Stmt = block(Defns, Statements),
- ( defns_contains_var(Defns, Name)
- ; statements_contains_var(Statements, Name)
- )
- ;
- Stmt = while(Rval, Statement, _Once),
- ( rval_contains_var(Rval, Name)
- ; statement_contains_var(Statement, Name)
- )
- ;
- Stmt = if_then_else(Cond, Then, MaybeElse),
- ( rval_contains_var(Cond, Name)
- ; statement_contains_var(Then, Name)
- ; maybe_statement_contains_var(MaybeElse, Name)
- )
- ;
- Stmt = switch(_Type, Val, _Range, Cases, Default),
- ( rval_contains_var(Val, Name)
- ; cases_contains_var(Cases, Name)
- ; default_contains_var(Default, Name)
- )
- ;
- Stmt = label(_Label),
- fail
- ;
- Stmt = goto(_),
- fail
- ;
- Stmt = computed_goto(Rval, _Labels),
- rval_contains_var(Rval, Name)
- ;
- Stmt = call(_Sig, Func, Obj, Args, RetLvals, _TailCall),
- ( rval_contains_var(Func, Name)
- ; maybe_rval_contains_var(Obj, Name)
- ; rvals_contains_var(Args, Name)
- ; lvals_contains_var(RetLvals, Name)
- )
- ;
- Stmt = return(Rvals),
- rvals_contains_var(Rvals, Name)
- ;
- Stmt = do_commit(Ref),
- rval_contains_var(Ref, Name)
- ;
- Stmt = try_commit(Ref, Statement, Handler),
- ( lval_contains_var(Ref, Name)
- ; statement_contains_var(Statement, Name)
- ; statement_contains_var(Handler, Name)
- )
- ;
- Stmt = atomic(AtomicStmt),
- atomic_stmt_contains_var(AtomicStmt, Name)
- ).
-
-:- pred cases_contains_var(list(mlds__switch_case), mlds__var).
-:- mode cases_contains_var(in, in) is semidet.
-
-cases_contains_var(Cases, Name) :-
- list__member(Case, Cases),
- Case = _MatchConds - Statement,
- statement_contains_var(Statement, Name).
-
-:- pred default_contains_var(mlds__switch_default, mlds__var).
-:- mode default_contains_var(in, in) is semidet.
-
-% default_contains_var(default_do_nothing, _) :- fail.
-% default_contains_var(default_is_unreachable, _) :- fail.
-default_contains_var(default_case(Statement), Name) :-
- statement_contains_var(Statement, Name).
-
-:- pred atomic_stmt_contains_var(mlds__atomic_statement, mlds__var).
-:- mode atomic_stmt_contains_var(in, in) is semidet.
-
-% atomic_stmt_contains_var(comment(_), _Name) :- fail.
-atomic_stmt_contains_var(assign(Lval, Rval), Name) :-
- ( lval_contains_var(Lval, Name)
- ; rval_contains_var(Rval, Name)
- ).
-atomic_stmt_contains_var(new_object(Target, _MaybeTag, _HasSecTag, _Type,
- _MaybeSize, _MaybeCtorName, Args, _ArgTypes), Name) :-
- ( lval_contains_var(Target, Name)
- ; rvals_contains_var(Args, Name)
- ).
-% atomic_stmt_contains_var(gc_check, _) :- fail.
-atomic_stmt_contains_var(mark_hp(Lval), Name) :-
- lval_contains_var(Lval, Name).
-atomic_stmt_contains_var(restore_hp(Rval), Name) :-
- rval_contains_var(Rval, Name).
-atomic_stmt_contains_var(trail_op(TrailOp), Name) :-
- trail_op_contains_var(TrailOp, Name).
-atomic_stmt_contains_var(inline_target_code(_Lang, Components), Name) :-
- list__member(Component, Components),
- target_code_component_contains_var(Component, Name).
-
-:- pred trail_op_contains_var(trail_op, mlds__var).
-:- mode trail_op_contains_var(in, in) is semidet.
-
-trail_op_contains_var(store_ticket(Lval), Name) :-
- lval_contains_var(Lval, Name).
-trail_op_contains_var(reset_ticket(Rval, _Reason), Name) :-
- rval_contains_var(Rval, Name).
-% trail_op_contains_var(discard_ticket, _Name) :- fail.
-% trail_op_contains_var(prune_ticket, _Name) :- fail.
-trail_op_contains_var(mark_ticket_stack(Lval), Name) :-
- lval_contains_var(Lval, Name).
-trail_op_contains_var(prune_tickets_to(Rval), Name) :-
- rval_contains_var(Rval, Name).
-
-:- pred target_code_component_contains_var(target_code_component, mlds__var).
-:- mode target_code_component_contains_var(in, in) is semidet.
-
-%target_code_component_contains_var(raw_target_code(_Code), _Name) :-
-% fail.
-%target_code_component_contains_var(user_target_code(_Code, _Context), _Name) :-
-% fail.
-target_code_component_contains_var(target_code_input(Rval), Name) :-
- rval_contains_var(Rval, Name).
-target_code_component_contains_var(target_code_output(Lval), Name) :-
- lval_contains_var(Lval, Name).
-target_code_component_contains_var(name(EntityName), VarName) :-
- EntityName = qual(ModuleName, data(var(UnqualVarName))),
- VarName = qual(ModuleName, UnqualVarName).
%-----------------------------------------------------------------------------%
Index: compiler/ml_optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_optimize.m,v
retrieving revision 1.14
diff -u -d -r1.14 ml_optimize.m
--- compiler/ml_optimize.m 11 Jan 2002 07:41:25 -0000 1.14
+++ compiler/ml_optimize.m 6 Feb 2002 16:08:35 -0000
@@ -12,6 +12,8 @@
% Currently the optimizations we do here are
% - turning tailcalls into loops;
% - converting assignments to local variables into variable initializers.
+% - eliminating initialized local variables entirely,
+% by replacing occurrences of such variables with their initializer
%
% Note that tailcall detection is done in ml_tailcall.m.
% It might be nice to move the detection here, and do both the
@@ -42,7 +44,7 @@
:- import_module ml_util, ml_code_util.
:- import_module builtin_ops, globals, options, error_util.
-:- import_module bool, list, require, std_util, string.
+:- import_module bool, int, list, require, std_util, string.
:- type opt_info --->
opt_info(
@@ -136,9 +138,11 @@
Stmt = optimize_in_call_stmt(OptInfo, Stmt0)
;
Stmt0 = block(Defns0, Statements0),
- convert_assignments_into_initializers(Defns0, Statements0,
- OptInfo, Defns, Statements1),
- Statements = optimize_in_statements(OptInfo, Statements1),
+ maybe_convert_assignments_into_initializers(Defns0, Statements0,
+ OptInfo, Defns1, Statements1),
+ maybe_eliminate_locals(Defns1, Statements1,
+ OptInfo, Defns, Statements2),
+ Statements = optimize_in_statements(OptInfo, Statements2),
Stmt = block(Defns, Statements)
;
Stmt0 = while(Rval, Statement0, Once),
@@ -201,6 +205,8 @@
% If we have a self-tailcall, assign to the arguments and
% then goto the top of the tailcall loop.
(
+ globals__lookup_bool_option(OptInfo ^ globals,
+ optimize_tailcalls, yes),
Stmt0 = call(_Signature, _FuncRval, _MaybeObject, CallArgs,
_Results, _IsTailCall),
can_optimize_tailcall(qual(OptInfo ^ module_name,
@@ -315,6 +321,8 @@
% Tailcall optimization -- if we do a self tailcall, we
% can turn it into a loop.
(
+ globals__lookup_bool_option(OptInfo ^ globals,
+ optimize_tailcalls, yes),
stmt_contains_statement(Stmt0, Call),
Call = mlds__statement(CallStmt, _),
can_optimize_tailcall(
@@ -416,6 +424,26 @@
% int v2 = v1 + 1; // wrong -- v2 == 1
% ...
+:- pred maybe_convert_assignments_into_initializers(
+ mlds__defns, mlds__statements, opt_info,
+ mlds__defns, mlds__statements).
+:- mode maybe_convert_assignments_into_initializers(in, in, in, out, out)
+ is det.
+
+maybe_convert_assignments_into_initializers(Defns0, Statements0, OptInfo,
+ Defns, Statements) :-
+ (
+ % Check if --optimize-initializations is enabled
+ globals__lookup_bool_option(OptInfo ^ globals,
+ optimize_initializations, yes)
+ ->
+ convert_assignments_into_initializers(Defns0, Statements0,
+ OptInfo, Defns, Statements)
+ ;
+ Defns = Defns0,
+ Statements = Statements0
+ ).
+
:- 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.
@@ -423,10 +451,6 @@
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.
@@ -494,6 +518,586 @@
Defn = Defn0,
set_initializer(Defns0, VarName, Rval, Defns)
).
+
+%-----------------------------------------------------------------------------%
+
+%
+% This is a pass to eliminate initialized local variable definitions,
+% by substituting the value of the initializer for occurrences
+% of the variable.
+%
+
+% XXX This is quadratic in the number of variable definitions,
+% since we done one pass over the block per variable definition.
+% A more efficient algorithm would be to do one pass to figure
+% out which variables could be eliminated, and then do another
+% pass to actually eliminate them.
+
+:- pred maybe_eliminate_locals(mlds__defns, mlds__statements,
+ opt_info, mlds__defns, mlds__statements).
+:- mode maybe_eliminate_locals(in, in, in, out, out) is det.
+
+maybe_eliminate_locals(Defns0, Statements0, OptInfo, Defns, Statements) :-
+ globals__lookup_bool_option(OptInfo ^ globals, eliminate_local_vars,
+ EliminateLocalVars),
+ ( EliminateLocalVars = yes ->
+ eliminate_locals(Defns0, Statements0, OptInfo,
+ Defns, Statements)
+ ;
+ Defns = Defns0,
+ Statements = Statements0
+ ).
+
+:- pred eliminate_locals(mlds__defns, mlds__statements,
+ opt_info, mlds__defns, mlds__statements).
+:- mode eliminate_locals(in, in, in, out, out) is det.
+
+eliminate_locals([], Statements, _OptInfo, [], Statements).
+eliminate_locals([Defn0 | Defns0], Statements0, OptInfo, Defns, Statements) :-
+ (
+ try_to_eliminate_defn(Defn0, Defns0, Statements0, OptInfo,
+ Defns1, Statements1)
+ ->
+ eliminate_locals(Defns1, Statements1, OptInfo,
+ Defns, Statements)
+ ;
+ eliminate_locals(Defns0, Statements0, OptInfo,
+ Defns2, Statements),
+ Defns = [Defn0 | Defns2]
+ ).
+
+ % This data structure holds information that we use
+ % in this pass to eliminate initialized local variable definitions.
+:- type var_elim_info
+ ---> var_elim_info(
+ %
+ % these fields remain constant
+ %
+ var_name :: mlds__var,
+ % the name of the variable to eliminate
+ var_value :: mlds__rval,
+ % the value to replace the
+ % eliminated variable with
+ %
+ % these get updated as we go along
+ %
+ replace_count :: int,
+ % the number of occurrences of the variable
+ invalidated :: bool
+ % `yes' if the optimization can't be applied,
+ % e.g. because the variable was assigned to,
+ % or because its address was taken
+ ).
+
+ % Check if this definition is a variable that we can eliminate.
+ % If so, replace uses of this variable with the variable's value.
+ % This will fail if the definition is not a variable definition,
+ % or if any of the statements or definitions take the address
+ % of the variable, or assign to it.
+:- pred try_to_eliminate_defn(mlds__defn::in, mlds__defns::in,
+ mlds__statements::in, opt_info::in,
+ mlds__defns::out, mlds__statements::out) is semidet.
+
+try_to_eliminate_defn(Defn0, Defns0, Statements0, OptInfo,
+ Defns, Statements) :-
+ Defn0 = mlds__defn(Name, _Context, Flags, DefnBody),
+
+ % Check if this definition is a local variable definition...
+ Name = data(var(VarName)),
+ Flags = ml_gen_local_var_decl_flags,
+ DefnBody = mlds__data(_Type, Initializer, _MaybeGCTraceCode),
+
+ % ... with a known initial value.
+ QualVarName = qual(OptInfo ^ module_name, VarName),
+ (
+ Initializer = init_obj(Rval),
+ Statements1 = Statements0
+ ;
+ Initializer = no_initializer,
+ find_initial_val_in_statements(QualVarName, Statements0,
+ Rval, Statements1)
+ ),
+
+ % It's only safe to do this transformation if the
+ % variable's value is constant, otherwise we might
+ % end up moving the rvalue across a statement which
+ % modifies it.
+ rval_will_not_change(Rval),
+
+ % This transformation moves evaluation of the rvalue later in
+ % the computation. If the rvalue is something which might
+ % loop, throw an exception, or abort (e.g. for division by zero),
+ % then this might change the behaviour of the program.
+ % In such cases, we can only do the transformation
+ % if reordering of both conjunctions and disjunctions
+ % (we can't tell here whether this MLDS code came from a
+ % conjunction or a disjunction) is allowed.
+ (
+ rval_cannot_throw(Rval)
+ ;
+ globals__lookup_bool_option(OptInfo ^ globals,
+ reorder_conj, yes),
+ globals__lookup_bool_option(OptInfo ^ globals,
+ reorder_disj, yes)
+ ),
+
+ % Replace uses of this variable with the variable's value,
+ % checking that none of the statements or definitions took the
+ % address of the variable, or assigned to it.
+ eliminate_var(QualVarName, Rval, Defns0, Defns,
+ Statements1, Statements, Count, Invalidated),
+ Invalidated = no,
+
+ % Make sure that we didn't duplicate the rval,
+ % unless it is just a constant or a variable,
+ % because duplicating any real operation would be
+ % a pessimization
+ ( Count =< 1
+ ; rval_is_cheap_enough_to_duplicate(Rval)
+ ).
+
+:- pred rval_is_cheap_enough_to_duplicate(mlds__rval::in) is semidet.
+rval_is_cheap_enough_to_duplicate(Rval) :-
+ ( Rval = const(_)
+ ; Rval = lval(var(_, _))
+ ; Rval = mem_addr(_)
+ ; Rval = self(_)
+ ).
+
+ % Succeed only if the specified rval definitely won't change
+ % in value.
+:- pred rval_will_not_change(mlds__rval::in) is semidet.
+rval_will_not_change(const(_)).
+rval_will_not_change(mkword(_Tag, Rval)) :-
+ rval_will_not_change(Rval).
+rval_will_not_change(unop(_Op, Rval)) :-
+ rval_will_not_change(Rval).
+rval_will_not_change(binop(_Op, Rval1, Rval2)) :-
+ rval_will_not_change(Rval1),
+ rval_will_not_change(Rval2).
+rval_will_not_change(mem_addr(var(_, _))).
+rval_will_not_change(mem_addr(mem_ref(Address, _Type))) :-
+ rval_will_not_change(Address).
+rval_will_not_change(mem_addr(field(_, Address, _, _, _))) :-
+ rval_will_not_change(Address).
+
+ % Succeed only if the given rval definitely can't loop,
+ % throw an exception, or abort.
+ % We use a pretty conservative approximation...
+:- pred rval_cannot_throw(mlds__rval::in) is semidet.
+rval_cannot_throw(const(_)).
+rval_cannot_throw(mkword(_Tag, Rval)) :-
+ rval_cannot_throw(Rval).
+rval_cannot_throw(mem_addr(_)).
+rval_cannot_throw(self(_)).
+
+% Search through a list of statements,
+% trying to find the first assignment to the specified variable.
+% Return the initial value, and a modified list of statements
+% with the initial assignment deleted.
+% Fail if the first value can't be determined.
+:- pred find_initial_val_in_statements(mlds__var::in, mlds__statements::in,
+ mlds__rval::out, mlds__statements::out) is semidet.
+find_initial_val_in_statements(VarName, [Statement0 | Statements0],
+ Rval, Statements) :-
+ (
+ find_initial_val_in_statement(VarName, Statement0,
+ Rval1, Statement1)
+ ->
+ Rval = Rval1,
+ ( Statement1 = mlds__statement(block([], []), _) ->
+ Statements = Statements0
+ ;
+ Statements = [Statement1 | Statements0]
+ )
+ ;
+ % Check that Statement0 doesn't modify the value of the
+ % variable -- this includes checking that there are no
+ % labels via which code could branch into the middle of
+ % Statement0. Only if we are sure that Statement0
+ % can't modify the variable's value is it safe to go
+ % on and look for the initial value in Statements0.
+ \+ statement_contains_var(Statement0, VarName),
+ \+ (
+ statement_contains_statement(Statement0, Label),
+ Label = mlds__statement(label(_), _)
+ ),
+ find_initial_val_in_statements(VarName, Statements0,
+ Rval, Statements1),
+ Statements = [Statement0 | Statements1]
+ ).
+
+:- pred find_initial_val_in_statement(mlds__var::in, mlds__statement::in,
+ mlds__rval::out, mlds__statement::out) is semidet.
+
+find_initial_val_in_statement(Var, Statement0, Rval, Statement) :-
+ Statement0 = mlds__statement(Stmt0, Context),
+ Statement = mlds__statement(Stmt, Context),
+ ( Stmt0 = atomic(assign(var(Var, _Type), Rval0)) ->
+ Rval = Rval0,
+ % delete the assignment, by replacing it with an empty block
+ Stmt = block([], [])
+ ; Stmt0 = block(Defns0, SubStatements0) ->
+ \+ defns_contains_var(Defns0, Var),
+ find_initial_val_in_statements(Var, SubStatements0,
+ Rval, SubStatements),
+ Stmt = block(Defns0, SubStatements)
+ ;
+ fail
+ ).
+
+ % Replace uses of this variable with the variable's value
+ % in the specified definitions and statements.
+ % This will return a count of how many occurrences
+ % of the variable there were.
+ % It will also return Invalidated = yes if
+ % any of the statements or definitions take the address
+ % of the variable, or assign to it; in that case,
+ % the transformation should not be performed.
+:- pred eliminate_var(mlds__var::in, mlds__rval::in,
+ mlds__defns::in, mlds__defns::out,
+ mlds__statements::in, mlds__statements::out,
+ int::out, bool::out) is det.
+
+eliminate_var(QualVarName, VarRval, Defns0, Defns1,
+ Statements0, Statements, Count, Invalidated) :-
+ Count0 = 0,
+ Invalidated0 = no,
+ VarElimInfo0 = var_elim_info(QualVarName, VarRval, Count0,
+ Invalidated0),
+ eliminate_var_in_block(Defns0, Defns1,
+ Statements0, Statements, VarElimInfo0, VarElimInfo),
+ Count = VarElimInfo ^ replace_count,
+ Invalidated = VarElimInfo ^ invalidated.
+
+% eliminate_var_in_*:
+% process the specified construct, replacing all rvalue occurences
+% of the variable (^var_name) with its value (^var_value),
+% incrementing the ^replace_count field for each occurrence
+% as an rvalue, and setting ^invalidated to yes if the variable
+% occurs as an lvalue.
+
+:- pred eliminate_var_in_block(mlds__defns::in, mlds__defns::out,
+ mlds__statements::in, mlds__statements::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_block(Defns0, Defns, Statements0, Statements) -->
+ eliminate_var_in_defns(Defns0, Defns),
+ eliminate_var_in_statements(Statements0, Statements).
+
+:- pred eliminate_var_in_defns(mlds__defns::in, mlds__defns::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_defns(Defns0, Defns) -->
+ list__map_foldl(eliminate_var_in_defn, Defns0, Defns).
+
+:- pred eliminate_var_in_defn(mlds__defn::in, mlds__defn::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_defn(Defn0, Defn) -->
+ { Defn0 = mlds__defn(Name, Context, Flags, DefnBody0) },
+ (
+ { DefnBody0 = mlds__data(Type, Initializer0,
+ MaybeGCTraceCode) },
+ eliminate_var_in_initializer(Initializer0, Initializer),
+ { DefnBody = mlds__data(Type, Initializer, MaybeGCTraceCode) }
+ ;
+ { DefnBody0 = mlds__class(_) },
+ % We assume that nested classes don't refer to local variables
+ % in the containing scope
+ { DefnBody = DefnBody0 }
+ ;
+ { DefnBody0 = mlds__function(Id, Params, Body0, Attributes) },
+ eliminate_var_in_function_body(Body0, Body),
+ { DefnBody = mlds__function(Id, Params, Body, Attributes) }
+ ),
+ { Defn = mlds__defn(Name, Context, Flags, DefnBody) }.
+
+:- pred eliminate_var_in_function_body(
+ mlds__function_body::in, mlds__function_body::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_function_body(external, external) --> [].
+eliminate_var_in_function_body(defined_here(Stmt0), defined_here(Stmt)) -->
+ eliminate_var_in_statement(Stmt0, Stmt).
+
+:- pred eliminate_var_in_initializer(
+ mlds__initializer::in, mlds__initializer::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_initializer(no_initializer, no_initializer) --> [].
+eliminate_var_in_initializer(init_obj(Rval0), init_obj(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_initializer(init_array(Elements0), init_array(Elements)) -->
+ list__map_foldl(eliminate_var_in_initializer, Elements0, Elements).
+eliminate_var_in_initializer(init_struct(Members0), init_struct(Members)) -->
+ list__map_foldl(eliminate_var_in_initializer, Members0, Members).
+
+:- pred eliminate_var_in_rvals(
+ list(mlds__rval)::in, list(mlds__rval)::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_rvals(Rvals0, Rvals) -->
+ list__map_foldl(eliminate_var_in_rval, Rvals0, Rvals).
+
+:- pred eliminate_var_in_maybe_rval(
+ maybe(mlds__rval)::in, maybe(mlds__rval)::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_maybe_rval(no, no) --> [].
+eliminate_var_in_maybe_rval(yes(Rval0), yes(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+
+:- pred eliminate_var_in_rval(mlds__rval::in, mlds__rval::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_rval(Rval0, Rval) -->
+ (
+ { Rval0 = lval(Lval0) },
+ VarName =^ var_name,
+ ( { Lval0 = var(VarName, _) } ->
+ % we found an rvalue occurrence of the variable --
+ % replace it with the rval for the variable's value,
+ % and increment the counter for the number of
+ % occurrences that we have replaced.
+ Rval =^ var_value,
+ Count0 =^ replace_count,
+ ^replace_count := Count0 + 1
+ ;
+ eliminate_var_in_lval(Lval0, Lval),
+ { Rval = lval(Lval) }
+ )
+ ;
+ { Rval0 = mkword(Tag, ArgRval0) },
+ eliminate_var_in_rval(ArgRval0, ArgRval),
+ { Rval = mkword(Tag, ArgRval) }
+ ;
+ { Rval0 = const(_) },
+ { Rval = Rval0 }
+ ;
+ { Rval0 = unop(Op, ArgRval0) },
+ eliminate_var_in_rval(ArgRval0, ArgRval),
+ { Rval = unop(Op, ArgRval) }
+ ;
+ { Rval0 = binop(Op, Arg1Rval0, Arg2Rval0) },
+ eliminate_var_in_rval(Arg1Rval0, Arg1Rval),
+ eliminate_var_in_rval(Arg2Rval0, Arg2Rval),
+ { Rval = binop(Op, Arg1Rval, Arg2Rval) }
+ ;
+ { Rval0 = mem_addr(Lval0) },
+ eliminate_var_in_lval(Lval0, Lval),
+ { Rval = mem_addr(Lval) }
+ ;
+ { Rval0 = self(_Type) },
+ { Rval = Rval0 }
+ ).
+
+:- pred eliminate_var_in_lvals(
+ list(mlds__lval)::in, list(mlds__lval)::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_lvals(Lvals0, Lvals) -->
+ list__map_foldl(eliminate_var_in_lval, Lvals0, Lvals).
+
+:- pred eliminate_var_in_lval(mlds__lval::in, mlds__lval::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_lval(Lval0, Lval) -->
+ (
+ { Lval0 = field(MaybeTag, Rval0, FieldId, FieldType, PtrType) },
+ eliminate_var_in_rval(Rval0, Rval),
+ { Lval = field(MaybeTag, Rval, FieldId, FieldType, PtrType) }
+ ;
+ { Lval0 = mem_ref(Rval0, Type) },
+ eliminate_var_in_rval(Rval0, Rval),
+ { Lval = mem_ref(Rval, Type) }
+ ;
+ { Lval0 = var(VarName, _Type) },
+ ( VarName =^ var_name ->
+ % we found an lvalue occurrence of the variable --
+ % if the variable that we are trying to eliminate
+ % has its address is taken, or is assigned to,
+ % or in general if it is used as an lvalue,
+ % then it's not safe to eliminate it
+ ^invalidated := yes
+ ;
+ []
+ ),
+ { Lval = Lval0 }
+ ).
+
+:- pred eliminate_var_in_statements(
+ mlds__statements::in, mlds__statements::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_statements(Statements0, Statements) -->
+ list__map_foldl(eliminate_var_in_statement, Statements0, Statements).
+
+:- pred eliminate_var_in_maybe_statement(
+ maybe(mlds__statement)::in, maybe(mlds__statement)::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_maybe_statement(no, no) --> [].
+eliminate_var_in_maybe_statement(yes(Statement0), yes(Statement)) -->
+ eliminate_var_in_statement(Statement0, Statement).
+
+:- pred eliminate_var_in_statement(mlds__statement::in, mlds__statement::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_statement(Statement0, Statement) -->
+ { Statement0 = mlds__statement(Stmt0, Context) },
+ eliminate_var_in_stmt(Stmt0, Stmt),
+ { Statement = mlds__statement(Stmt, Context) }.
+
+:- pred eliminate_var_in_stmt(mlds__stmt::in, mlds__stmt::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_stmt(Stmt0, Stmt) -->
+ (
+ { Stmt0 = block(Defns0, Statements0) },
+ eliminate_var_in_block(Defns0, Defns, Statements0, Statements),
+ { Stmt = block(Defns, Statements) }
+ ;
+ { Stmt0 = while(Rval0, Statement0, Once) },
+ eliminate_var_in_rval(Rval0, Rval),
+ eliminate_var_in_statement(Statement0, Statement),
+ { Stmt = while(Rval, Statement, Once) }
+ ;
+ { Stmt0 = if_then_else(Cond0, Then0, MaybeElse0) },
+ eliminate_var_in_rval(Cond0, Cond),
+ eliminate_var_in_statement(Then0, Then),
+ eliminate_var_in_maybe_statement(MaybeElse0, MaybeElse),
+ { Stmt = if_then_else(Cond, Then, MaybeElse) }
+ ;
+ { Stmt0 = switch(Type, Val0, Range, Cases0, Default0) },
+ eliminate_var_in_rval(Val0, Val),
+ list__map_foldl(eliminate_var_in_case, Cases0, Cases),
+ eliminate_var_in_default(Default0, Default),
+ { Stmt = switch(Type, Val, Range, Cases, Default) }
+ ;
+ { Stmt0 = label(_) },
+ { Stmt = Stmt0 }
+ ;
+ { Stmt0 = goto(_) },
+ { Stmt = Stmt0 }
+ ;
+ { Stmt0 = computed_goto(Rval0, Labels) },
+ eliminate_var_in_rval(Rval0, Rval),
+ { Stmt = computed_goto(Rval, Labels) }
+ ;
+ { Stmt0 = call(Sig, Func0, Obj0, Args0, RetLvals0, TailCall) },
+ eliminate_var_in_rval(Func0, Func),
+ eliminate_var_in_maybe_rval(Obj0, Obj),
+ eliminate_var_in_rvals(Args0, Args),
+ eliminate_var_in_lvals(RetLvals0, RetLvals),
+ { Stmt = call(Sig, Func, Obj, Args, RetLvals, TailCall) }
+ ;
+ { Stmt0 = return(Rvals0) },
+ eliminate_var_in_rvals(Rvals0, Rvals),
+ { Stmt = return(Rvals) }
+ ;
+ { Stmt0 = do_commit(Ref0) },
+ eliminate_var_in_rval(Ref0, Ref),
+ { Stmt = do_commit(Ref) }
+ ;
+ { Stmt0 = try_commit(Ref0, Statement0, Handler0) },
+ eliminate_var_in_lval(Ref0, Ref),
+ eliminate_var_in_statement(Statement0, Statement),
+ eliminate_var_in_statement(Handler0, Handler),
+ { Stmt = try_commit(Ref, Statement, Handler) }
+ ;
+ { Stmt0 = atomic(AtomicStmt0) },
+ eliminate_var_in_atomic_stmt(AtomicStmt0, AtomicStmt),
+ { Stmt = atomic(AtomicStmt) }
+ ).
+
+:- pred eliminate_var_in_case(mlds__switch_case::in, mlds__switch_case::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_case(Conds0 - Statement0, Conds - Statement) -->
+ list__map_foldl(eliminate_var_in_case_cond, Conds0, Conds),
+ eliminate_var_in_statement(Statement0, Statement).
+
+:- pred eliminate_var_in_default(
+ mlds__switch_default::in, mlds__switch_default::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_default(default_is_unreachable, default_is_unreachable) --> [].
+eliminate_var_in_default(default_do_nothing, default_do_nothing) --> [].
+eliminate_var_in_default(default_case(Statement0), default_case(Statement)) -->
+ eliminate_var_in_statement(Statement0, Statement).
+
+:- pred eliminate_var_in_atomic_stmt(
+ mlds__atomic_statement::in, mlds__atomic_statement::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_atomic_stmt(comment(C), comment(C)) --> [].
+eliminate_var_in_atomic_stmt(assign(Lval0, Rval0), assign(Lval, Rval)) -->
+ eliminate_var_in_lval(Lval0, Lval),
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_atomic_stmt(delete_object(Lval0), delete_object(Lval)) -->
+ eliminate_var_in_lval(Lval0, Lval).
+eliminate_var_in_atomic_stmt(new_object(Target0, MaybeTag, HasSecTag, Type,
+ MaybeSize, MaybeCtorName, Args0, ArgTypes),
+ new_object(Target, MaybeTag, HasSecTag, Type,
+ MaybeSize, MaybeCtorName, Args, ArgTypes)) -->
+ eliminate_var_in_lval(Target0, Target),
+ eliminate_var_in_rvals(Args0, Args).
+eliminate_var_in_atomic_stmt(gc_check, gc_check) --> [].
+eliminate_var_in_atomic_stmt(mark_hp(Lval0), mark_hp(Lval)) -->
+ eliminate_var_in_lval(Lval0, Lval).
+eliminate_var_in_atomic_stmt(restore_hp(Rval0), restore_hp(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_atomic_stmt(trail_op(TrailOp0), trail_op(TrailOp)) -->
+ eliminate_var_in_trail_op(TrailOp0, TrailOp).
+eliminate_var_in_atomic_stmt(inline_target_code(Lang, Components0),
+ inline_target_code(Lang, Components)) -->
+ list__map_foldl(eliminate_var_in_target_code_component,
+ Components0, Components).
+eliminate_var_in_atomic_stmt(outline_foreign_proc(Lang, Lvals0, Code),
+ outline_foreign_proc(Lang, Lvals, Code)) -->
+ eliminate_var_in_lvals(Lvals0, Lvals).
+
+:- pred eliminate_var_in_case_cond(
+ mlds__case_match_cond::in, mlds__case_match_cond::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_case_cond(match_value(Rval0), match_value(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_case_cond(match_range(Low0, High0), match_range(Low, High)) -->
+ eliminate_var_in_rval(Low0, Low),
+ eliminate_var_in_rval(High0, High).
+
+:- pred eliminate_var_in_target_code_component(
+ target_code_component::in, target_code_component::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_target_code_component(raw_target_code(Code, Attrs),
+ raw_target_code(Code, Attrs)) --> [].
+eliminate_var_in_target_code_component(user_target_code(Code, Context, Attrs),
+ user_target_code(Code, Context, Attrs)) --> [].
+eliminate_var_in_target_code_component(target_code_input(Rval0),
+ target_code_input(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_target_code_component(target_code_output(Lval0),
+ target_code_output(Lval)) -->
+ eliminate_var_in_lval(Lval0, Lval).
+eliminate_var_in_target_code_component(name(Name), name(Name)) --> [].
+
+:- pred eliminate_var_in_trail_op(trail_op::in, trail_op::out,
+ var_elim_info::in, var_elim_info::out) is det.
+
+eliminate_var_in_trail_op(store_ticket(Lval0), store_ticket(Lval)) -->
+ eliminate_var_in_lval(Lval0, Lval).
+eliminate_var_in_trail_op(reset_ticket(Rval0, Reason),
+ reset_ticket(Rval, Reason)) -->
+ eliminate_var_in_rval(Rval0, Rval).
+eliminate_var_in_trail_op(discard_ticket, discard_ticket) --> [].
+eliminate_var_in_trail_op(prune_ticket, prune_ticket) --> [].
+eliminate_var_in_trail_op(mark_ticket_stack(Lval0), mark_ticket_stack(Lval)) -->
+ eliminate_var_in_lval(Lval0, Lval).
+eliminate_var_in_trail_op(prune_tickets_to(Rval0), prune_tickets_to(Rval)) -->
+ eliminate_var_in_rval(Rval0, Rval).
%-----------------------------------------------------------------------------%
Index: compiler/ml_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_util.m,v
retrieving revision 1.15
diff -u -d -r1.15 ml_util.m
--- compiler/ml_util.m 11 Jan 2002 07:41:26 -0000 1.15
+++ compiler/ml_util.m 6 Feb 2002 13:25:28 -0000
@@ -47,6 +47,11 @@
:- pred stmt_contains_statement(mlds__stmt, mlds__statement).
:- mode stmt_contains_statement(in, out) is nondet.
+ % succeeds iff this statement contains a reference to the
+ % specified variable
+:- pred statement_contains_var(mlds__statement, mlds__var).
+:- mode statement_contains_var(in, in) is semidet.
+
:- pred has_foreign_languages(mlds__statement, list(foreign_language)).
:- mode has_foreign_languages(in, out) is det.
@@ -95,6 +100,16 @@
:- pred defn_is_public(mlds__defn).
:- mode defn_is_public(in) is semidet.
+ % Succeeds iff these definitions contains a reference to
+ % the specified variable.
+:- pred defns_contains_var(mlds__defns, mlds__var).
+:- mode defns_contains_var(in, in) is semidet.
+
+ % Succeeds iff this definition contains a reference to
+ % the specified variable.
+:- pred defn_contains_var(mlds__defn, mlds__var).
+:- mode defn_contains_var(in, in) is semidet.
+
%-----------------------------------------------------------------------------%
%
% routines that deal with lvals/rvals
@@ -184,6 +199,11 @@
% routines that deal with statements
%
+% statement_contains_statement:
+% statements_contains_statement:
+% maybe_statement_contains_statement:
+% nondeterministically generates sub-statements from statements.
+
statements_contains_statement(Statements, SubStatement) :-
list__member(Statement, Statements),
statement_contains_statement(Statement, SubStatement).
@@ -264,6 +284,161 @@
default_contains_statement(default_case(Statement), SubStatement) :-
statement_contains_statement(Statement, SubStatement).
+% statements_contains_var:
+% maybe_statement_contains_var:
+% statement_contains_var:
+% trail_op_contains_var:
+% atomic_stmt_contains_var:
+% Succeeds iff the specified construct contains a reference to
+% the specified variable.
+
+:- pred statements_contains_var(mlds__statements, mlds__var).
+:- mode statements_contains_var(in, in) is semidet.
+
+statements_contains_var(Statements, Name) :-
+ list__member(Statement, Statements),
+ statement_contains_var(Statement, Name).
+
+:- pred maybe_statement_contains_var(maybe(mlds__statement), mlds__var).
+:- mode maybe_statement_contains_var(in, in) is semidet.
+
+% maybe_statement_contains_var(no, _) :- fail.
+maybe_statement_contains_var(yes(Statement), Name) :-
+ statement_contains_var(Statement, Name).
+
+
+statement_contains_var(Statement, Name) :-
+ Statement = mlds__statement(Stmt, _Context),
+ stmt_contains_var(Stmt, Name).
+
+:- pred stmt_contains_var(mlds__stmt, mlds__var).
+:- mode stmt_contains_var(in, in) is semidet.
+
+stmt_contains_var(Stmt, Name) :-
+ (
+ Stmt = block(Defns, Statements),
+ ( defns_contains_var(Defns, Name)
+ ; statements_contains_var(Statements, Name)
+ )
+ ;
+ Stmt = while(Rval, Statement, _Once),
+ ( rval_contains_var(Rval, Name)
+ ; statement_contains_var(Statement, Name)
+ )
+ ;
+ Stmt = if_then_else(Cond, Then, MaybeElse),
+ ( rval_contains_var(Cond, Name)
+ ; statement_contains_var(Then, Name)
+ ; maybe_statement_contains_var(MaybeElse, Name)
+ )
+ ;
+ Stmt = switch(_Type, Val, _Range, Cases, Default),
+ ( rval_contains_var(Val, Name)
+ ; cases_contains_var(Cases, Name)
+ ; default_contains_var(Default, Name)
+ )
+ ;
+ Stmt = label(_Label),
+ fail
+ ;
+ Stmt = goto(_),
+ fail
+ ;
+ Stmt = computed_goto(Rval, _Labels),
+ rval_contains_var(Rval, Name)
+ ;
+ Stmt = call(_Sig, Func, Obj, Args, RetLvals, _TailCall),
+ ( rval_contains_var(Func, Name)
+ ; maybe_rval_contains_var(Obj, Name)
+ ; rvals_contains_var(Args, Name)
+ ; lvals_contains_var(RetLvals, Name)
+ )
+ ;
+ Stmt = return(Rvals),
+ rvals_contains_var(Rvals, Name)
+ ;
+ Stmt = do_commit(Ref),
+ rval_contains_var(Ref, Name)
+ ;
+ Stmt = try_commit(Ref, Statement, Handler),
+ ( lval_contains_var(Ref, Name)
+ ; statement_contains_var(Statement, Name)
+ ; statement_contains_var(Handler, Name)
+ )
+ ;
+ Stmt = atomic(AtomicStmt),
+ atomic_stmt_contains_var(AtomicStmt, Name)
+ ).
+
+:- pred cases_contains_var(list(mlds__switch_case), mlds__var).
+:- mode cases_contains_var(in, in) is semidet.
+
+cases_contains_var(Cases, Name) :-
+ list__member(Case, Cases),
+ Case = _MatchConds - Statement,
+ statement_contains_var(Statement, Name).
+
+:- pred default_contains_var(mlds__switch_default, mlds__var).
+:- mode default_contains_var(in, in) is semidet.
+
+% default_contains_var(default_do_nothing, _) :- fail.
+% default_contains_var(default_is_unreachable, _) :- fail.
+default_contains_var(default_case(Statement), Name) :-
+ statement_contains_var(Statement, Name).
+
+:- pred atomic_stmt_contains_var(mlds__atomic_statement, mlds__var).
+:- mode atomic_stmt_contains_var(in, in) is semidet.
+
+% atomic_stmt_contains_var(comment(_), _Name) :- fail.
+atomic_stmt_contains_var(assign(Lval, Rval), Name) :-
+ ( lval_contains_var(Lval, Name)
+ ; rval_contains_var(Rval, Name)
+ ).
+atomic_stmt_contains_var(new_object(Target, _MaybeTag, _HasSecTag, _Type,
+ _MaybeSize, _MaybeCtorName, Args, _ArgTypes), Name) :-
+ ( lval_contains_var(Target, Name)
+ ; rvals_contains_var(Args, Name)
+ ).
+% atomic_stmt_contains_var(gc_check, _) :- fail.
+atomic_stmt_contains_var(mark_hp(Lval), Name) :-
+ lval_contains_var(Lval, Name).
+atomic_stmt_contains_var(restore_hp(Rval), Name) :-
+ rval_contains_var(Rval, Name).
+atomic_stmt_contains_var(trail_op(TrailOp), Name) :-
+ trail_op_contains_var(TrailOp, Name).
+atomic_stmt_contains_var(inline_target_code(_Lang, Components), Name) :-
+ list__member(Component, Components),
+ target_code_component_contains_var(Component, Name).
+
+:- pred trail_op_contains_var(trail_op, mlds__var).
+:- mode trail_op_contains_var(in, in) is semidet.
+
+trail_op_contains_var(store_ticket(Lval), Name) :-
+ lval_contains_var(Lval, Name).
+trail_op_contains_var(reset_ticket(Rval, _Reason), Name) :-
+ rval_contains_var(Rval, Name).
+% trail_op_contains_var(discard_ticket, _Name) :- fail.
+% trail_op_contains_var(prune_ticket, _Name) :- fail.
+trail_op_contains_var(mark_ticket_stack(Lval), Name) :-
+ lval_contains_var(Lval, Name).
+trail_op_contains_var(prune_tickets_to(Rval), Name) :-
+ rval_contains_var(Rval, Name).
+
+:- pred target_code_component_contains_var(target_code_component, mlds__var).
+:- mode target_code_component_contains_var(in, in) is semidet.
+
+%target_code_component_contains_var(raw_target_code(_Code), _Name) :-
+% fail.
+%target_code_component_contains_var(user_target_code(_Code, _Context), _Name) :-
+% fail.
+target_code_component_contains_var(target_code_input(Rval), Name) :-
+ rval_contains_var(Rval, Name).
+target_code_component_contains_var(target_code_output(Lval), Name) :-
+ lval_contains_var(Lval, Name).
+target_code_component_contains_var(name(EntityName), VarName) :-
+ EntityName = qual(ModuleName, data(var(UnqualVarName))),
+ VarName = qual(ModuleName, UnqualVarName).
+
has_foreign_languages(Statement, Langs) :-
GetTargetCode = (pred(Lang::out) is nondet :-
statement_contains_statement(Statement, SubStatement),
@@ -319,6 +494,43 @@
Defn = mlds__defn(_Name, _Context, Flags, _Body),
access(Flags) = public.
+% defns_contains_var:
+% defn_contains_var:
+% defn_body_contains_var:
+% function_body_contains_var:
+% Succeeds iff the specified construct contains a reference to
+% the specified variable.
+%
+defns_contains_var(Defns, Name) :-
+ list__member(Defn, Defns),
+ defn_contains_var(Defn, Name).
+
+defn_contains_var(mlds__defn(_Name, _Context, _Flags, DefnBody), Name) :-
+ defn_body_contains_var(DefnBody, Name).
+
+:- pred defn_body_contains_var(mlds__entity_defn, mlds__var).
+:- mode defn_body_contains_var(in, in) is semidet.
+
+ % XXX Should we include variables in the GC_TraceCode field here?
+defn_body_contains_var(mlds__data(_Type, Initializer, _GC_TraceCode), Name) :-
+ initializer_contains_var(Initializer, Name).
+defn_body_contains_var(mlds__function(_PredProcId, _Params, FunctionBody,
+ _Attrs), Name) :-
+ function_body_contains_var(FunctionBody, Name).
+defn_body_contains_var(mlds__class(ClassDefn), Name) :-
+ ClassDefn = mlds__class_defn(_Kind, _Imports, _Inherits, _Implements,
+ CtorDefns, FieldDefns),
+ ( defns_contains_var(FieldDefns, Name)
+ ; defns_contains_var(CtorDefns, Name)
+ ).
+
+:- pred function_body_contains_var(function_body, mlds__var).
+:- mode function_body_contains_var(in, in) is semidet.
+
+% function_body_contains_var(external, _) :- fail.
+function_body_contains_var(defined_here(Statement), Name) :-
+ statement_contains_var(Statement, Name).
+
%-----------------------------------------------------------------------------%
%
% routines that deal with lvals/rvals
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.350
diff -u -d -r1.350 options.m
--- compiler/options.m 16 Dec 2001 08:11:09 -0000 1.350
+++ compiler/options.m 6 Feb 2002 14:35:44 -0000
@@ -414,6 +414,7 @@
% - MLDS
; optimize_tailcalls
; optimize_initializations
+ ; eliminate_local_vars
% - LLDS
; common_data
; optimize % also used for MLDS->MLDS optimizations
@@ -864,6 +865,7 @@
% MLDS
optimize_tailcalls - bool(no),
optimize_initializations - bool(no),
+ eliminate_local_vars - bool(no),
% LLDS
common_data - bool(no),
optimize - bool(no),
@@ -1097,9 +1099,11 @@
long_option("auto-comments", auto_comments).
long_option("show-dependency-graph", show_dependency_graph).
long_option("dump-hlds", dump_hlds).
+long_option("hlds-dump", dump_hlds).
long_option("dump-hlds-alias", dump_hlds_alias).
long_option("dump-hlds-options", dump_hlds_options).
long_option("dump-mlds", dump_mlds).
+long_option("mlds-dump", dump_mlds).
long_option("dump-rl", dump_rl).
long_option("dump-rl-bytecode", dump_rl_bytecode).
long_option("sign-assembly", sign_assembly).
@@ -1361,6 +1365,7 @@
long_option("optimise-tailcalls", optimize_tailcalls).
long_option("optimize-initializations", optimize_initializations).
long_option("optimise-initializations", optimize_initializations).
+long_option("eliminate-local-vars", eliminate_local_vars).
% LLDS optimizations
long_option("common-data", common_data).
@@ -1777,12 +1782,15 @@
% Currently this enables the search for construction unifications that can be
% delayed past failing computations, allows more passes of the low-level
% optimizations, and increases the inlining thresholds still further.
+% We also enable eliminate_local_vars only at this level,
+% because that pass is implemented pretty inefficiently.
opt_level(5, _, [
optimize_repeat - int(5),
delay_construct - bool(yes),
inline_compound_threshold - int(100),
- higher_order_size_limit - int(40)
+ higher_order_size_limit - int(40),
+ eliminate_local_vars - bool(yes)
]).
% Optimization level 6: apply optimizations which may have any
@@ -1800,6 +1808,32 @@
use_macro_for_redo_fail - bool(yes)
]).
+% The following optimization options are not enabled at any level:
+%
+% checked_nondet_tailcalls:
+% This is deliberate, because the transformation
+% might make code run slower.
+%
+% constraint_propagation:
+% I think this is deliberate, because the transformation
+% might make code run slower?
+%
+% prev_code:
+% Not useful?
+%
+% unneeded_code:
+% type_specialization:
+% optimize_rl_invariant:
+% XXX why not?
+%
+% introduce_accumulators:
+% XXX Disabled until a bug in extras/trailed_update/var.m
+% is resolved.
+%
+% optimize_rl_cse:
+% optimize_constructor_last_call:
+% Not implemented yet.
+
%-----------------------------------------------------------------------------%
options_help -->
@@ -2888,7 +2922,10 @@
"--no-optimize-initializations",
"\tLeave initializations of local variables as",
"\tassignment statements, rather than converting such",
- "\tassignment statements into initializers."
+ "\tassignment statements into initializers.",
+ "--eliminate-local-vars",
+ "\tEliminate local variables with known values, where possible,",
+ "\tby replacing occurrences of such variables with their values."
]).
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.287
diff -u -d -r1.287 user_guide.texi
--- doc/user_guide.texi 30 Jan 2002 14:51:04 -0000 1.287
+++ doc/user_guide.texi 6 Feb 2002 16:13:45 -0000
@@ -5115,6 +5115,11 @@
Leave initializations of local variables as assignment statements,
rather than converting such assignments statements into initializers.
+ at item --eliminate-local-variables
+ at findex --no-eliminate-local-variables
+ at findex --eliminate-local-variables
+Eliminate local variables with known values, where possible,
+by replacing occurrences of such variables with their values.
@end table
@node Medium-level (HLDS -> LLDS) optimization options
--
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
--------------------------------------------------------------------------
More information about the reviews
mailing list