Debian Codegraph @

src/Futhark/Pass/ExtractKernels/DistributeNests.hs

raw
1 {-# LANGUAGE LambdaCase #-}
2 {-# LANGUAGE TypeFamilies #-}
3 {-# OPTIONS_GHC -Wno-overlapping-patterns -Wno-incomplete-patterns -Wno-incomplete-uni-patterns -Wno-incomplete-record-updates #-}
4
5 module Futhark.Pass.ExtractKernels.DistributeNests
6 ( MapLoop (..),
7 mapLoopStm,
8 bodyContainsParallelism,
9 lambdaContainsParallelism,
10 determineReduceOp,
11 histKernel,
12 DistEnv (..),
13 DistAcc (..),
14 runDistNestT,
15 DistNestT,
16 liftInner,
17 distributeMap,
18 distribute,
19 distributeSingleStm,
20 distributeMapBodyStms,
21 addStmsToAcc,
22 addStmToAcc,
23 permutationAndMissing,
24 addPostStms,
25 postStm,
26 inNesting,
27 )
28 where
29
30 import Control.Arrow (first)
31 import Control.Monad
32 import Control.Monad.RWS.Strict
33 import Control.Monad.Reader
34 import Control.Monad.Trans.Maybe
35 import Control.Monad.Writer.Strict
36 import Data.List (find, partition, tails)
37 import Data.List.NonEmpty (NonEmpty (..))
38 import Data.Map qualified as M
39 import Data.Maybe
40 import Futhark.IR
41 import Futhark.IR.GPU.Op (SegVirt (..))
42 import Futhark.IR.SOACS (SOACS)
43 import Futhark.IR.SOACS qualified as SOACS
44 import Futhark.IR.SOACS.SOAC hiding (HistOp, histDest)
45 import Futhark.IR.SOACS.Simplify (simpleSOACS, simplifyStms)
46 import Futhark.IR.SegOp
47 import Futhark.MonadFreshNames
48 import Futhark.Pass.ExtractKernels.BlockedKernel
49 import Futhark.Pass.ExtractKernels.Distribution
50 import Futhark.Pass.ExtractKernels.ISRWIM
51 import Futhark.Pass.ExtractKernels.Interchange
52 import Futhark.Tools
53 import Futhark.Transform.CopyPropagate
54 import Futhark.Transform.FirstOrderTransform qualified as FOT
55 import Futhark.Transform.Rename
56 import Futhark.Util.Log
57
58 scopeForSOACs :: (SameScope rep SOACS) => Scope rep -> Scope SOACS
59 scopeForSOACs = castScope
60
61 data MapLoop = MapLoop (Pat Type) (StmAux ()) SubExp (Lambda SOACS) [VName]
62
63 mapLoopStm :: MapLoop -> Stm SOACS
64 mapLoopStm (MapLoop pat aux w lam arrs) =
65 Let pat aux $ Op $ Screma w arrs $ mapSOAC lam
66
67 data DistEnv rep m = DistEnv
68 { distNest :: Nestings,
69 distScope :: Scope rep,
70 distOnTopLevelStms :: Stms SOACS -> DistNestT rep m (Stms rep),
71 distOnInnerMap ::
72 MapLoop ->
73 DistAcc rep ->
74 DistNestT rep m (DistAcc rep),
75 distOnSOACSStms :: Stm SOACS -> Builder rep (Stms rep),
76 distOnSOACSLambda :: Lambda SOACS -> Builder rep (Lambda rep),
77 distSegLevel :: MkSegLevel rep m
78 }
79
80 data DistAcc rep = DistAcc
81 { distTargets :: Targets,
82 distStms :: Stms rep
83 }
84
85 data DistRes rep = DistRes
86 { accPostStms :: PostStms rep,
87 accLog :: Log
88 }
89
90 instance Semigroup (DistRes rep) where
91 DistRes ks1 log1 <> DistRes ks2 log2 =
92 DistRes (ks1 <> ks2) (log1 <> log2)
93
94 instance Monoid (DistRes rep) where
95 mempty = DistRes mempty mempty
96
97 newtype PostStms rep = PostStms {unPostStms :: Stms rep}
98
99 instance Semigroup (PostStms rep) where
100 PostStms xs <> PostStms ys = PostStms $ ys <> xs
101
102 instance Monoid (PostStms rep) where
103 mempty = PostStms mempty
104
105 typeEnvFromDistAcc :: (DistRep rep) => DistAcc rep -> Scope rep
106 typeEnvFromDistAcc = scopeOfPat . fst . outerTarget . distTargets
107
108 addStmsToAcc :: Stms rep -> DistAcc rep -> DistAcc rep
109 addStmsToAcc stms acc =
110 acc {distStms = stms <> distStms acc}
111
112 addStmToAcc ::
113 (MonadFreshNames m, DistRep rep) =>
114 Stm SOACS ->
115 DistAcc rep ->
116 DistNestT rep m (DistAcc rep)
117 addStmToAcc stm acc = do
118 onSoacs <- asks distOnSOACSStms
119 (stm', _) <- runBuilder $ onSoacs stm
120 pure acc {distStms = stm' <> distStms acc}
121
122 soacsLambda ::
123 (MonadFreshNames m, DistRep rep) =>
124 Lambda SOACS ->
125 DistNestT rep m (Lambda rep)
126 soacsLambda lam = do
127 onLambda <- asks distOnSOACSLambda
128 fst <$> runBuilder (onLambda lam)
129
130 newtype DistNestT rep m a
131 = DistNestT (ReaderT (DistEnv rep m) (WriterT (DistRes rep) m) a)
132 deriving
133 ( Functor,
134 Applicative,
135 Monad,
136 MonadReader (DistEnv rep m),
137 MonadWriter (DistRes rep)
138 )
139
140 liftInner :: (LocalScope rep m, DistRep rep) => m a -> DistNestT rep m a
141 liftInner m = do
142 outer_scope <- askScope
143 DistNestT $
144 lift $
145 lift $ do
146 inner_scope <- askScope
147 localScope (outer_scope `M.difference` inner_scope) m
148
149 instance (MonadFreshNames m) => MonadFreshNames (DistNestT rep m) where
150 getNameSource = DistNestT $ lift getNameSource
151 putNameSource = DistNestT . lift . putNameSource
152
153 instance (Monad m, ASTRep rep) => HasScope rep (DistNestT rep m) where
154 askScope = asks distScope
155
156 instance (Monad m, ASTRep rep) => LocalScope rep (DistNestT rep m) where
157 localScope types = local $ \env ->
158 env {distScope = types <> distScope env}
159
160 instance (Monad m) => MonadLogger (DistNestT rep m) where
161 addLog msgs = tell mempty {accLog = msgs}
162
163 runDistNestT ::
164 (MonadLogger m, DistRep rep) =>
165 DistEnv rep m ->
166 DistNestT rep m (DistAcc rep) ->
167 m (Stms rep)
168 runDistNestT env (DistNestT m) = do
169 (acc, res) <- runWriterT $ runReaderT m env
170 addLog $ accLog res
171 -- There may be a few final targets remaining - these correspond to
172 -- arrays that are identity mapped, and must have statements
173 -- inserted here.
174 pure $
175 unPostStms (accPostStms res) <> identityStms (outerTarget $ distTargets acc)
176 where
177 outermost = nestingLoop $
178 case distNest env of
179 (nest, []) -> nest
180 (_, nest : _) -> nest
181 params_to_arrs =
182 map (first paramName) $
183 loopNestingParamsAndArrs outermost
184
185 identityStms (rem_pat, res) =
186 stmsFromList $ zipWith identityStm (patElems rem_pat) res
187 identityStm pe (SubExpRes cs (Var v))
188 | Just arr <- lookup v params_to_arrs =
189 certify cs . Let (Pat [pe]) (defAux ()) . BasicOp $
190 Replicate mempty (Var arr)
191 identityStm pe (SubExpRes cs se) =
192 certify cs . Let (Pat [pe]) (defAux ()) . BasicOp $
193 Replicate (Shape [loopNestingWidth outermost]) se
194
195 addPostStms :: (Monad m) => PostStms rep -> DistNestT rep m ()
196 addPostStms ks = tell $ mempty {accPostStms = ks}
197
198 postStm :: (Monad m) => Stms rep -> DistNestT rep m ()
199 postStm stms = addPostStms $ PostStms stms
200
201 withStm ::
202 (Monad m, DistRep rep) =>
203 Stm SOACS ->
204 DistNestT rep m a ->
205 DistNestT rep m a
206 withStm stm = local $ \env ->
207 env
208 { distScope =
209 castScope (scopeOf stm) <> distScope env,
210 distNest =
211 letBindInInnerNesting provided $
212 distNest env
213 }
214 where
215 provided = namesFromList $ patNames $ stmPat stm
216
217 leavingNesting ::
218 (MonadFreshNames m, DistRep rep) =>
219 DistAcc rep ->
220 DistNestT rep m (DistAcc rep)
221 leavingNesting acc =
222 case popInnerTarget $ distTargets acc of
223 Nothing ->
224 error "The kernel targets list is unexpectedly small"
225 Just ((pat, res), newtargets)
226 | not $ null $ distStms acc -> do
227 -- Any statements left over correspond to something that
228 -- could not be distributed because it would cause irregular
229 -- arrays. These must be reconstructed into a a Map SOAC
230 -- that will be sequentialised. XXX: life would be better if
231 -- we were able to distribute irregular parallelism.
232 (Nesting _ inner, _) <- asks distNest
233 let MapNesting _ aux w params_and_arrs = inner
234 body = Body () (distStms acc) res
235 used_in_body = freeIn body
236 (used_params, used_arrs) =
237 unzip $
238 filter ((`nameIn` used_in_body) . paramName . fst) params_and_arrs
239 lam' =
240 Lambda
241 { lambdaParams = used_params,
242 lambdaBody = body,
243 lambdaReturnType = map rowType $ patTypes pat
244 }
245 stms <-
246 runBuilder_ . auxing aux . FOT.transformSOAC pat $
247 Screma w used_arrs $
248 mapSOAC lam'
249
250 pure $ acc {distTargets = newtargets, distStms = stms}
251 | otherwise -> do
252 -- Any results left over correspond to a Replicate or a Copy in
253 -- the parent nesting, depending on whether the argument is a
254 -- parameter of the innermost nesting.
255 (Nesting _ inner_nesting, _) <- asks distNest
256 let w = loopNestingWidth inner_nesting
257 aux = loopNestingAux inner_nesting
258 inps = loopNestingParamsAndArrs inner_nesting
259
260 remnantStm pe (SubExpRes cs (Var v))
261 | Just (_, arr) <- find ((== v) . paramName . fst) inps =
262 certify cs . Let (Pat [pe]) aux . BasicOp $
263 Replicate mempty (Var arr)
264 remnantStm pe (SubExpRes cs se) =
265 certify cs . Let (Pat [pe]) aux . BasicOp $
266 Replicate (Shape [w]) se
267
268 stms =
269 stmsFromList $ zipWith remnantStm (patElems pat) res
270
271 pure $ acc {distTargets = newtargets, distStms = stms}
272
273 mapNesting ::
274 (MonadFreshNames m, DistRep rep) =>
275 Pat Type ->
276 StmAux () ->
277 SubExp ->
278 Lambda SOACS ->
279 [VName] ->
280 DistNestT rep m (DistAcc rep) ->
281 DistNestT rep m (DistAcc rep)
282 mapNesting pat aux w lam arrs m =
283 local extend $ leavingNesting =<< m
284 where
285 nest =
286 Nesting mempty $
287 MapNesting pat aux w $
288 zip (lambdaParams lam) arrs
289 extend env =
290 env
291 { distNest = pushInnerNesting nest $ distNest env,
292 distScope = castScope (scopeOf lam) <> distScope env
293 }
294
295 inNesting ::
296 (Monad m, DistRep rep) =>
297 KernelNest ->
298 DistNestT rep m a ->
299 DistNestT rep m a
300 inNesting (outer, nests) = local $ \env ->
301 env
302 { distNest = (inner, nests'),
303 distScope = foldMap scopeOfLoopNesting (outer : nests) <> distScope env
304 }
305 where
306 (inner, nests') =
307 case reverse nests of
308 [] -> (asNesting outer, [])
309 (inner' : ns) -> (asNesting inner', map asNesting $ outer : reverse ns)
310 asNesting = Nesting mempty
311
312 bodyContainsParallelism :: Body SOACS -> Bool
313 bodyContainsParallelism = any isParallelStm . bodyStms
314 where
315 isParallelStm stm =
316 isMap (stmExp stm)
317 && not ("sequential" `inAttrs` stmAuxAttrs (stmAux stm))
318 isMap BasicOp {} = False
319 isMap Apply {} = False
320 isMap Match {} = False
321 isMap (Loop _ ForLoop {} body) = bodyContainsParallelism body
322 isMap (Loop _ WhileLoop {} _) = False
323 isMap (WithAcc _ lam) = bodyContainsParallelism $ lambdaBody lam
324 isMap Op {} = True
325
326 lambdaContainsParallelism :: Lambda SOACS -> Bool
327 lambdaContainsParallelism = bodyContainsParallelism . lambdaBody
328
329 distributeMapBodyStms ::
330 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
331 DistAcc rep ->
332 Stms SOACS ->
333 DistNestT rep m (DistAcc rep)
334 distributeMapBodyStms orig_acc = distribute <=< onStms orig_acc . stmsToList
335 where
336 onStms acc [] = pure acc
337 onStms acc (Let pat aux (Op (Stream w arrs accs lam)) : stms) = do
338 types <- asksScope scopeForSOACs
339 stream_stms <-
340 snd <$> runBuilderT (sequentialStreamWholeArray pat w accs lam arrs) types
341 stream_stms' <-
342 runReaderT (copyPropagateInStms simpleSOACS types stream_stms) types
343 onStms acc $ stmsToList (fmap (certify (stmAuxCerts aux)) stream_stms') ++ stms
344 onStms acc (stm : stms) =
345 -- It is important that stm is in scope if 'maybeDistributeStm'
346 -- wants to distribute, even if this causes the slightly silly
347 -- situation that stm is in scope of itself.
348 withStm stm $ maybeDistributeStm stm =<< onStms acc stms
349
350 onInnerMap :: (Monad m) => MapLoop -> DistAcc rep -> DistNestT rep m (DistAcc rep)
351 onInnerMap loop acc = do
352 f <- asks distOnInnerMap
353 f loop acc
354
355 onTopLevelStms :: (Monad m) => Stms SOACS -> DistNestT rep m ()
356 onTopLevelStms stms = do
357 f <- asks distOnTopLevelStms
358 postStm =<< f stms
359
360 maybeDistributeStm ::
361 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
362 Stm SOACS ->
363 DistAcc rep ->
364 DistNestT rep m (DistAcc rep)
365 maybeDistributeStm stm acc
366 | "sequential" `inAttrs` stmAuxAttrs (stmAux stm) =
367 addStmToAcc stm acc
368 maybeDistributeStm (Let pat aux (Op soac)) acc
369 | "sequential_outer" `inAttrs` stmAuxAttrs aux =
370 distributeMapBodyStms acc . fmap (certify (stmAuxCerts aux))
371 =<< runBuilder_ (FOT.transformSOAC pat soac)
372 maybeDistributeStm stm@(Let pat _ (Op (Screma w arrs form))) acc
373 | Just lam <- isMapSOAC form =
374 -- Only distribute inside the map if we can distribute everything
375 -- following the map.
376 distributeIfPossible acc >>= \case
377 Nothing -> addStmToAcc stm acc
378 Just acc' -> distribute =<< onInnerMap (MapLoop pat (stmAux stm) w lam arrs) acc'
379 maybeDistributeStm stm@(Let pat aux (Loop merge form@ForLoop {} body)) acc
380 | all (`notNameIn` freeIn (patTypes pat)) (patNames pat),
381 bodyContainsParallelism body =
382 distributeSingleStm acc stm >>= \case
383 Just (kernels, res, nest, acc')
384 | -- XXX: We cannot distribute if this loop depends on
385 -- certificates bound within the loop nest (well, we could,
386 -- but interchange would not be valid). This is not a
387 -- fundamental restriction, but an artifact of our
388 -- certificate representation, which we should probably
389 -- rethink.
390 not $
391 (freeIn form <> freeIn aux)
392 `namesIntersect` boundInKernelNest nest,
393 Just (perm, pat_unused) <- permutationAndMissing pat res ->
394 -- We need to pretend pat_unused was used anyway, by adding
395 -- it to the kernel nest.
396 localScope (typeEnvFromDistAcc acc') $ do
397 addPostStms kernels
398 nest' <- expandKernelNest pat_unused nest
399 types <- asksScope scopeForSOACs
400
401 -- Simplification is key to hoisting out statements that
402 -- were variant to the loop, but invariant to the outer maps
403 -- (which are now innermost).
404 stms <-
405 (`runReaderT` types) $
406 simplifyStms =<< interchangeLoops nest' (SeqLoop perm pat merge form body)
407 onTopLevelStms stms
408 pure acc'
409 _ ->
410 addStmToAcc stm acc
411 maybeDistributeStm stm@(Let pat _ (Match cond cases defbody ret)) acc
412 | all (`notNameIn` freeIn pat) (patNames pat),
413 any bodyContainsParallelism (defbody : map caseBody cases)
414 || not (all primType (matchReturns ret)) =
415 distributeSingleStm acc stm >>= \case
416 Just (kernels, res, nest, acc')
417 | not $
418 (freeIn cond <> freeIn ret) `namesIntersect` boundInKernelNest nest,
419 Just (perm, pat_unused) <- permutationAndMissing pat res ->
420 -- We need to pretend pat_unused was used anyway, by adding
421 -- it to the kernel nest.
422 localScope (typeEnvFromDistAcc acc') $ do
423 nest' <- expandKernelNest pat_unused nest
424 addPostStms kernels
425 types <- asksScope scopeForSOACs
426 let branch = Branch perm pat cond cases defbody ret
427 stms <-
428 (`runReaderT` types) $
429 simplifyStms . oneStm =<< interchangeBranch nest' branch
430 onTopLevelStms stms
431 pure acc'
432 _ ->
433 addStmToAcc stm acc
434 maybeDistributeStm stm@(Let pat _ (WithAcc inputs lam)) acc
435 | lambdaContainsParallelism lam =
436 distributeSingleStm acc stm >>= \case
437 Just (kernels, res, nest, acc')
438 | not $
439 freeIn (drop num_accs (lambdaReturnType lam))
440 `namesIntersect` boundInKernelNest nest,
441 Just (perm, pat_unused) <- permutationAndMissing pat res ->
442 -- We need to pretend pat_unused was used anyway, by adding
443 -- it to the kernel nest.
444 localScope (typeEnvFromDistAcc acc') $ do
445 nest' <- expandKernelNest pat_unused nest
446 types <- asksScope scopeForSOACs
447 addPostStms kernels
448 let withacc = WithAccStm perm pat inputs lam
449 stms <-
450 (`runReaderT` types) $
451 simplifyStms . oneStm =<< interchangeWithAcc nest' withacc
452 onTopLevelStms stms
453 pure acc'
454 _ ->
455 addStmToAcc stm acc
456 where
457 num_accs = length inputs
458 maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc
459 | Just [Reduce comm lam nes] <- isReduceSOAC form,
460 Just m <- irwim pat w comm lam $ zip nes arrs = do
461 types <- asksScope scopeForSOACs
462 (_, stms) <- runBuilderT (auxing aux m) types
463 distributeMapBodyStms acc stms
464
465 -- Parallelise segmented scatters.
466 maybeDistributeStm stm@(Let pat aux (Op (Scatter w ivs as lam))) acc =
467 distributeSingleStm acc stm >>= \case
468 Just (kernels, res, nest, acc')
469 | Just (perm, pat_unused) <- permutationAndMissing pat res ->
470 localScope (typeEnvFromDistAcc acc') $ do
471 nest' <- expandKernelNest pat_unused nest
472 lam' <- soacsLambda lam
473 addPostStms kernels
474 postStm =<< segmentedScatterKernel nest' perm pat (stmAuxCerts aux) w lam' ivs as
475 pure acc'
476 _ ->
477 addStmToAcc stm acc
478 -- Parallelise segmented Hist.
479 maybeDistributeStm stm@(Let pat aux (Op (Hist w as ops lam))) acc =
480 distributeSingleStm acc stm >>= \case
481 Just (kernels, res, nest, acc')
482 | Just (perm, pat_unused) <- permutationAndMissing pat res ->
483 localScope (typeEnvFromDistAcc acc') $ do
484 lam' <- soacsLambda lam
485 nest' <- expandKernelNest pat_unused nest
486 addPostStms kernels
487 postStm =<< segmentedHistKernel nest' perm (stmAuxCerts aux) w ops lam' as
488 pure acc'
489 _ ->
490 addStmToAcc stm acc
491 -- Parallelise Index slices if the result is going to be returned
492 -- directly from the kernel. This is because we would otherwise have
493 -- to sequentialise writing the result, which may be costly.
494 maybeDistributeStm stm@(Let (Pat [pe]) aux (BasicOp (Index arr slice))) acc
495 | not $ null $ sliceDims slice,
496 Var (patElemName pe) `elem` map resSubExp (snd (innerTarget (distTargets acc))) =
497 distributeSingleStm acc stm >>= \case
498 Just (kernels, _res, nest, acc') ->
499 localScope (typeEnvFromDistAcc acc') $ do
500 addPostStms kernels
501 postStm =<< segmentedGatherKernel nest (stmAuxCerts aux) arr slice
502 pure acc'
503 _ ->
504 addStmToAcc stm acc
505 -- If the scan can be distributed by itself, we will turn it into a
506 -- segmented scan.
507 --
508 -- If the scan cannot be distributed by itself, it will be
509 -- sequentialised in the default case for this function.
510 maybeDistributeStm stm@(Let pat aux (Op (Screma w arrs form))) acc
511 | Just (scans, map_lam) <- isScanomapSOAC form,
512 Scan lam nes <- singleScan scans =
513 distributeSingleStm acc stm >>= \case
514 Just (kernels, res, nest, acc')
515 | Just (perm, pat_unused) <- permutationAndMissing pat res ->
516 -- We need to pretend pat_unused was used anyway, by adding
517 -- it to the kernel nest.
518 localScope (typeEnvFromDistAcc acc') $ do
519 nest' <- expandKernelNest pat_unused nest
520 map_lam' <- soacsLambda map_lam
521 localScope (typeEnvFromDistAcc acc') $
522 segmentedScanomapKernel nest' perm (stmAuxCerts aux) w lam map_lam' nes arrs
523 >>= kernelOrNot mempty stm acc kernels acc'
524 _ ->
525 addStmToAcc stm acc
526 -- If the map function of the reduction contains parallelism we split
527 -- it, so that the parallelism can be exploited.
528 maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc
529 | Just (reds, map_lam) <- isRedomapSOAC form,
530 lambdaContainsParallelism map_lam = do
531 (mapstm, redstm) <-
532 redomapToMapAndReduce pat (w, reds, map_lam, arrs)
533 distributeMapBodyStms acc $ oneStm mapstm {stmAux = aux} <> oneStm redstm
534 -- if the reduction can be distributed by itself, we will turn it into a
535 -- segmented reduce.
536 --
537 -- If the reduction cannot be distributed by itself, it will be
538 -- sequentialised in the default case for this function.
539 maybeDistributeStm stm@(Let pat aux (Op (Screma w arrs form))) acc
540 | Just (reds, map_lam) <- isRedomapSOAC form,
541 Reduce comm lam nes <- singleReduce reds =
542 distributeSingleStm acc stm >>= \case
543 Just (kernels, res, nest, acc')
544 | Just (perm, pat_unused) <- permutationAndMissing pat res ->
545 -- We need to pretend pat_unused was used anyway, by adding
546 -- it to the kernel nest.
547 localScope (typeEnvFromDistAcc acc') $ do
548 nest' <- expandKernelNest pat_unused nest
549
550 lam' <- soacsLambda lam
551 map_lam' <- soacsLambda map_lam
552
553 let comm'
554 | commutativeLambda lam = Commutative
555 | otherwise = comm
556
557 regularSegmentedRedomapKernel nest' perm (stmAuxCerts aux) w comm' lam' map_lam' nes arrs
558 >>= kernelOrNot mempty stm acc kernels acc'
559 _ ->
560 addStmToAcc stm acc
561 maybeDistributeStm (Let pat aux (Op (Screma w arrs form))) acc = do
562 -- This Screma is too complicated for us to immediately do
563 -- anything, so split it up and try again.
564 scope <- asksScope scopeForSOACs
565 distributeMapBodyStms acc . fmap (certify (stmAuxCerts aux)) . snd
566 =<< runBuilderT (dissectScrema pat w form arrs) scope
567 maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate shape (Var stm_arr)))) acc = do
568 distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr ->
569 if shape == mempty
570 then pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr
571 else runBuilder_ $ auxing aux $ do
572 arr_t <- lookupType arr
573 let arr_r = arrayRank arr_t
574 nest_r = length (snd nest) + 1
575 res_r = arr_r + shapeRank shape
576 -- Move the to-be-replicated dimensions outermost.
577 arr_tr <-
578 letExp (baseString arr <> "_tr") . BasicOp $
579 Rearrange arr ([nest_r .. arr_r - 1] ++ [0 .. nest_r - 1])
580 -- Replicate the now-outermost dimensions appropriately.
581 arr_tr_rep <-
582 letExp (baseString arr <> "_tr_rep") . BasicOp $
583 Replicate shape (Var arr_tr)
584 -- Move the replicated dimensions back where they belong.
585 letBind outerpat . BasicOp $
586 Rearrange arr_tr_rep ([res_r - nest_r .. res_r - 1] ++ [0 .. res_r - nest_r - 1])
587 maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate shape v))) acc = do
588 distributeSingleStm acc stm >>= \case
589 Just (kernels, _, nest, acc')
590 | boundInKernelNest nest == mempty -> do
591 addPostStms kernels
592 let outerpat = loopNestingPat $ fst nest
593 nest_shape = Shape $ kernelNestWidths nest
594 localScope (typeEnvFromDistAcc acc') $ do
595 postStm <=< runBuilder_ . auxing aux . letBind outerpat $
596 BasicOp (Replicate (nest_shape <> shape) v)
597 pure acc'
598 _ -> addStmToAcc stm acc
599 -- Opaques are applied to the full array, because otherwise they can
600 -- drastically inhibit parallelisation in some cases.
601 maybeDistributeStm stm@(Let (Pat [pe]) aux (BasicOp (Opaque _ (Var stm_arr)))) acc
602 | not $ primType $ typeOf pe =
603 distributeSingleUnaryStm acc stm stm_arr $ \_ outerpat arr ->
604 pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr
605 maybeDistributeStm stm@(Let _ aux (BasicOp (Rearrange stm_arr perm))) acc =
606 distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr -> do
607 let r = length (snd nest) + 1
608 perm' = [0 .. r - 1] ++ map (+ r) perm
609 -- We need to add a copy, because the original map nest
610 -- will have produced an array without aliases, and so must we.
611 arr' <- newVName $ baseString arr
612 arr_t <- lookupType arr
613 pure $
614 stmsFromList
615 [ Let (Pat [PatElem arr' arr_t]) aux $ BasicOp $ Replicate mempty $ Var arr,
616 Let outerpat aux $ BasicOp $ Rearrange arr' perm'
617 ]
618 maybeDistributeStm stm@(Let _ aux (BasicOp (Reshape stm_arr reshape))) acc =
619 distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr -> do
620 let outer = Shape (kernelNestWidths nest)
621 reshape' = reshapeCoerce outer <> newshapeInner outer reshape
622 pure $ oneStm $ Let outerpat aux $ BasicOp $ Reshape arr reshape'
623 maybeDistributeStm stm@(Let pat aux (BasicOp (Update _ arr slice (Var v)))) acc
624 | not $ null $ sliceDims slice =
625 distributeSingleStm acc stm >>= \case
626 Just (kernels, res, nest, acc')
627 | map resSubExp res == map Var (patNames $ stmPat stm),
628 Just (perm, pat_unused) <- permutationAndMissing pat res -> do
629 addPostStms kernels
630 localScope (typeEnvFromDistAcc acc') $ do
631 nest' <- expandKernelNest pat_unused nest
632 postStm
633 =<< segmentedUpdateKernel nest' perm (stmAuxCerts aux) arr slice v
634 pure acc'
635 _ -> addStmToAcc stm acc
636 maybeDistributeStm stm@(Let _ aux (BasicOp (Concat d (x :| xs) w))) acc =
637 distributeSingleStm acc stm >>= \case
638 Just (kernels, _, nest, acc') ->
639 localScope (typeEnvFromDistAcc acc') $
640 segmentedConcat nest
641 >>= kernelOrNot (stmAuxCerts aux) stm acc kernels acc'
642 _ ->
643 addStmToAcc stm acc
644 where
645 segmentedConcat nest =
646 isSegmentedOp nest [0] mempty mempty [] (x : xs) $
647 \pat _ _ _ (x' : xs') ->
648 let d' = d + length (snd nest) + 1
649 in addStm $ Let pat aux $ BasicOp $ Concat d' (x' :| xs') w
650 maybeDistributeStm stm acc =
651 addStmToAcc stm acc
652
653 distributeSingleUnaryStm ::
654 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
655 DistAcc rep ->
656 Stm SOACS ->
657 VName ->
658 (KernelNest -> Pat Type -> VName -> DistNestT rep m (Stms rep)) ->
659 DistNestT rep m (DistAcc rep)
660 distributeSingleUnaryStm acc stm stm_arr f =
661 distributeSingleStm acc stm >>= \case
662 Just (kernels, res, nest, acc')
663 | map resSubExp res == map Var (patNames $ stmPat stm),
664 (outer, _) <- nest,
665 [(_, arr)] <- loopNestingParamsAndArrs outer,
666 boundInKernelNest nest `namesIntersection` freeIn stm
667 == oneName stm_arr,
668 perfectlyMapped arr nest -> do
669 addPostStms kernels
670 let outerpat = loopNestingPat $ fst nest
671 localScope (typeEnvFromDistAcc acc') $ do
672 postStm =<< f nest outerpat arr
673 pure acc'
674 _ -> addStmToAcc stm acc
675 where
676 perfectlyMapped arr (outer, nest)
677 | [(p, arr')] <- loopNestingParamsAndArrs outer,
678 arr == arr' =
679 case nest of
680 [] -> paramName p == stm_arr
681 x : xs -> perfectlyMapped (paramName p) (x, xs)
682 | otherwise =
683 False
684
685 distribute ::
686 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
687 DistAcc rep ->
688 DistNestT rep m (DistAcc rep)
689 distribute acc =
690 fromMaybe acc <$> distributeIfPossible acc
691
692 mkSegLevel ::
693 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
694 DistNestT rep m (MkSegLevel rep (DistNestT rep m))
695 mkSegLevel = do
696 mk_lvl <- asks distSegLevel
697 pure $ \w desc r -> do
698 (lvl, stms) <- lift $ liftInner $ runBuilderT' $ mk_lvl w desc r
699 addStms stms
700 pure lvl
701
702 distributeIfPossible ::
703 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
704 DistAcc rep ->
705 DistNestT rep m (Maybe (DistAcc rep))
706 distributeIfPossible acc = do
707 nest <- asks distNest
708 mk_lvl <- mkSegLevel
709 tryDistribute mk_lvl nest (distTargets acc) (distStms acc) >>= \case
710 Nothing -> pure Nothing
711 Just (targets, kernel) -> do
712 postStm kernel
713 pure $
714 Just
715 DistAcc
716 { distTargets = targets,
717 distStms = mempty
718 }
719
720 distributeSingleStm ::
721 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
722 DistAcc rep ->
723 Stm SOACS ->
724 DistNestT
725 rep
726 m
727 ( Maybe
728 ( PostStms rep,
729 Result,
730 KernelNest,
731 DistAcc rep
732 )
733 )
734 distributeSingleStm acc stm = do
735 nest <- asks distNest
736 mk_lvl <- mkSegLevel
737 tryDistribute mk_lvl nest (distTargets acc) (distStms acc) >>= \case
738 Nothing -> pure Nothing
739 Just (targets, distributed_stms) ->
740 tryDistributeStm nest targets stm >>= \case
741 Nothing -> pure Nothing
742 Just (res, targets', new_kernel_nest) ->
743 pure $
744 Just
745 ( PostStms distributed_stms,
746 res,
747 new_kernel_nest,
748 DistAcc
749 { distTargets = targets',
750 distStms = mempty
751 }
752 )
753
754 segmentedScatterKernel ::
755 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
756 KernelNest ->
757 [Int] ->
758 Pat Type ->
759 Certs ->
760 SubExp ->
761 Lambda rep ->
762 [VName] ->
763 [(Shape, Int, VName)] ->
764 DistNestT rep m (Stms rep)
765 segmentedScatterKernel nest perm scatter_pat cs scatter_w lam ivs dests = do
766 -- We replicate some of the checking done by 'isSegmentedOp', but
767 -- things are different because a scatter is not a reduction or
768 -- scan.
769 --
770 -- First, pretend that the scatter is also part of the nesting. The
771 -- KernelNest we produce here is technically not sensible, but it's
772 -- good enough for flatKernel to work.
773 let nesting =
774 MapNesting scatter_pat (StmAux cs mempty mempty ()) scatter_w $ zip (lambdaParams lam) ivs
775 nest' =
776 pushInnerKernelNesting (scatter_pat, bodyResult $ lambdaBody lam) nesting nest
777 (ispace, kernel_inps) <- flatKernel nest'
778
779 let (as_ws, as_ns, as) = unzip3 dests
780 indexes = zipWith (*) as_ns $ map length as_ws
781
782 -- The input/output arrays ('as') _must_ correspond to some kernel
783 -- input, or else the original nested scatter would have been
784 -- ill-typed. Find them.
785 as_inps <- mapM (findInput kernel_inps) as
786
787 mk_lvl <- mkSegLevel
788
789 let (is, vs) = splitAt (sum indexes) $ bodyResult $ lambdaBody lam
790 (is', k_body_stms) <- runBuilder $ do
791 addStms $ bodyStms $ lambdaBody lam
792 pure is
793
794 let grouped = groupScatterResults (zip3 as_ws as_ns as_inps) (is' ++ vs)
795 (_, dest_arrs, _) = unzip3 grouped
796
797 dest_arrs_ts <- mapM (lookupType . kernelInputArray) dest_arrs
798
799 let k_body =
800 KernelBody () k_body_stms $
801 zipWith (inPlaceReturn ispace) dest_arrs_ts grouped
802 -- Remove unused kernel inputs, since some of these might
803 -- reference the array we are scattering into.
804 kernel_inps' =
805 filter ((`nameIn` freeIn k_body) . kernelInputName) kernel_inps
806
807 (k, k_stms) <- mapKernel mk_lvl ispace kernel_inps' dest_arrs_ts k_body
808
809 traverse renameStm <=< runBuilder_ $ do
810 addStms k_stms
811
812 let pat = Pat . rearrangeShape perm $ patElems $ loopNestingPat $ fst nest
813 letBind pat $ Op $ segOp k
814 where
815 findInput kernel_inps a =
816 maybe bad pure $ find ((== a) . kernelInputName) kernel_inps
817 bad = error "Ill-typed nested scatter encountered."
818
819 inPlaceReturn ispace arr_t (_, inp, is_vs) =
820 WriteReturns write_cs (kernelInputArray inp) $ do
821 (is, v) <- is_vs
822 pure
823 ( fullSlice arr_t . map DimFix $
824 map Var (init gtids) ++ map resSubExp is,
825 resSubExp v
826 )
827 where
828 write_cs =
829 foldMap (foldMap resCerts . fst) is_vs
830 <> foldMap (resCerts . snd) is_vs
831 (gtids, _ws) = unzip ispace
832
833 segmentedUpdateKernel ::
834 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
835 KernelNest ->
836 [Int] ->
837 Certs ->
838 VName ->
839 Slice SubExp ->
840 VName ->
841 DistNestT rep m (Stms rep)
842 segmentedUpdateKernel nest perm cs arr slice v = do
843 (base_ispace, kernel_inps) <- flatKernel nest
844 let slice_dims = sliceDims slice
845 slice_gtids <- replicateM (length slice_dims) (newVName "gtid_slice")
846
847 let ispace = base_ispace ++ zip slice_gtids slice_dims
848
849 ((dest_t, res), kstms) <- runBuilder $ do
850 -- Compute indexes into full array.
851 v' <-
852 certifying cs . letSubExp "v" . BasicOp . Index v $
853 Slice (map (DimFix . Var) slice_gtids)
854 slice_is <-
855 traverse (toSubExp "index") $
856 fixSlice (fmap pe64 slice) $
857 map (pe64 . Var) slice_gtids
858
859 let write_is = map (Var . fst) base_ispace ++ slice_is
860 arr' =
861 maybe (error "incorrectly typed Update") kernelInputArray $
862 find ((== arr) . kernelInputName) kernel_inps
863 arr_t <- lookupType arr'
864 pure
865 ( arr_t,
866 WriteReturns mempty arr' [(Slice $ map DimFix write_is, v')]
867 )
868
869 -- Remove unused kernel inputs, since some of these might
870 -- reference the array we are scattering into.
871 let kernel_inps' =
872 filter ((`nameIn` (freeIn kstms <> freeIn res)) . kernelInputName) kernel_inps
873
874 mk_lvl <- mkSegLevel
875 (k, prestms) <-
876 mapKernel mk_lvl ispace kernel_inps' [dest_t] $
877 KernelBody () kstms [res]
878
879 traverse renameStm <=< runBuilder_ $ do
880 addStms prestms
881 let pat = Pat . rearrangeShape perm $ patElems $ loopNestingPat $ fst nest
882 letBind pat $ Op $ segOp k
883
884 segmentedGatherKernel ::
885 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
886 KernelNest ->
887 Certs ->
888 VName ->
889 Slice SubExp ->
890 DistNestT rep m (Stms rep)
891 segmentedGatherKernel nest cs arr slice = do
892 let slice_dims = sliceDims slice
893 slice_gtids <- replicateM (length slice_dims) (newVName "gtid_slice")
894
895 (base_ispace, kernel_inps) <- flatKernel nest
896 let ispace = base_ispace ++ zip slice_gtids slice_dims
897
898 ((res_t, res), kstms) <- runBuilder $ do
899 -- Compute indexes into full array.
900 slice'' <-
901 subExpSlice . sliceSlice (primExpSlice slice) $
902 primExpSlice $
903 Slice $
904 map (DimFix . Var) slice_gtids
905 v' <- certifying cs $ letSubExp "v" $ BasicOp $ Index arr slice''
906 v_t <- subExpType v'
907 pure (v_t, Returns ResultMaySimplify mempty v')
908
909 mk_lvl <- mkSegLevel
910 (k, prestms) <-
911 mapKernel mk_lvl ispace kernel_inps [res_t] $
912 KernelBody () kstms [res]
913
914 traverse renameStm <=< runBuilder_ $ do
915 addStms prestms
916
917 let pat = Pat $ patElems $ loopNestingPat $ fst nest
918
919 letBind pat $ Op $ segOp k
920
921 segmentedHistKernel ::
922 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
923 KernelNest ->
924 [Int] ->
925 Certs ->
926 SubExp ->
927 [SOACS.HistOp SOACS] ->
928 Lambda rep ->
929 [VName] ->
930 DistNestT rep m (Stms rep)
931 segmentedHistKernel nest perm cs hist_w ops lam arrs = do
932 -- We replicate some of the checking done by 'isSegmentedOp', but
933 -- things are different because a Hist is not a reduction or
934 -- scan.
935 (ispace, inputs) <- flatKernel nest
936 let orig_pat =
937 Pat . rearrangeShape perm $
938 patElems $
939 loopNestingPat $
940 fst nest
941
942 -- The input/output arrays _must_ correspond to some kernel input,
943 -- or else the original nested Hist would have been ill-typed.
944 -- Find them.
945 ops' <- forM ops $ \(SOACS.HistOp num_bins rf dests nes op) ->
946 SOACS.HistOp num_bins rf
947 <$> mapM (fmap kernelInputArray . findInput inputs) dests
948 <*> pure nes
949 <*> pure op
950
951 mk_lvl <- asks distSegLevel
952 onLambda <- asks distOnSOACSLambda
953 let onLambda' = fmap fst . runBuilder . onLambda
954 liftInner $
955 runBuilderT'_ $ do
956 -- It is important not to launch unnecessarily many threads for
957 -- histograms, because it may mean we unnecessarily need to reduce
958 -- subhistograms as well.
959 lvl <- mk_lvl (hist_w : map snd ispace) "seghist" $ NoRecommendation SegNoVirt
960 addStms
961 =<< histKernel onLambda' lvl orig_pat ispace inputs cs hist_w ops' lam arrs
962 where
963 findInput kernel_inps a =
964 maybe bad pure $ find ((== a) . kernelInputName) kernel_inps
965 bad = error "Ill-typed nested Hist encountered."
966
967 histKernel ::
968 (MonadBuilder m, DistRep (Rep m)) =>
969 (Lambda SOACS -> m (Lambda (Rep m))) ->
970 SegOpLevel (Rep m) ->
971 Pat Type ->
972 [(VName, SubExp)] ->
973 [KernelInput] ->
974 Certs ->
975 SubExp ->
976 [SOACS.HistOp SOACS] ->
977 Lambda (Rep m) ->
978 [VName] ->
979 m (Stms (Rep m))
980 histKernel onLambda lvl orig_pat ispace inputs cs hist_w ops lam arrs = runBuilderT'_ $ do
981 ops' <- forM ops $ \(SOACS.HistOp dest_shape rf dests nes op) -> do
982 (op', nes', shape) <- determineReduceOp op nes
983 op'' <- lift $ onLambda op'
984 pure $ HistOp dest_shape rf dests nes' shape op''
985
986 let isDest = flip elem $ concatMap histDest ops'
987 inputs' = filter (not . isDest . kernelInputArray) inputs
988
989 certifying cs $
990 addStms
991 =<< traverse renameStm
992 =<< segHist lvl orig_pat hist_w ispace inputs' ops' lam arrs
993
994 determineReduceOp ::
995 (MonadBuilder m) =>
996 Lambda SOACS ->
997 [SubExp] ->
998 m (Lambda SOACS, [SubExp], Shape)
999 determineReduceOp lam nes =
1000 -- FIXME? We are assuming that the accumulator is a replicate, and
1001 -- we fish out its value in a gross way.
1002 case mapM subExpVar nes of
1003 Just ne_vs' -> do
1004 let (shape, lam') = isVectorMap lam
1005 nes' <- forM ne_vs' $ \ne_v -> do
1006 ne_v_t <- lookupType ne_v
1007 letSubExp "hist_ne" $
1008 BasicOp $
1009 Index ne_v $
1010 fullSlice ne_v_t $
1011 replicate (shapeRank shape) $
1012 DimFix $
1013 intConst Int64 0
1014 pure (lam', nes', shape)
1015 Nothing ->
1016 pure (lam, nes, mempty)
1017
1018 isVectorMap :: Lambda SOACS -> (Shape, Lambda SOACS)
1019 isVectorMap lam
1020 | [Let (Pat pes) _ (Op (Screma w arrs form))] <-
1021 stmsToList $ bodyStms $ lambdaBody lam,
1022 map resSubExp (bodyResult (lambdaBody lam)) == map (Var . patElemName) pes,
1023 Just map_lam <- isMapSOAC form,
1024 arrs == map paramName (lambdaParams lam) =
1025 let (shape, lam') = isVectorMap map_lam
1026 in (Shape [w] <> shape, lam')
1027 | otherwise = (mempty, lam)
1028
1029 segmentedScanomapKernel ::
1030 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
1031 KernelNest ->
1032 [Int] ->
1033 Certs ->
1034 SubExp ->
1035 Lambda SOACS ->
1036 Lambda rep ->
1037 [SubExp] ->
1038 [VName] ->
1039 DistNestT rep m (Maybe (Stms rep))
1040 segmentedScanomapKernel nest perm cs segment_size lam map_lam nes arrs = do
1041 mk_lvl <- asks distSegLevel
1042 onLambda <- asks distOnSOACSLambda
1043 let onLambda' = fmap fst . runBuilder . onLambda
1044 isSegmentedOp nest perm (freeIn lam) (freeIn map_lam) nes [] $
1045 \pat ispace inps nes' _ -> do
1046 (lam', nes'', shape) <- determineReduceOp lam nes'
1047 lam'' <- onLambda' lam'
1048 let scan_op = SegBinOp Noncommutative lam'' nes'' shape
1049 lvl <- mk_lvl (segment_size : map snd ispace) "segscan" $ NoRecommendation SegNoVirt
1050 addStms
1051 =<< traverse renameStm
1052 =<< segScan lvl pat cs segment_size [scan_op] map_lam arrs ispace inps
1053
1054 regularSegmentedRedomapKernel ::
1055 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
1056 KernelNest ->
1057 [Int] ->
1058 Certs ->
1059 SubExp ->
1060 Commutativity ->
1061 Lambda rep ->
1062 Lambda rep ->
1063 [SubExp] ->
1064 [VName] ->
1065 DistNestT rep m (Maybe (Stms rep))
1066 regularSegmentedRedomapKernel nest perm cs segment_size comm lam map_lam nes arrs = do
1067 mk_lvl <- asks distSegLevel
1068 isSegmentedOp nest perm (freeIn lam) (freeIn map_lam) nes [] $
1069 \pat ispace inps nes' _ -> do
1070 let red_op = SegBinOp comm lam nes' mempty
1071 lvl <- mk_lvl (segment_size : map snd ispace) "segred" $ NoRecommendation SegNoVirt
1072 addStms
1073 =<< traverse renameStm
1074 =<< segRed lvl pat cs segment_size [red_op] map_lam arrs ispace inps
1075
1076 isSegmentedOp ::
1077 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
1078 KernelNest ->
1079 [Int] ->
1080 Names ->
1081 Names ->
1082 [SubExp] ->
1083 [VName] ->
1084 ( Pat Type ->
1085 [(VName, SubExp)] ->
1086 [KernelInput] ->
1087 [SubExp] ->
1088 [VName] ->
1089 BuilderT rep m ()
1090 ) ->
1091 DistNestT rep m (Maybe (Stms rep))
1092 isSegmentedOp nest perm free_in_op _free_in_fold_op nes arrs m = runMaybeT $ do
1093 -- We must verify that array inputs to the operation are inputs to
1094 -- the outermost loop nesting or free in the loop nest. Nothing
1095 -- free in the op may be bound by the nest. Furthermore, the
1096 -- neutral elements must be free in the loop nest.
1097 --
1098 -- We must summarise any names from free_in_op that are bound in the
1099 -- nest, and describe how to obtain them given segment indices.
1100
1101 let bound_by_nest = boundInKernelNest nest
1102
1103 (ispace, kernel_inps) <- flatKernel nest
1104
1105 when (free_in_op `namesIntersect` bound_by_nest) $
1106 fail "Non-fold lambda uses nest-bound parameters."
1107
1108 let indices = map fst ispace
1109
1110 prepareNe (Var v)
1111 | v `nameIn` bound_by_nest =
1112 fail "Neutral element bound in nest"
1113 prepareNe ne = pure ne
1114
1115 prepareArr arr =
1116 case find ((== arr) . kernelInputName) kernel_inps of
1117 Just inp
1118 | kernelInputIndices inp == map Var indices ->
1119 pure $ pure $ kernelInputArray inp
1120 Nothing
1121 | arr `notNameIn` bound_by_nest ->
1122 -- This input is something that is free inside
1123 -- the loop nesting. We will have to replicate
1124 -- it.
1125 pure $
1126 letExp
1127 (baseString arr ++ "_repd")
1128 (BasicOp $ Replicate (Shape $ map snd ispace) $ Var arr)
1129 _ ->
1130 fail "Input not free, perfectly mapped, or outermost."
1131
1132 nes' <- mapM prepareNe nes
1133
1134 mk_arrs <- mapM prepareArr arrs
1135
1136 lift $
1137 liftInner $
1138 runBuilderT'_ $ do
1139 nested_arrs <- sequence mk_arrs
1140
1141 let pat =
1142 Pat . rearrangeShape perm $
1143 patElems $
1144 loopNestingPat $
1145 fst nest
1146
1147 m pat ispace kernel_inps nes' nested_arrs
1148
1149 permutationAndMissing :: Pat Type -> Result -> Maybe ([Int], [PatElem Type])
1150 permutationAndMissing (Pat pes) res = do
1151 let (_used, unused) =
1152 partition ((`nameIn` freeIn res) . patElemName) pes
1153 res' = map resSubExp res
1154 res_expanded = res' ++ map (Var . patElemName) unused
1155 perm <- map (Var . patElemName) pes `isPermutationOf` res_expanded
1156 pure (perm, unused)
1157
1158 -- Add extra pattern elements to every kernel nesting level.
1159 expandKernelNest ::
1160 (MonadFreshNames m) => [PatElem Type] -> KernelNest -> m KernelNest
1161 expandKernelNest pes (outer_nest, inner_nests) = do
1162 let outer_size =
1163 loopNestingWidth outer_nest
1164 : map loopNestingWidth inner_nests
1165 inner_sizes = tails $ map loopNestingWidth inner_nests
1166 outer_nest' <- expandWith outer_nest outer_size
1167 inner_nests' <- zipWithM expandWith inner_nests inner_sizes
1168 pure (outer_nest', inner_nests')
1169 where
1170 expandWith nest dims = do
1171 pes' <- mapM (expandPatElemWith dims) pes
1172 pure
1173 nest
1174 { loopNestingPat =
1175 Pat $ patElems (loopNestingPat nest) <> pes'
1176 }
1177
1178 expandPatElemWith dims pe = do
1179 name <- newVName $ baseString $ patElemName pe
1180 pure
1181 pe
1182 { patElemName = name,
1183 patElemDec = patElemType pe `arrayOfShape` Shape dims
1184 }
1185
1186 kernelOrNot ::
1187 (MonadFreshNames m, DistRep rep) =>
1188 Certs ->
1189 Stm SOACS ->
1190 DistAcc rep ->
1191 PostStms rep ->
1192 DistAcc rep ->
1193 Maybe (Stms rep) ->
1194 DistNestT rep m (DistAcc rep)
1195 kernelOrNot cs stm acc _ _ Nothing =
1196 addStmToAcc (certify cs stm) acc
1197 kernelOrNot cs _ _ kernels acc' (Just stms) = do
1198 addPostStms kernels
1199 postStm $ fmap (certify cs) stms
1200 pure acc'
1201
1202 distributeMap ::
1203 (MonadFreshNames m, LocalScope rep m, DistRep rep) =>
1204 MapLoop ->
1205 DistAcc rep ->
1206 DistNestT rep m (DistAcc rep)
1207 distributeMap (MapLoop pat aux w lam arrs) acc =
1208 distribute
1209 =<< mapNesting
1210 pat
1211 aux
1212 w
1213 lam
1214 arrs
1215 (distribute =<< distributeMapBodyStms acc' lam_stms)
1216 where
1217 acc' =
1218 DistAcc
1219 { distTargets =
1220 pushInnerTarget
1221 (pat, bodyResult $ lambdaBody lam)
1222 $ distTargets acc,
1223 distStms = mempty
1224 }
1225
1226 lam_stms = bodyStms $ lambdaBody lam