Ershove Number

Ershov numbers are required in the field of computer science in the allocation of registers. You specify the number of registers that are needed for the evaluation of an expression.

The algorithm

The process can be associated with the register of the evaluation of arithmetic expressions, first calculates an arithmetic expression for a number Ershov ( a) of the registers that are required to evaluate the expression. It is named after the Russian computer scientist H. P. Ershov named, who has published the idea of the process. The method specifies a function of the form: Ershov: Expr → ℕ indicating a given arithmetic expression a is the number required for the evaluation of the register. For this purpose, a case distinction is necessary:

Constant

To evaluate a constant, a register is exactly needed. Accordingly, the following applies: Ershov (c) = 1

Variable

To evaluate a variable only one register is also required: Ershov (v) = 1

Unary expression

For the evaluation of a unary operator to an expression a, the number of registers that is needed is that a need, because the result of a register can be overwritten easily. Ershov (OP a) = Ershov ( a)

Binary expression

In the evaluation of a binary expression of the form a1 a2 OP three cases are further subdivided into:

Case I: Ershov (a1) < Ershov (a2)

In this case, A2 is evaluated, wherein Ershov (a2) registers are required. The result is now stored for example in Rx. The remaining registers are no longer required for a2, making them available for the calculation of a1 available. Accordingly, the following applies:

Ershov (a1) < Ershov (A2) → Ershov (a1 a2 OP ) = Ershov (a2)

Case II: Ershov (a1 ) = Ershov (a2 )

In this case register is required for the calculation of a1 Ershov (a1). Suppose this n registers were needed then is in register Rn, the result of a1. For the calculation of a2 n-1 unneeded registers are now available. But as required according to this case for the calculation of n registers a2 also applies:

Ershov (a1 ) = Ershov (A2) → Ershov (a1 a2 OP ) = Ershov (a1 ) 1

Case III: Ershov (a1) > Ershov (a2)

The reasoning is similar to Case I: Ershov (a1) > Ershov (A2) → Ershov (a1 a2 OP ) = Ershov (a1)

Function call

Since the results of a function call: f (a1, ..., an) are already written to the stack, it is not necessary, the result also to be stored in a register. From the same argument as in Case I for binary expressions follows: Ershov (f ( a1, ..., an) ) = max ( Ershov (a1 ), ..., Ershov ( in ) )

• Compiler