From: email@example.com (John R. Mashey)
Subject: Re: Why isn't hardware designed to run software? [A: do it in s/w]
Date: Wed, 29 Dec 1993 22:42:21 GMT
In article <rfgCIqGAu.AGv@netcom.com>, firstname.lastname@example.org
(Ronald F. Guilmette) writes:
> (Note that I have NOT mentioned Cray. One poster here mentioned how much
> money would be involved in providing 12.5% more memory on a Cray. My only
> response is ``Frankly my dear, I don't give a damn.'' I am not likely to
> own one of *those* beaties in the near future anyway, so the whole subject
> seems about as relevant as the fact that I would suffocate if I were suddenly
> transported to the surface of the moon. That isn't bloody likely to happen
> anytime soon either.)
> I think the bottom line is that the kind of feature I'm speaking of is not
> really all that different from the watchpoint registers available on x86
> machines. These registers provide a fast, hardware-based solution for a
> problem that could (in theory) be done in software. But as anyone who
> has ever had need of these watchpoint registers can testify, the hardware
> solution definitely has its advantages... and can be had for little cost,
> either in terms of $$$'s or in terms of effects upon overall performance.
> In short, as I said originally, I think its well past time for hardware
> designers to start taking the real-life problems of software developers
> a bit more seriously. You hardware guys may not get any more dhrystones
> or SPECmarks out of the deal, but you may win some additional converts
> amoung us software people all the same. (And please don't forget who it
> is that *really* makes your systems attractive to end-users, ok?)
1) This request arises again and again, but *really* one can do a lot
of it [uninitialized variable-checking & subscript-range-checking,
or the related ADA constraint-checks] in software. [I looked at this
20 years ago in detail and even then, one could do it]. WATFIV often
found bugs in "production" code, to people's great consternation. :-)
2) For some reason, people seem to assume that hardware people are unreceptive
to such thing for no good reason:
a) We (MIPS folks, H/W + S/W) have looked into debugging/checking
tag features for almost every chip we've ever done, and we've *never*
been able to figure out features that were truly useful that didn't
have severe performance hits/implementation problems of one sort
or another, despite having among the design teams software people
that are passionate advocates of such things. It always came down
to hardware folks being perfectly willing to:
a) Tell us (sw folks) the cost of an implementation
b) If we could tell them *what* we wanted, and that we were
sure that what we wanted was worth the price.
c) And us never being able to design something that we thought
was really good enough to be worth it.
d) Of course, this might just have been lack of imagination
on our part, but it might also be because it's hard.
It is possible that highly-super-scalar-issue chips may
do better, and we'll look at this again for post-T5 chips.
e) Personally, I'm still convinced there is *some*
truly general mechanism that survives high-performance
implementations and helps error-checking+tagged,
but that we still haven't figured out the right thing,
despite conversations with truly world-class folks.
Having seen past attempts in hardware turn out not to be
quite right, we have to be *sure* we've got
b) People have used bad-parity bits, years ago for such purposes ...
but not in any modern designs that I know of, and especially not
in byte-addressed machines / cached machines. In particular,
the load-from-cache path is *often* in the critical path,
and people are often loath to do anything else with it,
although the cost varies from design to design.
c) While the cost of CRAY memory may not be relevant to most people,
DRAM still costs money, but even worse, there is a chicken and
egg problem due to the cost advantages of standard SIMMs, i.e.,
no one would want to use an extra bit/byte, until there are SIMMs
that size, and no one will make them until there is a market :-)
d) Things like watch registers are *really* useful ... but sometimes,
software requirements make them less useful than you'd like,
i.e., if a debugger lets you set an arbitrary number of
watch points, it's hard to do that in hardware :-)
3) In any case, the *ideal* thing is a compiler option that generates
the checks ... but optimizes them well; such "constraint-check elimination"
is found in some ADA compilers, for example.
In modern optimizers, there is plenty of information around to make many
checks disappear; it would really be nice to see *someone* work hard on'
this problem, using current compilers, and see what the actual
run-time cost would be. If I had to guess, it's maybe 5-10% for many
kinds of applications, at least for the checking, assuming that there is
not too much overhead for initializing data to "uninitialized" like
WATFIV did. A general scheme for uninitialized-reference detection could be:
a) For each reference to each variable, maintain a bit that
indicates "known-to-be-defined", computed by:
a) Any assignment to that variable sets "defined"
b) Any code in which all paths to that usage are marked defined,
means that it is defined.
c) Any code in which one is not sure that it is defined require
generating a check, and then considering it defined.
b) For the entire code, if a check is ever generated for a specific
variable, then generate prolog code to initialize it to the "uninitialized"
value, else one doesn't need this code. On most machines, floating
point hardware supports NaNs or equivalent, so no code need ever
be generated to do checks, just (possibly) to do the initializations.
c) Start with minimalist optimization, then improve it until it gets
Let's try a few examples:
a) Assume that any function can *assume* that any values passed to it
are defined. [Why is this a good idea? because quite often the
caller knows something is defined, and they might even be constants;
why should hardware take any kind of hit whatsoever to check things
that are known to be constants].
b) Any variable initialized in its definition need *never* be checked;
const variables (I think) need not be checked.
c) In a lot of cases, the same optimizations that do value-propagation
or code-motion can help you eliminate checks:
y = x+1;
y = -1;
if (y > 5)
Needs no undefined-variable checks whatsoever; a good optimizer likely
knows that y has been set for sure.
func2(xp) int *xp;
*xp = *xp + 1;
That needs *one* check, no matter how many times *xp is
referenced, assuming xp doesn't change [and compilers already
look hard at pointers]. I.e., thoughout the entire code body
of func2, the compiler *knows* that the item referenced by *xp
was checked on the first access, and either it faulted then, or
not, but it doesn't need to be checked again.
func3(xp, yp, zp;) int *xp,*yp, *zp;
for (i =0; i <100; i++)
*zp++ = *xp + *yp;
This ought to generate 2 checks:
a) AN optimizer would like to pull the expression *xp + *yp out of
the loop, but couldn't, due to possible aliasing of zp.
b) But, there is always at least one *reference* to each of
*xp and *yp, and the addresses don't change, so the optimizer could
move the *checks* in front of the loop...
Compared to C, FORTRAN is probably easier: plusses and minues of
each might be:
- Pointers everywhere + No pointers
+ BSS initialized to zero, by definition- Memory not guaranteed
- Pointers not guaranteed to non-alias + Array parameters not aliased
- Loop terminations can be complex + Loops (in practice) simple
- moderate use of 8 & 16-bit data + little use, i.e., if values
these may be harder to check are 32- and 64-bit, it's
easier to find "uninit"
+ Heavy use of floating point:
most chips have NaNs
+ Call-by-value - Call-by-reference
Anyway, given the kinds of analysis that current good optimizers do,
I don't think this sort of analysis is all that bad to do; it would be nice
to see some research on this [maybe it's around, I haven't been following
it, but I do believe that it's possible to generate quite reasonable code,
and there is *nothing* about this technique that is very hardware-dependent
(except having natural NaNs or not).
4) Subscript-out-of-range detection/optimization is more work;
maybe somebody who's done this in ADA would comment. I expect this is
easier in FORTRAN than in C, and in any case, there's no chance of doing
this very well in hardware for current machines and languages.
1) There are subtle interactions between:
c) Language-design [some features cause more trouble than others]
d) Level of copmpiler technology.
and how much checking can be done easily.
2) There is *little chance* of getting general hardware uninitialized-variable
checking into currently-popular CPU families, and subscript-checks
are probably even worse. About the best that can be hoped for,
from hardware, are a few instructions (like TRAP on MIPS & others)
that do a check quickly, expecting to succeed, and trap otherwise),
and maybe (if someone every can figure out the right thing), some
hardware pattern-match-and-trap feature general enough to cover
enough cases to make it worth having. There is *little chance* of
using extra bits in the memory system.
3) BUT: current optimizing compilers already keep track of much information
that could help optimize many of the checks away, and they could do it with
existing machines. Hence, the likeliest hope of achieving this (desirable)
a) Encouraging more compiler research
b) Encouraging compilers writers to do it.
-john mashey DISCLAIMER: <generic disclaimer, I speak for me only, etc>
DDD: 415-390-3090 FAX: 415-967-8496
USPS: Silicon Graphics 6L-005, 2011 N. Shoreline Blvd, Mountain View, CA 94039-7311