Debian Codegraph @

src/Futhark/Pass/ExtractKernels/Distribution.hs

raw
1 {-# LANGUAGE LambdaCase #-}
2 {-# LANGUAGE TypeFamilies #-}
3
4 module Futhark.Pass.ExtractKernels.Distribution
5 ( Target,
6 Targets,
7 ppTargets,
8 singleTarget,
9 outerTarget,
10 innerTarget,
11 pushInnerTarget,
12 popInnerTarget,
13 targetsScope,
14 LoopNesting (..),
15 ppLoopNesting,
16 scopeOfLoopNesting,
17 Nesting (..),
18 Nestings,
19 ppNestings,
20 letBindInInnerNesting,
21 singleNesting,
22 pushInnerNesting,
23 KernelNest,
24 ppKernelNest,
25 newKernel,
26 innermostKernelNesting,
27 pushKernelNesting,
28 pushInnerKernelNesting,
29 scopeOfKernelNest,
30 kernelNestLoops,
31 kernelNestWidths,
32 boundInKernelNest,
33 boundInKernelNests,
34 flatKernel,
35 constructKernel,
36 tryDistribute,
37 tryDistributeStm,
38 )
39 where
40
41 import Control.Monad
42 import Control.Monad.RWS.Strict
43 import Control.Monad.Trans.Maybe
44 import Data.Bifunctor (second)
45 import Data.Foldable
46 import Data.List (elemIndex, sortOn)
47 import Data.Map.Strict qualified as M
48 import Data.Maybe
49 import Futhark.IR
50 import Futhark.IR.SegOp
51 import Futhark.MonadFreshNames
52 import Futhark.Pass.ExtractKernels.BlockedKernel
53 ( DistRep,
54 KernelInput (..),
55 MkSegLevel,
56 mapKernel,
57 readKernelInput,
58 )
59 import Futhark.Tools
60 import Futhark.Transform.Rename
61 import Futhark.Util
62 import Futhark.Util.Log
63
64 type Target = (Pat Type, Result)
65
66 -- | First pair element is the very innermost ("current") target. In
67 -- the list, the outermost target comes first. Invariant: Every
68 -- element of a pattern must be present as the result of the
69 -- immediately enclosing target. This is ensured by 'pushInnerTarget'
70 -- by removing unused pattern elements.
71 data Targets = Targets
72 { _innerTarget :: Target,
73 _outerTargets :: [Target]
74 }
75
76 ppTargets :: Targets -> String
77 ppTargets (Targets target targets) =
78 unlines $ map ppTarget $ targets ++ [target]
79 where
80 ppTarget (pat, res) = prettyString pat ++ " <- " ++ prettyString res
81
82 singleTarget :: Target -> Targets
83 singleTarget = flip Targets []
84
85 outerTarget :: Targets -> Target
86 outerTarget (Targets inner_target []) = inner_target
87 outerTarget (Targets _ (outer_target : _)) = outer_target
88
89 innerTarget :: Targets -> Target
90 innerTarget (Targets inner_target _) = inner_target
91
92 pushOuterTarget :: Target -> Targets -> Targets
93 pushOuterTarget target (Targets inner_target targets) =
94 Targets inner_target (target : targets)
95
96 pushInnerTarget :: Target -> Targets -> Targets
97 pushInnerTarget (pat, res) (Targets inner_target targets) =
98 Targets (pat', res') (targets ++ [inner_target])
99 where
100 (pes', res') = unzip $ filter (used . fst) $ zip (patElems pat) res
101 pat' = Pat pes'
102 inner_used = freeIn $ snd inner_target
103 used pe = patElemName pe `nameIn` inner_used
104
105 popInnerTarget :: Targets -> Maybe (Target, Targets)
106 popInnerTarget (Targets t ts) =
107 case reverse ts of
108 x : xs -> Just (t, Targets x $ reverse xs)
109 [] -> Nothing
110
111 targetScope :: (DistRep rep) => Target -> Scope rep
112 targetScope = scopeOfPat . fst
113
114 targetsScope :: (DistRep rep) => Targets -> Scope rep
115 targetsScope (Targets t ts) = mconcat $ map targetScope $ t : ts
116
117 data LoopNesting = MapNesting
118 { loopNestingPat :: Pat Type,
119 loopNestingAux :: StmAux (),
120 loopNestingWidth :: SubExp,
121 loopNestingParamsAndArrs :: [(Param Type, VName)]
122 }
123 deriving (Show)
124
125 scopeOfLoopNesting :: (LParamInfo rep ~ Type) => LoopNesting -> Scope rep
126 scopeOfLoopNesting = scopeOfLParams . map fst . loopNestingParamsAndArrs
127
128 ppLoopNesting :: LoopNesting -> String
129 ppLoopNesting (MapNesting _ _ _ params_and_arrs) =
130 prettyString (map fst params_and_arrs)
131 ++ " <- "
132 ++ prettyString (map snd params_and_arrs)
133
134 loopNestingParams :: LoopNesting -> [Param Type]
135 loopNestingParams = map fst . loopNestingParamsAndArrs
136
137 instance FreeIn LoopNesting where
138 freeIn' (MapNesting pat aux w params_and_arrs) =
139 freeIn' pat <> freeIn' aux <> freeIn' w <> freeIn' params_and_arrs
140
141 data Nesting = Nesting
142 { nestingLetBound :: Names,
143 nestingLoop :: LoopNesting
144 }
145 deriving (Show)
146
147 letBindInNesting :: Names -> Nesting -> Nesting
148 letBindInNesting newnames (Nesting oldnames loop) =
149 Nesting (oldnames <> newnames) loop
150 -- ^ First pair element is the very innermost ("current") nest. In
151 -- the list, the outermost nest comes first.
152
153 type Nestings = (Nesting, [Nesting])
154
155 ppNestings :: Nestings -> String
156 ppNestings (nesting, nestings) =
157 unlines $ map ppNesting $ nestings ++ [nesting]
158 where
159 ppNesting (Nesting _ loop) = ppLoopNesting loop
160
161 singleNesting :: Nesting -> Nestings
162 singleNesting = (,[])
163
164 pushInnerNesting :: Nesting -> Nestings -> Nestings
165 pushInnerNesting nesting (inner_nesting, nestings) =
166 (nesting, nestings ++ [inner_nesting])
167
168 -- | Both parameters and let-bound.
169 boundInNesting :: Nesting -> Names
170 boundInNesting nesting =
171 namesFromList (map paramName (loopNestingParams loop))
172 <> nestingLetBound nesting
173 where
174 loop = nestingLoop nesting
175
176 letBindInInnerNesting :: Names -> Nestings -> Nestings
177 letBindInInnerNesting names (nest, nestings) =
178 (letBindInNesting names nest, nestings)
179
180 -- | Note: first element is *outermost* nesting. This is different
181 -- from the similar types elsewhere!
182 type KernelNest = (LoopNesting, [LoopNesting])
183
184 ppKernelNest :: KernelNest -> String
185 ppKernelNest (nesting, nestings) =
186 unlines $ map ppLoopNesting $ nesting : nestings
187
188 -- | Retrieve the innermost kernel nesting.
189 innermostKernelNesting :: KernelNest -> LoopNesting
190 innermostKernelNesting (nest, nests) =
191 fromMaybe nest $ maybeHead $ reverse nests
192
193 -- | Add new outermost nesting, pushing the current outermost to the
194 -- list, also taking care to swap patterns if necessary.
195 pushKernelNesting :: Target -> LoopNesting -> KernelNest -> KernelNest
196 pushKernelNesting target newnest (nest, nests) =
197 ( fixNestingPatOrder newnest target (loopNestingPat nest),
198 nest : nests
199 )
200
201 -- | Add new innermost nesting, pushing the current outermost to the
202 -- list. It is important that the 'Target' has the right order
203 -- (non-permuted compared to what is expected by the outer nests).
204 pushInnerKernelNesting :: Target -> LoopNesting -> KernelNest -> KernelNest
205 pushInnerKernelNesting target newnest (nest, nests) =
206 (nest, nests ++ [fixNestingPatOrder newnest target (loopNestingPat innermost)])
207 where
208 innermost = case reverse nests of
209 [] -> nest
210 n : _ -> n
211
212 fixNestingPatOrder :: LoopNesting -> Target -> Pat Type -> LoopNesting
213 fixNestingPatOrder nest (_, res) inner_pat =
214 nest {loopNestingPat = basicPat pat'}
215 where
216 pat = loopNestingPat nest
217 pat' = map fst fixed_target
218 fixed_target = sortOn posInInnerPat $ zip (patIdents pat) res
219 posInInnerPat (_, SubExpRes _ (Var v)) = fromMaybe 0 $ elemIndex v $ patNames inner_pat
220 posInInnerPat _ = 0
221
222 newKernel :: LoopNesting -> KernelNest
223 newKernel nest = (nest, [])
224
225 kernelNestLoops :: KernelNest -> [LoopNesting]
226 kernelNestLoops (loop, loops) = loop : loops
227
228 scopeOfKernelNest :: (LParamInfo rep ~ Type) => KernelNest -> Scope rep
229 scopeOfKernelNest = foldMap scopeOfLoopNesting . kernelNestLoops
230
231 boundInKernelNest :: KernelNest -> Names
232 boundInKernelNest = mconcat . boundInKernelNests
233
234 boundInKernelNests :: KernelNest -> [Names]
235 boundInKernelNests =
236 map (namesFromList . map (paramName . fst) . loopNestingParamsAndArrs)
237 . kernelNestLoops
238
239 kernelNestWidths :: KernelNest -> [SubExp]
240 kernelNestWidths = map loopNestingWidth . kernelNestLoops
241
242 constructKernel ::
243 (DistRep rep, MonadFreshNames m, LocalScope rep m) =>
244 MkSegLevel rep m ->
245 KernelNest ->
246 Body rep ->
247 m (Stm rep, Stms rep)
248 constructKernel mk_lvl kernel_nest inner_body = runBuilderT' $ do
249 (ispace, inps) <- flatKernel kernel_nest
250 let aux = loopNestingAux first_nest
251 ispace_scope = M.fromList $ map ((,IndexName Int64) . fst) ispace
252 pat = loopNestingPat first_nest
253 rts = map (stripArray (length ispace)) $ patTypes pat
254
255 inner_body' <- fmap (uncurry (flip (KernelBody ()))) $
256 runBuilder . localScope ispace_scope $ do
257 mapM_ readKernelInput $ filter inputIsUsed inps
258 res <- bodyBind inner_body
259 forM res $ \(SubExpRes cs se) -> pure $ Returns ResultMaySimplify cs se
260
261 (segop, aux_stms) <- lift $ mapKernel mk_lvl ispace [] rts inner_body'
262
263 addStms aux_stms
264
265 pure $ Let pat aux $ Op $ segOp segop
266 where
267 first_nest = fst kernel_nest
268 inputIsUsed input = kernelInputName input `nameIn` freeIn inner_body
269
270 -- | Flatten a kernel nesting to:
271 --
272 -- (1) The index space.
273 --
274 -- (2) The kernel inputs - note that some of these may be unused.
275 flatKernel ::
276 (MonadFreshNames m) =>
277 KernelNest ->
278 m ([(VName, SubExp)], [KernelInput])
279 flatKernel (MapNesting _ _ nesting_w params_and_arrs, []) = do
280 i <- newVName "gtid"
281 let inps =
282 [ KernelInput pname ptype arr [Var i]
283 | (Param _ pname ptype, arr) <- params_and_arrs
284 ]
285 pure ([(i, nesting_w)], inps)
286 flatKernel (MapNesting _ _ nesting_w params_and_arrs, nest : nests) = do
287 i <- newVName "gtid"
288 (ispace, inps) <- flatKernel (nest, nests)
289
290 let inps' = map fixupInput inps
291 isParam inp =
292 snd <$> find ((== kernelInputArray inp) . paramName . fst) params_and_arrs
293 fixupInput inp
294 | Just arr <- isParam inp =
295 inp
296 { kernelInputArray = arr,
297 kernelInputIndices = Var i : kernelInputIndices inp
298 }
299 | otherwise =
300 inp
301
302 pure ((i, nesting_w) : ispace, extra_inps i <> inps')
303 where
304 extra_inps i =
305 [ KernelInput pname ptype arr [Var i]
306 | (Param _ pname ptype, arr) <- params_and_arrs
307 ]
308
309 -- | Description of distribution to do.
310 data DistributionBody = DistributionBody
311 { distributionTarget :: Targets,
312 distributionFreeInBody :: Names,
313 distributionIdentityMap :: M.Map VName Ident,
314 -- | Also related to avoiding identity mapping.
315 distributionExpandTarget :: Target -> Target
316 }
317
318 distributionInnerPat :: DistributionBody -> Pat Type
319 distributionInnerPat = fst . innerTarget . distributionTarget
320
321 distributionBodyFromStms ::
322 (ASTRep rep) =>
323 Targets ->
324 Stms rep ->
325 (DistributionBody, Result)
326 distributionBodyFromStms (Targets (inner_pat, inner_res) targets) stms =
327 let bound_by_stms = namesFromList $ M.keys $ scopeOf stms
328 (inner_pat', inner_res', inner_identity_map, inner_expand_target) =
329 removeIdentityMappingGeneral bound_by_stms inner_pat inner_res
330 free =
331 (foldMap freeIn stms <> freeIn (map resCerts inner_res))
332 `namesSubtract` bound_by_stms
333 in ( DistributionBody
334 { distributionTarget = Targets (inner_pat', inner_res') targets,
335 distributionFreeInBody = free,
336 distributionIdentityMap = inner_identity_map,
337 distributionExpandTarget = inner_expand_target
338 },
339 inner_res'
340 )
341
342 distributionBodyFromStm ::
343 (ASTRep rep) =>
344 Targets ->
345 Stm rep ->
346 (DistributionBody, Result)
347 distributionBodyFromStm targets stm =
348 distributionBodyFromStms targets $ oneStm stm
349
350 createKernelNest ::
351 forall rep m.
352 (MonadFreshNames m, HasScope rep m) =>
353 Nestings ->
354 DistributionBody ->
355 m (Maybe (Targets, KernelNest))
356 createKernelNest (inner_nest, nests) distrib_body = do
357 let Targets target targets = distributionTarget distrib_body
358 unless (length nests == length targets) $
359 error $
360 "Nests and targets do not match!\n"
361 ++ "nests: "
362 ++ ppNestings (inner_nest, nests)
363 ++ "\ntargets:"
364 ++ ppTargets (Targets target targets)
365 runMaybeT $ fmap prepare $ recurse $ zip nests targets
366 where
367 prepare (x, _, z) = (z, x)
368 bound_in_nest = mconcat $ map boundInNesting $ inner_nest : nests
369 distributableType =
370 (== mempty) . namesIntersection bound_in_nest . freeIn . arrayDims
371
372 distributeAtNesting ::
373 Nesting ->
374 Pat Type ->
375 (LoopNesting -> KernelNest, Names) ->
376 M.Map VName Ident ->
377 [Ident] ->
378 (Target -> Targets) ->
379 MaybeT m (KernelNest, Names, Targets)
380 distributeAtNesting
381 (Nesting nest_let_bound nest)
382 pat
383 (add_to_kernel, free_in_kernel)
384 identity_map
385 inner_returned_arrs
386 addTarget = do
387 let nest'@(MapNesting _ aux w params_and_arrs) =
388 removeUnusedNestingParts free_in_kernel nest
389 (params, arrs) = unzip params_and_arrs
390 param_names = namesFromList $ map paramName params
391 free_in_kernel' =
392 (freeIn nest' <> free_in_kernel) `namesSubtract` param_names
393 required_from_nest =
394 free_in_kernel' `namesIntersection` nest_let_bound
395
396 required_from_nest_idents <-
397 forM (namesToList required_from_nest) $ \name -> do
398 t <- lift $ lookupType name
399 pure $ Ident name t
400
401 (free_params, free_arrs, bind_in_target) <-
402 fmap unzip3 $
403 forM (inner_returned_arrs ++ required_from_nest_idents) $
404 \(Ident pname ptype) ->
405 case M.lookup pname identity_map of
406 Nothing -> do
407 arr <-
408 newIdent (baseString pname ++ "_r") $ arrayOfRow ptype w
409 pure
410 ( Param mempty pname ptype,
411 arr,
412 True
413 )
414 Just arr ->
415 pure
416 ( Param mempty pname ptype,
417 arr,
418 False
419 )
420
421 let free_arrs_pat =
422 basicPat $ map snd $ filter fst $ zip bind_in_target free_arrs
423 free_params_pat =
424 map snd $ filter fst $ zip bind_in_target free_params
425
426 (actual_params, actual_arrs) =
427 ( params ++ free_params,
428 arrs ++ map identName free_arrs
429 )
430 actual_param_names =
431 namesFromList $ map paramName actual_params
432
433 nest'' =
434 removeUnusedNestingParts free_in_kernel $
435 MapNesting pat aux w $
436 zip actual_params actual_arrs
437
438 free_in_kernel'' =
439 (freeIn nest'' <> free_in_kernel) `namesSubtract` actual_param_names
440
441 unless
442 ( all (distributableType . paramType) $
443 loopNestingParams nest''
444 )
445 $ fail "Would induce irregular array"
446 pure
447 ( add_to_kernel nest'',
448 free_in_kernel'',
449 addTarget (free_arrs_pat, varsRes $ map paramName free_params_pat)
450 )
451
452 recurse :: [(Nesting, Target)] -> MaybeT m (KernelNest, Names, Targets)
453 recurse [] =
454 distributeAtNesting
455 inner_nest
456 (distributionInnerPat distrib_body)
457 ( newKernel,
458 distributionFreeInBody distrib_body `namesIntersection` bound_in_nest
459 )
460 (distributionIdentityMap distrib_body)
461 []
462 $ singleTarget . distributionExpandTarget distrib_body
463 recurse ((nest, (pat, res)) : nests') = do
464 (kernel@(outer, _), kernel_free, kernel_targets) <- recurse nests'
465
466 let (pat', res', identity_map, expand_target) =
467 removeIdentityMappingFromNesting
468 (namesFromList $ patNames $ loopNestingPat outer)
469 pat
470 res
471
472 distributeAtNesting
473 nest
474 pat'
475 ( \k -> pushKernelNesting (pat', res') k kernel,
476 kernel_free
477 )
478 identity_map
479 (patIdents $ fst $ outerTarget kernel_targets)
480 ((`pushOuterTarget` kernel_targets) . expand_target)
481
482 removeUnusedNestingParts :: Names -> LoopNesting -> LoopNesting
483 removeUnusedNestingParts used (MapNesting pat aux w params_and_arrs) =
484 MapNesting pat aux w $ zip used_params used_arrs
485 where
486 (params, arrs) = unzip params_and_arrs
487 (used_params, used_arrs) =
488 unzip $ filter ((`nameIn` used) . paramName . fst) $ zip params arrs
489
490 removeIdentityMappingGeneral ::
491 Names ->
492 Pat Type ->
493 Result ->
494 ( Pat Type,
495 Result,
496 M.Map VName Ident,
497 Target -> Target
498 )
499 removeIdentityMappingGeneral bound pat res =
500 let (identities, not_identities) =
501 mapEither isIdentity $ zip (patElems pat) res
502 (not_identity_patElems, not_identity_res) = unzip not_identities
503 (identity_patElems, identity_res) = unzip identities
504 expandTarget (tpat, tres) =
505 ( Pat $ patElems tpat ++ identity_patElems,
506 tres ++ map (uncurry SubExpRes . second Var) identity_res
507 )
508 identity_map =
509 M.fromList $ zip (map snd identity_res) $ map patElemIdent identity_patElems
510 in ( Pat not_identity_patElems,
511 not_identity_res,
512 identity_map,
513 expandTarget
514 )
515 where
516 isIdentity (patElem, SubExpRes _ (Var v))
517 | v `notNameIn` bound = Left (patElem, (mempty, v))
518 isIdentity x = Right x
519
520 removeIdentityMappingFromNesting ::
521 Names ->
522 Pat Type ->
523 Result ->
524 ( Pat Type,
525 Result,
526 M.Map VName Ident,
527 Target -> Target
528 )
529 removeIdentityMappingFromNesting bound_in_nesting pat res =
530 let (pat', res', identity_map, expand_target) =
531 removeIdentityMappingGeneral bound_in_nesting pat res
532 in (pat', res', identity_map, expand_target)
533
534 tryDistribute ::
535 ( DistRep rep,
536 MonadFreshNames m,
537 LocalScope rep m,
538 MonadLogger m
539 ) =>
540 MkSegLevel rep m ->
541 Nestings ->
542 Targets ->
543 Stms rep ->
544 m (Maybe (Targets, Stms rep))
545 tryDistribute _ _ targets stms
546 | null stms =
547 -- No point in distributing an empty kernel.
548 pure $ Just (targets, mempty)
549 tryDistribute mk_lvl nest targets stms =
550 createKernelNest nest dist_body
551 >>= \case
552 Just (targets', distributed) -> do
553 (kernel_stm, w_stms) <-
554 localScope (targetsScope targets') $
555 constructKernel mk_lvl distributed $
556 mkBody stms inner_body_res
557 distributed' <- renameStm kernel_stm
558 logMsg $
559 "distributing\n"
560 ++ unlines (map prettyString $ stmsToList stms)
561 ++ prettyString (snd $ innerTarget targets)
562 ++ "\nas\n"
563 ++ prettyString distributed'
564 ++ "\ndue to targets\n"
565 ++ ppTargets targets
566 ++ "\nand with new targets\n"
567 ++ ppTargets targets'
568 pure $ Just (targets', w_stms <> oneStm distributed')
569 Nothing ->
570 pure Nothing
571 where
572 (dist_body, inner_body_res) = distributionBodyFromStms targets stms
573
574 tryDistributeStm ::
575 (MonadFreshNames m, HasScope t m, ASTRep rep) =>
576 Nestings ->
577 Targets ->
578 Stm rep ->
579 m (Maybe (Result, Targets, KernelNest))
580 tryDistributeStm nest targets stm =
581 fmap addRes <$> createKernelNest nest dist_body
582 where
583 (dist_body, res) = distributionBodyFromStm targets stm
584 addRes (targets', kernel_nest) = (res, targets', kernel_nest)