Sliding window / storage folding can't express rotating through a set of registers

[abadams]

The following code should be great, because g's values should rotate through 8 registers instead of ever touching memory. However sliding window can't slide over multiple nested loops at once (x, xi in this case), which is necessary to make this work.

g(x) = x;
f(x) = g(x-2) + g(x+2);

g.fold_storage(x, 8).store_root().compute_at(f, xi);
f.split(x, x, xi, 8, TailStrategy::RoundUp).unroll(xi);

[abadams]

Possible solution: the bulk of the sliding window logic just tries to slide over a var which is known to be monotonically stepping forwards and has a .min and .max symbol in scope. This property holds for many of the original Vars and intermediate Dims in a consumer's splits, not just the final Dims in the dim list. We could generate and order candidate vars to slide over by inspecting the consumer's schedule, rather than by finding serial for loops while inspecting the Stmt.

[jrk]

This feels like a more-right way of thinking about sliding window in general. It seems like it also points towards a model which would make it much saner to explicitly specify sliding in the schedule.

(We can discuss in person Monday.)

[pranavb-ca]

@abadams - This is a little confusing when it relates to vectorization.
For example, for the following code, I am actually seeing sliding window being able to slide max_y but not fold storage. Am I right in expecting this schedule to trigger storage folding? max_y is computed for every 'x' of output and for every 'x' of output 3 values of max_y are needed that can be computed in a circular buffer of size 3

    void generate() {
        max_y(x, y) = max(input(x, y-1), input(x, y), input(x, y+1));
        output(x, y) = max(max_y(x-1, y), max_y(x, y), max_y(x+1, y));
    }
    void schedule() {
        Var xi{"xi"}, yi{"yi"};

        if (get_target().features_any_of({Target::HVX_64, Target::HVX_128})) {
            const int vector_size = get_target().has_feature(Target::HVX_128) ? 128 : 64;
            max_y
              .store_at(Func(output), y)
              .compute_at(Func(output), x)
              .vectorize(x, vector_size, TailStrategy::RoundUp);
            Func(output)
              .vectorize(x, vector_size, TailStrategy::RoundUp);
        } else {
            const int vector_size = natural_vector_size<uint8_t>();
            Func(output)
                .vectorize(x, vector_size)
                .parallel(y, 16);
        }
    }

The following is the IR after sliding window

Sliding max_y over dimension x along loop variable output.s0.x.x
Sliding max_y, x
Pushing min up from ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1) to select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.\
s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1)))
Shrinking max from (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) to (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.\
s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min))

let output.s0.y.max = ((0 + output.extent.1) - 1)
let output.s0.y.min = 0
let output.s0.x.max = ((0 + output.extent.0) - 1)
let output.s0.x.min = 0
let max_y.s0.y.max = output.s0.y.max
let max_y.s0.y.min = output.s0.y.min
let max_y.s0.x.max = (output.s0.x.max + 1)
let max_y.s0.x.min = (output.s0.x.min + -1)
let input.extent.0.required = (((((((max_y.s0.x.max - max_y.s0.x.min)/128)*128) + max_y.s0.x.min) + 127) + 1) - max_y.s0.x.min)
let input.min.0.required = max_y.s0.x.min
let input.stride.0.required = 1
let input.extent.1.required = (((max_y.s0.y.max + 1) + 1) - (max_y.s0.y.min + -1))
let input.min.1.required = (max_y.s0.y.min + -1)
let input.stride.1.required = (input.stride.0.required*input.extent.0.required)
let output.extent.0.required = (((((((output.s0.x.max - output.s0.x.min)/128)*128) + output.s0.x.min) + 127) + 1) - (output.s0.x.min + 0))
let output.min.0.required = (output.s0.x.min + 0)
let output.stride.0.required = 1
let output.extent.1.required = ((output.s0.y.max + 1) - output.s0.y.min)
let output.min.1.required = output.s0.y.min
let output.stride.1.required = (output.stride.0.required*output.extent.0.required)
let input.stride.0.constrained = 1
let input.min.0.constrained = 0
let input.stride.1.constrained = ((input.stride.1/128)*128)
let input.min.1.constrained = 0
let output.stride.0.constrained = 1
let output.min.0.constrained = 0
let output.stride.1.constrained = ((output.stride.1/128)*128)
let output.min.1.constrained = 0
let input.stride.0.proposed = 1
let input.min.0.proposed = 0
let input.extent.0.proposed = input.extent.0.required
let input.stride.1.proposed = ((input.stride.1.required/128)*128)
let input.min.1.proposed = 0
let input.extent.1.proposed = input.extent.1.required
let output.stride.0.proposed = 1
let output.min.0.proposed = 0
let output.extent.0.proposed = output.extent.0.required
let output.stride.1.proposed = ((output.stride.1.required/128)*128)
let output.min.1.proposed = 0
let output.extent.1.proposed = output.extent.1.required
produce output {
  let output.s0.y.loop_max = output.s0.y.max
  let output.s0.y.loop_min = output.s0.y.min
  let output.s0.y.loop_extent = ((output.s0.y.max + 1) - output.s0.y.min)
  let output.s0.x.loop_max = output.s0.x.max
  let output.s0.x.loop_min = output.s0.x.min
  let output.s0.x.loop_extent = ((output.s0.x.max + 1) - output.s0.x.min)
  let output.s0.x.x.loop_extent = (((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128)
  let output.s0.x.x.loop_max = ((((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128) - 1)
  let output.s0.x.x.loop_min = 0
  let output.s0.x.tmp$1.loop_extent = 128
  let output.s0.x.tmp$1.loop_max = (128 - 1)
  let output.s0.x.tmp$1.loop_min = 0
  for (output.s0.y, output.s0.y.loop_min, output.s0.y.loop_extent) {
    let output.s0.y.min = output.s0.y
    let output.s0.y.max = output.s0.y.min
    let output.s0.x.min = (((output.s0.x.x.loop_min*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min)
    let output.s0.x.max = (((((output.s0.x.x.loop_extent + output.s0.x.x.loop_min)*128) + output.s0.x.loop_min) + -128) + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1)\
)
    let max_y.s0.y.max = output.s0.y.max
    let max_y.s0.y.min = output.s0.y.min
    let max_y.s0.x.max = (output.s0.x.max + 1)
    let max_y.s0.x.min = (output.s0.x.min + -1)
    realize max_y([max_y.x.min_realized, max_y.x.extent_realized], [max_y.y.min_realized, max_y.y.extent_realized]) {
      for (output.s0.x.x, output.s0.x.x.loop_min, output.s0.x.x.loop_extent) {
        let output.s0.x.tmp$1.base = ((output.s0.x.x*128) + output.s0.x.loop_min)
        let output.s0.y.min = output.s0.y
        let output.s0.y.max = output.s0.y.min
        let output.s0.x.min = (output.s0.x.tmp$1.base + output.s0.x.tmp$1.loop_min)
        let output.s0.x.max = (output.s0.x.tmp$1.base + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1))
        let max_y.s0.y.max = output.s0.y.max
        let max_y.s0.y.min = output.s0.y.min
        let max_y.s0.x.max = (output.s0.x.max + 1)
        let max_y.s0.x.min = select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x\
 - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1)))
        produce max_y {
          let max_y.s0.y.loop_max = max_y.s0.y.max
          let max_y.s0.y.loop_min = max_y.s0.y.min
          let max_y.s0.y.loop_extent = ((max_y.s0.y.max + 1) - max_y.s0.y.min)
          let max_y.s0.x.loop_max = max_y.s0.x.max
          let max_y.s0.x.loop_min = max_y.s0.x.min
          let max_y.s0.x.loop_extent = ((max_y.s0.x.max + 1) - max_y.s0.x.min)
          let max_y.s0.x.x.loop_extent = (((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128)
          let max_y.s0.x.x.loop_max = ((((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128) - 1)
          let max_y.s0.x.x.loop_min = 0
          let max_y.s0.x.tmp.loop_extent = 128
      let max_y.s0.x.tmp.loop_max = (128 - 1)
          let max_y.s0.x.tmp.loop_min = 0
          for (max_y.s0.y, max_y.s0.y.loop_min, max_y.s0.y.loop_extent) {
            for (max_y.s0.x.x, max_y.s0.x.x.loop_min, max_y.s0.x.x.loop_extent) {
              let max_y.s0.x.tmp.base = ((max_y.s0.x.x*128) + max_y.s0.x.loop_min)
              vectorized (max_y.s0.x.tmp, max_y.s0.x.tmp.loop_min, max_y.s0.x.tmp.loop_extent) {
                let max_y.s0.x = (max_y.s0.x.tmp.base + max_y.s0.x.tmp)
                max_y((max_y.s0.x.tmp.base + max_y.s0.x.tmp), max_y.s0.y) = (let t0 = (max_y.s0.x.tmp.base + max_y.s0.x.tmp) in max(input(t0, (max_y.s0.y - 1)), max(input(t0, max_y.s0.y), \
input(t0, (max_y.s0.y + 1)))))
              }
            }
          }
        }
        vectorized (output.s0.x.tmp$1, output.s0.x.tmp$1.loop_min, output.s0.x.tmp$1.loop_extent) {
          let output.s0.x = (output.s0.x.tmp$1.base + output.s0.x.tmp$1)
          output((output.s0.x.tmp$1.base + output.s0.x.tmp$1), output.s0.y) = max(max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) - 1), output.s0.y), max(max_y((output.s0.x.tmp$1.base \
+ output.s0.x.tmp$1), output.s0.y), max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) + 1), output.s0.y)))
        }
      }
    }
  }
}

[abadams]

Storage folding is pretty brittle in general, because it needs to analyze partially-lowered IR instead of using the Function DAG like sliding window does. In this case the selects injected by sliding window are confusing it. I can get it to work if I add a bunch of new simplifier rules, which isn't really a satisfying fix, but more simplifier rules are usually a good idea. I'll work on a PR. Considering folding max_y over for loop over output.s0.x.x Min: (((output.s0.x.x*128) + output.s0.x.loop_min) + -1) Max: max((((((0 - select((0 < output.s0.x.x), 1, -1))/128)*128) + (((output.s0.x.x*128) + output.s0.x.loop_min) + select((0 < output.s0.x.x), 1, -1))) + 255), (((output.s0.x.x*128) + output.s0.x.loop_min) + 128)) Not folding because extent not bounded by a constant not greater than 1024

…

On Wed, May 3, 2017 at 6:52 AM, Pranav Bhandarkar ***@***.***> wrote: @abadams <https://github.com/abadams> - This is a little confusing when it relates to vectorization. For example, for the following code, I am actually seeing sliding window being able to slide max_y but not fold storage. Am I right in expecting this schedule to trigger storage folding? max_y is computed for every 'x' of output and for every 'x' of output 3 values of max_y are needed that can be computed in a circular buffer of size 3 void generate() { max_y(x, y) = max(input(x, y-1), input(x, y), input(x, y+1)); output(x, y) = max(max_y(x-1, y), max_y(x, y), max_y(x+1, y)); } void schedule() { Var xi{"xi"}, yi{"yi"}; if (get_target().features_any_of({Target::HVX_64, Target::HVX_128})) { const int vector_size = get_target().has_feature(Target::HVX_128) ? 128 : 64; max_y .store_at(Func(output), y) .compute_at(Func(output), x) .vectorize(x, vector_size, TailStrategy::RoundUp); Func(output) .vectorize(x, vector_size, TailStrategy::RoundUp); } else { const int vector_size = natural_vector_size<uint8_t>(); Func(output) .vectorize(x, vector_size) .parallel(y, 16); } } The following is the IR after sliding window Sliding max_y over dimension x along loop variable output.s0.x.x Sliding max_y, x Pushing min up from ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1) to select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.\ s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1))) Shrinking max from (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) to (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.\ s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) let output.s0.y.max = ((0 + output.extent.1) - 1) let output.s0.y.min = 0 let output.s0.x.max = ((0 + output.extent.0) - 1) let output.s0.x.min = 0 let max_y.s0.y.max = output.s0.y.max let max_y.s0.y.min = output.s0.y.min let max_y.s0.x.max = (output.s0.x.max + 1) let max_y.s0.x.min = (output.s0.x.min + -1) let input.extent.0.required = (((((((max_y.s0.x.max - max_y.s0.x.min)/128)*128) + max_y.s0.x.min) + 127) + 1) - max_y.s0.x.min) let input.min.0.required = max_y.s0.x.min let input.stride.0.required = 1 let input.extent.1.required = (((max_y.s0.y.max + 1) + 1) - (max_y.s0.y.min + -1)) let input.min.1.required = (max_y.s0.y.min + -1) let input.stride.1.required = (input.stride.0.required*input.extent.0.required) let output.extent.0.required = (((((((output.s0.x.max - output.s0.x.min)/128)*128) + output.s0.x.min) + 127) + 1) - (output.s0.x.min + 0)) let output.min.0.required = (output.s0.x.min + 0) let output.stride.0.required = 1 let output.extent.1.required = ((output.s0.y.max + 1) - output.s0.y.min) let output.min.1.required = output.s0.y.min let output.stride.1.required = (output.stride.0.required*output.extent.0.required) let input.stride.0.constrained = 1 let input.min.0.constrained = 0 let input.stride.1.constrained = ((input.stride.1/128)*128) let input.min.1.constrained = 0 let output.stride.0.constrained = 1 let output.min.0.constrained = 0 let output.stride.1.constrained = ((output.stride.1/128)*128) let output.min.1.constrained = 0 let input.stride.0.proposed = 1 let input.min.0.proposed = 0 let input.extent.0.proposed = input.extent.0.required let input.stride.1.proposed = ((input.stride.1.required/128)*128) let input.min.1.proposed = 0 let input.extent.1.proposed = input.extent.1.required let output.stride.0.proposed = 1 let output.min.0.proposed = 0 let output.extent.0.proposed = output.extent.0.required let output.stride.1.proposed = ((output.stride.1.required/128)*128) let output.min.1.proposed = 0 let output.extent.1.proposed = output.extent.1.required produce output { let output.s0.y.loop_max = output.s0.y.max let output.s0.y.loop_min = output.s0.y.min let output.s0.y.loop_extent = ((output.s0.y.max + 1) - output.s0.y.min) let output.s0.x.loop_max = output.s0.x.max let output.s0.x.loop_min = output.s0.x.min let output.s0.x.loop_extent = ((output.s0.x.max + 1) - output.s0.x.min) let output.s0.x.x.loop_extent = (((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128) let output.s0.x.x.loop_max = ((((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128) - 1) let output.s0.x.x.loop_min = 0 let output.s0.x.tmp$1.loop_extent = 128 let output.s0.x.tmp$1.loop_max = (128 - 1) let output.s0.x.tmp$1.loop_min = 0 for (output.s0.y, output.s0.y.loop_min, output.s0.y.loop_extent) { let output.s0.y.min = output.s0.y let output.s0.y.max = output.s0.y.min let output.s0.x.min = (((output.s0.x.x.loop_min*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) let output.s0.x.max = (((((output.s0.x.x.loop_extent + output.s0.x.x.loop_min)*128) + output.s0.x.loop_min) + -128) + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1)\ ) let max_y.s0.y.max = output.s0.y.max let max_y.s0.y.min = output.s0.y.min let max_y.s0.x.max = (output.s0.x.max + 1) let max_y.s0.x.min = (output.s0.x.min + -1) realize max_y([max_y.x.min_realized, max_y.x.extent_realized], [max_y.y.min_realized, max_y.y.extent_realized]) { for (output.s0.x.x, output.s0.x.x.loop_min, output.s0.x.x.loop_extent) { let output.s0.x.tmp$1.base = ((output.s0.x.x*128) + output.s0.x.loop_min) let output.s0.y.min = output.s0.y let output.s0.y.max = output.s0.y.min let output.s0.x.min = (output.s0.x.tmp$1.base + output.s0.x.tmp$1.loop_min) let output.s0.x.max = (output.s0.x.tmp$1.base + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1)) let max_y.s0.y.max = output.s0.y.max let max_y.s0.y.min = output.s0.y.min let max_y.s0.x.max = (output.s0.x.max + 1) let max_y.s0.x.min = select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x\ - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1))) produce max_y { let max_y.s0.y.loop_max = max_y.s0.y.max let max_y.s0.y.loop_min = max_y.s0.y.min let max_y.s0.y.loop_extent = ((max_y.s0.y.max + 1) - max_y.s0.y.min) let max_y.s0.x.loop_max = max_y.s0.x.max let max_y.s0.x.loop_min = max_y.s0.x.min let max_y.s0.x.loop_extent = ((max_y.s0.x.max + 1) - max_y.s0.x.min) let max_y.s0.x.x.loop_extent = (((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128) let max_y.s0.x.x.loop_max = ((((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128) - 1) let max_y.s0.x.x.loop_min = 0 let max_y.s0.x.tmp.loop_extent = 128 let max_y.s0.x.tmp.loop_max = (128 - 1) let max_y.s0.x.tmp.loop_min = 0 for (max_y.s0.y, max_y.s0.y.loop_min, max_y.s0.y.loop_extent) { for (max_y.s0.x.x, max_y.s0.x.x.loop_min, max_y.s0.x.x.loop_extent) { let max_y.s0.x.tmp.base = ((max_y.s0.x.x*128) + max_y.s0.x.loop_min) vectorized (max_y.s0.x.tmp, max_y.s0.x.tmp.loop_min, max_y.s0.x.tmp.loop_extent) { let max_y.s0.x = (max_y.s0.x.tmp.base + max_y.s0.x.tmp) max_y((max_y.s0.x.tmp.base + max_y.s0.x.tmp), max_y.s0.y) = (let t0 = (max_y.s0.x.tmp.base + max_y.s0.x.tmp) in max(input(t0, (max_y.s0.y - 1)), max(input(t0, max_y.s0.y), \ input(t0, (max_y.s0.y + 1))))) } } } } vectorized (output.s0.x.tmp$1, output.s0.x.tmp$1.loop_min, output.s0.x.tmp$1.loop_extent) { let output.s0.x = (output.s0.x.tmp$1.base + output.s0.x.tmp$1) output((output.s0.x.tmp$1.base + output.s0.x.tmp$1), output.s0.y) = max(max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) - 1), output.s0.y), max(max_y((output.s0.x.tmp$1.base \ + output.s0.x.tmp$1), output.s0.y), max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) + 1), output.s0.y))) } } } } } — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1820 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAfdRjE0KumiMaFMH3VsRCw7i78ZAUwiks5r2IargaJpZM4L7Eea> .

[abadams]

Actually storage folding would tank the performance of this kernel anyway - the dense vector memory accesses become scatters/gathers because the lanes wrap around in the circular buffer. align_loads doesn't seem to fix things On Wed, May 3, 2017 at 2:07 PM, Andrew Adams <andrew.b.adams@gmail.com> wrote:

…

Storage folding is pretty brittle in general, because it needs to analyze partially-lowered IR instead of using the Function DAG like sliding window does. In this case the selects injected by sliding window are confusing it. I can get it to work if I add a bunch of new simplifier rules, which isn't really a satisfying fix, but more simplifier rules are usually a good idea. I'll work on a PR. Considering folding max_y over for loop over output.s0.x.x Min: (((output.s0.x.x*128) + output.s0.x.loop_min) + -1) Max: max((((((0 - select((0 < output.s0.x.x), 1, -1))/128)*128) + (((output.s0.x.x*128) + output.s0.x.loop_min) + select((0 < output.s0.x.x), 1, -1))) + 255), (((output.s0.x.x*128) + output.s0.x.loop_min) + 128)) Not folding because extent not bounded by a constant not greater than 1024 On Wed, May 3, 2017 at 6:52 AM, Pranav Bhandarkar < ***@***.***> wrote: > @abadams <https://github.com/abadams> - This is a little confusing when > it relates to vectorization. > For example, for the following code, I am actually seeing sliding window > being able to slide max_y but not fold storage. Am I right in expecting > this schedule to trigger storage folding? max_y is computed for every 'x' > of output and for every 'x' of output 3 values of max_y are needed that can > be computed in a circular buffer of size 3 > > void generate() { > max_y(x, y) = max(input(x, y-1), input(x, y), input(x, y+1)); > output(x, y) = max(max_y(x-1, y), max_y(x, y), max_y(x+1, y)); > } > void schedule() { > Var xi{"xi"}, yi{"yi"}; > > if (get_target().features_any_of({Target::HVX_64, Target::HVX_128})) { > const int vector_size = get_target().has_feature(Target::HVX_128) ? 128 : 64; > max_y > .store_at(Func(output), y) > .compute_at(Func(output), x) > .vectorize(x, vector_size, TailStrategy::RoundUp); > Func(output) > .vectorize(x, vector_size, TailStrategy::RoundUp); > } else { > const int vector_size = natural_vector_size<uint8_t>(); > Func(output) > .vectorize(x, vector_size) > .parallel(y, 16); > } > } > > The following is the IR after sliding window > > Sliding max_y over dimension x along loop variable output.s0.x.x > Sliding max_y, x > Pushing min up from ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1) to select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.\ > s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1))) > Shrinking max from (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) to (((output.s0.x.x*128) + output.s0.x.loop_min) + (output.\ > s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) > > let output.s0.y.max = ((0 + output.extent.1) - 1) > let output.s0.y.min = 0 > let output.s0.x.max = ((0 + output.extent.0) - 1) > let output.s0.x.min = 0 > let max_y.s0.y.max = output.s0.y.max > let max_y.s0.y.min = output.s0.y.min > let max_y.s0.x.max = (output.s0.x.max + 1) > let max_y.s0.x.min = (output.s0.x.min + -1) > let input.extent.0.required = (((((((max_y.s0.x.max - max_y.s0.x.min)/128)*128) + max_y.s0.x.min) + 127) + 1) - max_y.s0.x.min) > let input.min.0.required = max_y.s0.x.min > let input.stride.0.required = 1 > let input.extent.1.required = (((max_y.s0.y.max + 1) + 1) - (max_y.s0.y.min + -1)) > let input.min.1.required = (max_y.s0.y.min + -1) > let input.stride.1.required = (input.stride.0.required*input.extent.0.required) > let output.extent.0.required = (((((((output.s0.x.max - output.s0.x.min)/128)*128) + output.s0.x.min) + 127) + 1) - (output.s0.x.min + 0)) > let output.min.0.required = (output.s0.x.min + 0) > let output.stride.0.required = 1 > let output.extent.1.required = ((output.s0.y.max + 1) - output.s0.y.min) > let output.min.1.required = output.s0.y.min > let output.stride.1.required = (output.stride.0.required*output.extent.0.required) > let input.stride.0.constrained = 1 > let input.min.0.constrained = 0 > let input.stride.1.constrained = ((input.stride.1/128)*128) > let input.min.1.constrained = 0 > let output.stride.0.constrained = 1 > let output.min.0.constrained = 0 > let output.stride.1.constrained = ((output.stride.1/128)*128) > let output.min.1.constrained = 0 > let input.stride.0.proposed = 1 > let input.min.0.proposed = 0 > let input.extent.0.proposed = input.extent.0.required > let input.stride.1.proposed = ((input.stride.1.required/128)*128) > let input.min.1.proposed = 0 > let input.extent.1.proposed = input.extent.1.required > let output.stride.0.proposed = 1 > let output.min.0.proposed = 0 > let output.extent.0.proposed = output.extent.0.required > let output.stride.1.proposed = ((output.stride.1.required/128)*128) > let output.min.1.proposed = 0 > let output.extent.1.proposed = output.extent.1.required > produce output { > let output.s0.y.loop_max = output.s0.y.max > let output.s0.y.loop_min = output.s0.y.min > let output.s0.y.loop_extent = ((output.s0.y.max + 1) - output.s0.y.min) > let output.s0.x.loop_max = output.s0.x.max > let output.s0.x.loop_min = output.s0.x.min > let output.s0.x.loop_extent = ((output.s0.x.max + 1) - output.s0.x.min) > let output.s0.x.x.loop_extent = (((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128) > let output.s0.x.x.loop_max = ((((output.s0.x.loop_max - output.s0.x.loop_min) + 128)/128) - 1) > let output.s0.x.x.loop_min = 0 > let output.s0.x.tmp$1.loop_extent = 128 > let output.s0.x.tmp$1.loop_max = (128 - 1) > let output.s0.x.tmp$1.loop_min = 0 > for (output.s0.y, output.s0.y.loop_min, output.s0.y.loop_extent) { > let output.s0.y.min = output.s0.y > let output.s0.y.max = output.s0.y.min > let output.s0.x.min = (((output.s0.x.x.loop_min*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) > let output.s0.x.max = (((((output.s0.x.x.loop_extent + output.s0.x.x.loop_min)*128) + output.s0.x.loop_min) + -128) + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1)\ > ) > let max_y.s0.y.max = output.s0.y.max > let max_y.s0.y.min = output.s0.y.min > let max_y.s0.x.max = (output.s0.x.max + 1) > let max_y.s0.x.min = (output.s0.x.min + -1) > realize max_y([max_y.x.min_realized, max_y.x.extent_realized], [max_y.y.min_realized, max_y.y.extent_realized]) { > for (output.s0.x.x, output.s0.x.x.loop_min, output.s0.x.x.loop_extent) { > let output.s0.x.tmp$1.base = ((output.s0.x.x*128) + output.s0.x.loop_min) > let output.s0.y.min = output.s0.y > let output.s0.y.max = output.s0.y.min > let output.s0.x.min = (output.s0.x.tmp$1.base + output.s0.x.tmp$1.loop_min) > let output.s0.x.max = (output.s0.x.tmp$1.base + ((output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min) - 1)) > let max_y.s0.y.max = output.s0.y.max > let max_y.s0.y.min = output.s0.y.min > let max_y.s0.x.max = (output.s0.x.max + 1) > let max_y.s0.x.min = select((output.s0.x.x <= output.s0.x.x.loop_min), ((((output.s0.x.x*128) + output.s0.x.loop_min) + output.s0.x.tmp$1.loop_min) + -1), likely((((((output.s0.x.x\ > - 1)*128) + output.s0.x.loop_min) + (output.s0.x.tmp$1.loop_extent + output.s0.x.tmp$1.loop_min)) + 1))) > produce max_y { > let max_y.s0.y.loop_max = max_y.s0.y.max > let max_y.s0.y.loop_min = max_y.s0.y.min > let max_y.s0.y.loop_extent = ((max_y.s0.y.max + 1) - max_y.s0.y.min) > let max_y.s0.x.loop_max = max_y.s0.x.max > let max_y.s0.x.loop_min = max_y.s0.x.min > let max_y.s0.x.loop_extent = ((max_y.s0.x.max + 1) - max_y.s0.x.min) > let max_y.s0.x.x.loop_extent = (((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128) > let max_y.s0.x.x.loop_max = ((((max_y.s0.x.loop_max - max_y.s0.x.loop_min) + 128)/128) - 1) > let max_y.s0.x.x.loop_min = 0 > let max_y.s0.x.tmp.loop_extent = 128 > let max_y.s0.x.tmp.loop_max = (128 - 1) > let max_y.s0.x.tmp.loop_min = 0 > for (max_y.s0.y, max_y.s0.y.loop_min, max_y.s0.y.loop_extent) { > for (max_y.s0.x.x, max_y.s0.x.x.loop_min, max_y.s0.x.x.loop_extent) { > let max_y.s0.x.tmp.base = ((max_y.s0.x.x*128) + max_y.s0.x.loop_min) > vectorized (max_y.s0.x.tmp, max_y.s0.x.tmp.loop_min, max_y.s0.x.tmp.loop_extent) { > let max_y.s0.x = (max_y.s0.x.tmp.base + max_y.s0.x.tmp) > max_y((max_y.s0.x.tmp.base + max_y.s0.x.tmp), max_y.s0.y) = (let t0 = (max_y.s0.x.tmp.base + max_y.s0.x.tmp) in max(input(t0, (max_y.s0.y - 1)), max(input(t0, max_y.s0.y), \ > input(t0, (max_y.s0.y + 1))))) > } > } > } > } > vectorized (output.s0.x.tmp$1, output.s0.x.tmp$1.loop_min, output.s0.x.tmp$1.loop_extent) { > let output.s0.x = (output.s0.x.tmp$1.base + output.s0.x.tmp$1) > output((output.s0.x.tmp$1.base + output.s0.x.tmp$1), output.s0.y) = max(max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) - 1), output.s0.y), max(max_y((output.s0.x.tmp$1.base \ > + output.s0.x.tmp$1), output.s0.y), max_y(((output.s0.x.tmp$1.base + output.s0.x.tmp$1) + 1), output.s0.y))) > } > } > } > } > } > > > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#1820 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AAfdRjE0KumiMaFMH3VsRCw7i78ZAUwiks5r2IargaJpZM4L7Eea> > . >

[pranavb-ca]

What would be the size of the circular buffer? Will it be 130 (128+2)?

max_y(x-1) is computed as shuffle(max_y(x-128), max_y(x), 127, 1, 128)
max_y(x+1) is compute as shuffle(max_y(x), max_y(x+128), 1, 1, 128)

Align loads and LoopCary take care of cycling the input through a set of 3 registers for input(x-128), input(x)), and input(x+1). I was hoping storage folding would do the same for max_y, but storage folding doesn't know max_y(x-1) is shuffle(max_y(x-128), max_y(x), 127, 1, 128).

I need a LoopCarry style scratch space allocation based optimization to reuse max_y(x) and max_y(x+128) in every subsequent iteration

[abadams]

The size of the circular buffer is 256, but only because folding only uses powers of two. Unfortunately it's misaligned, and the store to max wraps around awkwardly. Stores aren't covered by align_loads. If I align_storage then the expressions become too nasty for storage folding again :(

…

On Thu, May 4, 2017 at 5:36 AM, Pranav Bhandarkar ***@***.***> wrote: What would be the size of the circular buffer? Will it be 130 (128+2)? max_y(x-1) is computed as shuffle(max_y(x-128), max_y(x), 127, 1, 128) max_y(x+1) is compute as shuffle(max_y(x), max_y(x+128), 1, 1, 128) Align loads and LoopCary take care of cycling the input through a set of 3 registers for input(x-128), input(x)), and input(x+1). I was hoping storage folding would do the same for max_y, but storage folding doesn't know max_y(x-1) is shuffle(max_y(x-128), max_y(x), 127, 1, 128). I need a LoopCarry style scratch space allocation based optimization to reuse max_y(x) and max_y(x+128) in every subsequent operation. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1820 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAfdRhxaxv7iGFDIA2y3nC1c_d-fujVUks5r2cZlgaJpZM4L7Eea> .

[abadams]

s/align_storage/align_bounds On Thu, May 4, 2017 at 8:02 AM, Andrew Adams <andrew.b.adams@gmail.com> wrote:

…

The size of the circular buffer is 256, but only because folding only uses powers of two. Unfortunately it's misaligned, and the store to max wraps around awkwardly. Stores aren't covered by align_loads. If I align_storage then the expressions become too nasty for storage folding again :( On Thu, May 4, 2017 at 5:36 AM, Pranav Bhandarkar < ***@***.***> wrote: > What would be the size of the circular buffer? Will it be 130 (128+2)? > > max_y(x-1) is computed as shuffle(max_y(x-128), max_y(x), 127, 1, 128) > max_y(x+1) is compute as shuffle(max_y(x), max_y(x+128), 1, 1, 128) > > Align loads and LoopCary take care of cycling the input through a set of > 3 registers for input(x-128), input(x)), and input(x+1). I was hoping > storage folding would do the same for max_y, but storage folding doesn't > know max_y(x-1) is shuffle(max_y(x-128), max_y(x), 127, 1, 128). > > I need a LoopCarry style scratch space allocation based optimization to > reuse max_y(x) and max_y(x+128) in every subsequent operation. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#1820 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AAfdRhxaxv7iGFDIA2y3nC1c_d-fujVUks5r2cZlgaJpZM4L7Eea> > . >

[pranavb-ca]

Thanks.

Is it better then to invest time in a loopcarry like pass that works after max_y(x-1) has been broken down into shuffles?

[abadams]

I think we're stuck on the sliding/folding thing, so yeah if that's an alternative path to good code, it makes sense to me.

…

On Thu, May 4, 2017 at 8:20 AM, Pranav Bhandarkar ***@***.***> wrote: Thanks. Is it better then to invest time in a loopcarry like pass that works after max_y(x-1) has been broken down into shuffles? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1820 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAfdRumNcmgLos0oJdGWARegZmPSebMCks5r2eytgaJpZM4L7Eea> .