Question: "Zuse's Device"

Dear all,


For concreteness, suppose you had a big-endian machine with two's
complement integer arithmetic, with 8-bit registers. A high bit
of '0' is a nonnegative value, and a high bit of '1' is a negative
value. Assume all variables are 8-bit integers.


You have some code fragment containing a conditional statement,
say:


                if k > 0 then
                                a = a + 1
                endif


and you want to recode this so that there are no
conditional instructions. So you recode the fragment as:


# get all the bits of k.
                k0 = k & 0x01
                k1 = (k & 0x02) >> 1
                k2 = (k & 0x04) >> 2
                k3 = (k & 0x08) >> 3
                k4 = (k & 0x10) >> 4
                k5 = (k & 0x20) >> 5
                k6 = (k & 0x40) >> 6
                k7 = (k & 0x80) >> 7
# set multiplier m to 1, if k7==0 and at least one of k0..k6 == 1;
# otherwise set multiplier m to 0.
                m = ((!k7) & 0x01) & (k6 | k5 | k4 | k3 | k2 | k1 | k0)
# now calculate what 'a' must be...
                a = a + (m * 1)


We've now got a computation that does the same thing as the original
fragment, but uses no conditional instructions. I wouldn't be surprised
if you could come up with a shorter way of doing this. The idea, though,
is that we've turned a conditional computation into an unconditional
one that produces the same outputs for the same inputs as the original.


Question:


Does this hackery have a name? In high school (1981?), we used to
do this with 6502 machine code. So this is not rocket science.
Konrad Zuse apparently knew about it when he was programming
his Z4 computer in the forties. So this idea is not new, either.


For lack of a name, I call this "Zuse's Device" (cf Jensen's Device),
but I was wondering if there was a commonly agreed-upon term for
this method. (aside from "Blecch!" :-)


Background: I've been thinking of ways to remove branches from sequences
of code in an instruction pipeline, and seeing if I could completely
"unconditionalize" the code, and thus side-step the problem of branch
prediction: no branches ==> no branch prediction necessary ==> no
pipeline stalls.


I've looked in compiler texts, e.g. Fischer & LeBlanc, the Dragon
Book, Muchnick's Advanced Compiler Design & Impl., but I haven't
been able to find a name for "Zuse's Device", and was wondering
if c.c. readers knew this method by some other name, and if so, what..?


Note to the moderator: no, this question is not from an assignment.
No teacher I have ever known would sanction such bletchery. :-)


-lg


Lou Glassy (glassy@cs.montana.edu)
[This sort of linearization is certainly a widely used technique,
particularly on deeply pipelined RISCs, but I don't know if it has a
commonly used name. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.