| 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) |