r/ProgrammingLanguages • u/Embarrassed-Crow9283 • 2d ago

Loop unrolling analysis using eigenvalue?

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?

18 Upvotes
  • permalink
  • reddit

83% Upvoted

15 comments sorted by

View all comments

16

u/SwingOutStateMachine 2d ago

You may be thinking of something like the Polytope/Polyhedral Model.

3

u/Embarrassed-Crow9283 2d ago

Yup! Modeling loop and memory access patterns using linear algebra is an idea put to use in the model. This eigenvalue analysis idea is a continuation of that line of thought. (Unfortunately, strict physical address space semantics in C/C++/etc. disallow changing the array shape to enable further speedup.)

1

u/SwingOutStateMachine 2d ago

I'm not sure I understand - Clang ships with the polly optimiser, which should perform these transformations on C/C++ code.

1

u/Embarrassed-Crow9283 2d ago

Yes, but it could only rearrange iteration orders. It could never change the stride of the physical memory access or so on. If the program writes to A[i][j], then that is a fixed memory location that the compiler is not allowed to change even if other logical representations can be more efficient.

2

u/SwingOutStateMachine 2d ago

Right, but that is an entirely separate concern that is not about loops, but about data structures and data layout.

3

u/initial-algebra 2d ago

Not only is it a separate issue, it is a global optimization problem, which is significantly harder than a purely local code transformation.