0
$\begingroup$

I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code.

For example, consider the following expression:

(a + b) + ((c + d) + e)

It can be transformed into:

a + (b + (c + (d + e)))

Does anybody know the name of this transformation?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Note that floating point addition is not associative. ​ ​ ​ $\endgroup$ – user12859 Oct 27 '15 at 5:27
  • $\begingroup$ Reordering maybe ? $\endgroup$ – Yves Daoust Oct 27 '15 at 11:59
  • 1
    $\begingroup$ Note that that "optimization" is actually a pessimization in this case - in the first example an out-of-order or pipelined CPU can issue [(a+b), (c+d)], then [(c+d)+e] then [(a + b) + ((c + d) + e)], taking 3 add latencies, whereas in the second case it takes 5 add latencies (as each add requires the previous one to be complete). $\endgroup$ – TLW Oct 27 '15 at 19:47
1
$\begingroup$

According to LLVM it is called "Reassociate expressions" and uses the flag "-reassociate"

According to here:

-reassociate: Reassociate expressions

This pass reassociates commutative expressions in an order that is designed to promote better constant propagation, GCSE, LICM, PRE, etc.

For example: 4 + (x + 5) ⇒ x + (4 + 5)

In the implementation of this algorithm, constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal of current function (starting at 2), which effectively gives values in deep loops higher rank than values not in loops.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.