2-11 Comparison Predicates

A "comparison predicate" is a function that compares two quantities, producing a single bit result of 1 if the comparison is true, and 0 if the comparison is false. Below we show branch-free expressions to evaluate the result into the sign position. To produce the 1/0 value used by some languages (e.g., C), follow the code with a shift right of 31. To produce the -1/0 result used by some other languages (e.g., Basic), follow the code with a shift right signed of 31.

These formulas are, of course, not of interest on machines such as MIPS, the Compaq Alpha, and our model RISC, which have comparison instructions that compute many of these predicates directly, placing a 0/1-valued result in a general purpose register.

A machine instruction that computes the negative of the absolute value is handy here. We show this function as "nabs." Unlike absolute value, it is well defined in that it never overflows. Machines that do not have "nabs" but have the more usual "abs" can use -abs(x) for nabs(x). If x is the maximum negative number, this overflows twice, but the result is correct. (We assume that the absolute value and the negation of the maximum negative number is itself.) Because some machines have neither "abs" nor "nabs," we give an alternative that does not use them.

The "nlz" function is the number of leading zeros in its argument. The "doz" function (difference or zero) is described on page 37.

For x > y, x y, and so on, interchange x and y in the formulas for x < y x y, and so on. The add of 0x80000000 may be replaced with any instruction that inverts the high-order bit (in x, y, or x - y).

Another class of formulas can be derived from the observation that the predicate x < y is given by the sign of x/2 - y/2, and the subtraction in that expression cannot overflow. The result can be fixed up by subtracting 1 in the cases in which the shifts discard essential information, as follows:

These execute in seven instructions on most machines (six if it has and not), which is no better than what we have above (five to seven instructions, depending upon the fullness of the set of logic instructions).

The formulas above involving "nlz" are due to [Shep], and his formula for the x = y predicate is particularly useful because a minor variation of it gets the predicate evaluated to a 1/0-valued result with only three instructions:

Signed comparisons to 0 are frequent enough to deserve special mention. Below are some formulas for these, mostly derived directly from the above. Again, the result is in the sign position.

Signed comparisons can be obtained from their unsigned counterparts by biasing the signed operands upwards by 2³¹ and interpreting the results as unsigned integers. The reverse transformation also works. Thus we have

Similar relations hold for and so on. Addition and subtraction of 2³¹ are equivalent, as they amount to inverting the sign bit.

Another way to get signed comparisons from unsigned is based on the fact that if x and y have the same sign, then whereas if they have opposite signs, then [Lamp]. Again, the reverse transformation also works, so we have

where x₃₁and y₃₁ are the sign bits of x and y, respectively. Similar relations hold for and so on.

Using either of these devices enables computing all the usual comparison predicates other than = and in terms of any one of them, with at most three additional instructions on most machines. For example, let us take as primitive, because it is one of the simplest to implement (it is the carry bit from y - x). Then the other predicates can be obtained as follows:

Comparison Predicates from the Carry Bit

If the machine can easily deliver the carry bit into a general purpose register, this may permit concise code for some of the comparison predicates. Below are listed several of these relations. The notation carry(expression) means the carry bit generated by the outermost operation in expression. We assume the carry bit for the subtraction x - y is what comes out of the adder for x + y?/span> + 1, which is the complement of "borrow."

For x > y, use the complement of the expression for x y, and similarly for other relations involving "greater than."

The GNU Superoptimizer has been applied to the problem of computing predicate expressions on the IBM RS/6000 computer and its close relative PowerPC [GK]. The RS/6000 has instructions for abs(x), nabs(x), doz(x, y), and a number of forms of add and subtract that use the carry bit. It was found that the RS/6000 can compute all the integer predicate expressions with three or fewer elementary (one-cycle) instructions, a result that surprised even the architects of the machine. "All" includes the six two-operand signed comparisons and the four two-operand unsigned comparisons, all of these with the second operand being 0, and all in forms that produce a 1/0 result or a -1/0 result. PowerPC, which lacks abs(x), nabs(x), and doz(x, y), can compute all the predicate expressions in four or fewer elementary instructions.

How the Computer Sets the Comparison Predicates

Most computers have a way of evaluating the integer comparison predicates to a 1-bit result. The result bit may be placed in a "condition register" or, for some machines (such as our RISC model), in a general purpose register. In either case, the facility is often implemented by subtracting the comparison operands and then performing a small amount of logic on the result bits to determine the 1-bit comparison result.

Below is the logic for these operations. It is assumed that the machine computes x - y as x + y?/span> + 1, and the following quantities are available in the result:

C_o, the carry out of the high-order position

C_i, the carry into the high-order position

N, the sign bit of the result

Z, which equals 1 if the result, exclusive of C_o, is all-0, and is otherwise 0

Then we have the following in Boolean algebra notation (juxtaposition denotes and, + denotes or):