[m-dev.] diff: --checked-nondet-tailcalls
Zoltan Somogyi
zs at cs.mu.OZ.AU
Wed Sep 29 15:36:08 AEST 1999
This has already been reviewed a while ago; I made the changes requested,
including using the more expressibve option name above.
Estimated hours taken: 6
Add a new option, --checked-nondet-tailcalls, that enables the use of
Prolog style nondet tail calls (which check whether the current frame is
on top of the nondet stack and only do a tail call if it is).
This option is not likely to help Mercury code, since most of the time
the test will fail, which means we incurred its cost and did not gain
the benefit of the tailcall. However, HAL often has predicates that are
declared nondet but are det or semidet most of the time, and these can
benefit.
compiler/options.m:
doc/user_guide.texi:
Add the new option, which is not on by default and is not turned on
at any optimization level; you have to give it explicitly.
compiler/llds.m:
Modify the call_model type to distinguish the new style nondet tail
call from the old (which does not do a runtime test).
compiler/code_info.m:
Check the fail state whether it is suitable for new style nondet
tail calls.
compiler/call_gen.m:
Put the result from code_info.m into the generated LLDS.
compiler/jumpopt.m:
Use the new status field in the LLDS to perform the optimization,
if the option is given.
Document the main predicate and its new argument.
compiler/optimize.m:
Pass the value of the new option to jumpopt.
tests/hard_coded/checked_nondet_tailcall.{m,exp}:
A new test case to check that the code we generate with the new
option works correctly. (Checking whether it actually reduces
nondet stack usage would be harder.)
Zoltan.
cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/call_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/call_gen.m,v
retrieving revision 1.134
diff -u -b -r1.134 call_gen.m
--- call_gen.m 1999/08/13 01:42:56 1.134
+++ call_gen.m 1999/09/21 01:59:26
@@ -394,8 +394,8 @@
{ FlushCode = empty }
;
{ CodeModel = model_non },
- code_info__may_use_nondet_tailcall(TailCall),
- { CallModel = nondet(TailCall) },
+ code_info__may_use_nondet_tailcall(TailCallStatus),
+ { CallModel = nondet(TailCallStatus) },
code_info__flush_resume_vars_to_stack(FlushCode),
code_info__set_resume_point_and_frame_to_unknown
).
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.240
diff -u -b -r1.240 code_info.m
--- code_info.m 1999/08/16 05:47:54 1.240
+++ code_info.m 1999/09/21 07:51:37
@@ -1188,12 +1188,12 @@
:- pred code_info__failure_is_direct_branch(code_addr::out,
code_info::in, code_info::out) is semidet.
- % Checks whether the current failure environment would allow
- % a model_non call at this point to be turned into a tail call,
- % provided of course that the return from the call is followed
- % immediately by succeed().
+ % Checks under what circumstances the current failure environment
+ % would allow a model_non call at this point to be turned into a
+ % tail call, provided of course that the return from the call is
+ % followed immediately by succeed().
-:- pred code_info__may_use_nondet_tailcall(bool::out,
+:- pred code_info__may_use_nondet_tailcall(nondet_tail_call::out,
code_info::in, code_info::out) is det.
% Materialize the given variables into registers or stack slots.
@@ -2102,18 +2102,24 @@
{ stack__top(ResumePoints, TopResumePoint) },
code_info__pick_matching_resume_addr(TopResumePoint, CodeAddr).
-code_info__may_use_nondet_tailcall(MayTailCall) -->
+code_info__may_use_nondet_tailcall(TailCallStatus) -->
code_info__get_fail_info(FailInfo),
- { FailInfo = fail_info(ResumePoints, ResumeKnown, _, _, _) },
- (
- { ResumeKnown = resume_point_known },
- { stack__top_det(ResumePoints, TopResumePoint) },
- { TopResumePoint = stack_only(_, do_fail) }
+ { FailInfo = fail_info(ResumePoints0, ResumeKnown, _, _, _) },
+ {
+ stack__pop(ResumePoints0, ResumePoint1, ResumePoints1),
+ stack__is_empty(ResumePoints1),
+ ResumePoint1 = stack_only(_, do_fail)
->
- { MayTailCall = yes }
+ (
+ ResumeKnown = resume_point_known,
+ TailCallStatus = unchecked_tail_call
;
- { MayTailCall = no }
- ).
+ ResumeKnown = resume_point_unknown,
+ TailCallStatus = checked_tail_call
+ )
+ ;
+ TailCallStatus = no_tail_call
+ }.
%---------------------------------------------------------------------------%
Index: compiler/jumpopt.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/jumpopt.m,v
retrieving revision 1.47
diff -u -b -r1.47 jumpopt.m
--- jumpopt.m 1999/07/10 07:19:51 1.47
+++ jumpopt.m 1999/09/21 07:51:24
@@ -17,15 +17,31 @@
:- import_module llds.
:- import_module list, bool.
-:- pred jumpopt_main(list(instruction), bool, bool, list(instruction), bool).
-:- mode jumpopt_main(in, in, in, out, out) is det.
+ % Take an instruction list and optimize jumps. This includes jumps
+ % implicit in procedure returns.
+ %
+ % The three bool inputs should be
+ %
+ % - the value of the --optimize-fulljumps option,
+ %
+ % - an indication of whether this is the final application of this
+ % optimization, and
+ %
+ % - the value of the --checked-nondet-tailcalls option respectively.
+ %
+ % The bool output says whether the instruction sequence was modified
+ % by the optimization.
+
+:- pred jumpopt_main(list(instruction), bool, bool, bool,
+ list(instruction), bool).
+:- mode jumpopt_main(in, in, in, in, out, out) is det.
%-----------------------------------------------------------------------------%
:- implementation.
:- import_module builtin_ops, code_util, opt_util.
-:- import_module std_util, map, string, require.
+:- import_module int, std_util, map, string, require.
% We first build up a bunch of tables giving information about labels.
% We then traverse the instruction list, using the information in the
@@ -53,7 +69,7 @@
% numbering, which can do a better job of optimizing this block, have
% been applied.
-jumpopt_main(Instrs0, Blockopt, Recjump, Instrs, Mod) :-
+jumpopt_main(Instrs0, Blockopt, Recjump, MostlyDetTailCall, Instrs, Mod) :-
map__init(Instrmap0),
map__init(Lvalmap0),
map__init(Procmap0),
@@ -65,8 +81,16 @@
Procmap0, Procmap, Sdprocmap0, Sdprocmap, Succmap0, Succmap),
map__init(Forkmap0),
jumpopt__build_forkmap(Instrs0, Sdprocmap, Forkmap0, Forkmap),
+ ( MostlyDetTailCall = yes ->
+ opt_util__get_prologue(Instrs0, ProcLabel, _, _, _),
+ opt_util__new_label_no(Instrs0, 500, LabelNum),
+ MostlyDetTailCallInfo = yes(ProcLabel - LabelNum)
+ ;
+ MostlyDetTailCallInfo = no
+ ),
jumpopt__instr_list(Instrs0, comment(""), Instrmap, Blockmap, Lvalmap,
- Procmap, Sdprocmap, Forkmap, Succmap, Instrs1),
+ Procmap, Sdprocmap, Forkmap, Succmap, MostlyDetTailCallInfo,
+ _, Instrs1),
opt_util__filter_out_bad_livevals(Instrs1, Instrs),
( Instrs = Instrs0 ->
Mod = no
@@ -184,14 +208,18 @@
% between the if-val and the goto.
:- pred jumpopt__instr_list(list(instruction), instr, instrmap, tailmap,
- lvalmap, tailmap, tailmap, tailmap, tailmap, list(instruction)).
-:- mode jumpopt__instr_list(in, in, in, in, in, in, in, in, in, out)
+ lvalmap, tailmap, tailmap, tailmap, tailmap,
+ maybe(pair(proc_label, int)), maybe(pair(proc_label, int)),
+ list(instruction)).
+:- mode jumpopt__instr_list(in, in, in, in, in, in, in, in, in, in, out, out)
is det.
jumpopt__instr_list([], _PrevInstr, _Instrmap, _Blockmap,
- _Lvalmap, _Procmap, _Sdprocmap, _Forkmap, _Succmap, []).
+ _Lvalmap, _Procmap, _Sdprocmap, _Forkmap, _Succmap,
+ MostlyDetTailCallInfo, MostlyDetTailCallInfo, []).
jumpopt__instr_list([Instr0 | Instrs0], PrevInstr, Instrmap, Blockmap,
- Lvalmap, Procmap, Sdprocmap, Forkmap, Succmap, Instrs) :-
+ Lvalmap, Procmap, Sdprocmap, Forkmap, Succmap,
+ MostlyDetTailCallInfo0, MostlyDetTailCallInfo, Instrs) :-
Instr0 = Uinstr0 - Comment0,
string__append(Comment0, " (redirected return)", Redirect),
(
@@ -209,7 +237,8 @@
opt_util__filter_out_livevals(Between0, Between1),
list__append(Between1, [livevals(Livevals) - "",
goto(Proc) - Redirect], NewInstrs),
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
% Look for semidet style tailcalls.
CallModel = semidet,
@@ -218,10 +247,12 @@
->
list__append(Between, [livevals(Livevals) - "",
goto(Proc) - Redirect], NewInstrs),
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
- % Look for nondet style tailcalls.
- CallModel = nondet(yes),
+ % Look for nondet style tailcalls which do not need
+ % a runtime check.
+ CallModel = nondet(unchecked_tail_call),
map__search(Succmap, RetLabel, BetweenIncl),
BetweenIncl = [livevals(_) - _, goto(_) - _],
PrevInstr = livevals(Livevals)
@@ -236,8 +267,37 @@
livevals(Livevals) - "",
goto(Proc) - Redirect
],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
+ % Look for nondet style tailcalls which do need
+ % a runtime check.
+ CallModel = nondet(checked_tail_call),
+ MostlyDetTailCallInfo0 = yes(ProcLabel - LabelNum0),
+ map__search(Succmap, RetLabel, BetweenIncl),
+ BetweenIncl = [livevals(_) - _, goto(_) - _],
+ PrevInstr = livevals(Livevals)
+ ->
+ NewLabel = local(ProcLabel, LabelNum0),
+ NewInstrs = [
+ if_val(binop(ne, lval(curfr), lval(maxfr)),
+ label(NewLabel))
+ - "branch around if cannot tail call",
+ assign(maxfr, lval(prevfr(lval(curfr))))
+ - "discard this frame",
+ assign(succip, lval(succip(lval(curfr))))
+ - "setup PC on return from tailcall",
+ assign(curfr, lval(succfr(lval(curfr))))
+ - "setup curfr on return from tailcall",
+ livevals(Livevals) - "",
+ goto(Proc) - Redirect,
+ label(NewLabel) - "non tail call",
+ Instr0
+ ],
+ RemainInstrs = Instrs0,
+ LabelNum1 is LabelNum0 + 1,
+ MostlyDetTailCallInfo1 = yes(ProcLabel - LabelNum1)
+ ;
% Short circuit the return label if possible.
map__search(Instrmap, RetLabel, RetInstr)
->
@@ -250,10 +310,12 @@
NewInstrs = [call(Proc, label(DestLabel),
GC, CallModel) - Redirect],
RemainInstrs = Instrs0
- )
+ ),
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
NewInstrs = [Instr0],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
)
;
Uinstr0 = goto(label(TargetLabel))
@@ -263,7 +325,8 @@
opt_util__is_this_label_next(TargetLabel, Instrs0, _)
->
NewInstrs = [],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
PrevInstr = if_val(_, label(IfTargetLabel)),
opt_util__is_this_label_next(IfTargetLabel, Instrs0, _)
@@ -275,7 +338,8 @@
% We cannot eliminate the instruction here because
% that would require altering the if_val instruction.
NewInstrs = [Instr0],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
% Replace a jump to a det epilog with the epilog.
map__search(Procmap, TargetLabel, Between0)
@@ -283,7 +347,8 @@
jumpopt__adjust_livevals(PrevInstr, Between0, Between),
list__append(Between, [goto(succip) - "shortcircuit"],
NewInstrs),
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
% Replace a jump to a semidet epilog with the epilog.
map__search(Sdprocmap, TargetLabel, Between0)
@@ -291,14 +356,16 @@
jumpopt__adjust_livevals(PrevInstr, Between0, Between),
list__append(Between, [goto(succip) - "shortcircuit"],
NewInstrs),
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
% Replace a jump to a nondet epilog with the epilog.
map__search(Succmap, TargetLabel, BetweenIncl0)
->
jumpopt__adjust_livevals(PrevInstr, BetweenIncl0,
NewInstrs),
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
% Replace a jump to a non-epilog block with the
% block itself. These jumps are treated separately
@@ -330,7 +397,9 @@
map__delete(Blockmap, DestLabel, CrippledBlockmap),
jumpopt__instr_list(AdjustedBlock, comment(""),
Instrmap, CrippledBlockmap, Lvalmap, Procmap,
- Sdprocmap, Forkmap, Succmap, NewInstrs),
+ Sdprocmap, Forkmap, Succmap,
+ MostlyDetTailCallInfo0,
+ MostlyDetTailCallInfo1, NewInstrs),
RemainInstrs = Instrs0
;
% Short-circuit the goto.
@@ -361,15 +430,18 @@
[Lvalinstr | NewInstrs0], NewInstrs)
;
NewInstrs = NewInstrs0
- )
+ ),
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
NewInstrs = [Instr0],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
)
; Uinstr0 = computed_goto(Index, LabelList0) ->
% Short-circuit all the destination labels.
jumpopt__short_labels(LabelList0, Instrmap, LabelList),
RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0,
( LabelList = LabelList0 ->
NewInstrs = [Instr0]
;
@@ -424,7 +496,8 @@
% the recursive call. We can't go into an infinite
% loop because each application of the transformation
% strictly reduces the size of the code.
- RemainInstrs = [NewInstr | AfterGoto]
+ RemainInstrs = [NewInstr | AfterGoto],
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
map__search(Instrmap, TargetLabel, TargetInstr)
->
@@ -488,15 +561,18 @@
;
NewInstrs = [Instr0],
RemainInstrs = Instrs0
- )
+ ),
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
;
NewInstrs = [Instr0],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
)
; Uinstr0 = assign(Lval, Rval0) ->
% Any labels mentioned in Rval0 should be short-circuited.
jumpopt__short_labels_rval(Rval0, Instrmap, Rval),
RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0,
( Rval = Rval0 ->
NewInstrs = [Instr0]
;
@@ -506,7 +582,8 @@
)
;
NewInstrs = [Instr0],
- RemainInstrs = Instrs0
+ RemainInstrs = Instrs0,
+ MostlyDetTailCallInfo1 = MostlyDetTailCallInfo0
),
( ( Uinstr0 = comment(_) ; NewInstrs = [] ) ->
NewPrevInstr = PrevInstr
@@ -514,7 +591,8 @@
NewPrevInstr = Uinstr0
),
jumpopt__instr_list(RemainInstrs, NewPrevInstr, Instrmap, Blockmap,
- Lvalmap, Procmap, Sdprocmap, Forkmap, Succmap, Instrs9),
+ Lvalmap, Procmap, Sdprocmap, Forkmap, Succmap,
+ MostlyDetTailCallInfo1, MostlyDetTailCallInfo, Instrs9),
list__append(NewInstrs, Instrs9, Instrs).
% We avoid generating statements that redefine the value of a location
Index: compiler/llds.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/llds.m,v
retrieving revision 1.249
diff -u -b -r1.249 llds.m
--- llds.m 1999/09/20 08:16:49 1.249
+++ llds.m 1999/09/21 01:56:54
@@ -195,10 +195,37 @@
:- type instruction == pair(instr, string).
% instruction, comment
+:- type nondet_tail_call
+ ---> no_tail_call
+ % At the point of the call, the procedure has
+ % more alternatives.
+ %
+ % Under these conditions, the call cannot be
+ % transformed into a tail call.
+ ; checked_tail_call
+ % At the point of the call, the procedure has
+ % no more alternatives, and curfr and maxfr
+ % are not guaranteed to be identical.
+ %
+ % Under these conditions, the call can be
+ % transformed into a tail call whenever its
+ % return address leads to the procedure
+ % epilogue AND curfr and maxfr are found
+ % to be identical at runtime.
+ ; unchecked_tail_call.
+ % At the point of the call the procedure has no
+ % more alternatives, and curfr and maxfr are
+ % guaranteed to be identical.
+ %
+ % Under these conditions, the call can be
+ % transformed into a tail call whenever its
+ % return address leads to the procedure
+ % epilogue.
+
:- type call_model
---> det
; semidet
- ; nondet(bool).
+ ; nondet(nondet_tail_call).
% `instr' defines the various LLDS virtual machine instructions.
% Each instruction gets compiled to a simple piece of C code
Index: compiler/optimize.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/optimize.m,v
retrieving revision 1.17
diff -u -b -r1.17 optimize.m
--- optimize.m 1999/07/12 06:21:21 1.17
+++ optimize.m 1999/09/21 00:50:13
@@ -134,6 +134,8 @@
),
globals__io_lookup_bool_option(optimize_jumps, Jumpopt),
globals__io_lookup_bool_option(optimize_fulljumps, FullJumpopt),
+ globals__io_lookup_bool_option(checked_nondet_tailcalls,
+ CheckedNondetTailCalls),
( { Jumpopt = yes } ->
( { VeryVerbose = yes } ->
io__write_string("% Optimizing jumps for "),
@@ -142,7 +144,8 @@
;
[]
),
- { jumpopt_main(Instrs1, FullJumpopt, Final, Instrs2, Mod1) },
+ { jumpopt_main(Instrs1, FullJumpopt, Final,
+ CheckedNondetTailCalls, Instrs2, Mod1) },
( { Mod1 = yes } ->
opt_debug__msg(DebugOpt, "after jump optimization"),
opt_debug__dump_instrs(DebugOpt, Instrs2)
@@ -248,6 +251,8 @@
[]
),
globals__io_lookup_bool_option(optimize_fulljumps, FullJumpopt),
+ globals__io_lookup_bool_option(checked_nondet_tailcalls,
+ CheckedNondetTailCalls),
( { Jumps = yes, FullJumpopt = yes } ->
( { VeryVerbose = yes } ->
io__write_string("% Optimizing jumps for "),
@@ -257,7 +262,7 @@
[]
),
{ jumpopt_main(Instrs1, FullJumpopt, Final,
- Instrs2, Mod2) },
+ CheckedNondetTailCalls, Instrs2, Mod2) },
( { Mod2 = yes } ->
opt_debug__msg(DebugOpt, "after jump optimization"),
opt_debug__dump_instrs(DebugOpt, Instrs2)
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.268
diff -u -b -r1.268 options.m
--- options.m 1999/09/13 04:51:05 1.268
+++ options.m 1999/09/29 04:51:58
@@ -322,6 +322,7 @@
; optimize_peep
; optimize_jumps
; optimize_fulljumps
+ ; checked_nondet_tailcalls
; optimize_labels
; optimize_dups
%%% unused: ; optimize_copyprop
@@ -663,6 +664,7 @@
optimize_peep - bool(no),
optimize_jumps - bool(no),
optimize_fulljumps - bool(no),
+ checked_nondet_tailcalls - bool(no),
optimize_labels - bool(no),
optimize_dups - bool(no),
%%% optimize_copyprop - bool(no),
@@ -1023,6 +1025,7 @@
long_option("optimise-jumps", optimize_jumps).
long_option("optimize-fulljumps", optimize_fulljumps).
long_option("optimise-fulljumps", optimize_fulljumps).
+long_option("checked-nondet-tailcalls", checked_nondet_tailcalls).
long_option("optimize-labels", optimize_labels).
long_option("optimise-labels", optimize_labels).
long_option("optimize-dups", optimize_dups).
@@ -2119,6 +2122,10 @@
"\tDisable elimination of jumps to jumps.",
"--no-optimize-fulljumps",
"\tDisable elimination of jumps to ordinary code.",
+ "--checked-nondet-tailcalls",
+ "\tConvert nondet calls into tail calls whenever possible, even",
+ "\twhen this requires a runtime check. This option tries to",
+ "\tminimize stack consumption, possibly at the expense of speed.",
"--no-optimize-labels",
"\tDisable elimination of dead labels and code.",
"--optimize-dups",
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing doc
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.184
diff -u -b -r1.184 user_guide.texi
--- user_guide.texi 1999/08/18 06:26:06 1.184
+++ user_guide.texi 1999/09/21 00:51:49
@@ -3576,6 +3576,12 @@
Disable elimination of jumps to ordinary code.
@sp 1
+ at item --checked-nondet-tailcalls
+Convert nondet calls into tail calls whenever possible, even
+when this requires a runtime check. This option tries to
+minimize stack consumption, possibly at the expense of speed.
+
+ at sp 1
@item --no-optimize-labels
Disable elimination of dead labels and code.
cvs diff: Diffing extras
cvs diff: Diffing extras/aditi
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing library
cvs diff: Diffing profiler
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/hard_coded
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.64
diff -u -b -r1.64 Mmakefile
--- Mmakefile 1999/08/31 12:55:48 1.64
+++ Mmakefile 1999/09/21 01:06:25
@@ -16,6 +16,7 @@
cc_and_non_cc_test \
cc_nondet_disj \
cc_multi_bug \
+ checked_nondet_tailcall \
closure_extension \
common_type_cast \
construct \
@@ -104,6 +105,7 @@
# some tests need to be compiled with particular options
+MCFLAGS-checked_nondet_tailcall = --checked-nondet-tailcall
MCFLAGS-bigtest = --intermodule-optimization -O3
MCFLAGS-lp = --intermodule-optimization -O3
MCFLAGS-boyer = --infer-all
Index: tests/hard_coded/checked_nondet_tailcall.exp
===================================================================
RCS file: checked_nondet_tailcall.exp
diff -N checked_nondet_tailcall.exp
--- /dev/null Wed Sep 29 15:20:58 1999
+++ checked_nondet_tailcall.exp Tue Sep 21 11:45:46 1999
@@ -0,0 +1,5 @@
+18 19
+21 22
+31
+41
+
Index: tests/hard_coded/checked_nondet_tailcall.m
===================================================================
RCS file: checked_nondet_tailcall.m
diff -N checked_nondet_tailcall.m
--- /dev/null Wed Sep 29 15:20:58 1999
+++ checked_nondet_tailcall.m Tue Sep 21 12:29:45 1999
@@ -0,0 +1,68 @@
+:- module checked_nondet_tailcall.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io__state::di, io__state::uo) is det.
+
+:- implementation.
+
+:- import_module list, std_util.
+
+main -->
+ { join(1, Ones) },
+ write_ints(Ones),
+ { join(2, Twos) },
+ write_ints(Twos),
+ { join(3, Threes) },
+ write_ints(Threes),
+ { join(4, Fours) },
+ write_ints(Fours),
+ { join(5, Fives) },
+ write_ints(Fives).
+
+:- pred edge1(int::in, int::out) is nondet.
+
+edge1(1, 11).
+edge1(1, 12).
+
+:- pred edge2(int::in, int::out) is nondet.
+
+edge2(11, 18).
+edge2(12, 19).
+edge2(2, 21).
+edge2(2, 22).
+edge2(3, 31).
+edge2(4, 41).
+
+:- pred edge12(int::in, int::out) is nondet.
+
+edge12(A, B) :-
+ ( edge1(A, C) ->
+ % When we come here after the last success of edge1,
+ % the call to edge2 will be a checked nondet tailcall.
+ % When we come here after a non-last success of edge1,
+ % the check will fail, and we will have to do a
+ % non-tail call.
+ D = C
+ ;
+ % When this arm of the switch is taken, the call to edge2
+ % will be a checked nondet tailcall.
+ D = A
+ ),
+ edge2(D, B).
+
+:- pred join(int::in, list(int)::out) is det.
+
+join(A, Bs) :-
+ solutions(lambda([B::out] is nondet, (edge12(A, B))), Bs).
+
+:- pred write_ints(list(int)::in, io__state::di, io__state::uo) is det.
+
+write_ints([]) -->
+ io__write_string("\n").
+write_ints([X | Xs]) -->
+ io__write_int(X),
+ io__write_string(" "),
+ write_ints(Xs).
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: [15:21:06] waiting for dgj's lock in /home/mercury1/repository/tests/hard_coded/typeclasses
cvs diff: [15:21:36] waiting for dgj's lock in /home/mercury1/repository/tests/hard_coded/typeclasses
cvs diff: [15:22:06] obtained lock in /home/mercury1/repository/tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/tabling
cvs diff: [15:22:22] waiting for zs's lock in /home/mercury1/repository/tests/tabling
cvs diff: [15:22:52] obtained lock in /home/mercury1/repository/tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing trial
cvs diff: Diffing util
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the developers
mailing list