News for hackers. Stuff that matters.
Re:Stoke – A stochastic superoptimizer and program synthesizer by radarsat1 on Friday May 29, 2020 @06:23AM (#23348289)
I guess this is what the second paragraph is about.

"In addition to searching over programs, STOKE contains verification infrastructure to show the equivalence between x86-64 programs. STOKE can consider test-cases, perform bounded verification all the way to fully formal verification that shows the equivalence for all possible inputs."

Re:Stoke – A stochastic superoptimizer and program synthesizer by _hl_ on Friday May 29, 2020 @07:46AM (#23348811)
Program equivalence is in general uncomputable if I'm not mistaken, so a big part of the possible performance enhancements depend on the strength of their algorithm for proving equivalence.

Definitely an interesting though extremely challenging problem.

Re:Stoke – A stochastic superoptimizer and program synthesizer by GregarianChild on Friday May 29, 2020 @07:55AM (#23348886)
Undecidability of program equivalence only means that there is no algorithm that correctly returns the correct answer to the question P = Q? for ALL programs P, Q in a Turing-complete programming language.

The original STOKE paper [1] only worked for loop free programs, which may be a program fragment for which program equivalence is decidable. Be that as it may, there is a fast heuristic for proving non-equivalence between two programs P and Q, just feed them with random input -- if they return different outputs, they are NOT equivalent, if OTOH they return the same results, they they are candidates for equivalence and you can throw a modern SMT solver at them which may actually be able to prove equivalence (or come up with a counterexample). Otherwise the SMT solver times out. You can even refine this scheme into some form of local search, in that you measure how much P and Q differ (e.g. Hamming distance). This is used in later papers, e.g. [2].

[1] Stochastic Superoptimization – ASPLOS 2013 https://raw.githubusercontent.com/StanfordPL/stoke/develop/d...

[2] Stochastic Program Optimization – CACM 2016 https://raw.githubusercontent.com/StanfordPL/stoke/develop/d...

Re:Stoke – A stochastic superoptimizer and program synthesizer by GTP on Friday May 29, 2020 @12:31PM (#23352080)
Thanks, I was looking for this explanation.
Re:Stoke – A stochastic superoptimizer and program synthesizer by jonnypotty on Friday May 29, 2020 @10:04AM (#23350073)
Thanks for this