[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