Confused about three optimization techniques

Question

1. How do you exactly perform "commoning"?
2. How does Kleene fixed-point theorem help in optimization?
3. How do you eliminate free variables from local function definitions in programs written in non-functional languages?

EDIT: These are NOT my homework questions. I am in my summer break.

EDIT2: Well I am just begininng to study compiler optimizations and dont have a particular code that I want to optimize. Could you just tell me what are the general methods you can use the above three optimization techniques or at least tell me the resouces that properly explain them?

Answer 1

Good answer from Norman. (I just hope your prof. doesn't confuse optimizations that a compiler might do with optimizations that the software programmer might do. The latter is less of a technical subject, so there is less to say about it, but in real application it is orders of magnitude more significant.)

Answer 2

1. Commoning is done by bottom-up hashing.
2. Kleene's theorem allows the compiler to implement an iterative solution to recursion equations that give facts about the program. A simple example of a fact is that at a certain point, variable i is always equal to 0.
3. If you have a local function with free variables that are let-bound or lambda-bound in an enclosing function, then by definition you are dealing with a language that has first-class functions. The free variables are typically dealt with by closure conversion, although some compilers use lambda-lifting.

Recommended search terms:

• Bottom-up hashing
• Common-subexpression elimination
• Iterative dataflow analysis
• Dataflow optimization made simple
• Continuation-passing, closure-passing style
• Closure conversion
• Lambda lifting

Answer 3

Last Question's Answer: http://en.wikipedia.org/wiki/Lambda_lifting

Answer 4

http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/ac55fd7d73a5fdb4#

Answer 5

These are what I found on the web, if somebody has access to further information please reply.

William Clinger teaches two of the above techniques and looks into more interesting ones in his class: http://www.ccis.neu.edu/home/will/csg262_fall2004/syllabus.html

These guys are using the Kleene algebra for data flow analysis. I think we can use it in optimizing compilers: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http://ieeexplore.ieee.org/iel5/4159639/4159640/04159673.pdf%3Fisnumber%3D4159640%26prod%3DCNF%26arnumber%3D4159673%26arSt%3D201%26ared%3D210%26arAuthor%3DFernandes%252C%2BT.&authDecision=-203

Unfortunately the above paper requires login.

This is what I found about commoning(but didnt help much): http://www.patentsurf.net/7,516,448