Lars T Hansen
2012-07-23 11:48:47 UTC
I'm porting Larceny to a new platform and this time all MacScheme
registers are hardware registers (so there are comparatively few of
them - R0..R5 at the time, but R6 and R7 are within reach). That
turned up an interesting cluster of very old bugs in the runtime.
In the code for rest arguments, there's this piece of documentation
(eg millicode.c, cglue.c):
There are four cases, depending on how many arguments are passed and
how many that are expected. ...
Let R = (the # of registers), r = (R - 1).
Let j = RESULT (the actual number of arguments).
Let n = SECOND (the number of fixed arguments).
Since the compiler enforces that all fixed arguments are in registers,
we then have two easy cases (the others are not relevant):
Case 0: n < R-2, j < r [i.e. all fixed args and varargs are in registers]
(set! REGn+1 (list REGn+1 ... REGj))
Case 1: n < R-2, j >= r [i.e. all fixed args are in registers, but
all varargs are not -- some are in a list in REGr].
(set! REGn+1 (append! (list REGn+1 ... REGr-1) (copylist REGr)))
The assertion that the compiler enforces that all fixed arguments are
in registers is not true (nor would it be helpful if it were, because
a lot of code would not compile on a port where all registers are
hardware registers and the are few hardware registers). The restargs
code has to be fixed to handle the a further two cases, documented in
the MacScheme Instruction Set note. (I've done so.)
For hack value, I went back to the RCS repositories to see when this
code might have been written. So far as I can tell the code was
committed on 13 September 1991. I remember having a conversation with
Will at some point that Twobit could enforce the invariant that is
documented above, hence we could simplify the runtime, and that's
probably why I wrote the code the way I did. Looking at the Twobit
code from around the same time, it has stubs (essentially panics) in
cases where the number of registers required exceeds 32 (hardcoded at
the time). So in a sense the code might have been correct when it was
written, but it became incorrect later, and in any case it should have
had checks on its assumptions.
There's a second bug in the rest arguments code. It uses mc_alloc to
allocate an arena for use for the result list, to avoid write barriers
and having to anchor intermediate results (at the time I thought it
was very clever). That code is only correct when allocating out of
the small-object nursery; I believe it is incorrect if Larceny might
allocate the arena object out of the large-object area because large
objects can't be split implicitly in the way small objects can. At
the time the code was written, Larceny had no large-object area, so it
was correct then, but became incorrect later.
(There may be a third bug, in Twobit, where it uses "car" rather than
"car:pair" to destructure the list of excess fixed arguments upon
procedure entry, but at most it would be a performance bug, I haven't
verified that the change would be legal, and in any case the presumed
unnecessary check is what helped me find the rest arguments bug, so
it's hard to complain.)
--lars
registers are hardware registers (so there are comparatively few of
them - R0..R5 at the time, but R6 and R7 are within reach). That
turned up an interesting cluster of very old bugs in the runtime.
In the code for rest arguments, there's this piece of documentation
(eg millicode.c, cglue.c):
There are four cases, depending on how many arguments are passed and
how many that are expected. ...
Let R = (the # of registers), r = (R - 1).
Let j = RESULT (the actual number of arguments).
Let n = SECOND (the number of fixed arguments).
Since the compiler enforces that all fixed arguments are in registers,
we then have two easy cases (the others are not relevant):
Case 0: n < R-2, j < r [i.e. all fixed args and varargs are in registers]
(set! REGn+1 (list REGn+1 ... REGj))
Case 1: n < R-2, j >= r [i.e. all fixed args are in registers, but
all varargs are not -- some are in a list in REGr].
(set! REGn+1 (append! (list REGn+1 ... REGr-1) (copylist REGr)))
The assertion that the compiler enforces that all fixed arguments are
in registers is not true (nor would it be helpful if it were, because
a lot of code would not compile on a port where all registers are
hardware registers and the are few hardware registers). The restargs
code has to be fixed to handle the a further two cases, documented in
the MacScheme Instruction Set note. (I've done so.)
For hack value, I went back to the RCS repositories to see when this
code might have been written. So far as I can tell the code was
committed on 13 September 1991. I remember having a conversation with
Will at some point that Twobit could enforce the invariant that is
documented above, hence we could simplify the runtime, and that's
probably why I wrote the code the way I did. Looking at the Twobit
code from around the same time, it has stubs (essentially panics) in
cases where the number of registers required exceeds 32 (hardcoded at
the time). So in a sense the code might have been correct when it was
written, but it became incorrect later, and in any case it should have
had checks on its assumptions.
There's a second bug in the rest arguments code. It uses mc_alloc to
allocate an arena for use for the result list, to avoid write barriers
and having to anchor intermediate results (at the time I thought it
was very clever). That code is only correct when allocating out of
the small-object nursery; I believe it is incorrect if Larceny might
allocate the arena object out of the large-object area because large
objects can't be split implicitly in the way small objects can. At
the time the code was written, Larceny had no large-object area, so it
was correct then, but became incorrect later.
(There may be a third bug, in Twobit, where it uses "car" rather than
"car:pair" to destructure the list of excess fixed arguments upon
procedure entry, but at most it would be a performance bug, I haven't
verified that the change would be legal, and in any case the presumed
unnecessary check is what helped me find the rest arguments bug, so
it's hard to complain.)
--lars