3 ms·

I'm not sure if I'm interpreting the paper [0] correctly, but both the abstract and the quote below from the Experiments section sound like they're not going to

I'm not sure if I'm interpreting the paper [0] correctly, but both the abstract and the quote below from the Experiments section sound like they're not going to aim for faster code, but for a meta goal (that I admit I don't understand) instead? "The goal is to give compiler developers actionable advice about missing optimizations. To do this, someone uses sclang to extract Souper left-hand sides from programs of interest. Since Souper finds many more optimizations than developers could reasonably implement, the crux is ranking them in such a way that desirable optimizations are found early in the list. We are not aware of any single best ranking function, but rather we have created several such functions that can be used together or separately" [0] https://arxiv.org/abs/1711.04422 https://arxiv.org/abs/1711.04422

jcranmer 6y ago
When you develop compilers, you generally have a three-way tradeoff that you can't get all three of simultaneously: runtime speed, generated code size, and compile time. For what's effectively a peephole pass, the main balance question is if the increase in runtime speed is going to be worth the extra time compiling the code. If patterns don't crop up very frequently, and the resulting code has only marginal speedups, then it's not going to be worth slowing everyone's compile time for that speedup. In the context of LLVM IR, there's a subtle issue which is even more important. LLVM IR is sufficiently divorced from actual hardware instructions to be a good basis for a cost model. I believe Souper is largely using instruction count as its cost model [1], which is going to really fall down when you handle i1 values, since most processors aren't capable of doing arithmetic on i1 values natively, and converting the result of a comparison instruction into one that can be reasoned about with boolean circuits can involve several extra instructions. [1] Regehr's original blog post on the matter says instructions are cost 1, constants and phis cost 0, and selects and div/rem cost 3. sexts/zexts/truncs aren't explicitly modeled, and so also presumably cost 0. So it's mostly instruction cost.

jcranmer 6y ago

When you develop compilers, you generally have a three-way tradeoff that you can't get all three of simultaneously: runtime speed, generated code size, and compile time. For what's effectively a peephole pass, the main balance question is if the increase in runtime speed is going to be worth the extra time compiling the code. If patterns don't crop up very frequently, and the resulting code has only marginal speedups, then it's not going to be worth slowing everyone's compile time for that speedup. In the context of LLVM IR, there's a subtle issue which is even more important. LLVM IR is sufficiently divorced from actual hardware instructions to be a good basis for a cost model. I believe Souper is largely using instruction count as its cost model [1], which is going to really fall down when you handle i1 values, since most processors aren't capable of doing arithmetic on i1 values natively, and converting the result of a comparison instruction into one that can be reasoned about with boolean circuits can involve several extra instructions. [1] Regehr's original blog post on the matter says instructions are cost 1, constants and phis cost 0, and selects and div/rem cost 3. sexts/zexts/truncs aren't explicitly modeled, and so also presumably cost 0. So it's mostly instruction cost.