| 1 |
module Futhark.Optimise.ArrayLayout.AnalyseTests (tests) where |
| 2 |
|
| 3 |
import Data.Map.Strict qualified as M |
| 4 |
import Futhark.Analysis.AccessPattern |
| 5 |
import Futhark.IR.GPU |
| 6 |
import Futhark.IR.GPUTests () |
| 7 |
import Futhark.IR.SyntaxTests () |
| 8 |
import Test.Tasty |
| 9 |
import Test.Tasty.HUnit |
| 10 |
|
| 11 |
tests :: TestTree |
| 12 |
tests = testGroup "Analyse" [analyseStmTests] |
| 13 |
|
| 14 |
analyseStmTests :: TestTree |
| 15 |
analyseStmTests = |
| 16 |
testGroup |
| 17 |
"analyseStm" |
| 18 |
[analyseIndexTests, analyseDimAccessesTests] |
| 19 |
|
| 20 |
analyseIndexTests :: TestTree |
| 21 |
analyseIndexTests = |
| 22 |
testGroup |
| 23 |
"analyseIndex" |
| 24 |
$ do |
| 25 |
let arr_name = "xss_5144" |
| 26 |
-- ============================= TestCase0 ============================= |
| 27 |
-- Most simple case where we want to manifest an array, hence, we record |
| 28 |
-- the Index in the IndexTable. |
| 29 |
let testCase0 = testCase "2D manifest" $ do |
| 30 |
let ctx = |
| 31 |
mempty |
| 32 |
{ parents = |
| 33 |
[ SegOpName (SegmentedMap "defunc_0_map_res_5204"), |
| 34 |
LoopBodyName "defunc_0_f_res_5208" |
| 35 |
], |
| 36 |
assignments = |
| 37 |
M.fromList |
| 38 |
[ ("gtid_5205", VariableInfo mempty 0 mempty ThreadID), |
| 39 |
("i_5209", VariableInfo mempty 1 mempty LoopVar) |
| 40 |
] |
| 41 |
} |
| 42 |
let patternNames = ["b_5211"] |
| 43 |
let dimFixes = |
| 44 |
[ DimFix (Var "gtid_5205"), |
| 45 |
DimFix (Var "i_5209") |
| 46 |
] |
| 47 |
let indexTable = |
| 48 |
M.fromList |
| 49 |
[ ( SegmentedMap "defunc_0_map_res_5204", |
| 50 |
M.fromList |
| 51 |
[ ( (arr_name, [], [0 .. 1]), |
| 52 |
M.fromList |
| 53 |
[ ( "b_5211", |
| 54 |
[ DimAccess (M.fromList [("gtid_5205", Dependency 0 ThreadID)]) (Just "gtid_5205"), |
| 55 |
DimAccess (M.fromList [("i_5209", Dependency 1 LoopVar)]) (Just "i_5209") |
| 56 |
] |
| 57 |
) |
| 58 |
] |
| 59 |
) |
| 60 |
] |
| 61 |
) |
| 62 |
] |
| 63 |
let (_, indexTable') = analyseIndex ctx patternNames arr_name dimFixes |
| 64 |
indexTable' @?= indexTable |
| 65 |
|
| 66 |
-- ============================= TestCase2 ============================= |
| 67 |
-- We don't want to manifest an array with only one dimension, so we don't |
| 68 |
-- record anything in the IndexTable. |
| 69 |
let testCase1 = testCase "1D manifest" $ do |
| 70 |
let ctx = |
| 71 |
mempty |
| 72 |
{ parents = |
| 73 |
[ SegOpName (SegmentedMap "defunc_0_map_res_5204"), |
| 74 |
LoopBodyName "defunc_0_f_res_5208" |
| 75 |
] |
| 76 |
} |
| 77 |
let patternNames = ["b_5211"] |
| 78 |
let dimFixes = [DimFix "i_5209"] |
| 79 |
|
| 80 |
let (_, indexTable') = analyseIndex ctx patternNames arr_name dimFixes |
| 81 |
indexTable' @?= mempty |
| 82 |
|
| 83 |
-- ============================= TestCase1 ============================= |
| 84 |
-- We don't want to record anything to the IndexTable when the array is |
| 85 |
-- not accessed inside a SegMap |
| 86 |
-- TODO: Create a similar one for MC with loops |
| 87 |
let testCase2 = testCase "Not inside SegMap" $ do |
| 88 |
let ctx = mempty |
| 89 |
let patternNames = ["b_5211"] |
| 90 |
let dimFixes = |
| 91 |
[ DimFix "gtid_5205", |
| 92 |
DimFix "i_5209" |
| 93 |
] |
| 94 |
let (_, indexTable') = analyseIndex ctx patternNames arr_name dimFixes |
| 95 |
indexTable' @?= mempty |
| 96 |
|
| 97 |
-- ============================= TestCase3 ============================= |
| 98 |
-- If an array is allocated inside a loop or SegMap, we want to record that |
| 99 |
-- information in the ArrayName of the IndexTable. |
| 100 |
let testCase3 = testCase "Allocated inside SegMap" $ do |
| 101 |
let parents' = |
| 102 |
[ SegOpName (SegmentedMap "defunc_0_map_res_5204"), |
| 103 |
LoopBodyName "defunc_0_f_res_5208" |
| 104 |
] |
| 105 |
let ctx = |
| 106 |
mempty |
| 107 |
{ parents = parents', |
| 108 |
assignments = |
| 109 |
M.fromList |
| 110 |
[ ("gtid_5205", VariableInfo mempty 0 mempty ThreadID), |
| 111 |
("i_5209", VariableInfo mempty 1 mempty LoopVar), |
| 112 |
(arr_name, VariableInfo mempty 0 parents' Variable) |
| 113 |
] |
| 114 |
} |
| 115 |
let patternNames = ["b_5211"] |
| 116 |
let dimFixes = |
| 117 |
[ DimFix "gtid_5205", |
| 118 |
DimFix "i_5209" |
| 119 |
] |
| 120 |
let indexTable = |
| 121 |
M.fromList |
| 122 |
[ ( SegmentedMap "defunc_0_map_res_5204", |
| 123 |
M.fromList |
| 124 |
[ ( (arr_name, parents', [0 .. 1]), |
| 125 |
M.fromList |
| 126 |
[ ( "b_5211", |
| 127 |
[ DimAccess (M.fromList [("gtid_5205", Dependency 0 ThreadID)]) (Just "gtid_5205"), |
| 128 |
DimAccess (M.fromList [("i_5209", Dependency 1 LoopVar)]) (Just "i_5209") |
| 129 |
] |
| 130 |
) |
| 131 |
] |
| 132 |
) |
| 133 |
] |
| 134 |
) |
| 135 |
] |
| 136 |
let (_, indexTable') = analyseIndex ctx patternNames arr_name dimFixes |
| 137 |
indexTable' @?= indexTable |
| 138 |
|
| 139 |
-- ============================= TestCase4 ============================= |
| 140 |
-- If the vars in the index are temporaries, we want to reduce them to |
| 141 |
-- to the thread IDs and or loop counters they are functions of. |
| 142 |
let testCase4 = testCase "Reduce dependencies" $ do |
| 143 |
let ctx = |
| 144 |
mempty |
| 145 |
{ parents = |
| 146 |
[ SegOpName (SegmentedMap "defunc_0_map_res_5204"), |
| 147 |
LoopBodyName "defunc_0_f_res_5208" |
| 148 |
], |
| 149 |
assignments = |
| 150 |
M.fromList |
| 151 |
[ ("gtid_5205", VariableInfo mempty 0 mempty ThreadID), |
| 152 |
("i_5209", VariableInfo mempty 1 mempty LoopVar), |
| 153 |
("tmp0_5210", VariableInfo (namesFromList ["gtid_5205"]) 2 mempty Variable), |
| 154 |
("tmp1_5211", VariableInfo (namesFromList ["i_5209"]) 3 mempty Variable), |
| 155 |
("k_5212", VariableInfo mempty 1 mempty ConstType) |
| 156 |
] |
| 157 |
} |
| 158 |
let patternNames = ["b_5211"] |
| 159 |
let dimFixes = |
| 160 |
[ DimFix "tmp0_5210", |
| 161 |
DimFix "tmp1_5211", |
| 162 |
DimFix "k_5212" |
| 163 |
] |
| 164 |
let indexTable = |
| 165 |
M.fromList |
| 166 |
[ ( SegmentedMap "defunc_0_map_res_5204", |
| 167 |
M.fromList |
| 168 |
[ ( (arr_name, [], [0 .. 2]), |
| 169 |
M.fromList |
| 170 |
[ ( "b_5211", |
| 171 |
[ DimAccess (M.fromList [("gtid_5205", Dependency 0 ThreadID)]) (Just "tmp0_5210"), |
| 172 |
DimAccess (M.fromList [("i_5209", Dependency 1 LoopVar)]) (Just "tmp1_5211"), |
| 173 |
DimAccess mempty (Just "k_5212") |
| 174 |
] |
| 175 |
) |
| 176 |
] |
| 177 |
) |
| 178 |
] |
| 179 |
) |
| 180 |
] |
| 181 |
let (_, indexTable') = analyseIndex ctx patternNames arr_name dimFixes |
| 182 |
indexTable' @?= indexTable |
| 183 |
|
| 184 |
[testCase0, testCase1, testCase2, testCase3, testCase4] |
| 185 |
|
| 186 |
analyseDimAccessesTests :: TestTree |
| 187 |
analyseDimAccessesTests = testGroup |
| 188 |
"analyseDimAccesses" |
| 189 |
$ do |
| 190 |
let testCase0 = testCase "Fold" $ do |
| 191 |
let indexTable = |
| 192 |
M.fromList |
| 193 |
[ ( SegmentedMap "defunc_0_map_res_5204", |
| 194 |
M.fromList |
| 195 |
[ ( ("xss_5144", [], [0, 1]), |
| 196 |
M.fromList |
| 197 |
[ ( "b_5211", |
| 198 |
[ DimAccess (M.fromList [("gtid_5205", Dependency 0 ThreadID)]) (Just "gtid_5205"), |
| 199 |
DimAccess (M.fromList [("i_5209", Dependency 1 LoopVar)]) (Just "i_5209") |
| 200 |
] |
| 201 |
) |
| 202 |
] |
| 203 |
) |
| 204 |
] |
| 205 |
) |
| 206 |
] |
| 207 |
let indexTable' = (analyseDimAccesses @GPU) prog0 |
| 208 |
indexTable' @?= indexTable |
| 209 |
|
| 210 |
[testCase0] |
| 211 |
where |
| 212 |
prog0 :: Prog GPU |
| 213 |
prog0 = |
| 214 |
"\ |
| 215 |
\entry(\"main\",\ |
| 216 |
\ {xss: [][]i64},\ |
| 217 |
\ {[]i64})\ |
| 218 |
\ entry_main (n_5142 : i64,\ |
| 219 |
\ m_5143 : i64,\ |
| 220 |
\ xss_5144 : [n_5142][m_5143]i64)\ |
| 221 |
\ : {[n_5142]i64#([2], [0])} = {\ |
| 222 |
\ let {segmap_group_size_5202 : i64} =\ |
| 223 |
\ get_size(segmap_group_size_5190, thread_block_size)\ |
| 224 |
\ let {segmap_usable_groups_5203 : i64} =\ |
| 225 |
\ sdiv_up64(n_5142, segmap_group_size_5202)\ |
| 226 |
\ let {defunc_0_map_res_5204 : [n_5142]i64} =\ |
| 227 |
\ segmap(thread; ; grid=segmap_usable_groups_5203; blocksize=segmap_group_size_5202)\ |
| 228 |
\ (gtid_5205 < n_5142) (~phys_tid_5206) : {i64} {\ |
| 229 |
\ let {defunc_0_f_res_5208 : i64} =\ |
| 230 |
\ loop {acc_5210 : i64} = {0i64}\ |
| 231 |
\ for i_5209:i64 < m_5143 do {\ |
| 232 |
\ let {b_5211 : i64} =\ |
| 233 |
\ xss_5144[gtid_5205, i_5209]\ |
| 234 |
\ let {defunc_0_f_res_5212 : i64} =\ |
| 235 |
\ add64(acc_5210, b_5211)\ |
| 236 |
\ in {defunc_0_f_res_5212}\ |
| 237 |
\ }\ |
| 238 |
\ return {returns defunc_0_f_res_5208}\ |
| 239 |
\ }\ |
| 240 |
\ in {defunc_0_map_res_5204}\ |
| 241 |
\}" |