Superoptimization is finding -the- optimal program to perform a task, as opposed to optimization which only looks for better programs. Loop-free means... no loops.

That said, their approach does not actually give you the superoptimal solution, since it is a stochastic search.

>What's "the loop-free binary superoptimization task"?

http://blog.regehr.org/archives/923

edit: oops, the above link describes what a stochastic-superoptimizer is. however, if you read through the whole thing, it may give an inkling what the authors have done...