6.7 Converting Floating Point Expressions to Assembly Language


6.7 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(); 

6.7.1 Converting Arithmetic Expressions to Postfix Notation

Because the process of translating arithmetic expressions into assembly language involves postfix (RPN) notation, 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 RPN 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 in 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"?) there isn't much to converting simple infix expressions into postfix notation.

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 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 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 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. Because 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. Because 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 / 

6.7.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.[4] For these reasons, conversion of floating point expressions into assembly language is actually easier than converting integer expressions.

[4]Assuming, of course, that your calculations aren't so complex that you exceed the eightelement limitation of the FPU stack.




The Art of Assembly Language
The Art of Assembly Language
ISBN: 1593272073
EAN: 2147483647
Year: 2005
Pages: 246
Authors: Randall Hyde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net