Initialize loops using other iterators

[rachitnigam]

This is a common pattern for offset-ted array accesses:

for (int i = 0; i < 8; i++) {
  for (int j = i; j < 8; j++) {
    a[i][j];
  }
}

The type checker will reject this program because the ranges must be static. However, we can rewrite the two loops to:

for (int i = 0; i < 8; i++) {
  for (int j = 0; j < 8; j++) {
    if (j >= i) { a[i][j]; }
  }
}

The benefit of the rewrite is that both the loops can be unrolled. Furthermore, it seems to me that the HLS compiler has to essentially discover this relationship b/w i and j to efficiently compile the hardware.

(1) Should we force programmers to write programs in the second form?

@sampsyo pointed out that the mux in front of the loop implies a logical time gap (@sampsyo please expand).

If we do choose (1), then this easily extends to while loops too (after #63):

  int f = 0;
  while(f > 10) {
    f++;
    for (int i = f; i < 10; i++) {
      a[i] *= f
    }
}

turns into

  int f = 0;
  while(f > 10) {
    f++;
    for (let i = 0..10) {
      if (i >= f) { a[i] *= f }
    }
 }

Concretely, this will allow us to rewrite the loops in fft (@tedbauer #60):

for(span=FFT_SIZE>>1; span; span>>=1, log++){
  for(odd=span; odd<FFT_SIZE; odd++) {
  ...
  }
}

into:

let span = FFT_SIZE>>1;
while(span == 0) {
  for(let odd = 0..FTT_SIZE) {
    if (odd >= span) {
    ...
    }  
  }
  span = span >> 1;
  log = log + 1;
}

[sampsyo]

@sampsyo pointed out that the mux in front of the loop implies a logical time gap (@sampsyo please expand).

The issue I was referring to is that putting an if inside the loop implies that those loop iterations still run, and take time, even though they don’t “do” anything. So requiring the program to condition off some iterations is a bit in conflict with our “informal cost model” we’re presenting to programmers.

Allowing the inner loop to have proper bounds that reflects its number of iterations would be nice! My rough alternative proposal was to use views: the inner loop could iterate over a view whose offset comes from the index of the outer loop.