# What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

On an imperative programming language, let us consider the following program:

for i in 0..N { // N is the length of the arrays A, B, C.
A[i] = A[i] + B[i];
}
for i in 0..N {
A[i] = A[i] + C[i];
}


This program just sums three arrays $$A + B + C$$ component-wisely and store it to $$A$$.

We can easily transform this program into the following equivalent one:

for i in 0..N {
let tmp = A[i] + B[i];
A[i] = tmp + C[i];
}


I think the latter code is more efficient than the former because we can decrease the number of memory accesses.

Now I have a question.

What is the name of this type of program transform or program optimization? Can we also call this deforestation?

• I'm not clear on why tmp is needed. – Acccumulation Jan 17 at 7:10
• Note that for floating point numbers, those two programs are no longer equivalent. As such kinds of loops over floating point arrays are common in scientific computing, it's important to understand the implications. Just in case you're wondering, why a compiler might refuse to apply this and other similar optimizations to some of your loops. – ComicSansMS Jan 17 at 8:56
• @ComicSansMS Interesting! Do you mean that, in general (for floating point numbers), there maybe exist an index $i$ such that $A[i] \text{(of the former)} \neq A[i] \text{(of the latter)}$? Would you explain how such a situation happens? – yuezato Jan 17 at 16:23
• @yuezato Apologies, I misread your example and thought there was a change in associativity of the operations (which would trigger the difficulties for floats), but that is not the case. I withdraw my earlier comment, sorry for the confusion. The example presented here would only be problematic if the compiler were to perform the float addition with a different precision (such as using a fused-3-way-add in the second loop, or keeping the results in an extended precision register), but that will not happen unless you take explicit measures to allow this kind of optimization. – ComicSansMS Jan 17 at 16:48
• @ComicSansMS Thank you for your kindly comment! I've understood. In a similar code, when a compiler translates $A[i] \gets A[i] + B[i]; A[i] \gets A[i] \times C[i]$ to $A[i] \gets \text{FMA}(A[i], B[i], C[i])$, where FMA is a Fused Multiply-Add, then the results maybe are different due to floating-point precision errors. Also, if $A[i] \gets A[i] + B[i]; A[i] \gets A[i] + C[i]$ is translated to $A[i] \gets A[i] + (B[i] + C[i])$, then they maybe are different due to the lack of associativity. – yuezato Jan 18 at 5:29

• Also worth noting that the reverse of this is considered a type of refactoring called split loop in the Martin Fowler refactoring book: refactoring.com/catalog/splitLoop.html. – mowwwalker Jan 17 at 16:23