Program Minimization

Question

Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs?

In particular my question is -

Do there exist algorithms to minimize the # of instructions for a given program. I know it's an undecidable problem but I'm not looking for a solution that returns something optimal.

While one can apply preexisting compiler transformations to accomplish this, I'm looking for something where I don't have to define a set of very narrow transformations and algorithms to search for them beforehand.

Edit: The other question I have is whether one can have a calculus that is sound and complete that allows us to explore the whole space of such semantically equivalent programs or is that not possible.

Answer 1

There is a naive algorithm for programs with bounded-size inputs: enumerate all programs in order of increasing length (or execution time, which is a bounded function of the length). If you can prove that the program is equivalent to the original, stop; otherwise keep searching.

This algorithm is sound. In order for it to be complete, you need to be able to prove all rejected programs are not equivalent to the original. This is possible in finitary machine models, as long as you have a bound for the input size.

Note that when the program execution time depends on the input, there may not be an optimal solution. If you look for e.g. a worst-case bound, you'll very quickly run into undecidable equivalences when you quantify over all possible unbounded inputs, and into untractable problems if the inputs are bounded.

A decade ago, “Denali: A Goal-Directed Superoptimizer” by Rajeev Joshi , Greg Nelson and Keith Randall was able to find optimal programs of about 5 machine instructions. I haven't looked at more recent results.