Content deleted Content added
Change the example, for making it correctly. |
|||
Line 11:
===Example===
For an arithmetic expression <math>a = (b + c+ f * g) * (d + 3)</math>, the [[abstract syntax tree]] looks like this:
=
Line 20:
+ +
/ \ / \
+ *
/ \ / \
To continue with the algorithm, we need only to examine the arithmetic expression <math>(b + c) * (d + 3)</math>, i.e. we only have to look at the right subtree of the assignment '=':▼
b c f g
▲To continue with the algorithm, we need only to examine the arithmetic expression <math>(b + c + f * g) * (d + 3)</math>, i.e. we only have to look at the right subtree of the assignment '=':
*
Line 29 ⟶ 31:
+ +
/ \ / \
+ *
/ \ / \
Now we start traversing the tree (in preorder for now), assigning the number of registers needed to evaluate each subtree (note that the last summand in the expression <math>(b + c) * (d + 3)</math> is a constant):▼
b c f g
▲Now we start traversing the tree (in preorder for now), assigning the number of registers needed to evaluate each subtree (note that the last summand in the expression <math>(b + c + f * g) * (d + 3)</math> is a constant):
*<sub>'''2'''</sub>
Line 38 ⟶ 42:
+<sub>'''2'''</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.
==Advanced Sethi-Ullman algorithm==
| |||