[m-rev.] for review: thread-local backjumping
Julien Fischer
juliensf at csse.unimelb.edu.au
Wed Mar 19 16:30:50 AEDT 2008
I have committed this one after discussion with Mark in-person
yesterday.
On Wed, 12 Mar 2008, Julien Fischer wrote:
>
> For review by Mark.
>
> Estimated hours taken: 7
> Branches: main
>
> Add support for thread-local backjumping in grades that support concurrency.
>
> library/backjump.m:
> Shift the C definition of backjump handlers and choice ids into the
> runtime. This is needed because MR_Context now refers to them and
> the runtime should not depend on the library.
>
> Delete the XXX comment regarding pred_is_external/3. (This has been
> fixed below.)
>
> runtime/mercury_backjump.h:
> runtime/mercury_backjump.c:
> New module that defines those parts of the backjumping support that
> the runtime requires access to.
>
> In high-level C .par grades make the global state required by
> backjumping thread-specific.
>
> Conform to the usual coding conventions in the runtime in the new
> versions of the data structures that were originally in backjump.m.
>
> Rename ML_Choice_Id to MR_BackJumpChoiceId, the latter is less
> ambiguous.
>
> runtime/mercury_context.h:
> runtime/mercury_context.c:
> In low-level C grades add two extra fields to the MR_Context
> structure
> to hold the global state required by backjumping.
>
> In high-level C .par grades initialise the the thread-specific data
> that
> is used to store the backjump global state at program startup.
>
> Reformat a function prototype.
>
> runtime/mercury_thread.h:
> Reformat a function prototype.
>
> runtime/Mmakefile:
> Include the new files.
>
> mdbcomp/program_representation.m:
> Update pred_is_external/3 to include backjump.builtin_choice_id/1
> and backjump.builtin_backjump/1.
>
> tests/hard_coded/Mmakefile:
> tests/hard_coded/tl_backjump_test.m:
> tests/hard_coded/tl_backjump_test.exp:
> Test thread-local backjumping.
>
> tests/hard_coded/tl_backjump_test.exp2:
> Expected output for the above test case for grades in which spawn/3
> does not work.
>
> Julien.
>
> Index: library/backjump.m
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/library/backjump.m,v
> retrieving revision 1.1
> diff -u -r1.1 backjump.m
> --- library/backjump.m 9 Mar 2008 09:39:24 -0000 1.1
> +++ library/backjump.m 12 Mar 2008 04:48:15 -0000
> @@ -112,53 +112,13 @@
> % mdbcomp/program_representation.m. The debugger needs to know what
> predicates
> % are defined externally, so that it knows not to expect events for those
> % predicates.
> -%
> -% XXX we haven't done this yet.
> -%
>
> :- external(builtin_choice_id/1).
> :- external(builtin_backjump/1).
>
> %-----------------------------------------------------------------------------%
>
> -:- pragma foreign_decl("C", "
> -
> -typedef MR_Integer ML_Choice_Id;
> -
> -typedef struct ML_BackJumpHandler_struct {
> - struct ML_BackJumpHandler_struct *prev;
> - ML_Choice_Id id;
> -
> -#ifdef MR_HIGHLEVEL_CODE
> -
> - jmp_buf handler;
> -
> -#else /* !MR_HIGHLEVEL_CODE */
> -
> - MR_Word *saved_sp;
> - MR_Word *saved_fr;
> -
> -#endif /* !MR_HIGHLEVEL_CODE */
> -
> -} ML_BackJumpHandler;
> -
> -
> -/*
> -** XXX Does not work properly in grades that support multiple threads.
> -*/
> -#define ML_GET_BACKJUMP_HANDLER() ML_backjump_handler
> -#define ML_SET_BACKJUMP_HANDLER(val) ML_backjump_handler = (val)
> -#define ML_GET_NEXT_CHOICE_ID() (ML_next_choice_id++)
> -
> -extern ML_BackJumpHandler *ML_backjump_handler;
> -extern ML_Choice_Id ML_next_choice_id;
> -
> -").
> -
> -:- pragma foreign_code("C", "
> - ML_BackJumpHandler *ML_backjump_handler;
> - ML_Choice_Id ML_next_choice_id = 0;
> -").
> +:- pragma foreign_decl("C", "#include \"mercury_backjump.h\"").
>
> %-----------------------------------------------------------------------------%
> %
> @@ -188,10 +148,10 @@
> #endif
>
> void MR_CALL
> -mercury__backjump__builtin_choice_id_1_p_0(ML_Choice_Id *id,
> MR_CONT_PARAMS);
> +mercury__backjump__builtin_choice_id_1_p_0(MR_BackJumpChoiceId *id,
> MR_CONT_PARAMS);
>
> void MR_CALL
> -mercury__backjump__builtin_backjump_1_p_0(ML_Choice_Id id);
> +mercury__backjump__builtin_backjump_1_p_0(MR_BackJumpChoiceId id);
>
> #endif /* MR_HIGHLEVEL_CODE */
> #endif /* ML_BACKJUMP_GUARD */
> @@ -213,18 +173,18 @@
> void MR_CALL
> mercury__backjump__builtin_choice_id_1_p_0(MR_Integer *id, MR_CONT_PARAMS)
> {
> - ML_BackJumpHandler this_handler;
> + MR_BackJumpHandler this_handler;
>
> - this_handler.prev = ML_GET_BACKJUMP_HANDLER();
> - this_handler.id = ML_GET_NEXT_CHOICE_ID();
> - ML_SET_BACKJUMP_HANDLER(&this_handler);
> + this_handler.MR_bjh_prev = MR_GET_BACKJUMP_HANDLER();
> + this_handler.MR_bjh_id = MR_GET_NEXT_CHOICE_ID();
> + MR_SET_BACKJUMP_HANDLER(&this_handler);
>
> - if (setjmp(this_handler.handler) == 0) {
> + if (setjmp(this_handler.MR_bjh_handler) == 0) {
> #ifdef MR_DEBUG_JMPBUFS
> fprintf(stderr, ""choice setjmp %p\\n"", this_handler.handler);
> #endif
>
> - *id = this_handler.id;
> + *id = this_handler.MR_bjh_id;
> MR_CONT_CALL();
> } else {
> #ifdef MR_DEBUG_JMPBUFS
> @@ -232,13 +192,15 @@
> #endif
> }
>
> - ML_SET_BACKJUMP_HANDLER(this_handler.prev);
> + MR_SET_BACKJUMP_HANDLER(this_handler.MR_bjh_prev);
> }
>
> void MR_CALL
> -mercury__backjump__builtin_backjump_1_p_0(ML_Choice_Id id)
> +mercury__backjump__builtin_backjump_1_p_0(MR_BackJumpChoiceId id)
> {
> - ML_BackJumpHandler *backjump_handler = ML_GET_BACKJUMP_HANDLER();
> + MR_BackJumpHandler *backjump_handler;
> + + backjump_handler = MR_GET_BACKJUMP_HANDLER();
>
> /*
> ** XXX when we commit and prune away nondet stack frames, we leave the
> @@ -260,10 +222,10 @@
> ** commits.)
> */
> while (backjump_handler != NULL) {
> - if (backjump_handler->id == id) {
> + if (backjump_handler->MR_bjh_id == id) {
> break;
> }
> - backjump_handler = backjump_handler->prev;
> + backjump_handler = backjump_handler->MR_bjh_prev;
> }
>
> if (backjump_handler == NULL) {
> @@ -272,9 +234,10 @@
> } else {
>
> #ifdef MR_DEBUG_JMPBUFS
> - fprintf(stderr, ""backjump longjmp %p\\n"",
> backjump_handler->handler);
> + fprintf(stderr, ""backjump longjmp %p\\n"",
> + backjump_handler->MR_bjh_handler);
> #endif
> - longjmp(backjump_handler->handler, 1);
> + longjmp(backjump_handler->MR_bjh_handler, 1);
> }
> }
>
> @@ -313,7 +276,7 @@
> #define ML_DUMMY_LINE 0
>
> #define ML_BACKJUMP_STRUCT \
> - (((ML_BackJumpHandler *) (MR_curfr + 1 - MR_NONDET_FIXED_SIZE)) - 1)
> + (((MR_BackJumpHandler *) (MR_curfr + 1 - MR_NONDET_FIXED_SIZE)) - 1)
>
> #ifdef ML_DEBUG_BACKJUMPS
> #define ML_BACKJUMP_CHECKPOINT(s, p) \
> @@ -321,7 +284,8 @@
> fflush(stdout); \
> fprintf(stderr, ""backjumps (%s): "" \
> ""loc %p, prev %p, id %d, sp %p, fr %p\\n"", \
> - s, p, p->prev, p->id, p->saved_sp, p->saved_fr); \
> + s, p, p->MR_bjh_prev, p->MR_bjh_id, p->MR_bjh_saved_sp, \
> + p->MR_bjh_saved_fr); \
> } while (0)
> #else
> #define ML_BACKJUMP_CHECKPOINT(s, p)
> @@ -355,43 +319,45 @@
>
> MR_define_entry(mercury__backjump__builtin_choice_id_1_0);
> {
> - MR_mkpragmaframe(""builtin_choice_id/1"", 0, ML_BackJumpHandler_struct,
> + MR_mkpragmaframe(""builtin_choice_id/1"", 0, MR_BackJumpHandler_Struct,
> MR_LABEL(mercury__backjump__builtin_choice_id_1_0_i1));
>
> - ML_BACKJUMP_STRUCT->prev = ML_GET_BACKJUMP_HANDLER();
> - ML_BACKJUMP_STRUCT->id = ML_GET_NEXT_CHOICE_ID();
> - ML_BACKJUMP_STRUCT->saved_sp = MR_sp;
> - ML_BACKJUMP_STRUCT->saved_fr = MR_curfr;
> - ML_SET_BACKJUMP_HANDLER(ML_BACKJUMP_STRUCT);
> + ML_BACKJUMP_STRUCT->MR_bjh_prev = MR_GET_BACKJUMP_HANDLER();
> + ML_BACKJUMP_STRUCT->MR_bjh_id = MR_GET_NEXT_CHOICE_ID();
> + ML_BACKJUMP_STRUCT->MR_bjh_saved_sp = MR_sp;
> + ML_BACKJUMP_STRUCT->MR_bjh_saved_fr = MR_curfr;
> + MR_SET_BACKJUMP_HANDLER(ML_BACKJUMP_STRUCT);
>
> ML_BACKJUMP_CHECKPOINT(""create"", ML_BACKJUMP_STRUCT);
>
> - MR_r1 = (MR_Word) ML_BACKJUMP_STRUCT->id;
> + MR_r1 = (MR_Word) ML_BACKJUMP_STRUCT->MR_bjh_id;
> MR_succeed();
> }
> MR_define_label(mercury__backjump__builtin_choice_id_1_0_i1);
> {
> /* Restore the previous handler. */
> - ML_SET_BACKJUMP_HANDLER(ML_BACKJUMP_STRUCT->prev);
> + MR_SET_BACKJUMP_HANDLER(ML_BACKJUMP_STRUCT->MR_bjh_prev);
> MR_fail();
> }
>
> MR_define_entry(mercury__backjump__builtin_backjump_1_0);
> {
> - ML_Choice_Id id = MR_r1;
> - ML_BackJumpHandler *backjump_handler = ML_GET_BACKJUMP_HANDLER();
> + MR_BackJumpChoiceId id = MR_r1;
> + MR_BackJumpHandler *backjump_handler;
> + + backjump_handler = MR_GET_BACKJUMP_HANDLER();
>
> /*
> ** XXX see comments in the high-level implementation.
> */
> while (backjump_handler != NULL) {
> - if (backjump_handler->id == id) {
> + if (backjump_handler->MR_bjh_id == id) {
> break;
> }
>
> ML_BACKJUMP_CHECKPOINT(""scan"", backjump_handler);
>
> - backjump_handler = backjump_handler->prev;
> + backjump_handler = backjump_handler->MR_bjh_prev;
> }
>
> if (backjump_handler == NULL) {
> @@ -406,9 +372,9 @@
> ** (possibly incorrect) backjump.
> */
>
> - ML_SET_BACKJUMP_HANDLER(backjump_handler->prev);
> - MR_sp_word = (MR_Word) backjump_handler->saved_sp;
> - MR_maxfr_word = (MR_Word) backjump_handler->saved_fr;
> + MR_SET_BACKJUMP_HANDLER(backjump_handler->MR_bjh_prev);
> + MR_sp_word = (MR_Word) backjump_handler->MR_bjh_saved_sp;
> + MR_maxfr_word = (MR_Word) backjump_handler->MR_bjh_saved_fr;
> MR_fail();
> }
> }
> Index: mdbcomp/program_representation.m
> ===================================================================
> RCS file:
> /home/mercury/mercury1/repository/mercury/mdbcomp/program_representation.m,v
> retrieving revision 1.29
> diff -u -r1.29 program_representation.m
> --- mdbcomp/program_representation.m 27 Feb 2008 07:23:56 -0000 1.29
> +++ mdbcomp/program_representation.m 12 Mar 2008 04:48:16 -0000
> @@ -1319,6 +1319,8 @@
> pred_is_external("builtin", "unify", 3).
> pred_is_external("builtin", "compare", 4).
> pred_is_external("builtin", "compare_representation", 4).
> +pred_is_external("backjump", "builtin_choice_id", 1).
> +pred_is_external("backjump", "builtin_backjump", 1).
>
> %-----------------------------------------------------------------------------%
>
> Index: runtime/Mmakefile
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/mercury/runtime/Mmakefile,v
> retrieving revision 1.144
> diff -u -r1.144 Mmakefile
> --- runtime/Mmakefile 11 Oct 2007 11:45:21 -0000 1.144
> +++ runtime/Mmakefile 12 Mar 2008 04:48:16 -0000
> @@ -26,6 +26,7 @@
> mercury_agc_debug.h \
> mercury_array_macros.h \
> mercury_atomic_ops.h \
> + mercury_backjump.h \
> mercury_bootstrap.h \
> mercury_builtin_types.h \
> mercury_builtin_types_proc_layouts.h \
> @@ -150,6 +151,7 @@
> mercury_accurate_gc.c \
> mercury_agc_debug.c \
> mercury_atomic_ops.c \
> + mercury_backjump.c \
> mercury_bootstrap.c \
> mercury_builtin_types.c \
> mercury_bitmap.c \
> Index: runtime/mercury_backjump.c
> ===================================================================
> RCS file: runtime/mercury_backjump.c
> diff -N runtime/mercury_backjump.c
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ runtime/mercury_backjump.c 12 Mar 2008 04:48:16 -0000
> @@ -0,0 +1,53 @@
> +/*
> +** vim: ts=4 sw=4 expandtab
> +*/
> +/*
> +** Copyright (C) 2008 The University of Melbourne.
> +** This file may only be copied under the terms of the GNU Library General
> +** Public License - see the file COPYING.LIB in the Mercury distribution.
> +*/
> +
> +#include "mercury_backjump.h"
> +#include "mercury_thread.h"
> +
> +#if defined(MR_THREAD_SAFE)
> + #include <pthread.h>
> +#endif
> +
> +/*
> +** The low-level C counterparts to these globals are the `backjump_handler'
> +** and `backjump_next_choice_id' fields of the MR_Context structure.
> +** (See mercury_context.h for details.)
> +*/
> +
> +#if defined(MR_HIGHLEVEL_CODE) + #if defined(MR_THREAD_SAFE)
> + + MercuryThreadKey MR_backjump_handler_key;
> + MercuryThreadKey MR_backjump_next_choice_id_key;
> +
> + #else /* not MR_THREAD_SAFE */
> + + MR_BackJumpHandler *MR_backjump_handler;
> + MR_BackJumpChoiceId MR_backjump_next_choice_id = 0;
> +
> + #endif /* not MR_THREAD_SAFE */
> +#endif /* not MR_HIGHLEVEL_CODE */
> +
> +#if defined(MR_HIGHLEVEL_CODE) && defined(MR_THREAD_SAFE)
> +
> +MR_BackJumpChoiceId
> +MR_get_tl_backjump_next_choice_id(void)
> +{
> + MR_BackJumpChoiceId new_choice_id;
> +
> + /* NOTE: this only works because sizeof(MR_Integer) == sizeof(void *).
> */
> + new_choice_id = (MR_Integer)
> MR_GETSPECIFIC(MR_backjump_next_choice_id_key);
> + pthread_setspecific(MR_backjump_next_choice_id_key,
> + (void *)(new_choice_id + 1));
> + return new_choice_id;
> +}
> +
> +#endif /* MR_HIGLEVEL_CODE && MR_THREAD_SAFE */
> +
> +/*---------------------------------------------------------------------------*/
> Index: runtime/mercury_backjump.h
> ===================================================================
> RCS file: runtime/mercury_backjump.h
> diff -N runtime/mercury_backjump.h
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ runtime/mercury_backjump.h 12 Mar 2008 04:48:16 -0000
> @@ -0,0 +1,109 @@
> +/*
> +** vim:ts=4 sw=4 expandtab
> +*/
> +/*
> +** Copyright (C) 2008 The University of Melbourne.
> +** This file may only be copied under the terms of the GNU Library General
> +** Public License - see the file COPYING.LIB in the Mercury distribution.
> +*/
> +
> +/*
> +** mercury_backjump.h - code for handling backjumping.
> +*/
> +
> +#ifndef MERCURY_BACKJUMP_H
> +#define MERCURY_BACKJUMP_H
> +
> +#include "mercury_conf.h"
> +#include "mercury_thread.h"
> +#include <setjmp.h>
> +
> +typedef MR_Integer MR_BackJumpChoiceId;
> +
> +typedef struct MR_BackJumpHandler_Struct {
> + struct MR_BackJumpHandler_Struct *MR_bjh_prev;
> + MR_BackJumpChoiceId MR_bjh_id;
> +
> +#ifdef MR_HIGHLEVEL_CODE
> +
> + jmp_buf MR_bjh_handler;
> +
> +#else /* !MR_HIGHLEVEL_CODE */
> +
> + MR_Word *MR_bjh_saved_sp;
> + MR_Word *MR_bjh_saved_fr;
> +
> +#endif /* !MR_HIGHLEVEL_CODE */
> +
> +} MR_BackJumpHandler;
> +
> +/*---------------------------------------------------------------------------*/
> +
> +/*
> +** This section defines the global state required to support backjumping.
> +** In low-level C grades this state is part of the MR_Context structure
> +** (see mercury_context.h). In non .par high-level C grades we store the
> +** state in global variables and in .par high-level C grades we need to use
> +** thread-local data.
> +*/
> +
> +#if defined(MR_HIGHLEVEL_CODE)
> +
> + #if defined(MR_THREAD_SAFE)
> +
> + extern MR_BackJumpChoiceId
> + MR_get_tl_backjump_next_choice_id(void);
> +
> + /*
> + ** MR_backjump_handler_key stores a key that can be used to get
> + ** the current backjump handler for the current thread.
> + ** MR_backjump_next_choice_id_key stores a key that can be used
> + ** to get the next available backjump choice id for the current
> thread.
> + ** NOTE: changes here may need to be reflected in the function
> + ** MR_init_thread_stuff() in mercury_context.c.
> + */
> + extern MercuryThreadKey MR_backjump_handler_key;
> + extern MercuryThreadKey MR_backjump_next_choice_id_key;
> +
> + #define MR_GET_BACKJUMP_HANDLER() \
> + MR_GETSPECIFIC(MR_backjump_handler_key)
> +
> + #define MR_SET_BACKJUMP_HANDLER(val) \
> + pthread_setspecific(MR_backjump_handler_key, (val))
> + + #define MR_GET_NEXT_CHOICE_ID() \
> + MR_get_tl_backjump_next_choice_id() +
> + #else /* not MR_THREAD_SAFE */
> + + /*
> + ** MR_backjump_handler points to the current backjump handler.
> + */ + extern MR_BackJumpHandler *MR_backjump_handler;
> + + /*
> + ** The value MR_backjump_next_choice_id is the next available +
> ** backjump choice id.
> + */
> + extern MR_BackJumpChoiceId MR_backjump_next_choice_id;
> +
> + #define MR_GET_BACKJUMP_HANDLER() MR_backjump_handler
> + #define MR_SET_BACKJUMP_HANDLER(val) MR_backjump_handler = (val)
> + #define MR_GET_NEXT_CHOICE_ID()
> (MR_backjump_next_choice_id++)
> +
> + #endif /* not MR_THREAD_SAFE */
> +
> +#else /* not MR_HIGHLEVEL_CODE */
> +
> + #define MR_GET_BACKJUMP_HANDLER() \
> + MR_ENGINE(MR_eng_this_context)->MR_ctxt_backjump_handler
> +
> + #define MR_SET_BACKJUMP_HANDLER(val) \
> + MR_ENGINE(MR_eng_this_context)->MR_ctxt_backjump_handler = (val)
> +
> + #define MR_GET_NEXT_CHOICE_ID() \
> + (MR_ENGINE(MR_eng_this_context)->MR_ctxt_backjump_next_choice_id++)
> +
> +#endif /* not MR_HIGHLEVEL_CODE */
> +
> +#endif /* not MERCURY_BACKJUMP_H */
> Index: runtime/mercury_context.c
> ===================================================================
> RCS file:
> /home/mercury/mercury1/repository/mercury/runtime/mercury_context.c,v
> retrieving revision 1.59
> diff -u -r1.59 mercury_context.c
> --- runtime/mercury_context.c 30 Oct 2007 00:46:22 -0000 1.59
> +++ runtime/mercury_context.c 12 Mar 2008 04:48:16 -0000
> @@ -33,8 +33,9 @@
> #include "mercury_engine.h" /* for `MR_memdebug' */
> #include "mercury_reg_workarounds.h" /* for `MR_fd*' stuff */
>
> -static void MR_init_context_maybe_generator(MR_Context *c,
> - const char *id, MR_GeneratorPtr gen);
> +static void
> +MR_init_context_maybe_generator(MR_Context *c, const char *id,
> + MR_GeneratorPtr gen);
>
> /*---------------------------------------------------------------------------*/
>
> @@ -104,6 +105,11 @@
> #endif
> MR_KEY_CREATE(&MR_exception_handler_key, NULL);
>
> + #ifdef MR_HIGHLEVEL_CODE
> + MR_KEY_CREATE(&MR_backjump_handler_key, NULL);
> + MR_KEY_CREATE(&MR_backjump_next_choice_id_key, (void *)0);
> + #endif +
> /* These are actually in mercury_thread.c. */
> pthread_mutex_init(&MR_thread_barrier_lock, MR_MUTEX_ATTR);
> #ifdef MR_HIGHLEVEL_CODE
> @@ -278,6 +284,11 @@
> c->MR_ctxt_ticket_high_water = 1;
> #endif
>
> +#ifndef MR_HIGHLEVEL_CODE
> + c->MR_ctxt_backjump_handler = NULL;
> + c->MR_ctxt_backjump_next_choice_id = 0;
> +#endif
> +
> #ifndef MR_CONSERVATIVE_GC
> if (gen != NULL) {
> MR_fatal_error("MR_init_context: generator and no conservative gc");
> Index: runtime/mercury_context.h
> ===================================================================
> RCS file:
> /home/mercury/mercury1/repository/mercury/runtime/mercury_context.h,v
> retrieving revision 1.44
> diff -u -r1.44 mercury_context.h
> --- runtime/mercury_context.h 11 Oct 2007 11:45:21 -0000 1.44
> +++ runtime/mercury_context.h 12 Mar 2008 04:48:16 -0000
> @@ -58,6 +58,7 @@
> #include "mercury_thread.h" /* for MercuryLock */
> #include "mercury_goto.h" /* for MR_GOTO() */
> #include "mercury_conf.h" /* for MR_CONSERVATIVE_GC */
> +#include "mercury_backjump.h" /* for MR_BackJumpHandler, etc */
>
> #ifdef MR_THREAD_SAFE
> #define MR_IF_THREAD_SAFE(x) x
> @@ -181,6 +182,11 @@
> ** ticket_highwater The saved MR_ticket_high_water for this context.
> ** (All accessed via abstract machine register.)
> **
> +** backjump_handler The backjump handler for this context.
> +** backjump_next_choice_id The next available backjump choice id counter
> +** for this context.
> +** (All accessed via MR_eng_context.)
> +**
> ** hp The saved hp for this context.
> ** (Accessed via abstract machine register.)
> **
> @@ -303,6 +309,11 @@
> MR_ChoicepointId MR_ctxt_ticket_high_water;
> #endif
>
> +#ifndef MR_HIGHLEVEL_CODE + MR_BackJumpHandler
> *MR_ctxt_backjump_handler;
> + MR_BackJumpChoiceId MR_ctxt_backjump_next_choice_id;
> +#endif
> +
> #ifndef MR_CONSERVATIVE_GC
> MR_Word *MR_ctxt_hp;
> MR_Word *MR_ctxt_min_hp_rec;
> Index: runtime/mercury_thread.h
> ===================================================================
> RCS file:
> /home/mercury/mercury1/repository/mercury/runtime/mercury_thread.h,v
> retrieving revision 1.24
> diff -u -r1.24 mercury_thread.h
> --- runtime/mercury_thread.h 3 May 2007 04:34:56 -0000 1.24
> +++ runtime/mercury_thread.h 12 Mar 2008 04:48:16 -0000
> @@ -244,7 +244,8 @@
> /*
> ** Allocate an index into the thread-local mutable array for a mutable.
> */
> -extern MR_Unsigned MR_new_thread_local_mutable_index(void);
> +extern MR_Unsigned
> +MR_new_thread_local_mutable_index(void);
>
> /*
> ** Allocate a thread-local mutable array.
> Index: tests/hard_coded/Mmakefile
> ===================================================================
> RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
> retrieving revision 1.342
> diff -u -r1.342 Mmakefile
> --- tests/hard_coded/Mmakefile 9 Mar 2008 09:39:25 -0000 1.342
> +++ tests/hard_coded/Mmakefile 12 Mar 2008 04:48:16 -0000
> @@ -473,6 +473,8 @@
> # defined.
> #
> # backjump_test fails because deep profiler cannot yet handle backjumps.
> +# tl_backjump_test fails because the deep profiler cannot yet handle
> +# backjumps and threads.
>
> ifeq "$(findstring profdeep,$(GRADE))" ""
> NON_PROFDEEP_PROGS = \
> @@ -491,6 +493,7 @@
> solver_default_eq_cmp \
> test_array2d \
> test_injection \
> + tl_backjump_test \
> user_defined_equality \
> version_array_test \
> write_binary
> @@ -670,7 +673,7 @@
> < $@.tmp > $@; \
> rm -f $@.tmp; \
> fi
> -
> +
> # final_excp.out is expected to fail (it calls throw/1).
> #
> final_excp.out: final_excp
> @@ -743,6 +746,20 @@
> done \
> ) > runtime_opt.out 2>&1
>
> +# The test checks the output from multiple threads and since that output
> +# may be interleaved arbitrarily we need to filter it so that all the output
> +# from each thread appears sequentially in a block.
> +tl_backjump_test.out: tl_backjump_test
> + if ./tl_backjump_test > $@.tmp 2>&1; then \
> + grep "^(TID: #2" $@.tmp > $@; \
> + grep "^(TID: #3" $@.tmp >> $@; \
> + grep "^spawn" $@.tmp >> $@; \
> + rm -f $@.tmp; \
> + else \
> + grep . $@.tmp; \
> + exit 1; \
> + fi +
> #-----------------------------------------------------------------------------#
>
> dir_test.out: prepare_for_dir_test
> Index: tests/hard_coded/tl_backjump_test.exp
> ===================================================================
> RCS file: tests/hard_coded/tl_backjump_test.exp
> diff -N tests/hard_coded/tl_backjump_test.exp
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ tests/hard_coded/tl_backjump_test.exp 12 Mar 2008 04:48:16 -0000
> @@ -0,0 +1,50 @@
> +(TID: #2) label A = 1, (0)
> +(TID: #2) label B = 1, (1)
> +(TID: #2) label C = 1, (2)
> +(TID: #2) label C = 2, (3)
> +(TID: #2) backjump (3)
> +(TID: #2) label C = 3, (4)
> +(TID: #2) solution 1, 1, 3
> +(TID: #2) label B = 2, (5)
> +(TID: #2) label C = 1, (6)
> +(TID: #2) backjump (0)
> +(TID: #2) label A = 2, (7)
> +(TID: #2) label B = 1, (8)
> +(TID: #2) label C = 1, (9)
> +(TID: #2) solution 2, 1, 1
> +(TID: #2) label C = 2, (10)
> +(TID: #2) backjump (8)
> +(TID: #2) label B = 2, (11)
> +(TID: #2) label C = 1, (12)
> +(TID: #2) label C = 2, (13)
> +(TID: #2) solution 2, 2, 2
> +(TID: #2) label C = 3, (14)
> +(TID: #2) Solutions:
> +(TID: #2) {1, 1, 3},
> +(TID: #2) {2, 1, 1},
> +(TID: #2) {2, 2, 2}
> +(TID: #3) label A = 1, (0)
> +(TID: #3) label B = 1, (1)
> +(TID: #3) label C = 1, (2)
> +(TID: #3) label C = 2, (3)
> +(TID: #3) backjump (3)
> +(TID: #3) label C = 3, (4)
> +(TID: #3) solution 1, 1, 3
> +(TID: #3) label B = 2, (5)
> +(TID: #3) label C = 1, (6)
> +(TID: #3) backjump (0)
> +(TID: #3) label A = 2, (7)
> +(TID: #3) label B = 1, (8)
> +(TID: #3) label C = 1, (9)
> +(TID: #3) solution 2, 1, 1
> +(TID: #3) label C = 2, (10)
> +(TID: #3) backjump (8)
> +(TID: #3) label B = 2, (11)
> +(TID: #3) label C = 1, (12)
> +(TID: #3) label C = 2, (13)
> +(TID: #3) solution 2, 2, 2
> +(TID: #3) label C = 3, (14)
> +(TID: #3) Solutions:
> +(TID: #3) {1, 1, 3},
> +(TID: #3) {2, 1, 1},
> +(TID: #3) {2, 2, 2}
> Index: tests/hard_coded/tl_backjump_test.exp2
> ===================================================================
> RCS file: tests/hard_coded/tl_backjump_test.exp2
> diff -N tests/hard_coded/tl_backjump_test.exp2
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ tests/hard_coded/tl_backjump_test.exp2 12 Mar 2008 04:48:16 -0000
> @@ -0,0 +1 @@
> +spawn/3 not supported in this grade
> Index: tests/hard_coded/tl_backjump_test.m
> ===================================================================
> RCS file: tests/hard_coded/tl_backjump_test.m
> diff -N tests/hard_coded/tl_backjump_test.m
> --- /dev/null 1 Jan 1970 00:00:00 -0000
> +++ tests/hard_coded/tl_backjump_test.m 12 Mar 2008 04:48:16 -0000
> @@ -0,0 +1,108 @@
> +%---------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sw=4 et
> +%---------------------------------------------------------------------------%
> +%
> +% Test for thread-local backjumping.
> +%
> +%---------------------------------------------------------------------------%
> +%---------------------------------------------------------------------------%
> +
> +:- module tl_backjump_test.
> +:- interface.
> +
> +:- import_module io.
> +
> +:- pred main(io::di, io::uo) is cc_multi.
> +
> +:- implementation.
> +
> +:- import_module backjump.
> +:- import_module list.
> +:- import_module solutions.
> +:- import_module string.
> +:- import_module thread.
> +
> +main(!IO) :-
> + ( can_spawn ->
> + thread.spawn(run_problem(2), !IO),
> + thread.spawn(run_problem(3), !IO)
> + ;
> + io.write_string("spawn/3 not supported in this grade", !IO)
> + ).
> + +:- type thread_id == int.
> +
> +:- pred run_problem(thread_id::in, io::di, io::uo) is cc_multi.
> +
> +run_problem(TId0, !IO) :-
> + cc_multi_equal(TId0, TId), % Make sure we are cc_multi.
> + solutions(problem(TId), Sols),
> + (
> + Sols = [],
> + io.format("(TID: #%d) No solutions!\n",
> + [i(TId)], !IO)
> + ;
> + Sols = [_ | _],
> + io.format("(TID: #%d) Solutions:\n", [i(TId)], !IO),
> + WriteSoln = (pred(Sol::in, !.IO::di, !:IO::uo) is det :- +
> io.format("(TID: #%d) ", [i(TId)], !IO),
> + io.write(Sol, !IO)
> + ),
> + io.write_list(Sols, ",\n", WriteSoln, !IO),
> + io.nl(!IO)
> + ).
> +
> +:- pred problem(thread_id::in, {int, int, int}::out) is nondet.
> +
> +problem(TId, {A, B, C}) :-
> + promise_pure (
> + impure label(TId, "A", [1, 2], A, PA),
> + impure label(TId, "B", [1, 2], B, PB),
> + impure label(TId, "C", [1, 2, 3], C, PC),
> + impure check(TId, A, B, C, PA, PB, PC)
> + ).
> +
> +:- impure pred label(thread_id::in, string::in, list(int)::in, int::out,
> + choice_id::out) is nondet.
> +
> +label(TId, Name, [N | _], N, P) :-
> + impure get_choice_id(P),
> + trace [io(!IO)] (
> + io.format("(TID: #%d) label %s = %d, (%d)\n",
> + [i(TId), s(Name), i(N), i(to_int(P))], !IO),
> + true
> + ).
> +label(TId, Name, [_ | Ns], N, P) :-
> + impure label(TId, Name, Ns, N, P).
> +
> +:- impure pred check(thread_id::in, int::in, int::in, int::in,
> choice_id::in,
> + choice_id::in, choice_id::in) is semidet.
> +
> +check(TId, A, B, C, PA, PB, PC) :-
> + ( is_nogood(A, B, C, PA, PB, PC, P) ->
> + trace [io(!IO)] (
> + io.format("(TID: #%d) backjump (%d)\n", [i(TId), i(to_int(P))],
> + !IO)
> + ),
> + impure backjump(P)
> + ;
> + is_solution(A, B, C),
> + trace [io(!IO)] (
> + io.format("(TID: #%d) solution %d, %d, %d\n",
> + [i(TId), i(A), i(B), i(C)], !IO)
> + )
> + ).
> +
> +:- pred is_nogood(int::in, int::in, int::in, choice_id::in, choice_id::in,
> + choice_id::in, choice_id::out) is semidet.
> +
> +is_nogood(1, 1, 2, _, _, P, P).
> +is_nogood(1, 2, 1, P, _, _, P).
> +is_nogood(2, 1, 2, _, P, _, P).
> +
> +:- pred is_solution(int::in, int::in, int::in) is semidet.
> +
> +is_solution(1, 1, 3).
> +is_solution(2, 1, 1).
> +is_solution(2, 2, 2).
> +
>
> --------------------------------------------------------------------------
> mercury-reviews mailing list
> Post messages to: mercury-reviews at csse.unimelb.edu.au
> Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
> Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
> --------------------------------------------------------------------------
>
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list