Debian Codegraph @

src/Futhark/Pass/ExtractKernels/Interchange.hs

raw
1 {-# LANGUAGE TypeFamilies #-}
2
3 -- | It is well known that fully parallel loops can always be
4 -- interchanged inwards with a sequential loop. This module
5 -- implements that transformation.
6 --
7 -- This is also where we implement loop-switching (for branches),
8 -- which is semantically similar to interchange.
9 module Futhark.Pass.ExtractKernels.Interchange
10 ( SeqLoop (..),
11 interchangeLoops,
12 Branch (..),
13 interchangeBranch,
14 WithAccStm (..),
15 interchangeWithAcc,
16 )
17 where
18
19 import Control.Monad
20 import Data.List (find)
21 import Data.Maybe
22 import Futhark.IR.SOACS
23 import Futhark.MonadFreshNames
24 import Futhark.Pass.ExtractKernels.Distribution
25 ( KernelNest,
26 LoopNesting (..),
27 kernelNestLoops,
28 scopeOfKernelNest,
29 )
30 import Futhark.Tools
31 import Futhark.Transform.Rename
32 import Futhark.Util (splitFromEnd)
33
34 -- | An encoding of a sequential do-loop with no existential context,
35 -- alongside its result pattern.
36 data SeqLoop
37 = SeqLoop [Int] (Pat Type) [(FParam SOACS, SubExp)] LoopForm (Body SOACS)
38
39 loopPerm :: SeqLoop -> [Int]
40 loopPerm (SeqLoop perm _ _ _ _) = perm
41
42 seqLoopStm :: SeqLoop -> Stm SOACS
43 seqLoopStm (SeqLoop _ pat merge form body) =
44 Let pat (defAux ()) $ Loop merge form body
45
46 interchangeLoop ::
47 (MonadBuilder m, Rep m ~ SOACS) =>
48 (VName -> Maybe VName) ->
49 SeqLoop ->
50 LoopNesting ->
51 m SeqLoop
52 interchangeLoop
53 isMapParameter
54 (SeqLoop perm loop_pat merge form body)
55 (MapNesting pat aux w params_and_arrs) = do
56 merge_expanded <-
57 localScope (scopeOfLParams $ map fst params_and_arrs) $
58 mapM expand merge
59
60 let loop_pat_expanded =
61 Pat $ map expandPatElem $ patElems loop_pat
62 new_params =
63 [Param attrs pname $ fromDecl ptype | (Param attrs pname ptype, _) <- merge]
64 new_arrs = map (paramName . fst) merge_expanded
65 rettype = map rowType $ patTypes loop_pat_expanded
66
67 -- If the map consumes something that is bound outside the loop
68 -- (i.e. is not a merge parameter), we have to copy() it. As a
69 -- small simplification, we just remove the parameter outright if
70 -- it is not used anymore. This might happen if the parameter was
71 -- used just as the inital value of a merge parameter.
72 ((params', arrs'), pre_copy_stms) <-
73 runBuilder $
74 localScope (scopeOfLParams new_params) $
75 unzip . catMaybes <$> mapM copyOrRemoveParam params_and_arrs
76
77 let lam = Lambda (params' <> new_params) rettype body
78 map_stm =
79 Let loop_pat_expanded aux $
80 Op $
81 Screma w (arrs' <> new_arrs) (mapSOAC lam)
82 res = varsRes $ patNames loop_pat_expanded
83 pat' = Pat $ rearrangeShape perm $ patElems pat
84
85 pure $
86 SeqLoop perm pat' merge_expanded form $
87 mkBody (pre_copy_stms <> oneStm map_stm) res
88 where
89 free_in_body = freeIn body
90
91 copyOrRemoveParam (param, arr)
92 | paramName param `notNameIn` free_in_body =
93 pure Nothing
94 | otherwise =
95 pure $ Just (param, arr)
96
97 expandedInit _ (Var v)
98 | Just arr <- isMapParameter v =
99 pure $ Var arr
100 expandedInit param_name se =
101 letSubExp (param_name <> "_expanded_init") $
102 BasicOp $
103 Replicate (Shape [w]) se
104
105 expand (merge_param, merge_init) = do
106 expanded_param <-
107 newParam (param_name <> "_expanded") $
108 -- FIXME: Unique here is a hack to make sure the copy from
109 -- makeCopyInitial is not prematurely simplified away.
110 -- It'd be better to fix this somewhere else...
111 arrayOf (paramDeclType merge_param) (Shape [w]) Unique
112 expanded_init <- expandedInit param_name merge_init
113 pure (expanded_param, expanded_init)
114 where
115 param_name = baseString $ paramName merge_param
116
117 expandPatElem (PatElem name t) =
118 PatElem name $ arrayOfRow t w
119
120 -- We need to copy some initial arguments because otherwise the result
121 -- of the loop might alias the input (if the number of iterations is
122 -- 0), which is a problem if the result is consumed.
123 maybeCopyInitial ::
124 (MonadBuilder m) =>
125 (VName -> Bool) ->
126 SeqLoop ->
127 m SeqLoop
128 maybeCopyInitial isMapInput (SeqLoop perm loop_pat merge form body) =
129 SeqLoop perm loop_pat <$> mapM f merge <*> pure form <*> pure body
130 where
131 f (p, Var arg)
132 | isMapInput arg,
133 Array {} <- paramType p =
134 (p,)
135 <$> letSubExp
136 (baseString (paramName p) <> "_inter_copy")
137 (BasicOp $ Replicate mempty $ Var arg)
138 f (p, arg) =
139 pure (p, arg)
140
141 manifestMaps :: [LoopNesting] -> [VName] -> Stms SOACS -> ([VName], Stms SOACS)
142 manifestMaps [] res stms = (res, stms)
143 manifestMaps (n : ns) res stms =
144 let (res', stms') = manifestMaps ns res stms
145 (params, arrs) = unzip $ loopNestingParamsAndArrs n
146 lam =
147 Lambda
148 params
149 (map rowType $ patTypes (loopNestingPat n))
150 (mkBody stms' $ varsRes res')
151 in ( patNames $ loopNestingPat n,
152 oneStm $
153 Let (loopNestingPat n) (loopNestingAux n) $
154 Op $
155 Screma (loopNestingWidth n) arrs (mapSOAC lam)
156 )
157
158 -- | Given a (parallel) map nesting and an inner sequential loop, move
159 -- the maps inside the sequential loop. The result is several
160 -- statements - one of these will be the loop, which will then contain
161 -- statements with @map@ expressions.
162 interchangeLoops ::
163 (MonadFreshNames m, HasScope SOACS m) =>
164 KernelNest ->
165 SeqLoop ->
166 m (Stms SOACS)
167 interchangeLoops full_nest = recurse (kernelNestLoops full_nest)
168 where
169 recurse nest loop
170 | (ns, [n]) <- splitFromEnd 1 nest = do
171 let isMapParameter v =
172 snd <$> find ((== v) . paramName . fst) (loopNestingParamsAndArrs n)
173 isMapInput v =
174 v `elem` map snd (loopNestingParamsAndArrs n)
175 (loop', stms) <-
176 runBuilder . localScope (scopeOfKernelNest full_nest) $
177 maybeCopyInitial isMapInput
178 =<< interchangeLoop isMapParameter loop n
179
180 -- Only safe to continue interchanging if we didn't need to add
181 -- any new statements; otherwise we manifest the remaining nests
182 -- as Maps and hand them back to the flattener.
183 if null stms
184 then recurse ns loop'
185 else
186 let loop_stm = seqLoopStm loop'
187 names = rearrangeShape (loopPerm loop') (patNames (stmPat loop_stm))
188 in pure $ snd $ manifestMaps ns names $ stms <> oneStm loop_stm
189 | otherwise = pure $ oneStm $ seqLoopStm loop
190
191 -- | An encoding of a branch with alongside its result pattern.
192 data Branch
193 = Branch [Int] (Pat Type) [SubExp] [Case (Body SOACS)] (Body SOACS) (MatchDec (BranchType SOACS))
194
195 branchStm :: Branch -> Stm SOACS
196 branchStm (Branch _ pat cond cases defbody ret) =
197 Let pat (defAux ()) $ Match cond cases defbody ret
198
199 interchangeBranch1 ::
200 (MonadFreshNames m, HasScope SOACS m) =>
201 Branch ->
202 LoopNesting ->
203 m Branch
204 interchangeBranch1
205 (Branch perm branch_pat cond cases defbody (MatchDec ret if_sort))
206 (MapNesting pat aux w params_and_arrs) = do
207 let ret' = map (`arrayOfRow` Free w) ret
208 pat' = Pat $ rearrangeShape perm $ patElems pat
209
210 (params, arrs) = unzip params_and_arrs
211 lam_ret = rearrangeShape perm $ map rowType $ patTypes pat
212
213 branch_pat' =
214 Pat $ map (fmap (`arrayOfRow` w)) $ patElems branch_pat
215
216 mkBranch branch = (renameBody =<<) $ runBodyBuilder $ do
217 let lam = Lambda params lam_ret branch
218 addStm $ Let branch_pat' aux $ Op $ Screma w arrs $ mapSOAC lam
219 pure $ varsRes $ patNames branch_pat'
220
221 cases' <- mapM (traverse mkBranch) cases
222 defbody' <- mkBranch defbody
223 pure . Branch [0 .. patSize pat - 1] pat' cond cases' defbody' $
224 MatchDec ret' if_sort
225
226 -- | Given a (parallel) map nesting and an inner branch, move the maps
227 -- inside the branch. The result is the resulting branch expression,
228 -- which will then contain statements with @map@ expressions.
229 interchangeBranch ::
230 (MonadFreshNames m, HasScope SOACS m) =>
231 KernelNest ->
232 Branch ->
233 m (Stm SOACS)
234 interchangeBranch nest loop =
235 branchStm <$> foldM interchangeBranch1 loop (reverse $ kernelNestLoops nest)
236
237 -- | An encoding of a WithAcc with alongside its result pattern.
238 data WithAccStm
239 = WithAccStm [Int] (Pat Type) [(Shape, [VName], Maybe (Lambda SOACS, [SubExp]))] (Lambda SOACS)
240
241 withAccStm :: WithAccStm -> Stm SOACS
242 withAccStm (WithAccStm _ pat inputs lam) =
243 Let pat (defAux ()) $ WithAcc inputs lam
244
245 interchangeWithAcc1 ::
246 (MonadFreshNames m, LocalScope SOACS m) =>
247 WithAccStm ->
248 LoopNesting ->
249 m WithAccStm
250 interchangeWithAcc1
251 (WithAccStm perm _withacc_pat inputs acc_lam)
252 (MapNesting map_pat map_aux w params_and_arrs) = do
253 inputs' <- mapM onInput inputs
254 lam_params' <- newAccLamParams $ lambdaParams acc_lam
255 iota_p <- newParam "iota_p" $ Prim int64
256 acc_lam' <- trLam (Var (paramName iota_p)) <=< runLambdaBuilder lam_params' $ do
257 let acc_params = drop (length inputs) lam_params'
258 orig_acc_params = drop (length inputs) $ lambdaParams acc_lam
259 iota_w <-
260 letExp "acc_inter_iota" . BasicOp $
261 Iota w (intConst Int64 0) (intConst Int64 1) Int64
262 let (params, arrs) = unzip params_and_arrs
263 maplam_ret = lambdaReturnType acc_lam
264 maplam = Lambda (iota_p : orig_acc_params ++ params) maplam_ret (lambdaBody acc_lam)
265 auxing map_aux . fmap subExpsRes . letTupExp' "withacc_inter" $
266 Op $
267 Screma w (iota_w : map paramName acc_params ++ arrs) (mapSOAC maplam)
268 let pat = Pat $ rearrangeShape perm $ patElems map_pat
269 pure $ WithAccStm perm pat inputs' acc_lam'
270 where
271 newAccLamParams ps = do
272 let (cert_ps, acc_ps) = splitAt (length ps `div` 2) ps
273 -- Should not rename the certificates.
274 acc_ps' <- forM acc_ps $ \(Param attrs v t) ->
275 Param attrs <$> newVName (baseString v) <*> pure t
276 pure $ cert_ps <> acc_ps'
277
278 num_accs = length inputs
279 acc_certs = map paramName $ take num_accs $ lambdaParams acc_lam
280 onArr v =
281 pure . maybe v snd $
282 find ((== v) . paramName . fst) params_and_arrs
283 onInput (shape, arrs, op) =
284 (Shape [w] <> shape,,) <$> mapM onArr arrs <*> traverse onOp op
285
286 onOp (op_lam, nes) = do
287 -- We need to add an additional index parameter because we are
288 -- extending the index space of the accumulator.
289 idx_p <- newParam "idx" $ Prim int64
290 pure (op_lam {lambdaParams = idx_p : lambdaParams op_lam}, nes)
291
292 trType :: TypeBase shape u -> TypeBase shape u
293 trType (Acc acc ispace ts u)
294 | acc `elem` acc_certs =
295 Acc acc (Shape [w] <> ispace) ts u
296 trType t = t
297
298 trParam :: Param (TypeBase shape u) -> Param (TypeBase shape u)
299 trParam = fmap trType
300
301 trLam i (Lambda params ret body) =
302 localScope (scopeOfLParams params) $
303 Lambda (map trParam params) (map trType ret) <$> trBody i body
304
305 trBody i (Body dec stms res) =
306 inScopeOf stms $ Body dec <$> traverse (trStm i) stms <*> pure res
307
308 trStm i (Let pat aux e) =
309 Let (fmap trType pat) aux <$> trExp i e
310
311 trSOAC i = mapSOACM mapper
312 where
313 mapper =
314 identitySOACMapper {mapOnSOACLambda = trLam i}
315
316 trExp i (WithAcc acc_inputs lam) =
317 WithAcc acc_inputs <$> trLam i lam
318 trExp i (BasicOp (UpdateAcc safety acc is ses)) = do
319 acc_t <- lookupType acc
320 pure $ case acc_t of
321 Acc cert _ _ _
322 | cert `elem` acc_certs ->
323 BasicOp $ UpdateAcc safety acc (i : is) ses
324 _ ->
325 BasicOp $ UpdateAcc safety acc is ses
326 trExp i e = mapExpM mapper e
327 where
328 mapper =
329 identityMapper
330 { mapOnBody = \scope -> localScope scope . trBody i,
331 mapOnRetType = pure . trType,
332 mapOnBranchType = pure . trType,
333 mapOnFParam = pure . trParam,
334 mapOnLParam = pure . trParam,
335 mapOnOp = trSOAC i
336 }
337
338 -- | Given a (parallel) map nesting and an inner withacc, move the
339 -- maps inside the branch. The result is the resulting withacc
340 -- expression, which will then contain statements with @map@
341 -- expressions.
342 interchangeWithAcc ::
343 (MonadFreshNames m, LocalScope SOACS m) =>
344 KernelNest ->
345 WithAccStm ->
346 m (Stm SOACS)
347 interchangeWithAcc nest withacc =
348 withAccStm <$> foldM interchangeWithAcc1 withacc (reverse $ kernelNestLoops nest)