2020-07-16
Linear scan, continued
Yesterday, and today
Yesterday, I spent most of the day implementing the linear scan algorithm and
refining the last-use analysis. Except for aliases, at the end of the day, my
ReuseAllocations pass (the name I've chosen for the implementation of the
linear scan algorithm) was able to keep track of allocations and frees
throughout a program, including inside kernels and other blocks. However,
because my pipeline didn't perform common subexpression elimintation, I ended up
not actually reusing any memory, because each alloc would use a distinct
subexpression. Thankfully, today, Troels pointed out that in order to get common
subexpression elimination, I just need to insert the
`Futhark.Optimise.CSE.performCSE` pass in my pipeline.
Consider the following program, which I've called psum:
1: let psum = scan (+) 0 2: 3: let main (xss: [][]i32) = 4: #[incremental_flattening(only_intra)] 5: map (psum >-> psum >-> psum) 6: xss
Using my ReuseAllocations pass, I can generate the following code:
1: -- xss_247 : [impl₀_245][impl₁_246]i32@@xss_mem_760-> 2: -- {base: [impl₀_245, impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; 3: -- strides: [impl₁_246, 1i32]; 4: -- rotates: [0i32, 0i32]; 5: -- shape: [impl₀_245, impl₁_246]; 6: -- permutation: [0, 1]; 7: -- monotonicity: [Inc, Inc]}]} 8: entry {*[?0][?1]i32@?2-> 9: {base: [?0, ?1]; contiguous: True; LMADs: [{offset: 0i32; 10: strides: [?1, 1i32]; 11: rotates: [0i32, 0i32]; 12: shape: [?0, ?1]; 13: permutation: [0, 1]; 14: monotonicity: [Inc, Inc]}]}} 15: main (mem xss_mem_760, i32 impl₀_245, i32 impl₁_246, 16: [impl₀_245][impl₁_246]i32 xss_247) = { 17: #[incremental_flattening(only_intra)] 18: let {i64 binop_x_775} = sext i32 impl₀_245 to i64 19: #[incremental_flattening(only_intra)] 20: let {i64 binop_y_776} = sext i32 impl₁_246 to i64 21: #[incremental_flattening(only_intra)] 22: let {i64 binop_x_777} = mul_nw64(binop_x_775, binop_y_776) 23: #[incremental_flattening(only_intra)] 24: let {i64 bytes_774} = mul_nw64(4i64, binop_x_777) 25: #[incremental_flattening(only_intra)] 26: let {mem mem_778} = 27: alloc(bytes_774) 28: let {i64 binop_x_764} = binop_y_776 29: let {i64 bytes_763} = mul_nw64(4i64, binop_y_776) 30: let {i64 binop_x_768} = binop_y_776 31: let {i64 bytes_767} = bytes_763 32: let {i64 binop_x_772} = binop_y_776 33: let {i64 bytes_771} = bytes_763 34: #[incremental_flattening(only_intra)] 35: -- res_409 : [impl₀_245][impl₁_246]i32@@mem_778-> 36: -- {base: [impl₀_245, impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; 37: -- strides: [impl₁_246, 1i32]; 38: -- rotates: [0i32, 0i32]; 39: -- shape: [impl₀_245, impl₁_246]; 40: -- permutation: [0, 1]; 41: -- monotonicity: [Inc, Inc]}]} 42: let {[impl₀_245][impl₁_246]i32 res_409} = 43: segmap_group 44: (#groups=impl₀_245; groupsize=impl₁_246) 45: (gtid_292 < impl₀_245) (~phys_tid_305) : {[impl₁_246]i32} { 46: let {mem@local mem_765} = 47: alloc(bytes_763, @local) 48: -- resarr0_416 : [impl₁_246]i32@@mem_765-> 49: -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 50: -- rotates: [0i32]; 51: -- shape: [impl₁_246]; 52: -- permutation: [0]; 53: -- monotonicity: [Inc]}]} 54: let {[impl₁_246]i32 resarr0_416} = 55: segscan_thread 56: (#groups=impl₀_245; groupsize=impl₁_246) 57: ({{0i32}, 58: [], 59: fn {i32} (i32 x_417, i32 x_418) => 60: let {i32 res_419} = add32(x_417, x_418) 61: in {res_419}}) 62: (gtid_295 < impl₁_246) (~phys_tid_296) : {i32} { 63: let {i32 x_420} = xss_247[gtid_292, gtid_295] 64: return {returns x_420} 65: } 66: let {mem@local mem_769} = 67: alloc(bytes_763, @local) 68: -- resarr0_426 : [impl₁_246]i32@@mem_769-> 69: -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 70: -- rotates: [0i32]; 71: -- shape: [impl₁_246]; 72: -- permutation: [0]; 73: -- monotonicity: [Inc]}]} 74: let {[impl₁_246]i32 resarr0_426} = 75: segscan_thread 76: (#groups=impl₀_245; groupsize=impl₁_246) 77: ({{0i32}, 78: [], 79: fn {i32} (i32 x_427, i32 x_428) => 80: let {i32 res_429} = add32(x_427, x_428) 81: in {res_429}}) 82: (gtid_297 < impl₁_246) (~phys_tid_298) : {i32} { 83: let {i32 x_430} = resarr0_416[gtid_297] 84: return {returns x_430} 85: } 86: -- mem_773 aliases mem_765 87: let {mem@local mem_773} = mem_765 88: -- resarr0_435 : [impl₁_246]i32@@mem_773-> 89: -- {base: [impl₁_246]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 90: -- rotates: [0i32]; 91: -- shape: [impl₁_246]; 92: -- permutation: [0]; 93: -- monotonicity: [Inc]}]} 94: let {[impl₁_246]i32 resarr0_435} = 95: segscan_thread 96: (#groups=impl₀_245; groupsize=impl₁_246) 97: ({{0i32}, 98: [], 99: fn {i32} (i32 x_436, i32 x_437) => 100: let {i32 res_438} = add32(x_436, x_437) 101: in {res_438}}) 102: (gtid_299 < impl₁_246) (~phys_tid_300) : {i32} { 103: let {i32 x_439} = resarr0_426[gtid_299] 104: return {returns x_439} 105: } 106: return {returns resarr0_435} 107: } 108: in {impl₀_245, impl₁_246, mem_778, res_409} 109: }
Notice that mem_765 is not being reused on line 66, because it's not free
until after line 83. However, on line 87, resarr0_416 and it's
associated memory block mem_765 is free, and we can therefore assign mem_773
to mem_765.
It also works on a program which consumes an array by doing in-place updates:
1: let main (n: i32): i32= 2: let xs = iota(10) 3: let xs[1] = xs[0] 4: 5: let x = reduce (+) 0 xs 6: 7: let ys = iota(10) 8: let ys[1] = ys[0] 9: 10: let y = reduce (+) 0 (scan (+) 0 ys) 11: 12: in x + y
The program above becomes
1: entry {i32} main (i32 n_186) = { 2: let {mem mem_260} = 3: alloc(40i64) 4: -- res_187 : [10i32]i32@@mem_260-> 5: -- {base: [10i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 6: -- rotates: [0i32]; shape: [10i32]; 7: -- permutation: [0]; 8: -- monotonicity: [Inc]}]} 9: let {[10i32]i32 res_187} = iota32(10i32, 0i32, 1i32) 10: -- xs_188 : [10i32]i32@@mem_260-> 11: -- {base: [10i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 12: -- rotates: [0i32]; shape: [10i32]; 13: -- permutation: [0]; 14: -- monotonicity: [Inc]}]} 15: let {[10i32]i32 xs_188} = 16: -- Consumes res_187 17: res_187 with [1i32] <- 0i32 18: let {mem mem_263} = 19: alloc(40i64) 20: -- res_189 : [10i32]i32@@mem_263-> 21: -- {base: [10i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 22: -- rotates: [0i32]; shape: [10i32]; 23: -- permutation: [0]; 24: -- monotonicity: [Inc]}]} 25: let {[10i32]i32 res_189} = iota32(10i32, 0i32, 1i32) 26: -- ys_190 : [10i32]i32@@mem_263-> 27: -- {base: [10i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 28: -- rotates: [0i32]; shape: [10i32]; 29: -- permutation: [0]; 30: -- monotonicity: [Inc]}]} 31: let {[10i32]i32 ys_190} = 32: -- Consumes res_189 33: res_189 with [1i32] <- 0i32 34: let {i32 segred_group_size_227} = 35: get_size(segred_group_size_226, group_size) 36: let {i32 num_groups_229} = 37: calc_num_groups(10i64, segred_num_groups_228, segred_group_size_227) 38: let {mem mem_267} = 39: alloc(4i64) 40: -- acc0_231 : [1i32]i32@@mem_267-> 41: -- {base: [1i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 42: -- rotates: [0i32]; shape: [1i32]; 43: -- permutation: [0]; 44: -- monotonicity: [Inc]}]} 45: let {[1i32]i32 acc0_231} = 46: segred_thread 47: (#groups=num_groups_229; groupsize=segred_group_size_227) 48: ({{0i32}, 49: [], 50: commutative fn {i32} (i32 x_201, i32 x_202) => 51: let {i32 res_203} = add32(x_201, x_202) 52: in {res_203}}) 53: (dummy_232 < 1i32, gtid_233 < 10i32) (~phys_tid_234) : {i32} { 54: let {i32 x_204} = xs_188[gtid_233] 55: return {returns x_204} 56: } 57: let {i32 acc0_200} = acc0_231[0i32] 58: let {i32 segscan_group_size_238} = 59: get_size(segscan_group_size_237, group_size) 60: let {i32 num_groups_240} = 61: calc_num_groups(10i64, segscan_num_groups_239, segscan_group_size_238) 62: -- mem_271 aliases mem_260 63: let {mem mem_271} = mem_260 64: -- resarr0_206 : [10i32]i32@@mem_271-> 65: -- {base: [10i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 66: -- rotates: [0i32]; shape: [10i32]; 67: -- permutation: [0]; 68: -- monotonicity: [Inc]}]} 69: let {[10i32]i32 resarr0_206} = 70: segscan_thread 71: (#groups=num_groups_240; groupsize=segscan_group_size_238) 72: ({{0i32}, 73: [], 74: fn {i32} (i32 x_207, i32 x_208) => 75: let {i32 res_209} = add32(x_207, x_208) 76: in {res_209}}) 77: (gtid_242 < 10i32) (~phys_tid_243) : {i32} { 78: let {i32 x_210} = ys_190[gtid_242] 79: return {returns x_210} 80: } 81: let {i32 segred_group_size_247} = 82: get_size(segred_group_size_246, group_size) 83: let {i32 num_groups_249} = 84: calc_num_groups(10i64, segred_num_groups_248, segred_group_size_247) 85: -- mem_275 aliases mem_267 86: let {mem mem_275} = mem_267 87: -- acc0_251 : [1i32]i32@@mem_275-> 88: -- {base: [1i32]; contiguous: True; LMADs: [{offset: 0i32; strides: [1i32]; 89: -- rotates: [0i32]; shape: [1i32]; 90: -- permutation: [0]; 91: -- monotonicity: [Inc]}]} 92: let {[1i32]i32 acc0_251} = 93: segred_thread 94: (#groups=num_groups_249; groupsize=segred_group_size_247) 95: ({{0i32}, 96: [], 97: commutative fn {i32} (i32 x_217, i32 x_218) => 98: let {i32 res_219} = add32(x_217, x_218) 99: in {res_219}}) 100: (dummy_252 < 1i32, gtid_253 < 10i32) (~phys_tid_254) : {i32} { 101: let {i32 x_220} = resarr0_206[gtid_253] 102: return {returns x_220} 103: } 104: let {i32 acc0_216} = acc0_251[0i32] 105: let {i32 res_223} = add32(acc0_200, acc0_216) 106: in {res_223} 107: }
Again, we can see on line 63 that mem_260 is being reused, but not until
after it's associated array res_187 and xs_188 go out of scope on lines
17 and 54, respectively.
There are still some test programs that don't work. The one below is called
if.fut, and in the ideal case, our pass should be able to spot that inside the
else branch, xs is able to be freely used. In other words, the indices xs
call on line 8 should be able to reuse the allocation for xs.
1: let main (n: i32): *[]i32 = 2: let xs = iota(n) 3: let xs[1] = xs[0] 4: let ys = 5: if xs[0] > 0 then 6: xs 7: else 8: indices xs 9: 10: let ys[2] = 4 11: in ys
I'm also concerned that actual aliasing isn't handled nicely by my last-use analysis, but I don't yet have any programs that demonstrate the problem. I'll have to get back to that at some point.
Psedo-code
Let's finally try to write down some pseudo-code for the linear-scan.
First, we need to define what data structures we'll be working with. In the
following, VName is a unique name for a variable in the futhark IR, while
SubExp can be either a VName or some constant.
type Frees = [(VName, SubExp)] type Allocs = [(VName, SubExp)] type LastUseMap = Map VName [VName]
The Frees and Allocs lists consist of pairs of VName and SubExp. A given
(vname, sexp) pair in an Allocs list means that a memory block with name
vname and size sexp has been allocated. Once the array using that memory
block are beyond their last-use, the pair is instead added to a Frees list, to
indicate that the particular memory block is free.
LastUseMap is a map from VName to a list of VName. Because each statement
in the Futhark IR is uniquely determined by the name of the first element in the
let pattern, the LastUseMap allows us to map statements to a list of VName
that are last-used in the expression within the statement. Hence, in any given
statement in the Futhark IR, we can use the LastUseMap to find out which
variables are free after that statement.
The basic algorithm then consists of the following
optimiseStm :: LastUseMap -> Alllocs -> Frees -> Stm -> (Allocs, Frees, Stm)
optimiseStm lu_map allocs frees (let p = exp) =
if exp is an allocation then
if there is a memory block x of appropriate size in frees then
return (allocs with (p, size of allocation), frees without x, let p = x)
else
return (allocs with (p, size of allocation), frees, let p = exp)
else if exp contains a body of stms (scope) b then
let (allocs', frees', b') = optimiseBody lu_map allocs frees b
return (allocs', frees', let p = exp with b')
else
let lus = lookup p in lu_map
let new_frees = map (memAndSize allocs) on lus
return (allocs, frees and new_frees, let p = exp)
Here, optimiseBody is just a function which calls optimiseStm on the
statements in a block, while memAndSize looks up the memory block (if any) of
a given VName, and returns the size of that memory block using the allocs
list.
Note about boolean in performCSE
While adding the CSE pass to my tests, which got ReuseAllocations to actually
do something useful on psum.fut, I noticed that it has a boolean argument
that's not very well documented.
Here's what Troels had to say:
07:01:35 munksgaard | Athas: Perfect! What does the boolean argument to performCSE do?
07:21:19 Athas | munksgaard: whether or not to perform CSE on expressions producing arrays.
07:27:14 munksgaard | And why would you not want that?
07:27:29 munksgaard | I see it's disabled in the GPU pipeline, for instance
07:58:37 Athas | It's disabled after we add memory information, because at that point arrays have identity beyond their value, and doing CSE on them may
| not be safe.
07:59:13 Athas | Although this is an old design, and maybe our representation of memory has improved since then. You can always try setting it to True
| and see if anything breaks.
I'm going to try to compile a version of Futhark that always performs CSE (by
setting that parameter to True) and see if it passes our tests and
benchmarks. If it turns out that we don't need it any more, I'll remove it from
the code. Otherwise, I'll add some notes in the documentation about what it
does.
Here are the results with my modified version of Futhark which always performs CSE on expressions producing arrays:
$ futhark test --backend=opencl --exclude=no_opencl tests/
tests/issue715.fut:
Compiling with --backend=opencl:
Running compiled program:
Running ./tests/issue715 -e main:
Entry point: main; dataset: #0 ("true"):
tests/issue715.fut.main.0.actual and tests/issue715.fut.main.0.expected do not match:
Value (1,0) expected 0i32, got 2i32
Entry point: main; dataset: #1 ("false"):
tests/issue715.fut.main.1.actual and tests/issue715.fut.main.1.expected do not match:
Value (1,0) expected 1i32, got 2i32
┌──────────┬────────┬────────┬───────────┐
│ │ passed │ failed │ remaining │
├──────────┼────────┼────────┼───────────┤
│ programs │ 1432 │ 1 │ 0/1433 │
├──────────┼────────┼────────┼───────────┤
│ runs │ 2532 │ 2 │ 0/2534 │
└──────────┴────────┴────────┴───────────┘
(3 program(s) excluded).
I'll add some documentation instead.
Here is the pull request.
Add ReuseAllocations as a real Pass in Futhark
It is done: https://github.com/diku-dk/futhark/tree/reuse-allocations
I think this will be an easier way to test things, going forward. To begin with, I might just use it to run all the existing tests to see how many of them fail with my changes.
Running the tests
Well, first of all, here are the errors I got when trying to run the futhark tests using my new pass:
$ futhark test --backend=opencl --exclude=no_opencl tests/
tests/fusion/Vers2.0/redomap0.fut:
Compiling with --backend=opencl:
Running compiled program:
Running ./tests/fusion/Vers2.0/redomap0 -e main:
Entry point: main; dataset: #0 ("[1.0f32, -4.0f32, -2.4f32]"):
tests/fusion/Vers2.0/redomap0.fut.main.0.actual and tests/fusion/Vers2.0/redomap0.fut.main.0.expected do not match:
Value (1,0) expected 2.0f32, got 3.0f32
tests/fusion/Vers2.0/mapored1.fut:
Compiling with --backend=opencl:
Running compiled program:
Running ./tests/fusion/Vers2.0/mapored1 -e main:
Entry point: main; dataset: #0 ("[1.0f64, -4.0f64, -2.4f64]"):
tests/fusion/Vers2.0/mapored1.fut.main.0.actual and tests/fusion/Vers2.0/mapored1.fut.main.0.expected do not match:
Value (1,0) expected 12.0f64, got 40.0f64
tests/fusion/Vers2.0/redomap1.fut:
Compiling with --backend=opencl:
Running compiled program:
Running ./tests/fusion/Vers2.0/redomap1 -e main:
Entry point: main; dataset: #0 ("[1.0f32, -4.0f32, -2.4f32]"):
tests/fusion/Vers2.0/redomap1.fut.main.0.actual and tests/fusion/Vers2.0/redomap1.fut.main.0.expected do not match:
Value (1,0) expected 2.0f32, got 4.0f32
tests/fusion/Vers2.0/redoredomapomap0.fut:
Compiling with --backend=opencl:
Running compiled program:
Running ./tests/fusion/Vers2.0/redoredomapomap0 -e main:
Entry point: main; dataset: #0 ("[1.0f64, -4.0f64, -2.4f64]"):
tests/fusion/Vers2.0/redoredomapomap0.fut.main.0.actual and tests/fusion/Vers2.0/redoredomapomap0.fut.main.0.expected do not match:
Value (1,0) expected 2.0f64, got 0.0f64
tests/badentry2.fut:
Compiling with --backend=opencl:
Expected warning:
^$
Got warnings:
allocs: []
frees: []
analyseStm res_11 aliases [] lus' [res_23]
analyseStm res_14 aliases [] lus' [x_12, x_13]
analyseStm x_15 aliases [] lus' [as_10, gtid_25]
analyseStm res_23 aliases [] lus' [segred_group_size_19, num_groups_21]
analyseStm mem_32 aliases [] lus' []
analyseStm num_groups_21 aliases [] lus' [n₀_16]
analyseStm segred_group_size_19 aliases [] lus' []
analyseStm n₀_16 aliases [] lus' [n₀_9]
n₀_16 adding new frees: [] to already [] from lus: [n₀_9] and allocs: []
segred_group_size_19 adding new frees: [] to already [] from lus: [] and allocs: []
num_groups_21 adding new frees: [] to already [] from lus: [n₀_16] and allocs: []
mem_32 frees []
x_15 adding new frees: [] to already [] from lus: [as_10, gtid_25] and allocs: [(mem_32, 4i64)]
res_14 adding new frees: [] to already [] from lus: [x_12, x_13] and allocs: [(mem_32, 4i64)]
res_11 adding new frees: [(mem_32, 4i64)] to already [] from lus: [res_23] and allocs: [(mem_32, 4i64)]
res_14 adding new frees: [] to already [] from lus: [x_12, x_13] and allocs: [(mem_32, 4i64)]
res_11 adding new frees: [(mem_32, 4i64)] to already [] from lus: [res_23] and allocs: [(mem_32, 4i64)]
allocs: [(mem_32, 4i64)]
frees: [(mem_32, 4i64)]
tests/badentry4.fut:
Compiling with --backend=opencl:
Expected warning:
^$
Got warnings:
allocs: []
frees: []
mem_6 frees []
analyseStm res_3 aliases [] lus' [x_2]
analyseStm mem_6 aliases [] lus' []
res_3 adding new frees: [] to already [] from lus: [x_2] and allocs: [(mem_6, 4i64)]
allocs: [(mem_6, 4i64)]
frees: []
tests/badentry3.fut:
Compiling with --backend=opencl:
Expected warning:
^$
Got warnings:
allocs: []
frees: []
mem_6 frees []
analyseStm res_3 aliases [] lus' [x_2]
analyseStm mem_6 aliases [] lus' []
res_3 adding new frees: [] to already [] from lus: [x_2] and allocs: [(mem_6, 4i64)]
allocs: [(mem_6, 4i64)]
frees: []
tests/badentry8.fut:
Compiling with --backend=opencl:
Expected warning:
^$
Got warnings:
allocs: []
frees: []
allocs: []
frees: []
┌──────────┬────────┬────────┬───────────┐
│ │ passed │ failed │ remaining │
├──────────┼────────┼────────┼───────────┤
│ programs │ 1426 │ 8 │ 0/1434 │
├──────────┼────────┼────────┼───────────┤
│ runs │ 2528 │ 8 │ 0/2536 │
└──────────┴────────┴────────┴───────────┘
(3 program(s) excluded).
Most of those are just caused by the debugging messages I'm outputting, but the fusion failures are probably right. I'll have to look into what exactly is going wrong in each case.
Futhark meeting
At the meeting today, I presented the algorithm above, and we had a nice discussion about it. Cosmin correctly pointed out that it assumes that allocations are quickly followed by their first-uses, in which an array is created in the allocated memory block. However, we cannot assume that that is always the case. In some cases, allocations are hoisted, so a program looks like the following example written by Troels:
let xs_mem = alloc ... let ys_mem = alloc ... ... let xs@xs_mem = ... ... ... last use of xs ... ... let ys@ys_mem = ... ... in ys -- or whatever
In order to handle that, we'll need to keep track of initial uses of memory blocks, in addition to their allocations.
There's also the additional complication that we want the pass to be able to run multiple times. Imagine that we've optimised the program above so that it looks like this:
let xs_mem = alloc ... let ys_mem = alloc ... ... let xs@xs_mem = ... ... ... last use of xs ... ... let ys@xs_mem = ... ... in ys -- or whatever
Now, our naive approach might find that xs_mem is last-used at the same time
as xs, but that's no longer the case.
Futhark highlighting in bat
I've been wanting this for a while, but I didn't want to have to write yet another syntax definition for Futhark. Thankfully, I realized that titouanc has already done the hard work and created a Futhark syntax highlighter for Sublime Text 3. Here are the commands I ran to get highlighting to work (adapted from this guide):
mkdir -p "$(bat --config-dir)/syntaxes" cd "$(bat --config-dir)/syntaxes" git clone git@github.com:titouanc/sublime-futhark.git bat cache --build
It would be nice to set that up automatically as part of my NixOS configuration, but I'm too lazy to figure out how to do that right now.
The Common Lisp Condition System
ICFP 2020 contest
The ICFP 2020 contest is coming up, and it looks like a lot of fun! I actually have time to do this for once, so I might give it a try over the weekend. Perhaps I'll post some technical diary entries for that.
Tomorrow
Think about the problems discussed in the section above, and see if I can amend the pseudocode to alleviate those problems. We might need a two-pass approach: One to gather the arrays, memory blocks and their last uses, and one to merge memory blocks by assignment.