[m-dev.] for review: cleanup of tabling

[Zoltan Somogyi]

> > runtime/mercury_tabling_macros.h:
> >     This new file contains macros that used to be part of the file
> >     mercury_tabling.h. The macros call the functions defined in
> >     mercury_tabling.c, but they also optionally print debugging messages.
>
> What's the rationale for moving these macros into a different header file?

Reducing clutter.

> > -typedef enum {
> > -   MR_SIMPLETABLE_UNINITIALIZED,
> > -   MR_SIMPLETABLE_WORKING,
> > -   MR_SIMPLETABLE_FAILED,
> > -   MR_SIMPLETABLE_SUCCEEDED
> > -} MR_SimpletableStatus;
> > +#define    MR_SIMPLETABLE_UNINITIALIZED    0
> > +#define    MR_SIMPLETABLE_WORKING          1
> > +#define    MR_SIMPLETABLE_FAILED           2
> > +#define    MR_SIMPLETABLE_SUCCEEDED        3
>
> What's the rationale for that change?

That fact that enums wouldn't work, since you cannot guarantee how much memory
the compiler allocates for them. In several places, the tabling code stores
e.g. into the MR_fix_table member and reads from the MR_simpletable_status
member. If e.g. the MR_simpletable_status member were only allocated a byte
of memory, and this was at the most significant end of the MR_fix_table member,
the code would be very confused.

This change does not lose any type safety. No member of the previous data
structure was of this enum type; the code always cast Words to it, just
before being used (i.e. there was no type safety in the first place).

> That comment seems to assume that floating point arguments will be boxed,
> which is not true for the MLDS back-end.  The comment should be clarified
> so that it is clear whether it is making that assumption and so that
> it is clear whether it applies only to the LLDS back-end or to all
> back-ends.

I presumed that tabling was not even supposed to work for the MLDS. Was I
wrong?

Memoization and loop check could possibly be made to work for MLDS, after
a lot of work has been put into eliminating the assumptions currently built in
(e.g. all arguments are Word sized) that are not true for the MLDS. However,
minimal model tabling for MLDS is at least a major research project, if it
is possible at all without giving up things such as compiler independence,
since it involves saving and restoring stacks.

For the time being I will try not to introduce new things that will prevent
the application of loopcheck and memo to MLDS, but I will not go out of my way
to fix existing things that do not work for MLDS.

A relative diff addressing your comments follow; its bootcheck is in progress. 

When can I expect a review of the rest of the change?

Zoltan.

diff -ur ws17/library/private_builtin.m ws23/library/private_builtin.m
--- ws17/library/private_builtin.m	Tue Dec 28 15:51:38 1999
+++ ws23/library/private_builtin.m	Thu Dec 30 20:29:37 1999
@@ -915,8 +915,7 @@
 
 		subgoal->status = MR_SUBGOAL_INACTIVE;
 		subgoal->leader = NULL;
-		subgoal->followers = MR_table_allocate(struct
-						MR_SubgoalListNode);
+		subgoal->followers = MR_table_allocate(MR_SubgoalListNode);
 		subgoal->followers->item = subgoal;
 		subgoal->followers->next = NULL;
 		subgoal->followers_tail = &(subgoal->followers->next);
diff -ur ws17/runtime/mercury_conf.h.date ws23/runtime/mercury_conf.h.date
--- ws17/runtime/mercury_conf.h.date	Sun Dec 26 22:19:56 1999
+++ ws23/runtime/mercury_conf.h.date	Thu Dec 30 19:33:10 1999
@@ -0,0 +1 @@
+datestamp
diff -ur ws17/runtime/mercury_tabling.c ws23/runtime/mercury_tabling.c
--- ws17/runtime/mercury_tabling.c	Tue Dec 28 15:49:10 1999
+++ ws23/runtime/mercury_tabling.c	Thu Dec 30 19:39:30 1999
@@ -33,7 +33,7 @@
 ** MAX_EL_SIZE_RATIO, we increase the table size to the next prime.
 */
 
-struct MR_Struct_HashTable {
+struct MR_HashTable_Struct {
 	Integer			size;
 	Integer			threshold;
 	Integer			used_slots;
@@ -1237,7 +1237,7 @@
 #endif
 
 	assert(*(subgoal->consumer_list_tail) == NULL);
-	listnode = table_allocate_bytes(sizeof(struct MR_ConsumerListNode));
+	listnode = table_allocate_bytes(sizeof(MR_ConsumerListNode));
 	*(subgoal->consumer_list_tail) = listnode;
 	subgoal->consumer_list_tail = &(listnode->next);
 	listnode->item = consumer;
diff -ur ws17/runtime/mercury_tabling.h ws23/runtime/mercury_tabling.h
--- ws17/runtime/mercury_tabling.h	Tue Dec 28 16:33:25 1999
+++ ws23/runtime/mercury_tabling.h	Thu Dec 30 20:26:00 1999
@@ -25,51 +25,97 @@
 
 /*---------------------------------------------------------------------------*/
 
-typedef	union MR_Union_TableNode	MR_TableNode;
-typedef	struct MR_Struct_HashTable	MR_HashTable;
-typedef	struct MR_Struct_StartTable	MR_StartTable;
-typedef	struct MR_SubgoalStruct		MR_Subgoal;
-typedef	struct MR_SubgoalListNode	*MR_SubgoalList;
-typedef	struct MR_AnswerListNodeStruct	MR_AnswerListNode;
-typedef	struct MR_AnswerListNodeStruct	*MR_AnswerList;
-typedef	struct MR_ConsumerListNode	*MR_ConsumerList;
+/*
+** Forward declarations of type names.
+*/
 
-typedef MR_TableNode			*MR_TrieNode;
+typedef	union MR_TableNode_Union		MR_TableNode;
+typedef	struct MR_HashTable_Struct		MR_HashTable;
+typedef	struct MR_Subgoal_Struct		MR_Subgoal;
+typedef	struct MR_SubgoalListNode_Struct	MR_SubgoalListNode;
+typedef	struct MR_AnswerListNode_Struct		MR_AnswerListNode;
+typedef	struct MR_ConsumerListNode_Struct	MR_ConsumerListNode;
+
+typedef MR_TableNode				*MR_TrieNode;
+typedef	MR_SubgoalListNode			*MR_SubgoalList;
+typedef	MR_AnswerListNode			*MR_AnswerList;
+typedef	MR_ConsumerListNode			*MR_ConsumerList;
 
 /*---------------------------------------------------------------------------*/
 
-union MR_Union_TableNode {
+/*
+** Tabling builds up two kinds of tables, both conceptually tries. For call
+** tables, there is one layer in the trie for each input argument; for answer
+** tables, there is one layer in the trie for each output argument. However,
+** the way each trie node is implemented depends on the type of the relevant
+** argument. In addition, what is stored at the tips of the call and answer
+** tables also depends on what kind of tabling (e.g. loopcheck, memo, minimal
+** model) is being performed on the current predicate, and (in some cases)
+** on what stage the execution of the current predicate has reached.
+**
+** We declare trie nodes to have type MR_TrieNode, which is a pointer to
+** MR_TableNode. MR_TableNode is a union of all the types that we may need
+** to be able to store in trie nodes: various kinds of trie implementations,
+** status indications, and answer blocks. Since in several places we write
+** to the union through one member and read from it through another, it is
+** important that all members be the same size; this is why the simple table
+** status field is an (unsigned) integer, not an enum.
+**
+** The integer field is by generic code that does not know what kind of node
+** the node will be; this means initialization. A value of zero means the node
+** is uninitialized; this must be true for all members. (Also, see below on
+** duplicate detection.)
+**
+** The hash table field is used when the "trie" node is implemented with a
+** hash table, whether of ints, floats, strings or another type that can be
+** coerced to one of these types.
+**
+** The fix table field implements a true trie node of fixed size, simply
+** indexed by an integer.
+**
+** The start table field implements a dynamically expandable trie node,
+** simply indexed by the difference between an integer value and a start value.
+**
+** The MR_simpletable_status member of the union gives the status of a
+** model_det or model_semi subgoal; it should be interpreted using the
+** macros below. Note that this word, which is at the end of the chain of
+** trie nodes given by the input arguments of the tabled subgoal, will be
+** overwritten by a pointer to the answer block containing the output
+** arguments when the goal succeeds; the MR_SIMPLETABLE_SUCCEEDED status code
+** is used only when the goal has no outputs, and this no answer block.
+** This is why MR_SIMPLETABLE_SUCCEEDED must have the highest value, and
+** why code looking at MR_simpletable_status must test for success with
+** "table->MR_simpletable_status >= MR_SIMPLETABLE_SUCCEEDED".
+**
+** The subgoal field contains the status of a model_non subgoal.
+**
+** The answer block field contains a pointer to an array of words, with
+** one word per output argument.
+**
+** The hash table, fix table and start table members may appear at any interior
+** node in the trie. The simple table status and subgoal members only appear
+** at the tips of call tables. The answer block member appears only at the tips
+** of call tables, either directly (for model_det and model_semi procedures),
+** or indirectly inside answer lists (for model_non procedures). There are no
+** answer tables for model_det and model_semi procedures, since they can only
+** ever have at most one answer. You can of course have answer tables for
+** model_non procedures, at whose tips you find only a duplicate indication.
+** When the tip nodes of answer tables are created, they are initialized to
+** zero as usual. Duplicate checking checks that the tip node is zero and
+** then sets the tip to a nonzero value; this way if the answer is generated
+** again, duplicate checking will fail.
+*/
+
+union MR_TableNode_Union {
 	Integer		MR_integer;
-	Integer		MR_simpletable_status;
 	MR_HashTable	*MR_hash_table;
-	MR_TableNode	*MR_start_table;
 	MR_TableNode	*MR_fix_table;
-	Word		*MR_answerblock;
+	MR_TableNode	*MR_start_table;
+	Unsigned	MR_simpletable_status;
 	MR_Subgoal	*MR_subgoal;
+	Word		*MR_answerblock;
 };
 
-/*---------------------------------------------------------------------------*/
-
-struct MR_AnswerListNodeStruct {
-	Integer		answer_num;
-	MR_TableNode	answer_data; /* always uses the MR_answerblock field */
-	MR_AnswerList	next_answer;
-};
-
-/*
-** The state of a model_det or model_semi subgoal.
-**
-** Note that the word containing the MR_SimpletableStatus,
-** which is at the end of the chain of trie nodes given by
-** the input arguments of the tabled subgoal, will be overwritten
-** by a pointer to the answer block containing the output arguments
-** when the goal succeeds. The MR_SIMPLETABLE_SUCCEEDED status code
-** is used only when the goal has no outputs. This is why
-** MR_SIMPLETABLE_SUCCEEDED must the last entry in the enum,
-** and why code looking at an MR_SimpletableStatus must test
-** for success with "(Unsigned) x >= MR_SIMPLETABLE_SUCCEEDED".
-*/
-
 #define	MR_SIMPLETABLE_UNINITIALIZED	0
 #define	MR_SIMPLETABLE_WORKING		1
 #define	MR_SIMPLETABLE_FAILED		2
@@ -81,6 +127,12 @@
 	MR_SUBGOAL_COMPLETE
 } MR_SubgoalStatus;
 
+struct MR_AnswerListNode_Struct {
+	Integer		answer_num;
+	MR_TableNode	answer_data; /* always uses the MR_answerblock member */
+	MR_AnswerList	next_answer;
+};
+
 /*
 ** The saved state of a generator or a consumer. While consumers get
 ** suspended while they are waiting for generators to produce more solutions,
@@ -133,7 +185,7 @@
 	MR_AnswerList	*remaining_answer_list_ptr;
 } MR_Consumer;
 
-struct MR_ConsumerListNode {
+struct MR_ConsumerListNode_Struct {
 	MR_Consumer			*item;
 	MR_ConsumerList			next;
 };
@@ -153,13 +205,13 @@
 	bool			changed;
 } MR_ResumeInfo;
 
-struct MR_SubgoalListNode {
+struct MR_SubgoalListNode_Struct {
 	MR_Subgoal		*item;
 	MR_SubgoalList		next;
 };
 
 /* Used to save info about a single subgoal in the table */
-struct MR_SubgoalStruct {
+struct MR_Subgoal_Struct {
 	MR_SubgoalStatus	status;
 	MR_Subgoal		*leader;
 	MR_SubgoalList		followers;
@@ -258,25 +310,25 @@
 	MR_GC_NEW(type)
 
   #define MR_table_allocate_array(type, count)				\
-	MR_GC_NEW_ARRAY(type, count)
+	MR_GC_NEW_ARRAY(type, (count))
 
   #define MR_table_reallocate_array(ptr, type, count)			\
-	MR_GC_NEW_ARRAY(ptr, type, count)
+	MR_GC_RESIZE_ARRAY((ptr), type, (count))
 
   #define table_allocate_bytes(size)					\
-	MR_GC_malloc(size)
+	MR_GC_malloc((size))
 
   #define table_reallocate_bytes(pointer, size)				\
-	MR_GC_realloc(pointer, size)
+	MR_GC_realloc((pointer), (size))
 
   #define table_allocate_words(size)					\
-	MR_GC_malloc(sizeof(Word) * size)
+	MR_GC_malloc(sizeof(Word) * (size))
 
   #define table_reallocate_words(pointer, size)				\
-	MR_GC_realloc(pointer, sizeof(Word) * size)
+	MR_GC_realloc((pointer), sizeof(Word) * (size))
 
   #define table_free(pointer)						\
-	MR_GC_free(pointer)
+	MR_GC_free((pointer))
 
   #define MR_table_list_cons(h, t)					\
 	MR_list_cons((h), (t))
@@ -312,11 +364,11 @@
 
 #endif /* CONSERVATIVE_GC */
 
-#define table_copy_bytes(Dest, Source, Size)				\
-	MR_memcpy(Dest, Source, Size)
+#define table_copy_bytes(dest, source, size)				\
+	MR_memcpy((dest), (source), (size))
 
-#define table_copy_words(Dest, Source, Size)				\
-	MR_memcpy((char *) (Dest), (char *) (Source), sizeof(Word) * Size)
+#define table_copy_words(dest, source, size)				\
+	MR_memcpy((char *) (dest), (char *) (source), sizeof(Word) * (size))
 
 /*---------------------------------------------------------------------------*/
 
diff -ur ws17/runtime/mercury_tabling_macros.h ws23/runtime/mercury_tabling_macros.h
--- ws17/runtime/mercury_tabling_macros.h	Tue Dec 28 15:33:16 1999
+++ ws23/runtime/mercury_tabling_macros.h	Thu Dec 30 20:23:31 1999
@@ -15,31 +15,31 @@
 */
 
 #define MR_RAW_TABLE_ANY(table, type_info, value)			\
-	MR_table_type(table, type_info, value)
+	MR_table_type((table), (type_info), (value))
 
 #define MR_RAW_TABLE_TAG(table, tag)					\
-	MR_int_fix_index_lookup_or_add(table, 1 << TAGBITS, tag)
+	MR_int_fix_index_lookup_or_add((table), 1 << TAGBITS, (tag))
 
 #define MR_RAW_TABLE_ENUM(table, range, value)				\
-	MR_int_fix_index_lookup_or_add(table, range, value)
+	MR_int_fix_index_lookup_or_add((table), (range), (value))
 
 #define MR_RAW_TABLE_WORD(table, value)					\
-	MR_int_hash_lookup_or_add(table, value);
+	MR_int_hash_lookup_or_add((table), (value));
 
 #define MR_RAW_TABLE_INT(table, value)					\
-	MR_int_hash_lookup_or_add(table, value);
+	MR_int_hash_lookup_or_add((table), (value));
 
 #define MR_RAW_TABLE_CHAR(table, value)					\
-	MR_int_hash_lookup_or_add(table, value);
+	MR_int_hash_lookup_or_add((table), (value));
 
 #define MR_RAW_TABLE_FLOAT(table, value)				\
-	MR_float_hash_lookup_or_add(table, value);
+	MR_float_hash_lookup_or_add((table), (value));
 
 #define MR_RAW_TABLE_STRING(table, value)	 			\
-	MR_string_hash_lookup_or_add(table, value);
+	MR_string_hash_lookup_or_add((table), (value));
 
 #define MR_RAW_TABLE_TYPEINFO(table, type_info)				\
-	MR_type_info_lookup_or_add(table, type_info)
+	MR_type_info_lookup_or_add((table), (type_info))
 
 #ifdef	MR_TABLE_DEBUG
 
@@ -325,11 +325,11 @@
 #define MR_TABLE_CREATE_ANSWER_BLOCK(table, num_slots)	 		\
 	do {								\
 		(table)->MR_answerblock = MR_table_allocate_array(Word,	\
-						num_slots);		\
+						(num_slots));		\
 	} while(0)
 
 #define MR_TABLE_GET_ANSWER(table, offset)				\
-	((table)->MR_answerblock)[offset]
+	((table)->MR_answerblock)[(offset)]
 
 #endif
 
@@ -345,10 +345,12 @@
   #define MR_TABLE_SAVE_ANSWER(table, offset, value, type_info)		\
 	do {								\
 		save_transient_hp();					\
-		{ Word local_val = Value;				\
-		(table)->MR_answerblock[offset] =			\
-			deep_copy(&local_val, (Word *) &type_info,	\
-				NULL, NULL);				\
+		{							\
+			Word	local_val = (value);			\
+			Word	local_type_info = (type_info);		\
+			(table)->MR_answerblock[(offset)] =		\
+				deep_copy(&local_val, &tlocal_type_info,\
+					NULL, NULL);			\
 		}							\
 		restore_transient_hp();					\
 	} while(0)
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------