While playing around with optimization sets in LLVM, it occurs to me that the order in which optimizations are run matters greatly since, in general, A(B(src)) is not equal to B(A(src)) where A and B are some optimization of type source -> source and src is of type source.

Are there optimizations for which that property holds? Are there projects or research that attempt to formalize or otherwise create these types of optimizations?

  • $\begingroup$ I'm not sure what kind of answer you are expecting. A list of all pairs of optimizations that commute would be too broad for this site. $\endgroup$
    – D.W.
    Commented Aug 24, 2016 at 0:17
  • $\begingroup$ What information is available? Are there optimizations that commute? I'm not asking for an exhaustive list. $\endgroup$
    – oconnor0
    Commented Aug 24, 2016 at 5:08
  • 1
    $\begingroup$ @oconnor0 What do you mean by optimisations don't commute. In general, optimisations should preserve the semantics of the original program, so $A \circ B$ should have the same meaning as $B \circ A$. To be sure, $A \circ B$ often does not result in the same code as $B \circ A$. So there are different notions of "the same" at play, which one are you interested in? $\endgroup$ Commented Aug 25, 2016 at 8:16
  • $\begingroup$ I'm interested in the same code, not the same semantics. At a crude level, I am interested in commuting optimizations such that diff "$A \circ B$" "$B \circ A$" returns no differences. $\endgroup$
    – oconnor0
    Commented Aug 25, 2016 at 14:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.