Shift operators
Mitch Bradley
> else result = logical shift right(x,n')
I do not agree with this description of the meaning of ANS Forth SHIFT.
The committee discussed this issue (what happens if the shift count is
larger than the cell size) at length at the Florida meeting. As I recall,
the decision was that this condition is ambiguous, allowing implementors
to avoid an explicit test of the magnitude of the shift count.
I agree that encoding the shift direction in the sign of the shift count
is not the best thing to do. I would prefer separate left-shift and
right-shift operators (I use the same names as C - << and >> , although
I wouldn't mind the names LSHIFT and RSHIFT). With SHIFT, I have trouble
remembering which direction corresponds to which sign.
One problem with the ROTATE proposal: the implied "mod 32" operation makes
it bidirection with signed shift counts, but that is an artifact of
two's-complement number representation.
If the goal is hardware efficiency, then separate left-shift and right-shift
operators, with an ambiguity for large shift counts, is the way to go.
*ALL* popular processors can do that in one instruction, and you don't
have to wave your hands and sweep the popular RISC processors under the
rug, as with the ROTATE proposal. The extra instructions necessary to
implement ROTATE are comparable in cost to the adverse pipeline effects
of a branch.
For reference, here is the SPARC code for ANS Forth SHIFT . This assumes
that the arguments have already been moved from the stack into registers,
which code is independent of the details of the computation to be performed.
(Input: shift count in TOS register, number to be shifted in SCR register.)
(Output: result left in TOS register)
addcc tos, %g0, %g0 \ Set condition codes from shift count
bgt,a 1f \ Branch if shift count positive,
\ cancelling delay slot if branch not taken
sll scr, tos, scr \ Perform left shift if branch taken
sub %g0, tos, tos \ Negate shift count if shift count negative
srl scr, tos, tos \ Perform right shift
1: \ Result is in TOS
This costs 3 clocks in the positive shift count case, and 5 in the
negative shift count case, so it looks like pretty much a wash compared
to the ROTATE code.
Mitch
John Hayes
>> if n' > 31 result = 0
>> else result = logical shift right(x,n')
Mitch Bradley responds:
>I do not agree with this description of the meaning of ANS Forth SHIFT.
>The committee discussed this issue (what happens if the shift count is
>larger than the cell size) at length at the Florida meeting. As I recall,
>the decision was that this condition is ambiguous, allowing implementors
>to avoid an explicit test of the magnitude of the shift count.
I vaguely remember the discusion mentioned but do not remember the
outcome. The current draft standard document (and all copies of the
Basis going back to the Florida meeting) contain no ambiguous
conditions on SHIFT. The range check IS required.
>I agree that encoding the shift direction in the sign of the shift count
>is not the best thing to do. I would prefer separate left-shift and
>right-shift operators (I use the same names as C - << and >> , although
>I wouldn't mind the names LSHIFT and RSHIFT). With SHIFT, I have trouble
>remembering which direction corresponds to which sign.
>One problem with the ROTATE proposal: the implied "mod 32" operation makes
>it bidirection with signed shift counts, but that is an artifact of
>two's-complement number representation.
True.
>If the goal is hardware efficiency, then separate left-shift and right-shift
>operators, with an ambiguity for large shift counts, is the way to go.
>*ALL* popular processors can do that in one instruction, and you don't
>have to wave your hands and sweep the popular RISC processors under the
>rug, as with the ROTATE proposal. The extra instructions necessary to
>implement ROTATE are comparable in cost to the adverse pipeline effects
>of a branch.
The bidirectional shift operator is probably a result of the parsimony
of Forth philosophy; why have two operators when one will do. Whether
or not I agree with this philosophy, a single bidirectional operator
is what is specified in ANS Forth. Since the bidirectional shift
is inefficient on all architectures (however, see footnote below),
even if the range of the shift extent does not have to be checked,
and since rotate can be implemented efficiently on some at least
some architectures, I would prefer rotate.
It might be instructive to define the useful range of applications
for shift operators. In my personal experience, I have used them
for bit field manipulations. Others, I am told, like to use them
to speed multiplication and division by powers of two. The
following is a table that outlines how SHIFT or ROTATE might
be used to implement these functions:
operation SHIFT ROTATE
____________________________________________________________
bit field -x SHIFT y AND -x ROTATE y AND
extract ok ok
bit field x SHIFT OR x ROTATE OR (details suppressed)
insert ok ok
multiply x SHIFT x ROTATE
unsigned by ok ok
power of 2
divide -x SHIFT -x ROTATE
unsigned by ok must mask to
power of 2 to get right answer
multiply x SHIFT x ROTATE
signed by only works broken!
power of 2 with 2's comp.
divide -x SHIFT -x ROTATE
signed by broken! broken!
power of 2
In my experience, ROTATE and SHIFT are interchangable for doing bit
field manipulations. Using SHIFT or ROTATE to multiply or divide
seems dubious to me. I would prefer to write my code using multiply
and let a compiler do strength reduction optimizations if appropriate.
Footnote:
A diligent reader pointed out that the PDP-11 has a bidirectional
shift instruction. However, it is an arithmetic shift and ANS
Forth specifies logical shift.
John R. Hayes jo...@aplcomm.jhuapl.edu
Applied Physics Laboratory
Johns Hopkins University
Andrew Scott
>The bidirectional shift operator is probably a result of the parsimony
>of Forth philosophy; why have two operators when one will do.
I thought part of the Forth philosophy was exactly the *opposite*. We
wouldn't have words like 1+ or 0< if efficiency wasn't regarded as more
important than a small set of consistent words.
--
Andrew Scott | mail: and...@idacom.hp.com
| - or - ..!uunet!ubc-cs!alberta!idacom!andrew
"Sometimes you're the windshield. Sometimes you're the bug." - Mark Knopfler