Número de Ershov

Los números de Ershov , llamados así por Andrey Petrovich Yershov , ^[1] se utilizan en la optimización de código para minimizar la cantidad de asignaciones de registros . Los números de Ershov se pueden utilizar en métodos para seleccionar registros de manera óptima cuando solo hay una expresión en un bloque de código. Dada una expresión E = E ₁ op E ₂ el objetivo es generar código de manera que se minimice la cantidad de registros utilizados o, si no hay una cantidad suficiente de registros disponibles, se minimice la cantidad de registros temporales que no sean registros necesarios.

Definición

El número de Ershov n de un nodo en un árbol de expresión dado se define de la siguiente manera: ^{[2] [3]}

1. Cada hoja tiene n = 1.
2. Para un nodo con un hijo, n es igual al del hijo.
3. Para un nodo con dos hijos, n se define como:

${\displaystyle n={\begin{cases}max(child_{1},child_{2})&child_{1}\neq child_{2}\\child_{1}+1&child_{1}=child_{2}\end{cases}}}$

El número de Ershov de un nodo representa la cantidad mínima de registros necesarios para evaluar la subexpresión cuya raíz es ese nodo. La idea es que primero evaluemos el hijo con el número de Ershov más grande, luego el otro hijo y luego realicemos la operación en la raíz.

Ejemplo

Supongamos que tenemos un árbol de expresión con una operación '+' en la raíz, y los subárboles izquierdo y derecho tienen números de Ershov de 3 y 4, respectivamente. El número de Ershov de este nodo es 4, por lo que deberíamos poder generar código para la expresión utilizando 4 registros.

1. Generar código para evaluar el hijo correcto utilizando los registros r1, r2, r3 y r4. Colocar el resultado en r1.
2. Generar código para evaluar el hijo izquierdo utilizando los registros r2, r3 y r4. Colocar el resultado en r2.
3. Emita la instrucción ADD r1, r1, r2, que suma r1 y r2 y almacena el resultado en r1.

Generación de código

El procedimiento general para generar código utilizando un número mínimo de cargas y almacenamientos desde la memoria es el siguiente:

1. Genere primero el código para el niño con el número de Ershov más grande
2. Emitir una instrucción para almacenar el resultado en un registro temporal o, si no hay ninguno disponible, en una ubicación temporal en la memoria.
3. Generar código para el niño con el número de Ershov más pequeño
4. Emitir una instrucción para cargar la variable temporal nuevamente en un registro
5. Emitir una instrucción para realizar la operación en la raíz

En el caso ideal, si hay n registros y la primera subexpresión requiere n registros y la siguiente subexpresión requiere n - 1 registros, se puede usar un solo registro para almacenar el resultado de la primera expresión, y todavía habrá n - 1 registros disponibles para calcular la siguiente subexpresión, por lo que no se requieren cargas ni almacenamientos desde la memoria en absoluto. ^[1]

Si el número de Ershov de la raíz del árbol de expresión es mayor que el número de registros disponibles, el número de Ershov también se puede utilizar para determinar la cantidad de espacio de memoria temporal adicional requerido, por ejemplo en la pila . ^[1]

Véase también

• Número de Strahler , el número mínimo de registros necesarios para evaluar una expresión sin ningún almacenamiento externo
• Algoritmo de Sethi-Ullman , básicamente el mismo concepto

Referencias

1. "Notas sobre la generación de código" (PDF) . Departamento de Ciencias de la Computación, Universidad de Calgary. 14 de septiembre de 2007. Consultado el 30 de mayo de 2022 .
2. "Generación óptima de código (para expresiones) y análisis de flujo de datos" (PDF) . Carleton University . Consultado el 30 de mayo de 2022 .
3. "Generación de código, capítulo 8" (PDF) . Western Michigan University . Consultado el 30 de mayo de 2022 .