Method of translating a source operation to a target operation, computer program, storage medium, computer and translation6817012Abstract A method is provided for translating a source operation to a target operation. The source operation acts on one or more source operands, each comprising a binary integer of a first bit-width. The target operation is required to be evaluated by a processor, such as a computer, which performs integer operations on binary integers of a second bit-width which is greater than first bit-width. The source operation is translated to a target operation having at least one target operand. The method identifies whether the value of unused bits of the or each target operand affects the value of the target operation and whether the target operand or any of the target operands is capable of having one or more unused bits of inappropriate value. If so, a correcting operation is added to the target operation for correcting the value of each of the bits of inappropriate value before performing the target operation. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
Integer Value (in bits) High-Bit Properties
unused significant sign-
bits bits masked extended
0000000 101011011 yes no
1111111 101011011 no yes
0010001 101011011 no no
0000000 010101101 yes yes
1111111 010101101 no no
A target expression is said to be faithful if, for every assignment, it evaluates to a value whose interpretation is the same as that of its significant bit-string (assuming the same sign). Therefore, an expression is faithful if: it is unsigned and has the masked property, or it is signed and has the sign-extended property. It is a sometimes convenient that every sub-expression of a target expression is also annotated with the type information because: the sign and representative width of the expression may be required by the operation which extracts a machine readable representation of the target expression; one can develop optimisations on the internal representation of the target expressions which make use of the significant width and high-bit properties. We can also generalise the high-bit values of the expression to give us the extent of the masking and sign-extension of the expression by using the following two values: masking extent: A target expression e has a masking extent of n, where n is smaller than the representative width of e, if for every assignment it always evaluates to a value whose bits in position greater than or equal to n are 0. 00000001010100011 has a masking extent of 10. 11111000000101010 has a masking extent of 17. sign-extension extent: A target expression e has a sign-extension extent of n, where n is smaller than the representative width of e and greater than 0, if for every assignment it always evaluates to a value whose bits in position greater than or equal to n are equal to bit n-1. 00000001010100011 has a sign-extension extent of 11. 11111000000101010 has a sign-extension extent of 13. Note that we are using the convention that the least significant bit of a bit-string is in position O. Representations of integer expressions can be made faithful by applying value correcting operations which guarantee that the values evaluated by the expression are masked or sign-extended as required. We assume that the following two operations on target expression representations can be defined: a masking operation which takes an expression t and returns an expression t' such that, for every assignment, the significant bit-strings of t and t' are the same, and that t' has the masked property. a sign-extending operation which takes an expression t and returns an expression t' such that, for every assignment, the significant bit-strings of t and t' are the same, and that t' has the sign-extending property. Given an expression t, we use the notation m(t) and s(t) to represent the expression t applied to the masking operation and-the sign-extending operation, respectively. We also define the `make-faithful` operation f(t) which given an expression t returns m(t) if t is unsigned, and returns s(t) if t is signed. We assume that the evaluation of the target expressions represented by m(t) and s(t) may be more time/space expensive than the evaluation of the target expression represented by t and that, therefore, the translation of source integer expressions into target integer expressions should try to minimise the applications of these operations, rather than applying them naively to every sub-expression that is translated. In certain cases, the implementation of a value correcting operation can be such that the time/space cost of evaluating some particular expression is the same as the evaluation of the value corrected expression. This is certainly the case for an already value corrected expression, since the operation can simply return the original expression. It is also the case for a constant expression, since it can be value corrected by correcting the constant value directly and thus returning another constant expression (of the same cost). An expression t is easily masked if the evaluation of m(t) has the same cost as the evaluation of t. Similarly, an expression t is easily sign-extended if the evaluation of s(t) has the same cost as the evaluation of t. When translating integer expressions involving side-effect free relational operators (such as < and <=) which return a boolean value (this is a representation for the two truth values: true and false), it may not be necessary to apply a value correcting operation to the operands. Instead, it is enough to apply a usually cheaper monotonic operation on the operands which satisfies the following properties: op.sub.s (s.sub.1, . . . , s.sub.n) computes a boolean value representing true if and only if op.sub.T (mn(t.sub.1), . . . , mn(t.sub.n)) computes a boolean value representing true; op.sub.s (s.sub.1, . . . , s.sub.n) computes a boolean value representing false if and only if op.sub.T (mn(t.sub.1), . . . ,mn(t.sub.n)) computes a boolean value representing false; where mn(t) represents the monotonic operation applied to the target expression t, op.sub.s is an n-ary relational operation in the source language, op.sub.T is the corresponding n-ary relational operation in the target language, s.sub.1, . . . , s.sub.n are source expressions, and t.sub.i, . . . , t.sub.n are their corresponding (not necessarily value corrected) target expressions. Different relational operators may require different monotonic operations. Also, there can be several monotonic operations that are applicable to the same relational operator. We now describe the transformation of type correct source expressions into the internal representation of the target expressions. We first describe the general mechanism for translating a source expression into a target expression, and then give a concrete illustration of this process on a set of arithmetic expressions involving several C-style operators. The transformation of the source expressions into target expressions depends on the different operators in the source language. The method uses the following properties of the operators in the source language: Property 1 deals with the values of the unused bits of the result of the operation. In certain operations, such as +, - and *, the unused bits of the operands do not affect the significant bits of the result and the operands of such operands are not applied to the value correcting operations when the source expressions are translated into target expressions. If the unused bits of an operand can affect the significant bits of the result, then this particular operand needs to be value corrected, or, in the case of relational operations, all operands need to be applied to is a valid monotonic operation. Property 2 deals with the way the unused bits and significant bits of the operands affect the unused bits of the result of the operation. In certain operations, such as .Yen. and %, the value of the result is guaranteed to be faithful, and therefore the appropriate high-bit property can be set in the type information of the target expression. Basically, the method described here: uses an extended data structure representing the arithmetic or logic expression which includes the high-bit values of the expression. considers the above two properties to apply the value correcting functions to the operands of an operation only when this is required. These points illustrate that the present method differs from known methods in which the value-correcting functions are always applied to the result of the operation. For example, we can extend the data structure to include the masking and sign-extension extent of the expression, and from these properties the present method significantly reduces the number of value-correcting functions required during the translation. In the following we simply store the masked and sign-extended property in the data-structure of the expressions, and explain how these two properties are used effectively by the present method to generate efficient target expressions. If we consider the masking and sign-extension extent instead of the masked and sign-extended property, then the method will generate slightly more efficient expressions. For example, the sub-expressions of the following expression: (a.sub.(US) & 3.sub.(US))+1.sub.(US) have the following masking extents: a.sub.(US) &3.sub.(US) 2 1.sub.(US) 1 and, by using the property of the +operator that the masking extent of the result is 1 added to the maximum masking extent of its operands, then we deduce that the masking extent of the main expression it 1+2=3. We therefore know that the main expression is masked, and hence faithful. As a result it never needs to be value corrected. If, instead of keeping track of the masking extent, we simply keep track of the masked property, then from the fact that the above two sub-expressions have the masked property, we cannot deduce that the main expression is also masked. This means that the expression may need to be value corrected by adding an additional masking operation. Given a source expression representation e of width .omega., the target expression representation is constructed as follows: Step 1 A table associating high-bit properties with the variables in the source expression e is constructed. This table is called the high-bit property mapping and has the form:
High-bit
Variable properties
U.sub.0 P.sub.0
U.sub.0 P.sub.1
. .
. .
. .
U.sub.n P.sub.n
where U.sub.0 . . . U.sub.n, are all the variables in the source expression e, and P.sub.0 . . . P.sub.n are their corresponding high-bit properties which may be one of the followings masked, sign-extended, or none (that is three possible values). The high-bit properties combination where both the masked and the sign-extended properties are set is not allowed in this table. Several data structures can be used for the Internal representation of the high-bit property mapping and appropriate ones include association lists and sorted binary trees if the variables U.sub.0 . . . U.sub.n can be ordered. The high-bit property mapping does not affect the correctness of the translation mechanism and, for instance, one can use the trivial mapping which gives no high-bit properties to all variables. However one can develop heuristics which construct a high-bit property mapping depending on how (and how often) the variables are used in the source expressions, so that the target expressions constructed by this translation mechanism can be potentially more efficient. Step 2 the type information with the following data is constructed: the same sign as the source expression; the significant width .omega.; the representative width r is chosen to be the smallest native width larger than or equal to .omega.: no high-bit properties are set (for the moment). This type information is denoted by i.sub.e. The type information i.sub.e is constructed from the type of e. For example, given a signed 5-bit expression and assuming that the native bit-widths of the target machine are 16, 32, 48, etc., then the type information with the following data is constructed:
sign: signed
significant width 5
representative width 16
high-bit properties none
Again, several basic data structures can be used for the internal representation of the above type information. An appropriate one is a record structure with a boolean field for the sign, two integer fields for the significant and representative widths, and two boolean fields for the high-bit properties (one for the masked property and the other for the sign-extended property). Step 3 The internal representation of the target expression is constructed recursively and the appropriate high-bit properties fields in the type information are set. The base case of this recursive method is when the source expression a is an atomic expression; the recursive case is when the source expression a is a compound expression. base case: If e is an atomic expression, then a corresponding target atomic expression is constructed. 1. If e is a source constant expression e.sub.s, then the target constant expression <i.sub.t > e.sub.t, is constructed, where the value of the constant e.sub.t is such that its interpretation is the same as that of e.sub.s, and the type information i.sub.t is the type information i.sub.e (which was constructed in step 2 above) with the high-bit properties set according to the value of the unused bits in e.sub.t. 2. If e is a source variable expression, then a target variable expression is constructed. A unique target variable identifier is used for every source variable identifier. More formally, the mapping from source variable identifiers into target variable identifiers is a total injective mapping. The high-bit properties fields of the type information i.sub.s constructed in step 2 above are set according to the entry in the high-bit property mapping constructed in step 1. If the high-bit property mapping entry for the source variable is the masked property, then the masked field is set. Similarly, if the entry is the sign-extended property, then the sign-extended field is set. If the entry states that no high-bit properties are assigned to the source variable, then no high-bit properties in the type information i.sub.e are set. recursion A source compound expression op (e.sub.1, e.sub.2, . . . , e.sub.n) 31 as shown in FIG. 6 is transformed into a target expression as follows: 1. The source operands e.sub.1, e.sub.2, . . . , e.sub.n are first translated 32 into target expressions t.sub.1, t.sub.2, . . . , t.sub.n using this method recursively. 2. The target expression 24 is then constructed using the operations 33 of the target machine such that: The target sub-expressions used in an arithmetic operation are applied to the masking operation or the sign-extending operation if the values in the unused bits of the operands can affect the values of the significant bits of the result of the operation. In the case of relational operations which simply compare the value of two or more expression (such as <), then it is usually enough to apply a monotonic operation which uses the value of the significant bit-string only and returns a value which uses all the bits in the target integer value. An efficient example of this is the operation which, given an expression e, returns a <<(r-v), where <<is the left-shift operator, and r and w are the representative and significant widths of e. When different operations (masking, sign-extending, monotonic operations) can be used on the internal representation of the target operands, then the operation which results in the cheapest target expression is chosen. The type information i.sub.t of the target expression is constructed from the type information i.sub.s (step 2 above) by setting the masked high-bit property when it can be guaranteed that the value of the operation is always masked: and similarly, the sign-extended high-bit property is set when it can be guaranteed that the value of the operation is always sign-extended. This step depends on the second property of the arithmetic operator concerned as described hereinbefore. Again, there are several data structures which can be used to represent the target expression internally. An appropriate one is a tree structure where the leaf nodes represent atomic expressions and the non-leaf nodes represent operators. Finally, as shown in FIGS. 3 and 5, the data representing the type information is stripped from the final Internal representation of the target expression. In the following example, it is assumed that the source and target languages contain constants, variables and compound expressions involving the following operators: The unary operators: !, .about. and - whose semantics are the same as their respective C unary operators as given in with the typing rule that the type of the operand of these operators should be the same as the type of the value of the operation. The binary infix operators: +, -, *, /, %, .vertline., , &&, .vertline..vertline., ==, !=, <=, >=, <, >, <<, >>, >>,, and =, whose semantics are the same as their respective C binary operators with the exception that for simplicity shifts (<< and >>) by values greater than the bit-width of their first operand are undefined. We also assume the following typing rules: 1. the operands of all the operators with the exception of = =, !=, <=, >=, <, >, <<, >>and, have the same type as that of the value they return; 2. the operands of the relational operators ==, !=, <=, >=, < and >have the same type; 3. the first operands of << and >>have the same type as the value they return; the second operands of << and >>are unsigned; 4. the second operand of , has the same type as the value it returns. Conditionals of the form: e.sub.1 ?e.sub.2 :e.sub.3 whose semantics is the same as C conditional expressions. We assume that the operands e; and e, have the same type as the value returned by the conditional expression. Typecasts of the form: (type) e.sub.1 where type has the form signed w or unsigned w which gives a new sign (sign or unsigned) and width (w) to the operand e.sub.1. The value of this operation is sign-extended automatically if the operand e.sub.1 is signed and narrower than w. Given the above operators, simple masking and sign-extending operations can be implemented as follows: masking Given an expression <i.sub.t >t, if the type information i.sub.t has the masked property, then this operation simply returns <i.sub.t >t. Otherwise, if the significant width of the expression is w, and its representative width is r, then we are required to mask the value of the expression with the bit integer whose lowest w bits are 1 and whose highest r-w bits are 0. Let us call this integer m. The type information i.sub.m associated with m has the same sign as i.sub.t, the significant width r and the representative width r. The required expression is therefore: <i'.sub.t >(<i.sub.t > & <i.sub.m >m) where i'.sub.t is the type information resulting from setting the masked property to i.sub.t and unsetting its sign-extended property. Given an expression e, we denote the application of the masking operation by m(e). sign extending Given an expression<i.sub.t >t, if the type information i, has the sign-extended property then this operation simply returns <i.sub.t >t. Otherwise if the significant width of the expression is w, and its representative width is r, then we can sign-extend the value of t by left-shifting by r-w places, and then applying an arithmetic right-shift by r-w places. (Note that an arithmetic right-shift preserves the highest bit of its operand.) Let us denote the constant r-w by u. The type information i.sub.u associated with u is unsigned, has the significant width r and the representative width r. If i.sub.t is signed, then the required expression is: <i".sub.t >((<i'.sub.t >(<i.sub.t >t<< <i.sub.u >u)) >> <i.sub.u >u) where i'.sub.t is the type information i.sub.t made precise by setting the significant field to r, and i".sub.t is the type information constructed from i.sub.t by setting the sign-extended high-bit property, and unsetting the masked property. If i.sub.t is unsigned, then the sub-expression: (<i'.sub.t >(<i.sub.t >t << <i.sub.u >U)) is type cast by signed r before it is right-shifted (in order to achieve an arithmetic right-shift, rather than a logical one), and the final expression is then type cast by unsigned r to retain its sign. Given an expression e, we denote the application of the sign-extending operation by m(e). We recall the definition of f(e) as m(s) if the expression e is unsigned, otherwise as s(e) if e is signed. We also define the following monotonic operation required during the translation of the relational operations involving ==, !=, <, <=, > and >=: monotonic operation Given an expression <i.sub.t >t with significant width w and representative width r, this operation returns: <i'.sub.t >(<i.sub.t>t<<<i.sub.u>u) where u to r-W, and the type information i'.sub.t has the same sign as i.sub.t, the significant width r and representative width r. The type information i.sub.u is unsigned, has the significant width r and representative width r. Given an expression e, we denote the application of this monotonic operation by mn(e). More efficient implementations of the masking, sign-extending and the above monotonic operations are possible, although the above implementations are sufficient for the correctness of the translation mechanism described herein. Such more efficient implementations use the technique of applying optimising transformations to improve the efficiency of the expressions. The following are transformations that can be applied on the operations: A masked operation e of the form t and m an be optimised as follows: If t is a constant k, then the value of e is calculated to say, 1, and e is replaced by 1. If t in of the form x & k or k & x where k is a constant, then the value of k and m is calculated to say, 1, and e is replaced by t & 1. If t Is of the form x & y where either (or both) x & m or y & m can be optimised to say, x' and y', then e is replaced by x' & y'. Similar rules apply for operations of the form x .vertline. y, x .sup..about. y, z ? x : Y. A sign-extended operation e of the form (t<<u)>>u can be optimised as follows: If t Is a constant k, then the value of e is calculated to say, 1, and e is replaced by 1. If t is of the form x<<k where k is a constant, then the value of k+u is calculated to say, 1, and e is replaced by (t<<1)>>u. If t is of the form x & y where either (or both) (x<<u)>>u or (y<<u)>>u can be optimised to say, x' and y', then e is replaced by x' y' Similar rules apply for operations of the form x .vertline. y, x .sup..about. y, z ? x : y. A monotonic operation e of the form t<<u can be optimised as follows: If t is a constant k, then the value of e is calculated to say, 1, and e is replaced by 1. If t Is of the form x<<k where k is a constant, then the value of k+u is calculated to say, 1, and e is replaced by t<<1. If t is of the form x & y where either (or both) x<<u or y<<u can be optimised to say, x' and y', then e is replaced by x' & y'. Similar rules apply for operations of the form x .vertline. y, x .sup..about. y, z ? x : y. We may sometimes require to choose the most efficient expression from a number of expressions. Given a number of expressions e.sub.1, . . . , e.sub.n, we use the term t"the cheapest of e.sub.1, . . . , e.sub.n " to denote the expression in e.sub.1, . . . , e.sub.n that is likely to be computed most efficiently. We also define this term on pairs of expressions: "the cheapest of (e.sub.1, e'.sub.1), . . . , (e.sub.n. e '.sub.n)" is the pair of expressions in (e.sub.1, e'.sub.1), . . . (e.sub.n, e'.sub.n) such that the computation of e followed by that of e' is likely to be the most efficient. A good measure of the efficiency of a target expression is the number of operators in its internal representation: the cheapest expression is the one with the least number of operators. We say that some type information 1.sub.1 to the type information i.sub.2 made faithful if i.sub.1 is constructed from i.sub.2 by setting the masked high-bit property if i.sub.2 is unsigned, and by setting the sign-extended high-bit property if i.sub.2 is signed. We now describe the method for translating source expressions Into target expressions: Constants and variables in the source language are transformed into target constants and variables as explained earlier. Given a unary operation e of the form: op (e.sub.1) we first construct the type information i.sub.t from the type of e (i.sub.t has no high-bit properties), and then transform the operand e.sub.1 recursively into t.sub.1. The expression t.sub.1 is annotated with its typing information since it is represented by the internal representation described hereinbefore. The requited target expression: <i'.sub.t >op(t'.sub.1) is then constructed, where if the operator op is: !1: the expression t'.sub.1 needs to be masked or sign-extended since the value of the unused bits of t.sub.1 may affect the significant bit-string in the result of the ! operation. Therefore the expressions m(t.sub.1) and (t.sub.1) are constructed and t'.sub.t is chosen to be the cheaper of the two. The type information i'.sub.t is the type information i.sub.t made faithful. the required operand t'.sub.1 is simply t.sub.1 since the unused bits in t.sub.1 do not affect the significant bit-string in the result of the .about. operation. The type information i'.sub.t is constructed from i.sub.t by setting the sign-extended property if and only if t, is sign-extended. the required operand t'.sub.1 is t.sub.1 and the type information i'.sub.t is i.sub.t since the value of the arithmetic negation operation--cannot be guaranteed to be always masked and/or sign-extended. Given a binary operation e of the form: e.sub.1 op e.sub.2 we first construct the type information i.sub.t from the type of e, and transform the operands e.sub.1 and e.sub.2 into t.sub.1 and t.sub.2, respectively. The required target expression is: <i'.sub.t >(t'.sub.1 op t'.sub.2) where if the operator op is: +, -, *: the operands t'.sub.1 and t'.sub.2 are t.sub.1 and t.sub.2, respectively. The type information i'.sub.t is i.sub.t. /, % : the operands t'.sub.1 and t'.sub.2 are f(t.sub.1) and f(t.sub.2). The type information i'.sub.t is i.sub.t made faithful. &&, .vertline..vertline.: the operand t'.sub.1 is the cheapest of m(t.sub.1), s(t.sub.2); and the operand t'.sub.2 is the cheapest of m(t.sub.2), s(t.sub.2). The type information i'.sub.t is i.sub.t made faithful. & : the operands t'.sub.1 and t'.sub.2 are t.sub.1 and t.sub.2. The type information i'.sub.t is constructed from i.sub.t by setting the masked property if either t.sub.1 or t.sub.2 masked, and then setting the sign-extended property if both t.sub.1 and t.sub.2 are sign-extended. .vertline., .sup..about. :the operands t'.sub.1 and t'.sub.2 are t.sub.1 and t.sub.2. The type information i'.sub.t is constructed from i.sub.t by setting the masked property if both t.sub.1 and t.sub.2 are masked, and then setting the sign-extended property if both t.sub.1 and t.sub.2 are sign-extended. ==, 1=: the pair of operands (t'.sub.1, t'.sub.2) is the cheapest of (m(t.sub.1), m(t.sub.2)), (s(t.sub.1), s(t.sub.2)), (mn(t.sub.1), mn(t.sub.2)). The type information i'.sub.t is i.sub.t made faithful. <=,>=, <, > : the pair of operands (t'.sub.1, t'.sub.1) is the cheapest of (f(t.sub.1),f(t.sub.2)), (mn(t.sub.1), mn(t.sub.2)). The type information i.sub.t is i.sub.t made faithful. << : the first operand t'.sub.1 is the expression t.sub.1, and the second operand t'.sub.2 is f(t.sub.2). The type information i'.sub.t is i.sub.t. >> : the operands t'.sub.1 and t'.sub.2 are f(t.sub.1) and f(t.sub.2), respectively. The type information i'.sub.t is i.sub.t made faithful. = : the first operand t'.sub.1 is simply the expression t.sub.1. The second operand t'.sub.2 is m(t.sub.2) if t'.sub.1 is masked, s(t.sub.2) if t'.sub.1 is sign-extended, or otherwise it is t.sub.2. The type information i'.sub.t is constructed from se by setting the masked property it t'.sub.2 is masked, and then setting the sign-extended property if t'.sub.2 is sign-extended. , : the operands t'.sub.1 and t'.sub.2 are t.sub.1 and t.sub.2. The type information i'.sub.t is constructed from i.sub.t by setting the masked property if t.sub.2 is masked, and then setting the sign-extended property if t.sub.2 is sign-extended. Given a conditional expression e of the form: e.sub.1 ? e.sub.2 : e.sub.3 we first construct the type information i.sub.t from the type of e, and then transform the operands e.sub.1, e.sub.2 and e.sub.3 into t.sub.1 t.sub.2 and t.sub.3, respectively. The required target expression is: <i'.sub.t > (t'.sub.1 ? t.sub.2 : t.sub.3) where t'.sub.1 is the cheapest of m(t.sub.1), s(t.sub.1). The type information i'.sub.t is constructed from i.sub.t by setting the masked property if both t.sub.2 and t.sub.3 are masked and then setting the sign-extended property if both t.sub.2 and t.sub.3 are sign-extended. A type cast expression e of the form: (type.sub.s) e.sub.1 is transformed into the required target expression as shown below: 1. The type information i.sub.t is constructed from the type type.sub.s. Let us define s.sub.t and r.sub.t as the significant width and representative width in I.sub.t, respectively. Let us define type.sub.s as the type of the required target expression; that is, type.sub.t has width r.sub.t and the sign of type.sub.s. 2. The operand e.sub.1 is transformed into the expression t.sub.1. Let us define s.sub.1 and r.sub.1 as the significant width and representative width of t.sub.1, respectively. 3. If s.sub.t the same as s.sub.1, then the target expression is: <i.sub.t.sup.(t1) >(type.sub.t)t.sub.1 where i.sub.t.sup.(t1) is constructed from i.sub.t by setting the masked property if t.sub.1 is masked and then setting the sign-extending property if t.sub.1 is sign-extended. 4. If s.sub.t is smaller than s.sub.1 then the required target expression is: <i.sub.t > (type.sub.t)t.sub.1 5. If s.sub.t is greater than s.sub.1 then: (a) If r.sub.t is the same as r.sub.1 then the target expression is: <i.sub.t.sup.(f(t1)) > (type.sub.t)f(t.sub.1) The type information i.sub.t.sup.(f(t1)) is constructed from i.sub.t by setting the masked property if f(t.sub.1) is masked, and then setting the sign-extending property if f(t.sub.1) is sign-extended. This does not make the type information i.sub.t.sup.(f(t1)) faithful since the sign of f(t.sub.1) may be different from that in type.sub.t. (b) If r.sub.t is greater than r.sub.1 then the target expression is: <i'.sub.t <(type.sub.t)f(t.sub.1) where i' is i.sub.t made faithful We now illustrate this method by translating the following source expression ((a.sub.(US) +b.sub.(US))*c.sub.(US)) /d .sub.(US) +e.sub.(US)) into a target expression that can be simulated by a 16 bit architecture. The given source expression is already type correct. Step 1: The trivial high-bit property mapping is constructed which associates every variable in the source expression with the "no high-bit properties" entry. Step 2: The type information data structure is constructed. Since the type of the source expression is unsigned5 and the target architecture is a 16-bit one, the following type information is constructed
sign: unsigned
significant width: 5
Representative width: 16
High-bit properties none
Since all sub-expressions in the given source expression have the same type, then the above data is constructed for each sub-expression during the recursive part of this method. In the following we use the notation: <high-bit properties>expession to denote a given target expression annotated with some particular high-bit properties. Step 3:The target source expression is constructed recursively as follows: 1. From the source expression s: ((a.sub.(US) +b.sub.(US) b.sub.(US))/(d.sub.(US) +e.sub.(US)) the two operands: s.sub.o =((a.sub.(US) +b.sub.(US))*c.sub.(US)) s.sub.1 =(d.sub.(US) =e.sub.(US)) are translated recursively into t.sub.o and t.sub.1 as follows: (a) From the source expression s.sub.o, the two operands: s.sub.00 =a.sub.(US) +b.sub.(US) s.sub.01 =c.sub.(US) are translated recursively into t.sub.00 and t.sub.01 as follows: i. From the source expression s.sub.00 =a.sub.(US) s.sub.000 =b.sub.(US) are translated recursively into t.sub.000 and t.sub.000 by simply constructing a unique target variable for each source variable and thus giving: s.sub.000 =<none>a.sub.(US) s.sub.000 =<none>b.sub.(US) The high-bit property mapping constructed in step 2 does not assign any high-bit properties to the above variables, and therefore none are set. ii. Since the operator concerned in s.sub.00 is +, then no value correcting operators need to be applied on the two operands t.sub.000 and t.sub.001 and therefore the following target expression t.sub.00 is constructed: t.sub.00 =<none>a.sub.(U16) +b.sub.(U16) No high-bit properties can be guaranteed and therefore none are set. iii. The source expression s.sub.01 is translated recursively into t.sub.01 by simply constructing a unique target variable for the source variable and thus giving: t.sub.01 =<none>c.sub.(U16) The high-bit property mapping constructed in step 2 does not assign any high-bit properties to the above variable, and therefore none are set. (b) Since the operator concerned in s.sub.0 is *, then no value correcting operators need to be applied on the two operands t.sub.00 and t.sub.01 and therefore the following target expression to it constructed: t.sub.0 =<none>((a.sub.(U16) +b.sub.(U16))*c.sub.U16)) No high-bit properties can be guaranteed and therefore none are set. (c) From the source expression s.sub.1, the two operands: s.sub.10 =d.sub.(US) s.sub.11 =e.sub.(US) are translated recursively into t.sub.10 and t.sub.11 by simply constructing a unique target variable for each source variable and thus giving: t.sub.10 =<none>d.sub.(US) t.sub.11 =<none>e.sub.(U16) The high-bit property mapping constructed in step 2 does not assign any high-bit properties to the above variables, and therefore none are set. (d) Since the operator concerned in s.sub.1 is +, then no value correcting operators need to be applied on the two operands t.sub.10 and t.sub.11 and therefore the following target expression t.sub.10 is constructed: t.sub.1 =<none>(d.sub.(US) +c.sub.(US)) No high-bit properties can be guaranteed and therefore none are set. 2. Since the operator concerned in s is /, then the target expressions t.sub.0 and t.sub.1 are applied to the masking value correcting operation giving: t'.sub.0 =<masked>((a.sub.(U16) +b.sub.(U16))*c.sub.(U16)) & 31.sub.(U16) t'.sub.1 =<masked>(d.sub.(U16) +e.sub.(U16)) & 31.sub.(U16) and the target expression t=<none> (((a.sub.(U16) +b.sub.(U16)) * c.sub.(U16)) & 31.sub.(U16))/ ((d.sub.(u16) +e.sub.(U16)) & 31.sub.(U16)) is constructed. Since the masked property can be guaranteed in the result of the unsigned operation, then the masked high-bit property of is set giving the following final internal representation of t the target expression: <masked> (((a.sub.(U16) +b.sub.(U16))*c.sub.(U16)) & 31.sub.(U16))/ ((d.sub.(u16) +e.sub.(U16)) & 31.sub.(U16)) The last stage is to strip the additional type information from the above expression, thus giving: (((a.sub.(U16) +b.sub.(U16)) *c.sub.(U16)) & 31.sub.(U16))/ ((d.sub.(u16) +e.sub.(U16)) & 31.sub.(U16)) This technique may be used in the efficient simulation of high-level descriptions of arithmetic circuits on a specified target machine. FIG. 7 illustrates an example of a Bach hardware design flow in which hardware is described in the Bach high-level language. The hardware description is implemented at 40 and results in Bach source code. A step 41 simulates the Bach hardware description and makes use of the method described hereinbefore to provide a translation of operations or expressions which are to be implemented in the arithmetic and/or logic circuits of the target machine. The simulation result is checked for correctness at 42. If incorrect, a fresh implementation is performed in the step 40. If the simulation result is correct, a stop 43 generates a low-level hardware description which is then converted using known or appropriate techniques to a silicon chip 44.
|
Same subclass Same class Consider this |
||||||||||