I am working on a project to automatically convert a custom language to Java and have been asked to do some basic optimizations of the code during the conversion process. For example, the custom code may have something like:
if someFunction(a, b) > x:
return someFunction(a, b) + y
in this instance, someFunction is called multiple times with the same inputs, so additional performance can be obtained by caching the value of someFunction() and only calling it once. Thus, an "optimized" version of the above code may look something like:
var1 = someFunction(a, b)
if var1 > x:
return var1 + y
Currently, this is done by hand during the conversion process. I run a program to convert the code in the custom language to Java and then manually examine the converted code to see what can be optimized. I want to automate the optimization process since these problems creep up again and again. The people who are writing the code in the custom language do not want to worry about such things, so I can't ask them to just make sure that the code they give me is already optimized.
What are some tutorials, papers, etc... that details how such things are done in modern compilers? I don't want to have to re-invent the wheel too much. Thanks in advance.
It can be assumed that the function is pure.
This is known as Common subexpression elimination.
Normally, this would require you pretty much implement a full compiler in order to do the data flow analysis. An algorithm is given in Dragon Book, "6.1.2 The Value-Number Method for Constructing DAG's" (for the local CSE at least).