Content deleted Content added
Change the example, for making it correctly. |
No edit summary |
||
Line 43:
/ \ / \
/ \ d<sub>'''1'''</sub> 3<sub>'''0'''</sub>
+<sub>'''1'''</sub> *<sub>'''1'''</sub>
/ \ / \
b<sub>'''1'''</sub> c<sub>'''0'''</sub> f<sub>'''1'''</sub> g<sub>'''0'''</sub>
From this tree it can be seen that we need 2 registers to compute the left subtree of the '*', but only 1 register to compute the right subtree.The reason of 'c' and 'g' do not need register is:If T is a tree leaf, then the number of registers to evaluate T is either 1 or 0 depending whether T is a left or a right subtree(since an operation such as add R1, A can handle the right component A directly without storing it into a register). Therefore we shall start to emit code for the left subtree first, because we might run into the situation that we only have 2 registers left to compute the whole expression. If we now computed the right subtree first (which needs only 1 register), we would then need a register to hold the result of the right subtree while computing the left subtree (which would still need 2 registers), therefore needing 3 registers concurrently. Computing the left subtree first needs 2 registers, but the result can be stored in 1, and since the right subtree needs only 1 register to compute, the evaluation of the expression can do with only 2 registers left.
| |||