🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Lazy expression evaluation

Started by
0 comments, last by Muzzafarath 24 years, 2 months ago
I''ve been reading the "Let''s build a compiler!" tutorials by Jack Crenshaw since I''m building my own compiler Anyway, in chapter 4 he mentions something called "lazy expression evaluation" that will produce much faster code. Where could I find information about this "lazy expression evaluation"? It takes 18 (assembler) instructions to do this: x = x + 3 - 2 - (5 - 4) But in fact "x = x + 3 - 2 - (5 - 4)" doesn''t NOTHING to x. Let''s "scale down" the expression: x = x + 3 - 2 - (5 - 4) = x = x + 3 - 2 - 1 = x = x + 3 - 3 = x = x + 0 = x = x = nothing As you see "x = x + 3 - 2 - (5 - 4)" is just a more complicated way to write nothing Using lazy expression evaluation could greatly optimize the code that my compiler produces. It seems to be really hard to do this kind of thing, but I''d like to learn more about it. So where could I find more info about it? /. Muzzafarath
I'm reminded of the day my daughter came in, looked over my shoulder at some Perl 4 code, and said, "What is that, swearing?" - Larry Wall
Advertisement
There''s always the Dragon book. (Aho, Sethi and Ullman "Compilers Principles, Techniques and Tools" ISBN 0-201-10088-6 (This is the second edition, the first edition was just Aho and Ullman (And the scary thing is that I recommend this book so often, I have the ISBN memorized)))

And depending on your language features and the binding of variable x, x = x + 3 - 2 - (5 - 4) is just an ugly way to write x = x, which is not the same as nothing. (Memory mapped i/o, binding x to ports, volatile memory, etc.) It could be a complex way of setting back the timer by 18 clock cycles.

But anyway, the basic gist of reducing irresponsible statements like that, is you build a abstract syntax tree (I''ll represent mine in postfix, as the board can''t mangle that.)

x x 3 + 2 - 5 4 - - =

Then the AST under goes constant reduction. Arithmetic operations on pairs of constants are reduced. As well, operations of the form + 0 or * 1 are reduced out.

x x 3 + 2 - 1 - =

Another step of optimization is to regroup constants together using associativity and communitivity rules.

x x 3 2 - + 1 - =
x x 1 + 1 - =
x x 1 1 - + =
x x 0 + =
x x =

At this point the compiler can throw it out as a assignment to itself.

This topic is closed to new replies.

Advertisement