This post is a note of this paper.
Introduction
This paper formulates the loop-free assembly code optimization task as a stochastic search problem.
It encodes the correctness and performance constraints during the code transformation in cost function and uses a MCMC sampler to explore the program space to find the optimization given a target program.
Beginning from llvm -O0 code, this approach can produce programs that match or outperform programs with O3 compiler optimization and in some cases expert hand-written assembly.