Other kinds of for loops

[rachitnigam]

Two common patterns of for loops I've encountered in PolyBench:

1. Loops instantiated with other loop variables (same as Initialize loops using other iterators #72).

for(let j = k + 1; j < PB_J; j++) // k is another loop bounds and PB_J is compile time constant

2. Loops range ends with other loop variables

for(let j = 0; j < k; j++) // k is another loop bounds

3. Non-1 steps for for loops

for(j = 0; j < PB_J; j += 2)

There might be interesting type system things we can do for these loops. Every other for loop should just be turned into a while loop.

For (3), we can do something of the form where only some of the banks are consumed since not all of them are touched.

Don't know what to do for (1) and (2).

[sampsyo]

Would it work to implement (1) and (2) by using prefix or suffix views and then iterating over those? We would, of course, need to figure out what it means to take a view using an index type…

[rachitnigam]

Well normally, the other loops wouldn't be unrolled so the iterator would be treated as "just" a dynamic number for slicing purposes.

I still don't know of a way to unroll the outer loop without doing the equivalent of the suggestion in #72...

The Jason Cong paper seems to recommend having the inner loop unrolled with a static bound while the outer (controller) loops has a dynamic bound.

[rachitnigam]

I don't think having a prefix view for (2) helps (unless I missed something). What we need is loops with dynamic bounds:

for (let i = 0..j) 

Right now, the compiler restricts j to be a syntactic number. The obvious implementation is allowing dynamic bounds and disallowing unrolling of these loops.

As a bonus, we can transitively calculate the TRIPCOUNTs for each of the variables if j or one of its initializers is a static integers. It seems like having the bounds check pass statically calculate the bounds for each expression is the right thing to do in the limit.

[sampsyo]

I suppose I was implicitly suggesting that loops might be written to use the size of an array for their bounds—sort of like a "foreach" loop. Then, you would do this by first taking a view on the array and then iterating over the entire array. This proposal doesn't really solve the problem; it just moves it into the view creation instead of the iteration…

[rachitnigam]

Yeah, I don't know if that fixes it. See the example in #193 which tries to use both the underlying array and the view together.