[m-rev.] for review: --warn-non-tail-recursion

[Peter Ross]

On Tue, Feb 12, 2002 at 12:58:58AM +1100, Fergus Henderson wrote:
> Estimated hours taken: 2
> Branches: main
> 
> Implement a new option `--warn-non-tail-recursion'.
> 
> compiler/ml_tailcall.m:
> 	Add a pass to warn about directly recursive calls that are not
> 	tail calls.
> 
> compiler/options.m:
> doc/user_guide.texi:
> 	Add a new option to enable the new pass.
> 
> compiler/mercury_compile.m:
> 	Add code to invoke the new pass.
> 
> compiler/handle_options.m:
> 	If --warn-non-tail-recursion is set, then report an error
> 	if either --high-level-code or --optimize-tailcalls is not,
> 	or if --error-check-only is set.
> 
> Workspace: /home/ceres/fjh/mercury
> Index: compiler/ml_tailcall.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/compiler/ml_tailcall.m,v
> retrieving revision 1.14
> diff -u -d -r1.14 ml_tailcall.m
> --- compiler/ml_tailcall.m	6 Feb 2002 18:44:19 -0000	1.14
> +++ compiler/ml_tailcall.m	11 Feb 2002 13:30:16 -0000
> @@ -11,6 +11,10 @@
>  % that marks function calls as tail calls whenever
>  % it is safe to do so, based on the assumptions described below.
>  
> +% This module also contains a pass over the MLDS that detects functions
> +% which are directly recursive, but not tail-recursive,
> +% and warns about them.
> +
>  % A function call can safely be marked as a tail call if
>  %	(1) it occurs in a position which would fall through into the
>  %	    end of the function body or to a `return' statement,
> @@ -60,10 +64,17 @@
>  :- pred ml_mark_tailcalls(mlds, mlds, io__state, io__state).
>  :- mode ml_mark_tailcalls(in, out, di, uo) is det.
>  
> +	% Traverse the MLDS, warning about all directly recursive calls
> +	% that are not marked as tail calls.
> +	%
> +:- pred ml_warn_tailcalls(mlds, io__state, io__state).
> +:- mode ml_warn_tailcalls(in, di, uo) is det.
> +
>  %-----------------------------------------------------------------------------%
>  %-----------------------------------------------------------------------------%
>  
>  :- implementation.
> +:- import_module prog_data, hlds_out, error_util, ml_util.
>  :- import_module list, std_util.
>  
>  ml_mark_tailcalls(MLDS0, MLDS) -->
> @@ -543,6 +554,86 @@
>  		Locals = params(Params),
>  		list__member(Param, Params),
>  		Param = mlds__argument(Name, _, _)
> +	).
> +
> +%-----------------------------------------------------------------------------%
> +
> +ml_warn_tailcalls(MLDS) -->
> +	{ solutions(nontailcall_in_mlds(MLDS), Warnings) },
> +	list__foldl(report_nontailcall_warning, Warnings).
> +
> +:- type tailcall_warning ---> tailcall_warning(
> +		mlds__pred_label,
> +		% XXX perhaps we should also include the proc_id here
> +		mlds__context
> +	).

Well as I see it the advantage of including the proc_id is that it would
allow one to report which mode is non tail recursive.  I think this
would be useful information as not all modes of a procedure will be tail
recursive.  So I suggest that you do it.

> +
> +:- pred nontailcall_in_mlds(mlds::in, tailcall_warning::out) is nondet.
> +nontailcall_in_mlds(MLDS, Warning) :-
> +	MLDS = mlds(ModuleName, _ForeignCode, _Imports, Defns),
> +	MLDS_ModuleName = mercury_module_name_to_mlds(ModuleName),
> +	nontailcall_in_defns(MLDS_ModuleName, Defns, Warning).
> +
> +:- pred nontailcall_in_defns(mlds_module_name::in, mlds__defns::in,
> +		tailcall_warning::out) is nondet.
> +nontailcall_in_defns(ModuleName, Defns, Warning) :-
> +	list__member(Defn, Defns),
> +	nontailcall_in_defn(ModuleName, Defn, Warning).
> +
> +:- pred nontailcall_in_defn(mlds_module_name::in, mlds__defn::in,
> +		tailcall_warning::out) is nondet.
> +nontailcall_in_defn(ModuleName, Defn, Warning) :-
> +	Defn = mlds__defn(Name, _Context, _Flags, DefnBody),
> +	(
> +		DefnBody = mlds__function(_PredProcId, _Params, FuncBody,
> +			_Attributes),
> +		FuncBody = defined_here(Body),
> +		nontailcall_in_statement(ModuleName, Name, Body, Warning)
> +	;
> +		DefnBody = mlds__class(ClassDefn),
> +		ClassDefn = class_defn(_Kind, _Imports, _BaseClasses,
> +			_Implements, CtorDefns, MemberDefns),
> +		( nontailcall_in_defns(ModuleName, CtorDefns, Warning)
> +		; nontailcall_in_defns(ModuleName, MemberDefns, Warning)
> +		)
> +	).
> +
> +:- pred nontailcall_in_statement(mlds_module_name::in, mlds__entity_name::in,
> +		mlds__statement::in, tailcall_warning::out) is nondet.
> +
> +nontailcall_in_statement(CallerModule, CallerFuncName, Statement, Warning) :-
> +	% nondeterministically find a non-tail call
> +	statement_contains_statement(Statement, SubStatement),
> +	SubStatement = mlds__statement(SubStmt, Context),
> +	SubStmt = call(_CallSig, Func, _This, _Args, _RetVals, IsTailCall),
> +	IsTailCall = call,
> +	% check if this call is a directly recursive call
> +	Func = const(code_addr_const(CodeAddr)),
> +	( CodeAddr = proc(QualProcLabel, _Sig), MaybeSeqNum = no
> +	; CodeAddr = internal(QualProcLabel, SeqNum, _Sig),
> +	  MaybeSeqNum = yes(SeqNum)
> +	),
> +	QualProcLabel = qual(CallerModule, PredLabel - ProcId),
> +	CallerFuncName = function(PredLabel, ProcId, MaybeSeqNum, _PredId),
> +	% if so, construct an appropriate warning
> +	Warning = tailcall_warning(PredLabel, Context). % XXX include ProcId?
> +
> +:- pred report_nontailcall_warning(tailcall_warning::in,
> +		io__state::di, io__state::uo) is det.
> +
> +report_nontailcall_warning(tailcall_warning(PredLabel, Context)) -->
> +	(
> +		{ PredLabel = pred(PredOrFunc, _MaybeModule, Name, Arity,
> +			_CodeModel, _NonOutputFunc) },
> +		{ hlds_out__simple_call_id_to_string(PredOrFunc -
> +			unqualified(Name) / Arity, CallId) },
> +		report_warning(mlds__get_prog_context(Context), 0, [
> +		    words("In "), fixed(CallId), nl,
> +		    words("  warning: recursive call is not tail recursive.")
> +		])
> +	;
> +		{ PredLabel = special_pred(_, _, _, _) }
> +		% don't warn about these
>  	).
>  
>  %-----------------------------------------------------------------------------%

Apart from the comment about the proc_id, this looks fine and I know
there have been times I would have found it useful.

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------