Where should the type information be: in tags and descriptors 417

Here's an example of what I'm driving at (using Ada syntax, but the same applies to many other languages):

type BitMap is array (1..20) of Boolean; for BitMap'ComponentSize use 1; -- 1 bit for each component.

Now an object of type BitMap will fit comfortably in a 32-bit word (BitMap is 20 bits in size).

HugeArray: array (1..1000000) of BitMap

for I in HugeArray'Range loop for J in BitMap'Range loop HugeArray(I)(J) := not HugeArray(I)(J); end loop; end loop;

I want HugeArray to fit in a million words. If the hardware is doing array bounds checking, we need to store the numbers 1 and 20 somewhere in memory at run time. A million copies of each? That triples the memory use. Or do we use an extra indirection, slowing down the hardware? With the software method, those bounds need not be stored at all, because in this example, they are known at compile time. (If the 20 were replaced by a run-time quanbreasty, it would typically be stored just once -- not a million times.)

Furthermore, for this example, a hardware implementation of array-bounds checking cannot *possibly* be faster than the software method used by a good compiler, because a good compiler will generate *zero* instructions for array bounds checking in the above loop. (And if the 20 were replaced by a run-time quanbreasty, a good compiler will *still* have zero overhead for bounds checking -- it doesn't need to know the bounds, nor the values of I and J, in order to prove that I and J are within the bounds.)

Now some hardware proposals would not check the 1..20 bounds -- they would just check that HugeArray(X)(Y) lies somewhere within HugeArray. That's nice, but it doesn't do what the language wants -- it fails to detect the bug where X = 1 and Y = 21, for example. That's an example of what I meant by "lousy semantic match" -- the hardware checks something, but it doesn't match the language semantics. So the compiler must generate software checking code in some cases anyway.

And it has to be that way -- the hardware can't possible be a good match for *all* languages, since different languages have different rules about array bounds.

- Bob