Debian Codegraph @

src-testing/Futhark/Optimise/ArrayLayout/AnalyseTests.hs

raw
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 \}"