Числа Ершова , названные в честь Андрея Петровича Ершова , [1] используются в оптимизации кода для минимизации количества выделений регистров . Числа Ершова можно использовать в методах оптимального выбора регистров, когда в блоке кода имеется только одно выражение. Учитывая выражение E = E 1 op E 2 , цель состоит в том, чтобы сгенерировать код, чтобы либо минимизировать количество используемых регистров, либо, если доступно недостаточное количество регистров, минимизировать количество требуемых нерегистровых временных объектов.
Число Ершова узла представляет собой минимальное количество регистров, необходимых для вычисления подвыражения, корнем которого является этот узел. Идея состоит в том, что сначала мы оцениваем дочерний элемент с большим числом Ершова, затем другой дочерний элемент, а затем выполняем операцию над корнем.
Предположим, у нас есть дерево выражений с операцией '+' в корне, а левое и правое поддеревья имеют числа Ершова 3 и 4 соответственно. Число Ершова этого узла равно 4, поэтому мы должны иметь возможность генерировать код для выражения, используя 4 регистра.
Общая процедура генерации кода с использованием минимального количества загрузок и сохранений из памяти выглядит следующим образом:
В идеальном случае, если есть n регистров и для первого подвыражения требуется n регистров, а для следующего подвыражения требуется n - 1 регистров, для хранения результата первого выражения можно использовать один регистр, и все равно будет n - 1 регистры, доступные для вычисления следующего подвыражения, поэтому вообще не требуют загрузки или сохранения из памяти. [1]
Если число Ершова корня дерева выражений больше числа доступных регистров, число Ершова также можно использовать для определения объема требуемого дополнительного пространства временной памяти, например, в стеке . [1]