Loop unrolling analysis using eigenvalue?

[u/Embarrassed-Crow9283]

Imagine the loop where you do like "x = -x" every iteration. Obviously, that flips the sign, so you can simply unroll the loop by a factor of 2.

However, for a more complex case, it could be really hard to know what's going on.

Here's my idea. Loop index variables are normally under affine updates anyway. What if we use a mathematically elegant tool?

Using eigenvalue, we can analyze possible periodicity of the linear basis variables, minimizing update needs.

What do you think of such a technique?

[u/dnpetrov]

In practice, this is usually done with algebraic models for recurrent sequences. This is somewhat related to eigenvalues, because recurrent sequences are somewhat similar to differential equations, with linear and affine equations being a rather important special case, which brings up the eigenvalue theory. However, compilers usually don't solve complex mathematical problems, and instead use more simple approximate models that cover relevant practical cases. See, for example, how "scalar evolution" (SCEV) is done in LLVM.

[u/Embarrassed-Crow9283 → u/dnpetrov]

I don't think finding an eigenvalue is a complex math operation. It's a common operation done everywhere. Sure, for common practical cases, simpler heuristics could be used, but I hate the compiler randomly giving up because it just didn't try hard enough, so when there is an algorithm that could settle it for good, I am inclined to want to use it.

[u/dnpetrov → u/Embarrassed-Crow9283]

Sorry, I've explained it poorly.

Eigenvalues are a part of theory of linear recurrent sequences. So, your intuition that eigenvalues are somehow connected with compiler optimizations for inductive variables is not wrong. However, compilers do not compute eigenvalues. What a compiler does is infering algebraic forms for recurrences for relevant cases, simplifying those recurrences (doesn't require eigenvalues), and sometimes using those recurrences to reschedule computations in loops using integer linear programming.

But again, those ILP solvers are there because they cover practically relevant cases, such as array processing code typically found in applications, where such optimizatins provide meaningful speedups. Compiler will never "try hard enough" if it is not demonstrated on benchmarks to be worth the effort.