C and tagged pointers

[jdb at s1-c]

The S-1 project at the Lawrence Livermore National Laboratory is
building a supercomputer.  We are implementing several languages
on it, including C.  Unlike many other machines, pointers on the
S-1 contain a 5-bit tag field along with a (31-bit) offset.  Of the
32 possible values, 23 are reserved for user-defined uses, two
values (0 and 31) are considered invalid and will cause a trap if
the pointer is used or copied (it is possible to avoid this by
treating it as an integer), a value is used to designate a "nil"
pointer, and the remainder of the values are used for protection
purposes.  Pointers with a "nil" tag can be copied, but they cannot
be used in an indirect reference.

The difficulty that arises is the use by C of the literal value 0
for a "nil" pointer.  STDIO is the most obvious case, but there
are many others.  In our case we either cannot use zero or we must
avoid all instructions that treat pointers as pointers (rather than
as integers) because the tag 0 is illegal (deliberately so, in order
to trap indirect references through data).

Has anyone else encountered this type of problem?  If so, what
solutions did you try?  One thought which occurred to me was to
treat the constant 0 as an implicit "nil" so that the assignment

	p = (char *)0;

would construct a pointer with a "nil" tag and the comparison

	if (p == (char *)0) ...

would actually check for a "nil" tag in "p".  This isn't really
desirable, though, because it forbids me from creating and using
a "real" zero pointer unless I do something ugly such as:

	p = (char *)4;
	p -= 4;

I know that there are other tagged architectures out there;
I'd appreciate any comments or references that you could provide.
Please respond to me rather than posting to the list.

	John Bruner
	Lawrence Livermore National Laboratory
	P.O. Box 5503
	Livermore, CA  94550
	(415) 422-0758

	jdb at s1-c			[ARPA]
	...!decvax!decwrl!mordor!jdb	[UUCP -- sometimes flakey]