Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Ershov Number
open-in-new
<h2 id="definition">Definition</h2> <p>The Ershov number n {\displaystyle n} of a node in a given <a href="/facts/Expression_tree/HqbKYU43">expression tree</a> is defined as follows:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <ol><li>Every leaf has n = 1 {\displaystyle n=1} .</li> <li>For a node with one child, n {\displaystyle n} is the same as the child's.</li> <li>For a node with two children with Ershov numbers n 1 {\displaystyle n_{1}} and n 2 {\displaystyle n_{2}} , n {\displaystyle n} is defined as:</li></ol> n = { max ( n 1 , n 2 ) if n 1 ≠ n 2 , n 1 + 1 if n 1 = n 2 . {\displaystyle n={\begin{cases}\max(n_{1},n_{2})&{\text{if }}n_{1}\neq n_{2},\\n_{1}+1&{\text{if }}n_{1}=n_{2}.\end{cases}}} <p>The Ershov number of a <a href="/facts/Node_(graph_theory)/WhlWmL3o">node</a> represents the minimum number of registers required to evaluate the subexpression whose root is that node. The idea is that we evaluate the child with the larger Ershov number first, then the other child, then perform the operation at the root. </p> <h2 id="example">Example</h2> <p>Suppose we have an expression tree with a '+' operation at the root, and the left and right <a href="/facts/Subtree/RcXz9noF">subtrees</a> have Ershov numbers of 3 and 4, respectively. The Ershov number of this node is 4, so we should be able to generate code for the expression using 4 registers. </p> <ol><li>Generate code to evaluate the right child using registers r1, r2, r3, and r4. Place the result in r1.</li> <li>Generate code to evaluate the left child using registers r2, r3, and r4. Place the result in r2.</li> <li>Issue the instruction ADD r1, r1, r2, which adds r1 and r2 and stores the result in r1.</li></ol> <h2 id="code-generation">Code generation</h2> <p>The general procedure for generating code using a minimal number of loads and stores from memory is as follows: </p> <ol><li>Generate code for the child with the largest Ershov number first</li> <li>Issue an instruction to store the result in a temporary register, or, if none is available, a temporary location in memory</li> <li>Generate code for the child with the smaller Ershov number</li> <li>Issue an instruction to load the temporary variable back into a register</li> <li>Issue an instruction to perform the operation at the root</li></ol> <p>In the ideal case, if there are <i>n</i> registers and the first subexpression requires <i>n</i> registers and the next subexpression requires <i>n - 1</i> registers, a single register can be used to store the result of the first expression, and there will still be <i>n - 1</i> registers available to compute the next subexpression, therefore requiring no loads or stores from memory at all.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p><p>If the Ershov number of the root of the expression tree is greater than the number of registers available, the Ershov number can also be used to determine the amount of additional temporary memory space required, for example on the <a href="/facts/Stack-based_memory_allocation/Wem3dQa6">stack</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Strahler_number/NvIPLc2u">Strahler number</a>, the minimum number of registers needed to evaluate an expression without any external storage</li> <li><a href="/facts/Sethi%25E2%2580%2593Ullman_algorithm/L56k6Mh4">Sethi–Ullman algorithm</a>, basically the same concept</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Notes on Code generation" (PDF). Department of Computer Science, University of Calgary. 14 September 2007. Retrieved 30 May 2022. <a href="https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf" target="_blank">https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Optimal Code Generation (for Expressions) and Data-Flow Analysis" (PDF). Carleton University. Retrieved 30 May 2022. <a href="http://cglab.ca/~morin/teaching/3002/notes/dataflow.pdf" target="_blank">http://cglab.ca/~morin/teaching/3002/notes/dataflow.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>"Code Generation, Chapter 8" (PDF). Western Michigan University. Retrieved 30 May 2022. <a href="https://cs.wmich.edu/~zijiang/CS5810/Chap8.pdf" target="_blank">https://cs.wmich.edu/~zijiang/CS5810/Chap8.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>"Notes on Code generation" (PDF). Department of Computer Science, University of Calgary. 14 September 2007. Retrieved 30 May 2022. <a href="https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf" target="_blank">https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>"Notes on Code generation" (PDF). Department of Computer Science, University of Calgary. 14 September 2007. Retrieved 30 May 2022. <a href="https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf" target="_blank">https://pages.cpsc.ucalgary.ca/~robin/class/510/cg-expressions.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> </ol>