a style question

[John Mashey]

In article <MEISSNER.90Oct2140411 at osf.osf.org> meissner at osf.org (Michael Meissner) writes:
>In article <1990Oct2.151644.1581 at phri.nyu.edu> roy at phri.nyu.edu (Roy
>Smith) writes:
>
>| 	Are there actually any machines in which a compare-and-branch for
>| inequality is any faster or slower than a compare-and-branch for less-than?
>| It seems to me that either should take one pass through the ALU to do the
>| comparison and set some flags, so they should both take the same amount of
>| time.  I'm basing my assumption on experience with pdp-11 type machines,
>| but I find it hard to imagine any other machine being significantly
>| different......
Well, they are different....

>Yes, any computer based on the MIPS chipset (MIPS, DECstation, SGI) is
>faster to do a branch on both equality and inquality, than for the
>other comparison operators.

>Mips does not have a branch on a < b (unless b is 0).  It has a set
>register to 1 if a < b instruction (& 0 otherwise).  Thus to do the
>branch, you set the scratch register to be the value of a < b, and
>then do a branch on that register being zero.  It does have a direct
>instruction to branch if two registers are equal or not equal.
....example....
>From looking at the way the bits are set down, the blez (branch on
>less than or equal zero) and bgtz (branch on greater than zero)
>instructions could have been defined as ble and bgt, since the second
>register field is required to be 0 (and register $0 is hardwired to
>0).  I suspect the decision may have been due to chip real estate, and
>the fact that equality comparisons happen more frequently in real
>programs.

OK, now the real reason is the cycle time tradeoff, which may or
may not be relevant to other chips, because it depends on other decisions
you have made.  The R3000 worked pretty hard to get 1-cycle
compare-and-branch for everything that it could, including such things
as a micro-tlb because it couldn't do a lookup in the main tlb quite
fast enough.  SO, WHY does it have:
1.	branch on a == b	2 registers
2.	branch on a != b	""
3.	branch on a <= 0	register & 0
4.	branch on a > 0		""
5.	branch on a < 0		""
6.	branch on a >= 0	""

But not
7,8.	branch on a < b, or a <= b

ANS:
	7-8 require a 32-bit subtract.
	1-6 do not require any subtract, and can be implemented with logic
	that is faster than subtract, in less space.
	Note that 1 & 2 can be implemented by xoring a & b, and seeing
	if the resulting bits are all zero (1), or not all zero (2).
	Cases 5 & 6 need only test the sign bit.
	Cases 3 and 4 test the sign bit plus whether or not all other
	bits are 0.
	
	The timing was tight enough, for us, that a subtract as part of
	a compare-and-branch would have lengthened the cycle time,
	or would have added another branch delay cycle, losing
	more than the compensation gained by having the extra instruction.
	Deciding this took simulation, including noting that the most
	frequent (>50%) test is a == 0 or a != 0  (1 or 2), and that smart
	compilers can often turn some loop termninations from a <= N
	into a == N.  Note that one must still include a compare
	instruction (in our case Set Less Than), that is essentially
	a subtract, but delivers the 0/1 indication to another register,
	and easily fits in the same timing as a normal subtract, but does
	not have to obtain the result quite as quickly as the compare-branch
	instructions must.

See pages 106-107 in Hennessy & Patterson for further discussion.

Again, note that this reasoning may or may not be valid for everybody,
as it depends on the other architectural predecessors & expected
implementation technologies.  For example, I think HP PA chose the other
direction. 

However, such choices are hardly random events, or people leaving things
out for no particular reason.  I recall this one got studied a lot,
because conditional branches are important, and they tend not to go
away, even with good optimizers.
-- 
-john mashey	DISCLAIMER: <generic disclaimer, I speak for me only, etc>
UUCP: 	 mash at mips.com OR {ames,decwrl,prls,pyramid}!mips!mash 
DDD:  	408-524-7015, 524-8253 or (main number) 408-720-1700
USPS: 	MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086