Loop fission and fusion

Fission

Example in C

int a[100];
int b[100];
for (int i = 0; i < 100; i++) {
    a[i] = 1;
    b[i] = 2;
}

is equivalent to:

int a[100];
int b[100];
for (int i = 0; i < 100; i++) {
    a[i] = 1;
}
for (int i = 0; i < 100; i++) {
    b[i] = 2;
}

Fusion

Example in C++ and MATLAB

Consider the following MATLAB code: x = 0:999; % Create an array of numbers from 0 to 999 (range is inclusive) y = sin(x) + 4; % Take the sine of x (element-wise) and add 4 to each element

The same syntax can be achieved in C++ by using function and operator overloading:

import <cassert>;

import std;

using std::unique_ptr;

class FloatArray {
private:
    size_t length;
    std::unique_ptr<float[]> data;
    
    // Internal constructor that produces an uninitialized array
    explicit FloatArray(size_t n): 
        length{n}, data{new float[n]} { }
public:
    // Factory method to produce an array over an integer range (the upper
    // bound is exclusive, unlike MATLAB's ranges).
    [[nodiscard]]
    static FloatArray range(size_t start, size_t end) {
        assert(end > start);
        size_t length = end - start;
        FloatArray a(length);
        for (size_t i = 0; i < length; ++i) {
            a[i] = start + i;
        }
        return a;
    }
    
    // Basic array operations
    [[nodiscard]]
    size_t size() const noexcept { 
        return length; 
    }

    float& operator[](size_t i) noexcept { 
        return data[i]; 
    }

    const float& operator[](size_t i) const noexcept { 
        return data[i]; 
    }

    // Declare an overloaded addition operator as a free friend function (this
    // syntax defines operator+ as a free function that is a friend of this
    // class, despite it appearing as a member function declaration).
    friend FloatArray operator+(const FloatArray& a, float b) {
        FloatArray c(a.size());
        for (size_t i = 0; i < a.size(); ++i) {
            c[i] = a[i] + b;
        }
        return c;
    }
    
    // Similarly, we can define an overload for the sin() function. In practice,
    // it would be unwieldy to define all possible overloaded math operations as
    // friends inside the class like this, but this is just an example.
    friend FloatArray sin(const FloatArray& a) {
        FloatArray b(a.size());
        for (size_t i = 0; i < a.size(); ++i) {
            b[i] = std::sin(a[i]);
        }
        return b;
    }
};

int main(int argc, char* argv[]) {
    // Here, we perform the same computation as the MATLAB example
    FloatArray x = FloatArray::range(0, 1000);
    FloatArray y = sin(x) + 4;
    
    // Print the result out - just to make sure the optimizer doesn't remove
    // everything (if it's smart enough to do so).
    std::println("The result is: ");
    for (float f: y) {
        std::println("{}", f);
    }
    
    return 0;
}

However, the above example unnecessarily allocates a temporary array for the result of sin(x). A more efficient implementation would allocate a single array for y, and compute y in a single loop. To optimize this, a C++ compiler would need to:

1. Inline the sin and operator+ function calls.
2. Fuse the loops into a single loop.
3. Remove the unused stores into the temporary arrays (can use a register or stack variable instead).
4. Remove the unused allocation and free.

All of these steps are individually possible. Even step four is possible despite the fact that functions like malloc and free have global side effects, since some compilers hardcode symbols such as malloc and free so that they can remove unused allocations from the code. However, as of clang 12.0.0 and gcc 11.1, this loop fusion and redundant allocation removal does not occur - even on the highest optimization level.

Some languages specifically targeted towards numerical computing such as Julia might have the concept of loop fusion built into it at a high level, where the compiler will notice adjacent elementwise operations and fuse them into a single loop. Currently, to achieve the same syntax in general purpose languages like C++, the sin and operator+ functions must pessimistically allocate arrays to store their results, since they do not know what context they will be called from. This issue can be avoided in C++ by using a different syntax that does not rely on the compiler to remove unnecessary temporary allocations (e.g., using functions and overloads for in-place operations, such as operator+= or std::transform).

References

• Loop fission

References

1. (3 October 2018). "The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition". CRC Press.
2. (2001). "Optimizing Compilers for Modern Architectures: A Dependence-based Approach". Morgan Kaufmann.
3. (15 August 1997). "Advanced Compiler Design Implementation". Morgan Kaufmann.
4. Johnson, Steven G.. (21 January 2017). "More Dots: Syntactic Loop Fusion in Julia".
5. "Loop Fusion".
6. Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)".
7. Godbolt, Matt. "Compiler Explorer - C++ (x86-64 clang 12.0.0)".
8. Godbolt, Matt. "Compiler Explorer - C++ (x86-64 gcc 11.1)".
9. "Functions · The Julia Language".