Hacker News Reader

Comment by caf | Hacker News Reader

It's not either/or, adding superoptimiser-derived optimisations at the IR level doesn't mean you can't also add different ones at the backend.

View on HN

The problem is that superoptimised IR may obscure more useful optimisations lower down.

Is there any evidence for this?

Is there any proof that they wouldn't?

My advisor once said "Optimization means: sometimes, it is not getting worse", and that's excactly what happens if you perform any optimization on IR level. You don't have any guarantee that your result is optimal (regarding whatever). That's exactly the reason why Massalin introduced the term superoptimization, because on machine level you can provide such guarantees for the considered instruction sequence.

Of course there a cases where preventing an IR optimization can trigger a more powerful one and the resulting code gets better. However, in general I would say it's the other way around: Performing the IR superoptimization leads to better code quality.

I'd guess either approach will become stuck in local minima. Ideally, you'd want to check all permutations systematically. Of course, there is probably no polynomial-time algorithm to find the optimal, but adding some basic depth bounds should give a practical implementation that can explore at least some of the space, instead of relying on gut instinct about which approach may or may not be better.

The permutation problem is not related to IR superoptimization itself.

The goal of an optimization pass is to improve the performance of an average, and that's exactly what the IR superoptimization does.

My intuition is that stacking general super optimizers will be at best equally or less effective than just running a machine specific one for twice as long.

I believe the intention here is to use the super-optimiser to derive specific generally-applicable optimisations that can be contributed back to LLVM as peephole optimisations, rather than running the super-optimiser as part of the usual compilation process.

That being the case, it seems like it would be advantageous to create optimisations that work at both stages of compilation - not least because the IR-level ones will be more widely applicable.

The advantage of performing superoptimization on IR level is that you have explicit data dependencies (due to SSA form). Thus you don't have unrelated instructions in between. Figure 1 of the cited Optgen paper http://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwa... shows an example that can be optimized with IR-based superoptimization but not with a machine-specific one.

In summary, no approache subsumes the other one. Thus, it is worthwhile to have them both.

Reply on news.ycombinator.com