Superoptimizer, CSC530, Spring 2021

First, read through Henry Massalin’s 1987 superoptimizer paper:

Massalin, Henry. "Superoptimizer: a look at the smallest program." ACM SIGARCH Computer Architecture News 15.5 (1987): 122-126.

Make sure you understand the ideas presented in this paper.

One choice at this point is to go ahead and just take a crack at implementing something like this yourself. This will work best if you have a machine that runs native 8086. Also, you’ll have to choose an insanely simplified set of instructions. I recommend using the examples in the paper, and more or less cheating by choosing those instructions that you know you’ll need, based on his examples. See how it goes.

Alternatively, you can take a look at Henry Warren’s "AHA" (A Hacker’s Assistant). It’s documented by this paper:

Warren, Henry S. A Hacker’s Assistant.

In this case, you can start with the code for Henry Warren’s adaptation of Henry Massalin’s work. It’s contained in this github repo, on the "distrib" branch:

https://github.com/dpt/Aha

Let me know how it goes!

1 Time

Don’t feel you need to spend more than three or four hours on this. If you get interested, that’s fine, and you’re welcome to do more, but you can set a timer for four hours and call yourself done at the end of it.