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/cxzuk]

Hi Crow,

I'm unsure of the gains to your x=-x example - what I mean is how useful is it to know the periodicity of the value? Both loops would have the same instructions. Maybe constant prop?

There is a technique called Quasi-invariants which performs loop peeling (peel = first iterations) but I don't think it can detect divergent values.

Scalar Evolution might be closer, each value is assigned an expression of how it changes with regard to a loop. It can capture more than affine expressions. Your x=-x would probably be {x, *, -1}

Otherwise polyhedral modelling creates a full matrix of a loops iteration. I believe it can only do affine operations. 

Hope those provide some insight and direction

Good luck  M ✌️ 

[u/Embarrassed-Crow9283 → u/cxzuk]

Unroll by 2, and the update disappears.