4 ms·
I wonder if it's possible to do a similar thing for codegen. i.e. generate more efficient code based on SMT solver and CPU model.
by ingenter 11y ago
I wonder if it's possible to do a similar thing for codegen. i.e. generate more efficient code based on SMT solver and CPU model.
- andrewchambers 11y agoI want to see efficient backends automatically generated from a flat list of assembly instruction descriptions using similar methods.
- cwzwarich 11y agoIt's been done: http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://theory.stanford.edu/~aiken/publications/papers/asplos... They had to restrict themselves to instruction sequences of length 3 due to limited resources, and say that to go beyond instruction sequences of length 4 they would need a better approach.
- fulafel 11y agoThis has been done in '87 by Massalin: https://www.cs.arizona.edu/~collberg/Teaching/553/2011/Resources/superoptimizer-massalin.pdf https://www.cs.arizona.edu/~collberg/Teaching/553/2011/Resou... (both are brute force though, not solver-based)
- cwzwarich 11y agoMassalin's superoptimizer required humans to check the correctness of optimizations. It also didn't generate parameterized peephole optimizations; it directly optimized concrete instruction sequences.
- joajoa 11y agoAbsolutely. See [1] for instance. Superoptimization has been around since the 80s and at the first superoptimizer by Alexia Massalin targeted the 68000 instruction set. [1] http://superoptimization.org/w/images/f/f1/Wp4.pdf http://superoptimization.org/w/images/f/f1/Wp4.pdf
- deleted 11y ago[deleted]
- DannyBee 11y agoYes, there are tons of papers on doing optimal scheduling/instruction selection/register allocation by using integer linear programming. Modeling is not even the hard part, it's modeling in a way that doesn't take till the heat death of the sun to solve ;-)