[m-rev.] for review: accurately calculate depth to build subtrees to
Ian MacLarty
maclarty at cs.mu.OZ.AU
Tue May 10 17:48:41 AEST 2005
This diff replaces a previous one I submitted under the subject "build subtrees
based on desired nodes, instead of desired depth". I never
committed that diff since the heuristic it used turned out to be grossly
inaccurate when used on the Mercury compiler. The required depth is now
calculated instead of estimated.
Julien partially reviewed that diff and I have included any changes he
suggested in this diff, though most of the code is different.
I have omitted the changes to the test cases from this diff since they are
superficial and there are a lot of them.
For review by anyone.
Estimated hours taken: 15
Branches: main
In the declarative debugger, dynamically calculate the depth implicit subtrees
need to be built to, to achieve a desired weight.
This is done by recording the number of events at each depth in each
implicit subtree. The array used to record these depths need only be
as big as the desired weight divided by two, since the thinnest a tree can be
is a stick with two events at each depth (a CALL and an EXIT/FAIL/EXCP).
Initially the tree is built down to a predetermined, conservative depth. At
the root of each implicit subtree in the newly materialized tree, we record
the depth the implicit subtree needs to be built to, to achieve the desired
weight (this is refered to as the ideal depth in the code). This is done
everytime we materialize a new implicit subtree.
This results in about a 3.6% slowdown when the declarative debugger reexecutes
a portion of the program. However, this also reduces the number of
reexecutions of the program, since we needn't be conservative about how deep to
build subtrees to anymore. We also avoid adding too many nodes to the
annotated trace if the tree has a large branching factor, so we are able to
control memory usage more easily.
I also added a progress indicator which is activated if a reexecution continues
for more than a second.
I added some macros to optionally print benchmarking information when
building a new portion of the annotated trace.
browser/declarative_debugger.m:
Pass the ideal depth to build a subtree to, to the backend.
browser/declarative_execution.m:
Record the ideal depth at the CALL event corresponding to the root
of an implicit subtree.
Add predicates to get and set this value from the backend.
browser/declarative_tree.m:
Export a new predicate, trace_implicit_tree_info, which is used to
get the info stored at the root of an implicit root.
doc/user_guide.texi:
Change the --depth-step-size dd option to just --depth which is now
only used as the initial depth to build the subtree to. Comment out
the --depth option, since it requires knowledge of the internal
workings of the declarative debugger.
Document the new dd option, --nodes, which controls how many nodes
to build in the annotated trace at a time.
library/gc.m:
Export garbage_collect so it can be called from the backend when
printing out benchmarking information.
tests/debugger/declarative/*.{inp*, exp*}
For the tests set the --nodes and --depth options to a low value, so
that we exercise the code that builds new portions of the annotated
trace.
trace/mercury_trace_declarative.[ch]:
Move the MR_DECL_UNTABLED_IO_RETRY_MESSAGE macro to
mercury_trace_declarative.h.
Add some macros and functions which print benchmarking information
if the MR_DD_PRINT_EDT_STATS macro is defined.
Show progress if the tree takes more than a second to generate.
Count the events at each depth in each implicit subtree.
Calculate the ideal depth when exiting an implicit subtree and store
this in the annotated trace.
Add the depth limit as an argument to MR_trace_restart_decl_debug
instead of using the value of the global MR_edt_depth_step_size
(which no longer exists).
trace/mercury_trace_internal.c:
Add and handle the --nodes dd option. Rename the --depth-step-size
option to --depth.
Index: browser/declarative_debugger.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_debugger.m,v
retrieving revision 1.57
diff -u -b -r1.57 declarative_debugger.m
--- browser/declarative_debugger.m 10 May 2005 04:28:20 -0000 1.57
+++ browser/declarative_debugger.m 10 May 2005 04:57:54 -0000
@@ -260,15 +260,27 @@
% The analyser requires the back end to reproduce
% part of the annotated trace, with a greater
- % depth bound. The event number and sequence
+ % depth bound.
+ %
+ ; require_subtree(
+ %
+ % The event number and sequence
% number are for the final event required (the
% first event required is the call event with
% the same sequence number).
- % R is the node preceeding the call node. This is
- % needed so the root of the new tree can have the
- % correct preceding node.
%
- ; require_subtree(event_number, sequence_number, R)
+ require_subtree_final_event :: event_number,
+ require_subtree_seqno :: sequence_number,
+
+ % The node preceding the call node. This
+ % is needed so the root of the new tree can
+ % have the correct preceding node.
+ require_subtree_call_preceding_node :: R,
+
+ % The maximum depth to build the new subtree
+ % to.
+ require_subtree_max_depth :: int
+ )
% The analyser requires events before and after the
% current set of materialized events to be generated.
@@ -455,10 +467,19 @@
handle_oracle_response(Store, OracleResponse, Response, !Diagnoser,
!IO).
-handle_analyser_response(Store, require_explicit_subtree(Node), _,
- Response, Diagnoser, Diagnoser, !IO) :-
+handle_analyser_response(Store, require_explicit_subtree(Node), _, Response,
+ Diagnoser, Diagnoser, !IO) :-
edt_subtree_details(Store, Node, Event, Seqno, CallPreceding),
- Response = require_subtree(Event, Seqno, CallPreceding).
+ (
+ trace_implicit_tree_info(wrap(Store), Node, ImplicitTreeInfo)
+ ->
+ ImplicitTreeInfo = implicit_tree_info(IdealDepth)
+ ;
+ throw(internal_error("handle_analyser_response",
+ "subtree requested for node which is not an " ++
+ "implicit root"))
+ ),
+ Response = require_subtree(Event, Seqno, CallPreceding, IdealDepth).
handle_analyser_response(Store, require_explicit_supertree(Node), _,
Response, Diagnoser, Diagnoser, !IO) :-
@@ -649,14 +670,14 @@
diagnoser_no_bug_found(no_bug_found).
:- pred diagnoser_require_subtree(diagnoser_response(trace_node_id)::in,
- event_number::out, sequence_number::out, trace_node_id::out)
+ event_number::out, sequence_number::out, trace_node_id::out, int::out)
is semidet.
-:- pragma export(diagnoser_require_subtree(in, out, out, out),
+:- pragma export(diagnoser_require_subtree(in, out, out, out, out),
"MR_DD_diagnoser_require_subtree").
-diagnoser_require_subtree(require_subtree(Event, SeqNo, CallPreceding),
- Event, SeqNo, CallPreceding).
+diagnoser_require_subtree(require_subtree(Event, SeqNo, CallPreceding,
+ MaxDepth), Event, SeqNo, CallPreceding, MaxDepth).
:- pred diagnoser_require_supertree(diagnoser_response(trace_node_id)::in,
event_number::out, sequence_number::out) is semidet.
Index: browser/declarative_execution.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_execution.m,v
retrieving revision 1.42
diff -u -b -r1.42 declarative_execution.m
--- browser/declarative_execution.m 12 Apr 2005 01:53:54 -0000 1.42
+++ browser/declarative_execution.m 10 May 2005 04:57:54 -0000
@@ -49,8 +49,12 @@
% Call sequence number.
call_event :: event_number,
% Trace event number.
- call_at_max_depth :: bool,
- % At the maximum depth?
+ call_at_max_depth :: maybe(implicit_tree_info),
+ % yes if the node is the root
+ % of an implicitly represented
+ % tree. Some information about
+ % the implicit tree is also
+ % stored.
call_return_label :: maybe(label_layout),
% The return label, if there
% is one.
@@ -200,6 +204,15 @@
% data structures.
).
+:- type implicit_tree_info
+ ---> implicit_tree_info(
+ % The maximum depth the implicit subtree can be
+ % materialized to, so that the weight of the
+ % materialized subtree will be less than or
+ % equal to the desired subtree weight.
+ ideal_depth :: int
+ ).
+
:- func get_trace_exit_atom(trace_node(R)) = trace_atom.
:- mode get_trace_exit_atom(in(trace_node_exit)) = out is det.
:- mode get_trace_exit_atom(in) = out is semidet.
@@ -1057,6 +1070,49 @@
%
set_trace_node_arg(Call1, 1, Last, Call).
+:- func call_node_update_implicit_tree_info(trace_node(trace_node_id)::di,
+ int::di) = (trace_node(trace_node_id)::out) is det.
+
+:- pragma export(call_node_update_implicit_tree_info(di, di) = out,
+ "MR_DD_call_node_update_implicit_tree_info").
+
+call_node_update_implicit_tree_info(Call0, IdealDepth) = Call :-
+ (
+ Call0 = call(_, _, _, _, _, _, _, _, _)
+ ->
+ Call1 = Call0
+ ;
+ throw(internal_error("call_node_update_implicit_tree_info",
+ "not a CALL node"))
+ ),
+ % call_at_max_depth is the sixth field, so we pass 5
+ % (since argument numbers start from 0).
+ %
+ set_trace_node_arg(Call1, 5, yes(implicit_tree_info(IdealDepth)),
+ Call).
+
+:- func get_implicit_tree_ideal_depth(trace_node(trace_node_id)) = int.
+
+:- pragma export(get_implicit_tree_ideal_depth(in) = out,
+ "MR_DD_get_implicit_tree_ideal_depth").
+
+get_implicit_tree_ideal_depth(Call) = IdealDepth :-
+ (
+ MaybeImplicitTreeInfo = Call ^ call_at_max_depth
+ ->
+ (
+ MaybeImplicitTreeInfo = yes(implicit_tree_info(
+ IdealDepth))
+ ;
+ MaybeImplicitTreeInfo = no,
+ throw(internal_error("get_implicit_tree_max_depth",
+ "not at max depth"))
+ )
+ ;
+ throw(internal_error("get_implicit_tree_max_depth",
+ "not a CALL node"))
+ ).
+
:- func cond_node_set_status(trace_node(trace_node_id)::di, goal_status::di)
= (trace_node(trace_node_id)::out) is det.
@@ -1238,16 +1294,26 @@
%
:- func construct_call_node(trace_node_id, list(trace_atom_arg),
- sequence_number, event_number, bool, maybe(label_layout),
- label_layout, int) = trace_node(trace_node_id).
+ sequence_number, event_number, bool, maybe(label_layout), label_layout,
+ int) = trace_node(trace_node_id).
:- pragma export(construct_call_node(in, in, in, in, in, in, in, in) = out,
"MR_DD_construct_call_node").
-construct_call_node(Preceding, AtomArgs, SeqNo, EventNo, MaxDepth,
+construct_call_node(Preceding, AtomArgs, SeqNo, EventNo, AtMaxDepth,
MaybeReturnLabel, Label, IoSeqNum) = Call :-
- Call = call(Preceding, Answer, AtomArgs, SeqNo, EventNo, MaxDepth,
- MaybeReturnLabel, Label, IoSeqNum),
- null_trace_node_id(Answer).
+ (
+ AtMaxDepth = no,
+ MaybeImplicitTreeInfo = no
+ ;
+ AtMaxDepth = yes,
+ % The ideal depth of the implicit tree will be updated
+ % when the corresponding EXIT, FAIL or EXCP event occurs,
+ % so for now we just set it to 0.
+ MaybeImplicitTreeInfo = yes(implicit_tree_info(0))
+ ),
+ null_trace_node_id(LastInterface),
+ Call = call(Preceding, LastInterface, AtomArgs, SeqNo, EventNo,
+ MaybeImplicitTreeInfo, MaybeReturnLabel, Label, IoSeqNum).
:- func make_yes_maybe_label(label_layout) = maybe(label_layout).
:- pragma export(make_yes_maybe_label(in) = out, "MR_DD_make_yes_maybe_label").
Index: browser/declarative_tree.m
===================================================================
RCS file: /home/mercury1/repository/mercury/browser/declarative_tree.m,v
retrieving revision 1.26
diff -u -b -r1.26 declarative_tree.m
--- browser/declarative_tree.m 11 Apr 2005 06:43:34 -0000 1.26
+++ browser/declarative_tree.m 10 May 2005 04:57:54 -0000
@@ -40,6 +40,9 @@
:- pred trace_atom_subterm_is_ground(trace_atom::in, arg_pos::in,
term_path::in) is semidet.
+:- pred trace_implicit_tree_info(wrap(S)::in, edt_node(R)::in,
+ implicit_tree_info::out) is semidet <= annotated_trace(S, R).
+
%-----------------------------------------------------------------------------%
:- implementation.
@@ -304,6 +307,11 @@
trace_is_implicit_root(wrap(Store), dynamic(Ref)) :-
get_edt_call_node(Store, Ref, CallId),
\+ not_at_depth_limit(Store, CallId).
+
+trace_implicit_tree_info(wrap(Store), dynamic(Ref), ImplicitTreeInfo) :-
+ get_edt_call_node(Store, Ref, CallId),
+ call_node_from_id(Store, CallId, CallNode),
+ CallNode ^ call_at_max_depth = yes(ImplicitTreeInfo).
:- pred trace_weight(wrap(S)::in, edt_node(R)::in, int::out, int::out)
is det <= annotated_trace(S, R).
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.435
diff -u -b -r1.435 user_guide.texi
--- doc/user_guide.texi 9 May 2005 08:05:05 -0000 1.435
+++ doc/user_guide.texi 10 May 2005 04:57:54 -0000
@@ -3312,22 +3312,28 @@
@ref{Declarative debugging} for details.
@sp 1
@table @code
- at item dd [-r] [-d at var{depth}] [-s at var{search-mode}]
- at c @item dd [--assume-all-io-is-tabled]
+ at item dd [-r] [-n at var{nodes}] [-s at var{search-mode}]
+ at c @item dd [--assume-all-io-is-tabled] [-d at var{depth}]
@c The --assume-all-io-is-tabled option is for developers only. Specifying it
@c makes an assertion, and if the assertion is incorrect, the resulting
@c behaviour would be hard for non-developers to understand. The option is
@c therefore deliberately not documented.
+ at c The value of the @samp{-d} or @samp{--depth} option determines
+ at c how much of the annotated trace to build initially. Subsequent runs
+ at c will try to add @var{nodes} events to the annotated trace, but initially
+ at c there is not enough information available to do this. We do not document
+ at c this option since it requires an understanding of the internal workings of
+ at c the declarative debugger.
Starts declarative debugging using the current event as the initial symptom.
@sp 1
When searching for bugs the declarative debugger needs to keep portions of the
execution trace in memory. If it requires a new portion of the trace then it
-needs to rerun the program. The @samp{-d at var{depth}} and
- at samp{--depth-step-size @var{depth}} options tell the declarative debugger how
+needs to rerun the program. The @samp{-n at var{nodes}} or
+ at samp{--nodes @var{nodes}} option tells the declarative debugger how
much of the execution trace to gather when it reruns the program. A higher
- at var{depth} will require more memory, but will improve the performance of the
-declarative debugger for long running programs since it will not have to rerun
-the program as much.
+value for @var{nodes} will require more memory, but will improve the
+performance of the declarative debugger for long running programs since it will
+not have to rerun the program as much.
@sp 1
The @samp{-s at var{search-mode}} or @samp{--search-mode @var{search-mode}}
option tells the declarative debugger which
@@ -3340,9 +3346,9 @@
declarative debugging session. If the @samp{--resume} option is given and
there were no previous declarative debugging sessions then the option will be
ignored. A @samp{dd --resume} command can be issued at any event. The
- at samp{--search-mode} or @samp{--depth-step-size} options can be used in
-conjunction with the @samp{--resume} option to change the search mode or depth
-step size of a previously started declarative debugging session.
+ at samp{--search-mode} option can be used in
+conjunction with the @samp{--resume} option to change the search mode
+of a previously started declarative debugging session.
@sp 1
@item trust @var{module-name}|@var{proc-spec}
@kindex trust (mdb command)
Index: library/gc.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/gc.m,v
retrieving revision 1.17
diff -u -b -r1.17 gc.m
--- library/gc.m 1 Apr 2005 08:25:36 -0000 1.17
+++ library/gc.m 10 May 2005 04:57:54 -0000
@@ -41,6 +41,8 @@
:- pragma no_inline(garbage_collect/0).
+:- pragma export(garbage_collect, "ML_garbage_collect").
+
:- pragma foreign_proc("C",
garbage_collect,
[may_call_mercury, terminates],
Index: trace/mercury_trace_declarative.c
===================================================================
RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_declarative.c,v
retrieving revision 1.88
diff -u -b -r1.88 mercury_trace_declarative.c
--- trace/mercury_trace_declarative.c 10 May 2005 04:28:22 -0000 1.88
+++ trace/mercury_trace_declarative.c 10 May 2005 04:57:54 -0000
@@ -54,11 +54,14 @@
#include "mercury_deep_copy.h"
#include "mercury_stack_trace.h"
#include "mercury_string.h"
+#include "mercury_timing.h"
#include "mercury_trace_base.h"
#include "mdb.declarative_debugger.mh"
#include "mdb.declarative_execution.mh"
+#include "benchmarking.mh"
+#include "gc.mh"
#include "std_util.mh"
#include <errno.h>
@@ -100,15 +103,25 @@
#endif
/*
-** The message to display when attempting to retry of an untabled area.
+** If this macro is defined then some stats will be printed to stderr whenever
+** a new subtree or supertree is built.
*/
-#define MR_DECL_UNTABLED_IO_RETRY_MESSAGE \
- "The declarative debugger needs to perform a retry across\n" \
- "an area in which IO is not tabled. This is not always safe.\n" \
- "To avoid this warning restart mdb and issue a `table_io start'\n" \
- "command at an event before the suspect area.\n" \
- "Do you wish to proceed with the retry? "
+#ifdef MR_DD_PRINT_EDT_STATS
+
+static MR_Unsigned MR_edt_stats_total_constructed_nodes = 0;
+static MR_Unsigned MR_edt_stats_constructed_nodes_this_time = 0;
+static MR_Unsigned MR_edt_stats_total_reexecutions = 0;
+
+#define MR_decl_maybe_print_edt_stats() MR_decl_print_edt_stats()
+#define MR_decl_maybe_inc_constructed_nodes() MR_decl_inc_constructed_nodes()
+
+#else /* MR_DD_PRINT_EDT_STATS */
+
+#define MR_decl_maybe_print_edt_stats()
+#define MR_decl_maybe_inc_constructed_nodes()
+
+#endif
/*
** The declarative debugger back end is controlled by the
@@ -196,6 +209,28 @@
static MR_Unsigned MR_edt_max_depth;
/*
+** The time, in milliseconds since the start of the program, when collecting of
+** events for the current portion of the annotated trace being materialized
+** started.
+*/
+
+static MR_Unsigned MR_edt_start_time;
+
+/*
+** The first event executed during the current re-execution.
+*/
+static MR_Unsigned MR_edt_first_event;
+
+/*
+** The following global will point to an array which records the number of
+** events at different depths in implicit subtrees. These are then used
+** to determine to what depth an implicit subtree should be materialized to.
+*/
+
+static MR_Unsigned *MR_edt_implicit_subtree_counters;
+static MR_Unsigned MR_edt_implicit_subtree_num_counters;
+
+/*
** The declarative debugger ignores modules that were not compiled with
** the required information. However, this may result in incorrect
** assumptions being made about the code, so the debugger gives a warning
@@ -304,6 +339,7 @@
MR_Unsigned event,
MR_Unsigned seqno,
MR_bool create_supertree,
+ MR_Unsigned depth_limit,
MR_Trace_Cmd_Info *cmd,
MR_Event_Info *event_info,
MR_Event_Details *event_details);
@@ -330,6 +366,8 @@
MR_Event_Info *event_info);
static void MR_decl_checkpoint_loc(const char *str,
MR_Trace_Node node);
+static void MR_decl_print_edt_stats(void);
+static void MR_decl_inc_constructed_nodes(void);
static void MR_trace_edt_build_sanity_check(
MR_Event_Info *event_info,
const MR_Proc_Layout *entry);
@@ -339,10 +377,21 @@
static MR_Unsigned MR_trace_calculate_event_depth(
MR_Event_Info *event_info);
static void MR_trace_construct_node(MR_Event_Info *event_info);
+static void MR_trace_count_event_in_implicit_subtree(
+ MR_Event_Info *event_info, MR_Unsigned depth);
+static void MR_trace_maybe_update_implicit_tree_ideal_depth(
+ MR_Unsigned depth, MR_Trace_Node call);
+static void MR_trace_maybe_show_progress(MR_Unsigned event_number);
+static void MR_trace_init_implicit_subtree_counters(
+ MR_Unsigned size);
+static void MR_trace_reset_implicit_subtree_counters(void);
+static void MR_trace_free_implicit_subtree_counters(void);
+static MR_Unsigned MR_trace_calc_implicit_subtree_ideal_depth(void);
MR_bool MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
-MR_Integer MR_edt_depth_step_size = MR_TRACE_DECL_INITIAL_DEPTH;
+MR_Unsigned MR_edt_desired_nodes_in_subtree = MR_TRACE_DESIRED_SUBTREE_NODES;
+MR_Unsigned MR_edt_default_depth_limit = MR_TRACE_DECL_INITIAL_DEPTH;
MR_bool MR_trace_decl_in_dd_dd_mode = MR_FALSE;
@@ -378,12 +427,16 @@
MR_trace_edt_build_sanity_check(event_info, entry);
+ MR_trace_maybe_show_progress(event_info->MR_event_number);
+
if (! MR_trace_include_event(entry, event_info, &jumpaddr)) {
return jumpaddr;
}
event_depth = MR_trace_calculate_event_depth(event_info);
+ MR_trace_count_event_in_implicit_subtree(event_info, event_depth);
+
if (MR_TRACE_EVENT_TOO_DEEP(event_depth)) {
return NULL;
}
@@ -413,12 +466,16 @@
|| (MR_edt_building_supertree && event_depth == 0
&& MR_port_is_final(event_info->MR_trace_port)))
{
+ MR_trace_free_implicit_subtree_counters();
+ MR_decl_maybe_print_edt_stats();
+
/*
** Call the front end.
*/
event_details.MR_call_seqno = MR_trace_call_seqno;
event_details.MR_call_depth = MR_trace_call_depth;
event_details.MR_event_number = MR_trace_event_number;
+
return MR_decl_diagnosis(MR_edt_return_node, cmd,
event_info, &event_details, MR_TRUE);
}
@@ -427,6 +484,27 @@
}
static void
+MR_trace_count_event_in_implicit_subtree(MR_Event_Info *event_info,
+ MR_Unsigned depth)
+{
+ if (depth == MR_edt_max_depth
+ && (event_info->MR_trace_port == MR_PORT_CALL
+ || event_info->MR_trace_port == MR_PORT_REDO))
+ {
+ /*
+ ** Reset the accumulators, since we are entering the
+ ** top of an implicit subtree.
+ */
+ MR_trace_reset_implicit_subtree_counters();
+ }
+ if ((depth >= MR_edt_max_depth) && (depth - MR_edt_max_depth <
+ MR_edt_implicit_subtree_num_counters))
+ {
+ MR_edt_implicit_subtree_counters[depth - MR_edt_max_depth]++;
+ }
+}
+
+static void
MR_trace_edt_build_sanity_check(MR_Event_Info *event_info,
const MR_Proc_Layout *entry)
{
@@ -658,6 +736,7 @@
MR_fatal_error("MR_trace_construct_node: unknown port");
}
MR_decl_checkpoint_alloc(trace);
+ MR_decl_maybe_inc_constructed_nodes();
MR_debug_enabled = MR_TRUE;
MR_update_trace_func_enabled();
@@ -802,7 +881,15 @@
call = MR_trace_matching_call(prev);
MR_decl_checkpoint_match(call);
+
MR_TRACE_CALL_MERCURY(
+ /*
+ ** We need to add 1 to MR_edt_depth since this is an EXIT
+ ** event, so 1 should already have been subtracted from
+ ** MR_edt_depth in MR_trace_calculate_event_depth.
+ */
+ MR_trace_maybe_update_implicit_tree_ideal_depth(
+ MR_edt_depth + 1, call);
last_interface = MR_DD_call_node_get_last_interface(
(MR_Word) call);
node = (MR_Trace_Node) MR_DD_construct_exit_node(
@@ -882,6 +969,13 @@
MR_decl_checkpoint_match(call);
MR_TRACE_CALL_MERCURY(
+ /*
+ ** We need to add 1 to MR_edt_depth since this is a FAIL
+ ** event, so 1 should already have been subtracted from
+ ** MR_edt_depth in MR_trace_calculate_event_depth.
+ */
+ MR_trace_maybe_update_implicit_tree_ideal_depth(
+ MR_edt_depth + 1, call);
redo = MR_DD_call_node_get_last_interface((MR_Word) call);
node = (MR_Trace_Node) MR_DD_construct_fail_node(
(MR_Word) prev, (MR_Word) call,
@@ -905,6 +999,13 @@
MR_decl_checkpoint_match(call);
MR_TRACE_CALL_MERCURY(
+ /*
+ ** We need to add 1 to MR_edt_depth since this is an EXCP
+ ** event, so 1 should already have been subtracted from
+ ** MR_edt_depth in MR_trace_calculate_event_depth.
+ */
+ MR_trace_maybe_update_implicit_tree_ideal_depth(
+ MR_edt_depth + 1, call);
last_interface = MR_DD_call_node_get_last_interface(
(MR_Word) call);
MR_DD_construct_excp_node(
@@ -1470,7 +1571,6 @@
MR_Retry_Result result;
const MR_Proc_Layout *entry;
FILE *out;
- MR_Unsigned edt_depth_limit;
const char *message;
MR_Trace_Level trace_level;
static MR_bool first_time = MR_TRUE;
@@ -1554,12 +1654,11 @@
MR_trace_decl_mode = trace_mode;
MR_trace_decl_ensure_init();
- edt_depth_limit = MR_edt_depth_step_size;
MR_trace_current_node = (MR_Trace_Node) NULL;
message = MR_trace_start_collecting(event_info->MR_event_number,
- event_info->MR_call_seqno, edt_depth_limit,
+ event_info->MR_call_seqno, MR_edt_default_depth_limit,
MR_FALSE, cmd, event_info, event_details, jumpaddr);
if (message == NULL) {
@@ -1578,10 +1677,10 @@
static MR_Code *
MR_trace_restart_decl_debug(
MR_Trace_Node call_preceding, MR_Unsigned event, MR_Unsigned seqno,
- MR_bool create_supertree, MR_Trace_Cmd_Info *cmd, MR_Event_Info
- *event_info, MR_Event_Details *event_details)
+ MR_bool create_supertree, MR_Unsigned depth_limit,
+ MR_Trace_Cmd_Info *cmd, MR_Event_Info *event_info,
+ MR_Event_Details *event_details)
{
- MR_Unsigned edt_depth_limit;
const char *message;
MR_Code *jumpaddr;
@@ -1593,9 +1692,7 @@
*/
MR_trace_current_node = call_preceding;
- edt_depth_limit = MR_edt_depth_step_size;
-
- message = MR_trace_start_collecting(event, seqno, edt_depth_limit,
+ message = MR_trace_start_collecting(event, seqno, depth_limit,
create_supertree, cmd, event_info, event_details,
&jumpaddr);
@@ -1688,6 +1785,16 @@
MR_edt_max_depth = maxdepth;
MR_edt_inside = MR_FALSE;
MR_edt_building_supertree = create_supertree;
+ MR_edt_start_time = MR_get_user_cpu_miliseconds();
+ MR_edt_first_event = event_details->MR_event_number;
+
+ /*
+ ** The deepest we will build any implicit subtree to will be
+ ** the number of desired nodes divided by two, since the minimum
+ ** events at each depth will be 2 (the CALL and EXIT).
+ */
+ MR_trace_init_implicit_subtree_counters(
+ MR_edt_desired_nodes_in_subtree / 2 + 1);
/*
** Restore globals from the saved copies.
@@ -1734,6 +1841,7 @@
MR_Integer use_old_io_map;
MR_Unsigned io_start;
MR_Unsigned io_end;
+ MR_Integer requested_subtree_depth;
if (MR_edt_compiler_flag_warning) {
fflush(MR_mdb_out);
@@ -1820,7 +1928,8 @@
require_subtree = MR_DD_diagnoser_require_subtree(response,
(MR_Integer *) &final_event,
(MR_Integer *) &topmost_seqno,
- (MR_Trace_Node *) &call_preceding);
+ (MR_Trace_Node *) &call_preceding,
+ (MR_Integer *) &requested_subtree_depth);
require_supertree = MR_DD_diagnoser_require_supertree(response,
(MR_Integer *) &final_event,
(MR_Integer *) &topmost_seqno);
@@ -1861,20 +1970,25 @@
/*
** Front end requires a subtree to be made explicit. Restart
** the declarative debugger with the appropriate depth limit.
+ ** We subtract 1 from the depth limit, since nodes will be
+ ** materialized one level below the depth limit for the
+ ** reason described in the comment above the
+ ** MR_TRACE_EVENT_TOO_DEEP macro above.
*/
return MR_trace_restart_decl_debug(call_preceding,
final_event, topmost_seqno, MR_FALSE,
- cmd, event_info, event_details);
+ requested_subtree_depth - 1, cmd, event_info,
+ event_details);
}
if (require_supertree) {
/*
- ** Front end requires a supertree to be made
- ** explicit.
+ ** Front end requires a supertree to be made explicit.
*/
return MR_trace_restart_decl_debug((MR_Trace_Node)NULL,
final_event, topmost_seqno, MR_TRUE,
- cmd, event_info, event_details);
+ MR_edt_default_depth_limit, cmd,
+ event_info, event_details);
}
/* We shouldn't ever get here. */
@@ -2060,6 +2174,167 @@
return next;
}
+static void
+MR_trace_reset_implicit_subtree_counters()
+{
+ int i = 0;
+
+ while ((i < MR_edt_implicit_subtree_num_counters)
+ && (MR_edt_implicit_subtree_counters[i] != 0))
+ {
+ MR_edt_implicit_subtree_counters[i] = 0;
+ i++;
+ }
+}
+
+static void
+MR_trace_init_implicit_subtree_counters(MR_Unsigned size)
+{
+ int i;
+
+ MR_edt_implicit_subtree_counters = (MR_Unsigned *) malloc(
+ size * sizeof(MR_Unsigned));
+
+ for (i = 0; i < size; i++) {
+ MR_edt_implicit_subtree_counters[i] = 0;
+ }
+
+ MR_edt_implicit_subtree_num_counters = size;
+}
+
+static void
+MR_trace_free_implicit_subtree_counters()
+{
+ free(MR_edt_implicit_subtree_counters);
+}
+
+static MR_Unsigned
+MR_trace_calc_implicit_subtree_ideal_depth()
+{
+ MR_Integer depth = 0;
+ MR_Unsigned total = 0;
+ MR_Unsigned events_at_depth;
+
+ while (depth < MR_edt_implicit_subtree_num_counters) {
+ events_at_depth = MR_edt_implicit_subtree_counters[depth];
+
+ total += events_at_depth;
+
+ if (total > MR_edt_desired_nodes_in_subtree) {
+ /*
+ ** Since we have gone over the desired number of nodes,
+ ** the ideal depth is depth - 1. We want the depth to
+ ** be at least 2 because if it is 1, the root of the
+ ** new tree will have its at-depth-limit flag set.
+ */
+ return (depth - 1) < 2 ? 2 : (depth - 1);
+ }
+
+ if (events_at_depth == 0) {
+ /*
+ ** This implicit subtree can be fully materialized.
+ ** We add 1 in the unlikely event that
+ ** MR_edt_implicit_subtree_num_counters is 1.
+ */
+ return MR_edt_implicit_subtree_num_counters + 1;
+ }
+
+ depth++;
+ }
+
+ /*
+ ** We didn't record the number of events at greater depths, so
+ ** be conservative and return the biggest depth we recorded up to.
+ */
+ return (depth - 1) < 2 ? 2 : (depth - 1);
+}
+
+/*
+** NOTE: This function should be called within a MR_TRACE_CALL_MERCURY
+** wrapper.
+*/
+static void
+MR_trace_maybe_update_implicit_tree_ideal_depth(MR_Unsigned current_depth,
+ MR_Trace_Node call)
+{
+ if (current_depth == MR_edt_max_depth) {
+ MR_Unsigned ideal_depth;
+ MR_Unsigned prev_ideal_depth;
+
+ ideal_depth = MR_trace_calc_implicit_subtree_ideal_depth();
+ /*
+ ** Use the lowest depth if the ideal depth was set on a
+ ** previous EXIT.
+ ** XXX In future the implicit subtree information should be
+ ** stored at final events, not CALL events, however this
+ ** goes hand in hand with a change to build pieces of the
+ ** annotated trace only between a REDO and its EXIT, if the
+ ** events between the CALL and the previous EXIT have already
+ ** been materialized (currently the events between the CALL
+ ** and EXIT will be materialized twice in this kind of
+ ** situation).
+ */
+ prev_ideal_depth = MR_DD_get_implicit_tree_ideal_depth(call);
+ if (prev_ideal_depth == 0 || prev_ideal_depth > ideal_depth)
+ {
+ MR_DD_call_node_update_implicit_tree_info(call,
+ ideal_depth);
+ }
+ }
+}
+
+static void
+MR_trace_maybe_show_progress(MR_Unsigned event_number)
+{
+ static MR_Unsigned last_tick = 0;
+ MR_Unsigned current_tick;
+
+ /*
+ ** We can't show progress when building a supertree since we don't
+ ** know what the final event will be.
+ ** XXX In future, when building a supertree we should not
+ ** reexecute the part of the program already materialized in the
+ ** annotated trace, but should instead get the output arguments
+ ** from the annotated trace and put them in the correct registers.
+ ** This would mean we could build small supertrees without reexecuting
+ ** all the events under the supertree everytime, so building of
+ ** supertrees should be quick and we wouldn't ever need to show
+ ** progress anyway.
+ */
+ if (!MR_edt_building_supertree && (
+ (event_number % MR_DECL_PROGRESS_CHECK_INTERVAL == 0)
+ || event_number == MR_edt_last_event))
+ {
+ if (last_tick == 0 &&
+ (MR_edt_start_time + MR_DECL_DISPLAY_PROGRESS_DELAY
+ < MR_get_user_cpu_miliseconds()))
+ {
+ fprintf(MR_mdb_out, MR_DECL_PROGRESS_MESSAGE);
+ fflush(MR_mdb_out);
+ /*
+ ** We count the initial progress message as the first
+ ** tick.
+ */
+ last_tick = 1;
+ } else if (last_tick > 0) {
+ current_tick = ((event_number - MR_edt_first_event)
+ * MR_DECL_PROGRESS_TOTAL)
+ / (MR_edt_last_event - MR_edt_first_event);
+ if (current_tick != last_tick) {
+ for (; last_tick < current_tick; last_tick++) {
+ fprintf(MR_mdb_out,
+ MR_DECL_PROGRESS_TICK_STRING);
+ fflush(MR_mdb_out);
+ }
+ if (current_tick == MR_DECL_PROGRESS_TOTAL) {
+ fprintf(MR_mdb_out, "\n");
+ last_tick = 0;
+ }
+ }
+ }
+ }
+}
+
#ifdef MR_DEBUG_DD_BACK_END
static void
@@ -2090,3 +2365,54 @@
}
#endif /* MR_DEBUG_DD_BACK_END */
+
+#ifdef MR_DD_PRINT_EDT_STATS
+
+static void
+MR_decl_print_edt_stats()
+{
+ MR_bool debug_enabled_before = MR_debug_enabled;
+
+ MR_edt_stats_total_constructed_nodes +=
+ MR_edt_stats_constructed_nodes_this_time;
+ MR_edt_stats_total_reexecutions++;
+
+ fflush(NULL);
+ /*
+ ** We use stderr instead of MR_mdb_err since ML_report_stats()
+ ** writes to stderr.
+ */
+ fprintf(stderr, "EDT construction stats: \n");
+ fprintf(stderr, "\tTotal reexecutions so far = %i\n",
+ MR_edt_stats_total_reexecutions);
+ fprintf(stderr, "\tNodes constructed in this run = %i\n",
+ MR_edt_stats_constructed_nodes_this_time);
+ fprintf(stderr, "\tMax depth for this run = %i\n",
+ MR_edt_max_depth);
+ fprintf(stderr, "\tTotal nodes constructed so far = %i\n",
+ MR_edt_stats_total_constructed_nodes);
+ fprintf(stderr, "Benchmarking stats follow:\n");
+
+ MR_debug_enabled = MR_FALSE;
+ MR_update_trace_func_enabled();
+
+ MR_TRACE_CALL_MERCURY(
+ ML_garbage_collect();
+ ML_report_stats();
+ );
+
+ MR_debug_enabled = debug_enabled_before;
+ MR_update_trace_func_enabled();
+
+ fflush(stderr);
+
+ MR_edt_stats_constructed_nodes_this_time = 0;
+}
+
+static void
+MR_decl_inc_constructed_nodes()
+{
+ MR_edt_stats_constructed_nodes_this_time++;
+}
+
+#endif /* MR_DD_PRINT_EDT_STATS */
Index: trace/mercury_trace_declarative.h
===================================================================
RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_declarative.h,v
retrieving revision 1.23
diff -u -b -r1.23 mercury_trace_declarative.h
--- trace/mercury_trace_declarative.h 2 Mar 2005 01:20:23 -0000 1.23
+++ trace/mercury_trace_declarative.h 10 May 2005 04:57:54 -0000
@@ -112,21 +112,74 @@
#define MR_TRACE_STATUS_UNDECIDED (MR_Word) 2
/*
-** The initial depth step size. The choice of 3 is quite arbitrary, but
-** it does mean the code which generates new portions of the annotated trace
-** is exercised more during testing.
+** The initial depth step size. We want to be quite conservative with this
+** value since initially we don't know what the branching factor of the tree
+** is.
*/
-#define MR_TRACE_DECL_INITIAL_DEPTH 3
+#define MR_TRACE_DECL_INITIAL_DEPTH 5
/*
-** We only build the annotated trace for events down to a certain depth.
-** MR_edt_depth_step_size gives the default depth limit (relative to the
-** starting depth). In future it would be nice to adjust this factor based on
-** profiling information.
+** The default desired number of nodes to add to the annotated trace when
+** materializing a new subtree.
*/
-extern MR_Integer MR_edt_depth_step_size;
+#define MR_TRACE_DESIRED_SUBTREE_NODES 10000
+
+/*
+** The message to display when attempting to retry over an untabled area.
+*/
+
+#define MR_DECL_UNTABLED_IO_RETRY_MESSAGE \
+ "The declarative debugger needs to perform a retry across\n" \
+ "an area in which IO is not tabled. This is not always safe.\n" \
+ "To avoid this warning restart mdb and issue a `table_io start'\n" \
+ "command at an event before the suspect area.\n" \
+ "Do you wish to proceed with the retry? "
+
+/*
+** How often to update the progress message, expressed in terms of number of
+** events.
+*/
+
+#define MR_DECL_PROGRESS_CHECK_INTERVAL 100000
+
+/*
+** The total number of progress ticks that should be displayed when building of
+** the current portion of the annotated trace is 100% complete.
+*/
+
+#define MR_DECL_PROGRESS_TOTAL 40
+
+/*
+** The progress message to display and the tick string to repeatedly display
+** after the initial progress message.
+*/
+
+#define MR_DECL_PROGRESS_MESSAGE "Generating execution trace.."
+#define MR_DECL_PROGRESS_TICK_STRING "."
+
+/*
+** How many milliseconds to wait before displaying progress.
+*/
+
+#define MR_DECL_DISPLAY_PROGRESS_DELAY 1000
+
+/*
+** When building a new explicit tree we build it to the largest depth such
+** that the number of nodes in the explicit tree is less than or equal to
+** MR_edt_desired_nodes_in_subtree.
+*/
+
+extern MR_Unsigned MR_edt_desired_nodes_in_subtree;
+
+/*
+** In the event that the ideal depth to build a tree to cannot be calculated,
+** because it is the initial build of the annotated trace or a supertree is
+** being built, use the value of the following global as the depth limit.
+*/
+
+extern MR_Unsigned MR_edt_default_depth_limit;
/*
** The following variable indicates whether the declarative debugger was
Index: trace/mercury_trace_internal.c
===================================================================
RCS file: /home/mercury1/repository/mercury/trace/mercury_trace_internal.c,v
retrieving revision 1.203
diff -u -b -r1.203 mercury_trace_internal.c
--- trace/mercury_trace_internal.c 5 May 2005 04:39:07 -0000 1.203
+++ trace/mercury_trace_internal.c 10 May 2005 04:57:54 -0000
@@ -596,7 +596,7 @@
MR_bool *split, MR_bool *close_window, char ***words,
int *word_count, const char *cat, const char *item);
static MR_bool MR_trace_options_dd(MR_bool *assume_all_io_is_tabled,
- MR_Integer *depth_step_size,
+ MR_Integer *default_depth, MR_Integer *num_nodes,
MR_Decl_Search_Mode *search_mode,
MR_bool *search_mode_was_set, MR_bool *new_session,
char ***words, int *word_count, const char *cat,
@@ -5659,13 +5659,14 @@
MR_bool new_session = MR_TRUE;
MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
- MR_edt_depth_step_size = MR_TRACE_DECL_INITIAL_DEPTH;
+ MR_edt_default_depth_limit = MR_TRACE_DECL_INITIAL_DEPTH;
search_mode = MR_trace_get_default_search_mode();
MR_trace_decl_in_dd_dd_mode = MR_FALSE;
if (! MR_trace_options_dd(&MR_trace_decl_assume_all_io_is_tabled,
- &MR_edt_depth_step_size, &search_mode, &search_mode_was_set,
- &new_session, &words, &word_count, "dd", "dd"))
+ &MR_edt_default_depth_limit, &MR_edt_desired_nodes_in_subtree,
+ &search_mode, &search_mode_was_set, &new_session,
+ &words, &word_count, "dd", "dd"))
{
; /* the usage message has already been printed */
} else if (word_count == 1) {
@@ -5704,13 +5705,14 @@
MR_bool new_session = MR_TRUE;
MR_trace_decl_assume_all_io_is_tabled = MR_FALSE;
- MR_edt_depth_step_size = MR_TRACE_DECL_INITIAL_DEPTH;
- search_mode = (MR_Word) -1;
+ MR_edt_default_depth_limit = MR_TRACE_DECL_INITIAL_DEPTH;
+ search_mode = MR_trace_get_default_search_mode();
MR_trace_decl_in_dd_dd_mode = MR_TRUE;
if (! MR_trace_options_dd(&MR_trace_decl_assume_all_io_is_tabled,
- &MR_edt_depth_step_size, &search_mode, &search_mode_was_set,
- &new_session, &words, &word_count, "dd", "dd_dd"))
+ &MR_edt_default_depth_limit, &MR_edt_desired_nodes_in_subtree,
+ &search_mode, &search_mode_was_set, &new_session,
+ &words, &word_count, "dd", "dd_dd"))
{
; /* the usage message has already been printed */
} else if (word_count <= 2) {
@@ -6962,7 +6964,8 @@
static struct MR_option MR_trace_dd_opts[] =
{
{ "assume-all-io-is-tabled", MR_no_argument, NULL, 'a' },
- { "depth-step-size", MR_required_argument, NULL, 'd' },
+ { "depth", MR_required_argument, NULL, 'd' },
+ { "nodes", MR_required_argument, NULL, 'n' },
{ "search-mode", MR_required_argument, NULL, 's' },
{ "resume", MR_required_argument, NULL, 'r' },
{ NULL, MR_no_argument, NULL, 0 }
@@ -6970,15 +6973,15 @@
static MR_bool
MR_trace_options_dd(MR_bool *assume_all_io_is_tabled,
- MR_Integer *depth_step_size, MR_Decl_Search_Mode *search_mode,
- MR_bool *search_mode_was_set, MR_bool *new_session,
- char ***words, int *word_count, const char *cat,
+ MR_Integer *default_depth, MR_Integer *num_nodes,
+ MR_Decl_Search_Mode *search_mode, MR_bool *search_mode_was_set,
+ MR_bool *new_session, char ***words, int *word_count, const char *cat,
const char *item)
{
int c;
MR_optind = 0;
- while ((c = MR_getopt_long(*word_count, *words, "ad:s:r",
+ while ((c = MR_getopt_long(*word_count, *words, "ad:n:s:r",
MR_trace_dd_opts, NULL)) != EOF)
{
switch (c) {
@@ -6988,7 +6991,14 @@
break;
case 'd':
- if (!MR_trace_is_natural_number(MR_optarg, depth_step_size)) {
+ if (! MR_trace_is_natural_number(MR_optarg, default_depth)) {
+ MR_trace_usage(cat, item);
+ return MR_FALSE;
+ }
+ break;
+
+ case 'n':
+ if (! MR_trace_is_natural_number(MR_optarg, num_nodes)) {
MR_trace_usage(cat, item);
return MR_FALSE;
}
@@ -8004,8 +8014,8 @@
{ "all", "interface", "entry", NULL };
static const char *const MR_trace_dd_cmd_args[] =
- { "-s", "-a", "-d", "--search-mode",
- "--assume-all-io-is-tabled", "--depth-step-size",
+ { "-s", "-a", "-d", "-n", "--search-mode",
+ "--assume-all-io-is-tabled", "--depth", "--nodes",
"top_down", "divide_and_query", NULL };
/*
--------------------------------------------------------------------------
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