2020-07-22

So, what's the status?

For now, we're only concerned with kernels. We know that all allocations and array initializations that we have to look at take place inside those kernels. Allocations can still be hoisted to the top of the kernel, and we preferably still want to be able to run the pass multiple times, but not after the ExpandAllocations pass has run. In addition, we should be a bit more conservative when creating our interference graph for loops and nested kernels.

This means that we are mostly concerned with kernels that look like this:

1: SegMap_n {
2:   let xs_mem = alloc x
3:   let xs@xs_mem = ...
4:   ...
5:   let ys_mem = alloc y
6:   let ys@ys_mem = ...
7: }

Although it can also be a nested map with an outer SegMapGroup. So let's imagine we have a pass that runs through the program, and then when it hits a kernel it runs the analyseBody and optimiseBody functions from yesterday.

Let's paste it here as well, so we know what we're talking about:

analyseStm :: LastUseMap -> InUse -> MemGraph -> Stm -> (InUse, LastUsed, MemGraph, Stm)
analyseStm lu_map inuse graph (let p = exp) =
  let (inuse_new, lus_new, graph_new, stm_new) =
    if exp is a loop with body b then
      let (inuse', lus, graph', b') = analyseBody lu_map b
      let graph'' = graph ∪ graph' ∪ (inuse ↔ (inuse' ∪ lus))
      let inuse'' = inuse ∖ lus ∪ inuse'
      in (inuse'', lus, graph'', let p = exp with b')
    else if exp is a if with bodies b1, b2 then
      let (inuse1, lus1, g1, b1') = analyseBody lu_map b1
      let (inuse2, lus2, g2, b2') = analyseBody lu_map b2
      let lus = lus1 ∪ lus2
      let inuse' = (inuse ∪ inuse1 ∪ inuse2) ∖ lus
      let g = graph ∪ g1 ∪ g2
                ∪ ((inuse1 ∪ lus1) ↔ (inuse ∖ (lus2 ∖ lus1)))
                ∪ ((inuse2 ∪ lus2) ↔ (inuse ∖ (lus1 ∖ lus2)))
      in (inuse', lus, g, let p = exp with b1' and b2')
    else if exp is a kernel call with a body b then
      same as loop†
    else
      let lus = lookup p in lu_map
      let lus_mems = memory blocks referenced in lus
      let inuse' = inuse ∖ lus_mems
      in (inuse'', lus_mems, graph, stm)

  let mems = memory blocks referenced in p
  let inuse_end = inuse_new ∪ mems
  let graph_end = graph_new ∪ (inuse_end ↔ inuse_end)
  in (inuse_end, lus_new, graph_end, stm_new)

The first thing we need to do, is make sure any memory blocks referenced in p interferes with the memory blocks inside exp.

analyseStm :: LastUseMap -> InUse -> MemGraph -> Stm -> (InUse, LastUsed, MemGraph, Stm)
analyseStm lu_map inuse0 graph0 (let p = exp) =
  let mems = memory blocks referenced in p
  let inuse = inuse0 ∪ mems
  let graph = graph0 ∪ (inuse ↔ inuse)

  if exp is a loop with body b then
    let (inuse', lus, graph', b') = analyseBody lu_map b
    let graph'' = graph ∪ graph' ∪ (inuse ↔ (inuse' ∪ lus))
    let inuse'' = inuse ∖ lus ∪ inuse'
    in (inuse'', lus, graph'', let p = exp with b')
  else if exp is a if with bodies b1, b2 then
    let (inuse1, lus1, g1, b1') = analyseBody lu_map b1
    let (inuse2, lus2, g2, b2') = analyseBody lu_map b2
    let lus = lus1 ∪ lus2
    let inuse' = (inuse ∪ inuse1 ∪ inuse2) ∖ lus
    let g = graph ∪ g1 ∪ g2
              ∪ ((inuse1 ∪ lus1) ↔ (inuse ∖ (lus2 ∖ lus1)))
              ∪ ((inuse2 ∪ lus2) ↔ (inuse ∖ (lus1 ∖ lus2)))
    in (inuse', lus, g, let p = exp with b1' and b2')
  else if exp is a kernel call with a body b then
    same as loop†
  else
    let lus = lookup p in lu_map
    let lus_mems = memory blocks referenced in lus
    let inuse' = inuse ∖ lus_mems
    in (inuse'', lus_mems, graph, stm)

That should do it.

I kinda want to just go ahead and implement this now…

Well, it didn't happen today. I think I'll jump into it tomorrow.