3 ms·
Happy to see this! Superoptimizers are one of my all time favorite topics. My favorite trick when cutting down the search space of possible programs is to gene
by mungoman2 3y ago
Happy to see this! Superoptimizers are one of my all time favorite topics.
My favorite trick when cutting down the search space of possible programs is to generate DAGs directly instead of an instruction sequence. This way, it's easier to write rules that avoid nonsensical programs and to some extent avoid generating multiple equivalent programs.
For example to avoid programs that overwrite calculations you make sure that each node in the generated DAG has something that depends on it.
In a suitable environment the DAG can then be executed directly without lowering to a sequence of instructions.
- shoo 3y agoThis sounds a little bit like representing boolean functions as binary decision diagrams -- although for a superoptimizer presumably each node in the DAG would correspond to an instruction from the target instruction set, which might do something rather complicated, not just a primitive logical operation between a few bits. https://en.wikipedia.org/wiki/Binary_decision_diagram https://en.wikipedia.org/wiki/Binary_decision_diagram (i first read about BDDs in Knuth's, "The Art of Computer Programming", Volume 4, Fascicle 1, then spent an enjoyable few weeks going down a rabbit hole of building a boolean function to decide if an input 2d grid of bits was a maze or not, then uniformly sampling mazes from it...)