3 ms·
From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimiz
by pubby 4y ago
From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a symbolic approach to determine equivalence. Its results are not always optimal, and portions like the PBQP stuff is obviously different.
- peterfirefly 4y agoI think you'll be (very!) interested in e-graphs: https://en.wikipedia.org/wiki/E-graph https://en.wikipedia.org/wiki/E-graph Google fodder: "Equality Saturation: A New Approach to Optimization" "Denali: A Goal-directed Superoptimizer" "Z3: An Efficient SMT Solver" "Efficient E-matching for SMT Solvers" "egg: Fast and Extensible Equality Saturation" "Rewrite Rule Inference Using Equality Saturation"
- ant6n 4y agoIt also only uses one possible ordering for the IR instructions? Still a nice result. It looks like a dynamic programming solution to code generation. Next to the game boy. ;-)
- ant6n 4y agoIt’s probably possible to incorporate all possible orderings of instructions, if the set of already computed instructions is part of the state of the dynamic programming algorithm.