<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>A decade ago, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5676&amp;rank=4">“Denali: A Goal-Directed Superoptimizer” by Rajeev Joshi , Greg Nelson and Keith Randall</a> was able to find optimal programs of about 5 machine instructions. I haven't looked at more recent results.</p>

CC BY-SA 3.0
2014-03-11T12:52:07.323Z
One of our students here at the University of Sussex used superoptimisation to shorten the length of some core Java routine (such as addition). He burned enormous amounts of Amazon EC2 computation to do this. His dissertation is [here](http://www.tomhume.org/superoptimisation-and-vms.pdf). Clearly not a feasible approach for anything but really short programs.
Martin Berger
CC BY-SA 3.0
2014-03-11T11:24:00.937Z
2014-03-11T11:24:00.937Z
Gilles 'SO- stop being evil'
<p><a href="https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions">Circuit Minimization</a> is the problem to minimize the size of a given circuit. Is there anything similar for general programs? </p>

<p>In particular my question is -</p>

<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-11T20:16:13.640Z
the two fields are related in that another approach is to convert the programs to the family of circuits for varying input sizes $f_n$
vzn
<pl.programming-languages><optimization><circuit-complexity><semantics><compilers>
Program Minimization
Opt
# Program Minimization

(Asked by: username_0 on 2014-03-10)

[Circuit Minimization](https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions) 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.

**Tags:** pl.programming-languages, optimization, circuit-complexity, semantics, compilers
> **Comments:**
> **username_1**: the two fields are related in that another approach is to convert the programs to the family of circuits for varying input sizes $f_n$  

---

## 1 answers

### Answer by username_2 on 2014-03-11. Score: 10 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5676&rank=4) was able to find optimal programs of about 5 machine instructions. I haven't looked at more recent results.

> **Comments:**
> **username_3**: One of our students here at the University of Sussex used superoptimisation to shorten the length of some core Java routine (such as addition). He burned enormous amounts of Amazon EC2 computation to do this. His dissertation is [here](http://www.tomhume.org/superoptimisation-and-vms.pdf). Clearly not a feasible approach for anything but really short programs.  

---

