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