[m-rev.] diff: java tail recursion optimization
Fergus Henderson
fjh at cs.mu.OZ.AU
Mon Feb 11 22:26:08 AEDT 2002
Estimated hours taken: 2
Branches: main
Implement tail call optimization for the Java back-end.
Also change tail call optimization for the C back-end to
use while/break/continue rather than gotos.
compiler/mlds.m:
Add support for C-style `break' and `continue' statements:
change the argument of the MLDS `goto' statement from a label
to a new type `goto_target' which is either `break', `continue',
or a label.
compiler/ml_optimize.m:
Add a new predicate `target_supports_break_and_continue',
and for targets where this predicate succeeds, generate tail
recursion using while/break/continue rather than label/goto.
compiler/ml_simplify_switch.m:
compiler/ml_string_switch.m:
compiler/mlds_to_c.m:
compiler/mlds_to_gcc.m:
compiler/mlds_to_il.m:
compiler/mlds_to_java.m:
Minor changes to handle the new type for the argument of the
`goto' statement.
Workspace: /home/ceres/fjh/mercury
Index: compiler/ml_optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_optimize.m,v
retrieving revision 1.15
diff -u -d -r1.15 ml_optimize.m
--- compiler/ml_optimize.m 7 Feb 2002 03:55:45 -0000 1.15
+++ compiler/ml_optimize.m 11 Feb 2002 10:07:14 -0000
@@ -55,11 +55,6 @@
context :: mlds__context
).
- % The label name we use for the top of the loop introduced by
- % tailcall optimization.
-:- func tailcall_loop_label_name = string.
-tailcall_loop_label_name = "loop_top".
-
optimize(MLDS0, MLDS) -->
globals__io_get_globals(Globals),
{ MLDS0 = mlds(ModuleName, ForeignCode, Imports, Defns0) },
@@ -215,7 +210,8 @@
CommentStatement = statement(
atomic(comment("direct tailcall eliminated")),
OptInfo ^ context),
- GotoStatement = statement(goto(tailcall_loop_label_name),
+ GotoStatement = statement(
+ goto(tailcall_loop_top(OptInfo ^ globals)),
OptInfo ^ context),
OptInfo ^ func_params = mlds__func_params(FuncArgs, _RetTypes),
generate_assign_args(OptInfo, FuncArgs, CallArgs,
@@ -233,6 +229,29 @@
Stmt = Stmt0
).
+ % This specifies how we should branch to the top of the loop
+ % introduced by tailcall opptimization.
+:- func tailcall_loop_top(globals) = mlds__goto_target.
+tailcall_loop_top(Globals) =
+ ( target_supports_break_and_continue(Globals) ->
+ % the function body has been wrapped inside
+ % `while (true) { ... break; }', and so to
+ % branch to the top of the function, we just do
+ % a `continue' which will continue the next iteration
+ % of the loop
+ continue
+ ;
+ % a label has been inserted at the start of the function,
+ % and so to branch to the top of the function, we just
+ % branch to that label
+ label(tailcall_loop_label_name)
+ ).
+
+ % The label name we use for the top of the loop introduced by
+ % tailcall optimization, when we're doing it with labels & gotos.
+:- func tailcall_loop_label_name = string.
+tailcall_loop_label_name = "loop_top".
+
%----------------------------------------------------------------------------
% Assign the specified list of rvals to the arguments.
@@ -330,13 +349,58 @@
CallStmt)
->
Comment = atomic(comment("tailcall optimized into a loop")),
- Label = label(tailcall_loop_label_name),
- Stmt = block([], [statement(Comment, Context),
- statement(Label, Context),
- statement(Stmt0, Context)])
+ CommentStmt = statement(Comment, Context),
+ % The loop can be defined either using while, break, and
+ % continue, or using a label and goto. We prefer to
+ % use the former, if possible, since it is a higher-level
+ % construct that may help the back-end compiler's optimizer.
+ ( target_supports_break_and_continue(OptInfo ^ globals) ->
+ % Wrap a while loop around the function body:
+ % while (true) {
+ % /* tailcall optimized into a loop */
+ % <function body goes here>
+ % break;
+ % }
+ % Any tail calls in the function body will have
+ % been replaced with `continue' statements.
+ Stmt = while(const(true),
+ statement(block([],
+ [CommentStmt,
+ statement(Stmt0, Context),
+ statement(goto(break), Context)]),
+ Context), no)
+ ;
+ % Add a loop_top label at the start of the function
+ % body:
+ % {
+ % loop_top:
+ % /* tailcall optimized into a loop */
+ % <function body goes here>
+ % }
+ % Any tail calls in the function body will have
+ % been replaced with `goto loop_top' statements.
+ Label = label(tailcall_loop_label_name),
+ Stmt = block([], [CommentStmt,
+ statement(Label, Context),
+ statement(Stmt0, Context)])
+ )
;
Stmt = Stmt0
).
+
+:- pred target_supports_break_and_continue(globals::in) is semidet.
+
+target_supports_break_and_continue(Globals) :-
+ globals__get_target(Globals, Target),
+ target_supports_break_and_continue_2(Target) = yes.
+
+:- func target_supports_break_and_continue_2(compilation_target) = bool.
+
+target_supports_break_and_continue_2(c) = yes.
+target_supports_break_and_continue_2(asm) = no. % asm means via gnu back-end
+target_supports_break_and_continue_2(il) = no.
+target_supports_break_and_continue_2(java) = yes.
+% target_supports_break_and_continue_2(c_sharp) = yes.
%-----------------------------------------------------------------------------%
Index: compiler/ml_simplify_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_simplify_switch.m,v
retrieving revision 1.4
diff -u -d -r1.4 ml_simplify_switch.m
--- compiler/ml_simplify_switch.m 24 Oct 2001 13:34:27 -0000 1.4
+++ compiler/ml_simplify_switch.m 11 Feb 2002 07:01:35 -0000
@@ -340,7 +340,7 @@
atomic(comment("branch to end of dense switch")),
MLDS_Context) },
{ JumpCode = mlds__statement(
- goto(EndLabel),
+ goto(label(EndLabel)),
MLDS_Context) },
{ MLDS_Decls = [] },
{ MLDS_Statements = [LabelComment, LabelCode, CaseStatement,
Index: compiler/ml_string_switch.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_string_switch.m,v
retrieving revision 1.9
diff -u -d -r1.9 ml_string_switch.m
--- compiler/ml_string_switch.m 11 Jan 2002 07:41:25 -0000 1.9
+++ compiler/ml_string_switch.m 11 Feb 2002 07:01:39 -0000
@@ -79,7 +79,7 @@
%
ml_gen_new_label(EndLabel),
{ GotoEndStatement = mlds__statement(
- goto(EndLabel),
+ goto(label(EndLabel)),
MLDS_Context) },
{
Index: compiler/mlds.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds.m,v
retrieving revision 1.82
diff -u -d -r1.82 mlds.m
--- compiler/mlds.m 29 Jan 2002 01:51:52 -0000 1.82
+++ compiler/mlds.m 11 Feb 2002 07:11:20 -0000
@@ -888,7 +888,7 @@
% Defines a label that can be used as the
% target of calls, gotos, etc.
- ; goto(mlds__label)
+ ; goto(mlds__goto_target)
% goto(Target)
% Branch to the specified address.
@@ -1051,6 +1051,18 @@
%
:- type mlds__label == string.
+
+:- type mlds__goto_target
+ ---> label(mlds__label) % Branch to the specified label.
+ ; break % Branch to just after the end of the
+ % immediately enclosing loop or switch,
+ % just like a C/C++/Java `break' statement.
+ % Not supported by all target languages.
+ ; continue. % Branch to the end of the loop body for
+ % the immediately enclosing loop,
+ % just like a C/C++/Java/C# `continue'
+ % statement.
+ % Not supported by all target languages.
%-----------------------------------------------------------------------------%
%
Index: compiler/mlds_to_c.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_c.m,v
retrieving revision 1.117
diff -u -d -r1.117 mlds_to_c.m
--- compiler/mlds_to_c.m 6 Feb 2002 10:04:21 -0000 1.117
+++ compiler/mlds_to_c.m 11 Feb 2002 07:02:28 -0000
@@ -2124,11 +2124,17 @@
mlds_indent(Indent - 1),
mlds_output_label_name(LabelName),
io__write_string(":;\n").
-mlds_output_stmt(Indent, _FuncInfo, goto(LabelName), _) -->
+mlds_output_stmt(Indent, _FuncInfo, goto(label(LabelName)), _) -->
mlds_indent(Indent),
io__write_string("goto "),
mlds_output_label_name(LabelName),
io__write_string(";\n").
+mlds_output_stmt(Indent, _FuncInfo, goto(break), _) -->
+ mlds_indent(Indent),
+ io__write_string("break;\n").
+mlds_output_stmt(Indent, _FuncInfo, goto(continue), _) -->
+ mlds_indent(Indent),
+ io__write_string("continue;\n").
mlds_output_stmt(Indent, _FuncInfo, computed_goto(Expr, Labels), Context) -->
% XXX for GNU C, we could output potentially more efficient code
% by using an array of labels; this would tell the compiler that
Index: compiler/mlds_to_gcc.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_gcc.m,v
retrieving revision 1.61
diff -u -d -r1.61 mlds_to_gcc.m
--- compiler/mlds_to_gcc.m 28 Jan 2002 17:27:22 -0000 1.61
+++ compiler/mlds_to_gcc.m 11 Feb 2002 08:54:55 -0000
@@ -2453,10 +2453,17 @@
{ LabelTable = DefnInfo ^ label_table },
{ GCC_Label = map__lookup(LabelTable, LabelName) },
gcc__gen_label(GCC_Label).
-gen_stmt(DefnInfo, goto(LabelName), _) -->
+gen_stmt(DefnInfo, goto(label(LabelName)), _) -->
{ LabelTable = DefnInfo ^ label_table },
{ GCC_Label = map__lookup(LabelTable, LabelName) },
gcc__gen_goto(GCC_Label).
+gen_stmt(_DefnInfo, goto(break), _) -->
+ gcc__gen_break.
+gen_stmt(_DefnInfo, goto(continue), _) -->
+ % XXX not yet implemented
+ % but we set target_supports_break_and_continue to no
+ % for this target, so we shouldn't get any
+ { unexpected(this_file, "continue") }.
gen_stmt(_DefnInfo, computed_goto(_Expr, _Labels), _) -->
% XXX not yet implemented
% but we set target_supports_computed_goto to no
Index: compiler/mlds_to_il.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_il.m,v
retrieving revision 1.102
diff -u -d -r1.102 mlds_to_il.m
--- compiler/mlds_to_il.m 8 Feb 2002 13:50:23 -0000 1.102
+++ compiler/mlds_to_il.m 11 Feb 2002 07:10:36 -0000
@@ -1645,7 +1645,6 @@
}.
-
statement_to_il(statement(return(Rvals), Context), Instrs) -->
( { Rvals = [Rval] } ->
load(Rval, LoadInstrs),
@@ -1668,15 +1667,19 @@
label(Label)
]) }.
-
-
-statement_to_il(statement(goto(Label), Context), Instrs) -->
+statement_to_il(statement(goto(label(Label)), Context), Instrs) -->
{ string__format("goto %s", [s(Label)], Comment) },
{ Instrs = node([
comment(Comment),
context_instr(Context),
br(label_target(Label))
]) }.
+
+statement_to_il(statement(goto(break), _Context), _Instrs) -->
+ { sorry(this_file, "break") }.
+
+statement_to_il(statement(goto(continue), _Context), _Instrs) -->
+ { sorry(this_file, "continue") }.
statement_to_il(statement(do_commit(_Ref), Context), Instrs) -->
Index: compiler/mlds_to_java.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_java.m,v
retrieving revision 1.21
diff -u -d -r1.21 mlds_to_java.m
--- compiler/mlds_to_java.m 8 Feb 2002 00:41:25 -0000 1.21
+++ compiler/mlds_to_java.m 11 Feb 2002 08:55:17 -0000
@@ -1901,9 +1901,15 @@
output_stmt(_Indent, _FuncInfo, label(_LabelName), _Context) -->
{ unexpected(this_file,
"output_stmt: labels not supported in Java.") }.
-output_stmt(_Indent, _FuncInfo, goto(_LabelName), _Context) -->
+output_stmt(_Indent, _FuncInfo, goto(label(_LabelName)), _Context) -->
{ unexpected(this_file,
"output_stmt: gotos not supported in Java.") }.
+output_stmt(Indent, _FuncInfo, goto(break), _Context) -->
+ indent_line(Indent),
+ io__write_string("break;\n").
+output_stmt(Indent, _FuncInfo, goto(continue), _Context) -->
+ indent_line(Indent),
+ io__write_string("continue;\n").
output_stmt(_Indent, _FuncInfo, computed_goto(_Expr, _Labels), _Context) -->
{ unexpected(this_file,
"output_stmt: computed gotos not supported in Java.") }.
--
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