I’m reading Muchnick’s “Advanced Compiler Design & Implementation”, where Fig 12.6 lists 20 transformation rules which, if applied in order, do constant folding and reassociation to move constants together. The rules (leaving out distributitvity rules) are (my syntax: c are literals, t terms, operators with spaces around are in in the source, whereas operators without spaces indicate a compile-time calculation involving literals):
R1: c1 + c2 = c1+c2 R3: c1 * c2 = c1*c2 R5: c1 - c2 = c1-c2 R2: t + c = c + t R4: t * c = c * t R6: t - c = (-c) + t R7: t1 + (t2 + t3) = (t1 + t2) + t3 R8: t1 * (t2 * t3) = (t1 * t2) * t3 R9: (c1 + t) + c2 = (c1+c2) + t R10: (c1 * t) * c2 = (c1*c2) * t
He writes “recursively apply the tree transformation rules [..] in the order given“, but I fail to see how that works out. Given ((c1 + t1) + t2) + c2, how would I have to apply the rules to get to (c1+c2 + t1) + t2 or something similar?
(I could come up with a different set of rules that would work, but I’d like to understand what’s in the book, in case I’m just reading it wrong).
I don't have the book, but I'll give it a try. Starting expression:
((c1 + t1) + t2) + c2
Apply R2:
c2 + ((c1 + t1) + t2)
The recursive application of the rules on the sub-expression on the right doesn't yield any matches. Continue by applying R7 on the whole expression (literals are also terms):
(c2 + (c1 + t1)) + t2
Recursion. Apply R7 on the left sub-expression.
(c2 + c1) + t1
Recursion. Apply R1 on the left sub-expression:
c2+c1
Final result: (c2+c1 + t1) + t2