radford@calgary.UUCP (Radford Neal) (02/12/85)
Any comments on the following idea?
Take a machine with bytes, words, longs, etc. - all of sizes which are
a power of two of some basic unit - and which requires such data to be
aligned, with the address of a unit of size 2**N being required to have
N low-order zero bits.
Such a machine presumably has instructions for handling the different
data units - e.g. MOVEB, MOVEW, MOVEL, etc. Let's say there are no
registers, so a MOVE instruction always requires two memory addresses
to be specified in some fashion.
Here's the idea: Get rid of the MOVEB, MOVEW, MOVEL, etc. instructions
and replace them with a single MOVE instruction, with the type of
unit to be moved determined by the memory address given. Addresses
have a new format, as for instance:
0 0 1 A8 A7 A6 A5 A4 A3 A2
This example specifies a long operand (four bytes) with address
A8 A7 A6 A5 A4 A3 A2 0 0
In general, the size of an operand is 2**N, where N is the number of
leading zeros in its address. The "actual" address is the bits after
the highest-order one bit, padded with zeros to make it come out the
the right size. In this scheme, the address
0 0 0 0 0 0 0 0 0 1
addresses all of memory as a single block (assuming the scheme has been
carried to this extreme).
Notice that this format requires only a single extra bit in addresses
to encode the size of the object pointed to. This is possible because
traditional addresses on aligned machines waste information space, as
evidenced by the existence of illegal addresses (e.g. odd word addresses).
Notice also that this scheme is different from a "tagged" architecture
in that the size is a property of the POINTER, not of the data. If you
want to start looking at your integer as a series of bytes, you need only
shift your pointer left a bit, you don't have to change what's stored in
memory.
In addition to getting rid of all the various forms of MOVE instruction,
this scheme also gets rid of all the conversion instructions - moving
from a byte address to a long address automatically zero-extends. At most
you need two instructions, MOVEU and MOVES, to allow you a choice of
zero-extend or sign-extend.
Also, there is no need for "stride adjustment" with statements such as
int *p;
p += 1;
Adding one to an address always gets you the next element, regardless
of the size of the data type pointed to.
Finally, this scheme allows one to write more general subroutines than
one can without it, e.g. something like:
long max(a,n)
anyinttype a[];
int n;
{ long r; int i;
r = a[0];
for (i = 1; i<n; i++) if (a[i]>r) r = a[i];
return;
}
should compile to efficient code which will find the maximum of an array
of bytes, words, or longs.
I can see a few problems here myself. A minor one is figuring out what
to do with registers - a simple register number won't contain the
size information. The register numbers could be changed in the same
fashion as the memory addresses to encode the size, or the registers could
be treated specially, always using all their bits for instance.
Another problem is that the shifting required to get the "real" address
might slow down the processor too much. Any ideas on how much?
Finally, any programs which actually used the flexibility illustrated
by the "max" function above would become hopelessly un-portable to a
standard architecture.
Radford Neal
The University of Calgarydmmartindale@watcgl.UUCP (Dave Martindale) (02/13/85)
I think the idea of having addresses encode the data type is ultimately unworkable, for the following reasons: 1) How do you handle different data types of the same size? For example, the VAX "long" and "float" data types are the same size, but have different move instructions. Why? The floating point one may fault on certain bit patterns (undefined operand) while the integer one had better not. 2) The addressing scheme assumes that every object is a power of 2 bytes in size. What do you do about structures? If their size is rounded up to the next power of 2, you may waste almost half of your memory. If their size is not rounded, then you need to come up with some way to represent a pointer to an odd-sized object that is not aligned on a power-of-two boundary; your addressing scheme does not handle this. 3) All objects must be aligned on a "natural" boundary. While I am willing to tolerate the wasted memory or address space that results from aligning a 4-byte object on a 4-byte boundary, and even the occasional movement of something up to a 512-byte or 2048-byte boundary because of hardware page sizes, I don't think anyone will tolerate the requirement that a 4Mb table be aligned on a 4Mb boundary. (If you think this is a ridiculous example, and that the scheme would never be used for large blocks, I agree, but the original article showed how the addressing scheme provided a natural method for referencing all of memory.)
dmr@grigg.UUCP (02/15/85)
Radford Neal's suggestion, in which memory addresses encode the size of the addressed object, is a good one, but it isn't new. So far as I know, David Wheeler, of Cambridge University, was the first to suggest it several years ago. I don't know if it was ever published. We learned of it when he was visiting Bell Labs, and have since called it "the Wheeler device." Most of Martindale's objections to the idea aren't important. Different data types of the same size: so long as you accept that floating add is an operation different from fixed add, and (if you like) that the same is true for move, the fact that different data types may be the same size doesn't matter. The plan doesn't contemplate extending the idea to big data objects, just the usual byte-to-quadword range. It does indeed require that objects be aligned on a boundary divisible by their size. There has been debate about this, but I don't think it is an onerous requirement. Neal worries about registers. I don't think he should. It all works out if you just make register references use their full width; that is, the Wheeler device is a gadget that fiddles with data going between the CPU and memory, and has nothing to do with registers. It deserves to be tried. The potential advantage is that you can use the redundancy provided by requiring alignment of operands to reduce the number of bits needed for the opcode and/or address specification, while still providing orthogonality of references. The disadvantage is more complicated decoding and the need to be careful when moving pointers around. Dennis Ritchie
radford@calgary.UUCP (Radford Neal) (02/16/85)
> I think the idea of having addresses encode the data type is ultimately > unworkable, for the following reasons: > > 1) How do you handle different data types of the same size? For example, > the VAX "long" and "float" data types are the same size, but have > different move instructions... > > 2) The addressing scheme assumes that every object is a power of 2 bytes > in size. What do you do about structures? If their size is rounded > up to the next power of 2, you may waste almost half of your memory. > If their size is not rounded, then you need to come up with some way > to represent a pointer to an odd-sized object... > > 3) All objects must be aligned on a "natural" boundary. ... I don't think > anyone will tolerate the requirement that a 4Mb table be aligned on a > 4Mb boundary... These are certainly problems of a sort, but I don't think they render the scheme unworkable. With regard to (1): The scheme I propose manages to encode the "type" using only one bit. The cost of this is that actually only the length of the datum, not things like int vs. float are encoded in the pointer, so you don't get a full "object-oriented" architecture. Instead, you would still need an "integer-add" and a "floating-point-add" instruction. Whether you still need an "integer-move" and a "floating-point-move" is open to debate (I don't like traps on moves myself), but that's another subject. If you want you can devote eight bits (or some such) to type information in a pointer and get rid of all type specificity in operation codes, but it costs more than one bit of course. As for (2): Although I wouldn't totally rule out rounding structure sizes to a power of two, I'm not really advocating that radical a solution. You can copy structures with a loop like lots of machines do. I'd probably limit the extent of the scheme to whatever the largest data type of the machine is (8 byte quad integers or whatever). This way you also don't have to align your 4MB table... Radford Neal The University of Calgary
bcase@uiucdcs.UUCP (02/18/85)
I first saw the Wheeler Device described in the Bell technical report: "A 32-bit processor design" by Steve Johnson. The description given there pointed out that there is some redundancy in address specification which can be used for a small degree of error checking.
radford@calgary.UUCP (Radford Neal) (02/21/85)
> ... Perhaps it would be more convenient to put the > size encoding bits on the right. The automatic "stride adjustment" > feature goes away, but addresses no longer have to be shifted before > use, the effects of arithmetic overflow during address computation > are less painful, and direct comparison of pointers to objects of > different sizes makes a little more sense.... The effects of overflow would indeed be more "expected" (wrap-around to the beginning of memory rather than total garblement into a different kind of pointer). However I'm not sure you save by getting rid of the shift. The format of a pointer to a long would in that scheme be something like A8 A7 A6 A5 A4 A3 A2 1 0 0 A1 and A0 would still have to be converted to 0 0 rather than 1 0, which might be as bothersome as a shift. Comparisons of pointers to different types could be done by casting them to a common type as described below. > I think the main problem with encoding size in addresses is that it > would be necessary to override encoded size too often... A properly written C program will use casts for all changes of pointer type. E.g. short *a; ... *(char*)a = 1; The cast in this code would be a run-time operation (shift left by one). In the other direction - char *b; ... *(short*)b = 1; The code is not guaranteed to work unless the pointer is properly aligned. The run-time code for the cast is a shift right by one. A special shift operation could be used that trapped if a one bit was shifted out, thus detecting an alignment error at the time of the cast rather than when the pointer is used (possibly much later). All this requires only one additional machine instruction to handle type overrides, which doesn't seem excessive even if they are common, which they shouldn't be in modern programs. BTW: One advantage of the scheme I hadn't thought of before is that is certainly guarantees that zero isn't a valid pointer... -:) Radford Neal The University of Calgary
dan@petrus.UUCP (08/06/85)
> > Any comments on the following idea? > > > Take a machine with bytes, words, longs, etc. - all of sizes which are > a power of two of some basic unit - and which requires such data to be > aligned, with the address of a unit of size 2**N being required to have > N low-order zero bits. > ... > > Here's the idea: Get rid of the MOVEB, MOVEW, MOVEL, etc. instructions > and replace them with a single MOVE instruction, with the type of > unit to be moved determined by the memory address given. Addresses > have a new format, as for instance: > > 0 0 1 A8 A7 A6 A5 A4 A3 A2 > > This example specifies a long operand (four bytes) with address > > A8 A7 A6 A5 A4 A3 A2 0 0 > > In general, the size of an operand is 2**N, where N is the number of > leading zeros in its address. The "actual" address is the bits after > the highest-order one bit, padded with zeros to make it come out the > the right size. In this scheme, the address > This is a neat idea. Perhaps it would be more convenient to put the size encoding bits on the right. The automatic "stride adjustment" feature goes away, but addresses no longer have to be shifted before use, the effects of arithmetic overflow during address computation are less painful, and direct comparison of pointers to objects of different sizes makes a little more sense. Think how much easier it would be to explain this address representation to a freshman computer programming class. An extra machine instruction could be provided for pointer arithmetic with automatic "stride adjustment". I think the main problem with encoding size in addresses is that it would be necessary to override encoded size too often (I guess I don't really know this -- hacking a C compiler to gather statistics is too much work). What kind of machine language would a C compiler generate to access structure members?