In typical PGO you have access to the source code, the compiler instruments it for you automatically, you run the program with what You consider good input. During that time the instrumentation records a lot of interesting stuff. Then the compiler recompiles your program with that extra knowledge, making much better decisions[1]. For instance the compiler might realize: "Oh, this function is called much more often than I thought, I will now inline it."

Here (Link to the paper:[2]) this is different: The authors do NOT have access to the source code, they only have stripped binaries. From these unreadable binary instructions, they are able to identify interesting patterns: they extract the algorithm from the assembly. For this to work, they seem to need run time information. This means, as in conventional PGO, they need to have a wide variety of valuable input. It apparently cannot be done at compile time: "Current state-of-the-art techniques are not capable of extracting the simple algorithms from these highly optimized program."

Once the algorithm is figured out, the Helium framework is generating domain specific code in "Halide". Halide compilers knows how to optimize these stencil computation better than old hand written code, which give them these impressive improvements.

[1]https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx

[2] http://groups.csail.mit.edu/commit/papers/2015/mendis-pldi15...