CODEWITHSUNDEEP
optimizationcompiler-constructionprogram-transformation
Joachim Breitner
Joachim Breitner

Reputation: 25763

Reassociation according to Muchnick

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).

Upvotes: 4

Views: 1477

Answers (1)

thomie
thomie

Reputation: 1434

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

Upvotes: 6

Related Questions