[m-dev.] for review: MLDS code generator design

[Fergus Henderson]

The following comments document the algorithms that I intend
to use for generating conjunction, disjunction, if-then-else,
and commits in the HLDS->MLDS code generator.

This algorithm generates nice high-level code;
apart from the throw or longjmp used for commits,
the generated code does not contain any gotos ;-)

I'd appreciate it if someone (Zoltan, Tom, and Tyson spring to mind ;-)
could review this before I get too far down the track of implementing it.  

Thanks,
	Fergus.

%-----------------------------------------------------------------------------%

% File: ml_code_gen.m
% Main author: fjh

% MLDS code generation -- convert from HLDS to MLDS.

% This module is an alternative to the original code generator.
% The original code generator compiles from HLDS to LLDS, generating
% very low-level code.  This code generator instead compiles to MLDS,
% generating much higher-level code than the original code generator.

% For nondeterministic predicates, we generate code using an explicit
% continuation passing style: on success, a function calls its continuation,
% and on failure it returns.  To keep things easy, this pass generates
% code which may contain nested functions; if the target language doesn't
% support nested functions (or doesn't support them _efficiently_) then
% a later MLDS->MLDS simplification pass will convert it to a form that
% does not use nested functions.

%-----------------------------------------------------------------------------%
% CODE GENERATION SUMMARY
%-----------------------------------------------------------------------------%
%
% The calling convention for sub-goals is as follows.
%
%	model_det goal:
%		On success, fall through.
%		(May clobber `succeeded'.)
%	model_semi goal:
%		On success, set `succeeded' to TRUE and fall through.
%		On failure, set `succeeded' to FALSE and fall through.
%	model_non goal:
%		On success, call the success continuation.
%		On failure, fall through.
%		(May clobber `succeeded' in either case.)
%
% In comments, we use the following notation to distinguish between
% these three.
%
%	model_det goal:
%		<do Goal>
%	model_semi goal:
%		<succeeded = Goal>
%	model_non goal:
%		<Goal && CONT()>
%
% The notation 
%
%	[situation]:
%		<[construct]>
%	===>
%		[code]
%
% means that in the situation described by [situation],
% for the the specified [construct] we will generate the specified [code].

%-----------------------------------------------------------------------------%
%
% Code for commits
%

%	model_non in semi context: (using catch/throw)
%		<succeeded = Goal>
% 	===>
%		bool succeeded;
%		void success() {
%			throw COMMIT;
%		}
%		try {
%		   <Goal && success()>
%		   succeeded = FALSE;
%		} catch (COMMIT) {
%		   succeeded = TRUE;
%		}

%	model_non in semi context: (using setjmp/longjmp)
%		<succeeded = Goal>
% 	===>
%		bool succeeded;
%		jmp_buf buf;
%		void success() {
%			longjmp(buf, TRUE);
%		}
%		if (setjmp(buf)) {
%			succeeded = TRUE;
%		} else {
%			<Goal && success()>
%			succeeded = FALSE;
%		}

%	model_non in det context (using catch/throw):
%		<do Goal>
%	===>
%		void success() {
%			throw COMMIT;
%		}
%		try {
%		   <Goal && success()>
%		} catch (COMMIT) {}

%	model_non in det context (using setjmp/longjmp):
%		<do Goal>
% 	===>
%		jmp_buf buf;
%		void success() {
%			longjmp(buf, TRUE);
%		}
%		if (setjmp(buf) == 0) {
%			<Goal && success()>
%		}

%-----------------------------------------------------------------------------%
%
% Code for conjunctions
%

%	model_det goal:
%		<Goal, Goals>
% 	===>
%		<do Goal>
%		<Goals>
%	

%	model_semi goal:
%		<Goal, Goals>
% 	===>
%	{
%		bool succeeded;
%
%		<succeeded = Goal>;
%		if (succeeded) {
%		    <Goals>;
%		}
%	}

%	model_non goal (unoptimized)
%		<Goal, Goals>
% 	===>
%	{
%		entry_func() {
%			<Goal && succ_func()>;
%		}
%		succ_func() {
%			<Goals && SUCCEED()>;
%	 	}
%
%		entry_func();
%	}
%
%	model_non goal (optimized):
%		<Goal, Goals>
% 	===>
%	{
%	        succ_func() {
%			<Goals && SUCCEED()>;
%	        }
%
%	        <Goal && succ_func()>;
%	}

%	model_non goals (unoptimized):
%		<Goal1, Goal2, Goal3, Goals>
% 	===>
%	{
%	        label0_func() {
%		        <Goal1 && label1_func()>;
%	        }
%	        label1_func() {
%		        <Goal2 && label2_func()>;
%	        }
%	        label2_func() {
%		        <Goal3 && label3_func()>;
%	        }
%	        label3_func() {
%		        <Goals && SUCCEED()>;
%	        }
%
%	        label0_func();
%	}

%	model_non goals (optimized):
%		<Goal1, Goal2, Goal3, Goals>
% 	===>
%	{
%	        label3_func() {
%		        <Goals && SUCCEED()>;
%	        }
%	        label2_func() {
%		        <Goal3 && label3_func()>;
%	        }
%	        label1_func() {
%		        <Goal2 && label2_func()>;
%	        }
%
%	        <Goal1 && label1_func()>;
%	}

%-----------------------------------------------------------------------------%
%
% Code for disjunctions
%

% model_det disj:

%	model_det goal:
%		<do (Goal ; Goals)>
%	===>
%		<do Goal>
%		/* <Goals> will never be reached */

%	model_semi goal:
%		<do (Goal ; Goals)>
%	===>
%	{
%		bool succeeded;
%	
%		<succeeded = Goal>;
%		if (!succeeded) {
%		    <do Goals>;
%		}
%	}

% model_semi disj:

%	model_det goal:
%		<succeeded = (Goal ; Goals)>
%	===>
%	{
%		bool succeeded;
%
%		<do Goal>
%		succeeded = TRUE
%		/* <Goals> will never be reached */
%	}

%	model_semi goal:
%		<succeeded = (Goal ; Goals)>
%	===>
%	{
%		bool succeeded;
%
%		<succeeded = Goal>;
%		if (!succeeded) {
%		    <succeeded = Goals>;
%		}
%	}

% model_non disj:
%
%	model_det goal:
%		<(Goal ; Goals) && SUCCEED()>
%	===>
%		<Goal>
%		SUCCEED();
%		<Goals && SUCCEED()>
%
%	model_semi goal:
%		<(Goal ; Goals) && SUCCEED()>
%	===>
%	{
%		bool succeeded;
%	
%		<succeeded = Goal>
%		if (succeeded) SUCCEED();
%		<Goals && SUCCEED()>
%	}
%
%	model_non goal:
%		<(Goal ; Goals) && SUCCEED()>
%	===>
%		<Goal && SUCCEED()>
%		<Goals && SUCCEED()>

%-----------------------------------------------------------------------------%
%
% Code for if-then-else
%

%	model_semi cond:
%		<(Cond -> Then ; Else)>
%	===>
%	{
%		bool succeeded;
%	
%		<succeeded = Cond>
%		if (succeeded) {
%			<Then>
%		} else {
%			<Else>
%		}
%	}

%	/*
%	** XXX The following transformation does not do as good a job of GC
%	**     as it could.  Ideally we ought to ensure that stuff used only
%	**     in the `Else' part will be reclaimed if a GC occurs during
%	**     the `Then' part.  But that is a bit tricky to achieve.
%	*/
%
%	model_non cond:
%		<(Cond -> Then ; Else)>
%	===>
%	{
%		bool succeeded;
%
%		void then_func() {
%			succeeded = TRUE;
%			<Then>
%		}
%
%		succeeded = FALSE;
%		<Cond && then_func()>
%		if (!succeeded) {
%			<Else>
%		}
%	}

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