Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!pasteur!ucbvax!hplabs!pyramid!prls!mips!sjc
From: sjc@mips.COM (Steve "The" Correll)
Newsgroups: comp.arch
Subject: Re: conditional branches
Message-ID: <1578@quacky.mips.COM>
Date: 15 Feb 88 08:18:37 GMT
References: <191@telesoft.UUCP> <1556@gumby.mips.COM> <208@telesoft.UUCP>
Lines: 40

In article <208@telesoft.UUCP>, roger@telesoft.UUCP (Roger Arnold @prodigal) writes:
> ...there aren't
> enough bits to specify two operands and a target address in one fixed 
> size instruction.  Not, at least, without imposing restrictions that do 
> ugly things to the instuction set's orthogonality.  (E.g., both operands 
> in a register, target address a limited displacement PC relative mode).  
> Then, too, condition codes enable instruction scheduling; very good for 
> pipelining and low level parallelism in top end hardware.

As an illustration, the MIPS compare-and-branch allocates 6 bits to an opcode,
5 bits to each register field, and 16 bits to a word-offset target.

The register-operand-only restriction seems painless in practice (if a value
is being tested often, the optimizer is happy to keep it in a register, and
one of the registers acts like a literal zero) and we have immediate "set
less than" instructions which set the low-order bit of a register for testing
later on. This is similar to a condition code, but uses any available
general-purpose register rather than a dedicated boolean. Sometimes that
really pays off. For example, I like to avoid branches by implementing the
three-way comparison used by Unix "qsort" (yielding -1/0/+1) as:

  (t0 > t1) - (t0 < t1)

This translates into two "set less than"s and a "subtract"; it's possible
precisely because the result of each comparison goes into a general register
rather than a dedicated boolean. One can similarly use arithmetic in lieu of
branches for certain range-checks, and one can use "set less than" followed
by an ordinary add to propagate a carry in multiple-precision arithmetic; I
can't prove it's superior to a carry flag plus "addc" and "subc" instructions,
but it's satisfyingly simple and elegant.

The 16-bit offset restriction is almost never a problem, but loops with more
than 128k bytes of code inside them do exist, and they are indeed a pain.

Condition codes can be good or bad for instruction-scheduling: in some CISC
architectures, so many instructions bash so many condition codes that you
have to keep the test and the branch adjacent anyway.

-- 
...decwrl!mips!sjc						Steve Correll