Because the FPU register organization is different than the 80x86 integer register set, translating arithmetic expressions involving floating-point operands is a little different than the techniques for translating integer expressions. Therefore, it makes sense to spend some time discussing how to manually translate floating-point expressions into assembly language.
In one respect, it's actually easier to translate floating-point expressions into assembly language. The stack architecture of the Intel FPU eases the translation of arithmetic expressions into assembly language. If you've ever used a Hewlett-Packard calculator, you'll be right at home on the FPU because, like the HP calculator, the FPU uses postfix notation (also called Reverse Polish notation, or RPN ), for arithmetic operations. Once you get used to using postfix notation, it's actually a bit more convenient for translating expressions because you don't have to worry about allocating temporary variables—they always wind up on the FPU stack.
Postfix notation, as opposed to standard infix notation, places the operands before the operator. The following examples give some simple examples of infix notation and the corresponding postfix notation:
infix notation postfix notation
5 + 6 5 6 +
7 − 2 7 2 −
x * y x y *
a / b a b /A postfix expression like 5 6 + says, "push 5 onto the stack, push 6 onto the stack, and then pop the value off the top of stack (6) and add it to the new top of stack." Sound familiar? This is exactly what the fld and fadd instructions do. In fact, you can calculate this using the following code:
fld( 5.0 );
fld( 6.0 );
fadd(); // 11.0 is now on the top of the FPU stack.As you can see, postfix is a convenient notation because it's very easy to translate this code into FPU instructions.
One advantage to postfix notation is that it doesn't require any parentheses. The following examples demonstrate some slightly more complex infix-to-postfix conversions:
infix notation postfix notation
(x + y) * 2 x y + 2 *
x * 2 − (a + b) x 2 * a b + −
(a + b) * (c + d) a b + c d + *The postfix expression x y + 2 * says, "Push x, then push y; next, add those values on the stack (producing x + y on the stack). Next, push 2 and then multiply the two values (2 and x + y) on the stack to produce two times the quantity x + y." Once again, we can translate these postfix expressions directly into assembly language. The following code demonstrates the conversion for each of the above expressions:
// x y + 2 *
fld( x );
fld( y );
fadd();
fld( 2.0 );
fmul();
// x 2 * a b + −
fld( x );
fld( 2.0 );
fmul();
fld( a );
fld( b );
fadd();
fsub();
// a b + c d + *
fld( a );
fld( b );
fadd();
fld( c );
fld( d );
fadd();
fmul();Because the process of translating arithmetic expressions into assembly language involves postfix notation (RPN), converting arithmetic expressions into postfix notation seems like a good place to begin our discussion of floating-point expression conversion. This section will concentrate on postfix conversion.
For simple expressions, those involving two operands and a single expression, the translation is trivial. Simply move the operator from the infix position to the postfix position (that is, move the operator from between the operands to after the second operand). For example, 5 + 6 becomes 5 6 +. Other than separating your operands so you don't confuse them (i.e., is it 5 and 6 or 56?), converting simple infix expressions into postfix notation is straightforward.
For complex expressions, the idea is to convert the simple subexpressions into postfix notation and then treat each converted subexpression as a single operand in the remaining expression. The following discussion surrounds completed conversions with square brackets so it is easy to see which text needs to be treated as a single operand in the conversion.
As for integer expression conversion, the best place to start is in the innermost parenthetical subexpression and then work your way outward considering precedence, associativity, and other parenthetical subexpressions. As a concrete working example, consider the following expression:
x = ((y - z) * a) - ( a + b * c ) / 3.14159
A possible first translation is to convert the subexpression (y - z) into postfix notation:
x = ([y z -] * a) - ( a + b * c ) / 3.14159
Square brackets surround the converted postfix code just to separate it from the infix code. These exist only to make the partial translations more readable. Remember, for the purposes of conversion we will treat the text inside the square brackets as a single operand. Therefore, you would treat [y z -] as though it were a single variable name or constant.
The next step is to translate the subexpression ([y z -] * a ) into postfix form. This yields the following:
x = [y z - a *] - ( a + b * c ) / 3.14159
Next, we work on the parenthetical expression ( a + b * c ). Because multiplication has higher precedence than addition, we convert b * c first:
x = [y z - a *] - ( a + [b c *]) / 3.14159
After converting b * c we finish the parenthetical expression:
x = [y z - a *] - [a b c * +] / 3.14159
This leaves only two infix operators: subtraction and division. Because division has the higher precedence, we'll convert that first:
x = [y z - a *] - [a b c * + 3.14159 /]
Finally, we convert the entire expression into postfix notation by dealing with the last infix operation, subtraction:
x = [y z - a *] [a b c * + 3.14159 /] -
Removing the square brackets to give us true postfix notation yields the following postfix expression:
x = y z - a * a b c * + 3.14159 / -
The following steps demonstrate another infix-to-postfix conversion for the expression:
a = (x * y - z + t) / 2.0
Work inside the parentheses. Because multiplication has the highest precedence, convert that first:
a = ( [x y *] - z + t) / 2.0
Still working inside the parentheses, we note that addition and subtraction have the same precedence, so we rely on associativity to determine what to do next. These operators are left associative, so we must translate the expressions in a left-to-right order. This means translate the subtraction operator first:
a = ( [x y * z -] + t) / 2.0
Now translate the addition operator inside the parentheses. Because this finishes the parenthetical operators, we can drop the parentheses:
a = [x y * z - t +] / 2.0
Translate the final infix operator (division). This yields the following:
a = [x y * z - t + 2.0 / ]
Drop the square brackets and we're done:
a = x y * z - t + 2.0 /
Once you've translated an arithmetic expression into postfix notation, finishing the conversion to assembly language is easy. All you have to do is issue an fld instruction whenever you encounter an operand and issue an appropriate arithmetic instruction when you encounter an operator. This section uses the completed examples from the previous section to demonstrate how little there is to this process.
x = y z - a * a b c * + 3.14159 / -
Convert y to fld(y).
Convert z to fld(z).
Convert - to fsub().
Convert a to fld(a).
Convert * to fmul().
Continuing in a left-to-right fashion, generate the following code for the expression:
fld( y );
fld( z );
fsub();
fld( a );
fmul();
fld( a );
fld( b );
fld( c );
fmul();
fadd();
fldpi(); // Loads pi (3.14159)
fdiv();
fsub();
fstp( x ); // Store result away into x.Here's the translation for the second example in the previous section:
a = x y * z - t + 2.0 /
fld( x );
fld( y );
fmul();
fld( z );
fsub();
fld( t );
fadd();
fld( 2.0 );
fdiv();
fstp( a ); // Store result away into a.As you can see, the translation is fairly simple once you've converted the infix notation to postfix notation. Also note that, unlike integer expression conversion, you don't need any explicit temporaries. It turns out that the FPU stack provides the temporaries for you.[104] For these reasons, conversion of floating-point expressions into assembly language is actually easier than converting integer expressions.
[104] This assumes, of course, that your calculations aren't so complex that you exceed the eight-element limitation of the FPU stack.