arXiv:1211.0557cs.PF
Stochastic Superoptimization
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We formulate the loop-free, binary superoptimization task as a stochastic search problem. The competing constraints of transformation correctness and performance improvement are encoded as terms in a cost function, and a Markov Chain Monte Carlo sampler is used to rapidly explore the space of all possible programs to find one that is an optimization of a given target program. Although our method sacrifices com- pleteness, the scope of programs we are able to reason about, and the quality of the programs we produce, far exceed those of existing superoptimizers. Beginning from binaries com- piled by llvm -O0 for 64-bit X86, our prototype implemen- tation, STOKE, is able to produce programs which either match or outperform the code sequences produced by gcc with full optimizations enabled, and, in some cases, expert handwritten assembly.
Superoptimizers have gotten a lot better in the past few years. E.g. have a look at [1]. [1] https://arxiv.org/abs/1211.0557
titzerView on HNParent context