11.3 Converting Floating Point Expressions to Assembly Language

11.3 Converting Floating Point Expressions to Assembly Language

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 reverse polish notation, or RPN, for arithmetic calculations. Once you get used to using RPN, 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.

RPN, 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 RPN notation:
		infix notation						RPN notation
 
			5 + 6						5  6  +
 
			7 - 2						7  2  -
 
			x * y						x  y  *
 
			a / b						a  b  /
 

 
An RPN expression like "5 6 +" says "push five onto the stack, push six onto the stack, then pop the value off the top of stack (six) 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, RPN is a convenient notation because it's very easy to translate this code into FPU instructions.

One advantage to RPN (or 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 (two 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();
 

 
11.3.1 Converting Arithmetic Expressions to Postfix Notation

Since the process of translating arithmetic expressions into assembly language involves postfix (RPN) notation, converting arithmetic expressions into postfix notation seems like the right place to start. This section will concentrate on that 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 inbetween 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"?) there isn't much to converting simple infix expressions into postfix notation.

For complex expressions, the idea is to convert the simple sub-expressions into postfix notation and then treat each converted subexpression as a single operand in the remaining expression. The following discussion will surround completed conversions in 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 inner-most parenthetical sub-expression and then work your way outward considering precedence, associativity, and other parenthetical sub-expressions. 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. This is accomplished as follows:
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 )." Since 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. Since 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 RPN expression:
x = y z - a * a b c * + 3.14159 / -
 

 

 

 
Here is another example of an infix to postfix conversion:
a = (x * y - z + t)/2.0
 

 
Step 1: Work inside the parentheses. Since multiplication has the highest precedence, convert that first:
a = ( [x y *] - z + t)/2.0
 

 
Step 2: Still working inside the parentheses, we note that addition and subtraction have the same precedence, so we rely upon 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
 

 
Step 3: Now translate the addition operator inside the parentheses. Since this finishes the parenthetical operators, we can drop the parentheses:
a = [x y * z - t +]/2.0
 

 
Step 4: Translate the final infix operator (division). This yields the following:
a = [x y * z - t + 2.0 / ]
 

 
Step 5: Drop the square brackets and we're done:
a = x y * z - t + 2.0 /
 

 
11.3.2 Converting Postfix Notation to Assembly Language

Once you've translated an arithmetic expression into postfix notation, finishing the conversion to assembly language is especially 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 will use 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 / -
 

 
Step 1: Convert y to FLD(y);
Step 2: Convert z to FLD(z);
Step 3: Convert "-" to FSUB();
Step 4: Convert a to FLD(a);
Step 5: Convert "*" to FMUL();
Steps 6-n: 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 trivial 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¹. For these reasons, conversion of floating point expressions into assembly language is actually easier than converting integer expressions.

11.3.3 Mixed Integer and Floating Point Arithmetic

Throughout the previous sections on floating point arithmetic an unstated assumption was made: all operands in the expressions were floating point variables or constants. In the real world, you'll often need to mix integer and floating point operands in the same expression. Thanks to the FILD instruction, this is a trivial exercise.

Of course, the FPU cannot operate on integer operands. That is, you cannot push an integer operand (in integer format) onto the FPU stack and add this integer to a floating point value that is also on the stack. Instead, you use the FILD instruction to load and translate the integer value; this winds up pushing the floating point equivalent of the integer onto the FPU stack. Once the value is converted to a floating point number, you continue the calculation using the standard real arithmetic operations.

Embedding a floating point value in an integer expression is a little more problematic. In this case you must convert the floating point value to an integer value for use in the integer expression. To do this, you must use the FIST instruction. FIST converts the floating point value on the top of stack into an integer value according to the setting of the rounding bits in the floating point control register (See "The FPU Control Register" on page 612). By default, FIST will round the floating point value to the nearest integer before storing the value into memory; if you want to use the more common fraction truncation mode, you will need to change the value in the FPU control register. You compute the integer expression using the techniques from the previous chapter (see "Complex Expressions" on page 600). The FPU participates only to the point of converting the floating point value to an integer.
static
 
	intVal1 : uns32 := 1;
 
	intVal2 : uns32 := 2;
 
	realVal : real64;
 
		.
 
		.
 
		.
 
		fild( intVal1 );
 
		fild( intVal2 );
 
		fadd();
 
		fstp( realVal );
 
		stdout.put( "realVal = ", realVal, nl );
 
¹Assuming, of course, that your calculations aren't so complex that you exceed the eight-element limitation of the FPU stack.

11.3 Converting Floating Point Expressions to Assembly Language

11.3.1 Converting Arithmetic Expressions to Postfix Notation

11.3.2 Converting Postfix Notation to Assembly Language

11.3.3 Mixed Integer and Floating Point Arithmetic

Web Site Hits Since Jan 1, 2000

Web Site Hits Since
Jan 1, 2000