| 1 |
{-# LANGUAGE TypeFamilies #-} |
| 2 |
|
| 3 |
-- | Interchanging scans with inner maps. |
| 4 |
module Futhark.Pass.ExtractKernels.ISRWIM |
| 5 |
( iswim, |
| 6 |
irwim, |
| 7 |
rwimPossible, |
| 8 |
) |
| 9 |
where |
| 10 |
|
| 11 |
import Control.Arrow (first) |
| 12 |
import Control.Monad |
| 13 |
import Futhark.IR.SOACS |
| 14 |
import Futhark.MonadFreshNames |
| 15 |
import Futhark.Tools |
| 16 |
|
| 17 |
-- | Interchange Scan With Inner Map. Tries to turn a @scan(map)@ into a |
| 18 |
-- @map(scan) |
| 19 |
iswim :: |
| 20 |
(MonadBuilder m, Rep m ~ SOACS) => |
| 21 |
Pat Type -> |
| 22 |
SubExp -> |
| 23 |
Lambda SOACS -> |
| 24 |
[(SubExp, VName)] -> |
| 25 |
Maybe (m ()) |
| 26 |
iswim res_pat w scan_fun scan_input |
| 27 |
| Just (map_pat, map_aux, map_w, map_fun) <- rwimPossible scan_fun = Just $ do |
| 28 |
let (accs, arrs) = unzip scan_input |
| 29 |
arrs' <- transposedArrays arrs |
| 30 |
accs' <- mapM (letExp "acc" . BasicOp . SubExp) accs |
| 31 |
|
| 32 |
let map_arrs' = accs' ++ arrs' |
| 33 |
(scan_acc_params, scan_elem_params) = |
| 34 |
splitAt (length arrs) $ lambdaParams scan_fun |
| 35 |
map_params = |
| 36 |
map removeParamOuterDim scan_acc_params |
| 37 |
++ map (setParamOuterDimTo w) scan_elem_params |
| 38 |
map_rettype = map (setOuterDimTo w) $ lambdaReturnType scan_fun |
| 39 |
|
| 40 |
scan_params = lambdaParams map_fun |
| 41 |
scan_body = lambdaBody map_fun |
| 42 |
scan_rettype = lambdaReturnType map_fun |
| 43 |
scan_fun' = Lambda scan_params scan_rettype scan_body |
| 44 |
scan_input' = |
| 45 |
map (first Var) $ |
| 46 |
uncurry zip $ |
| 47 |
splitAt (length arrs') $ |
| 48 |
map paramName map_params |
| 49 |
(nes', scan_arrs) = unzip scan_input' |
| 50 |
|
| 51 |
scan_soac <- scanSOAC [Scan scan_fun' nes'] |
| 52 |
let map_body = |
| 53 |
mkBody |
| 54 |
( oneStm $ |
| 55 |
Let (setPatOuterDimTo w map_pat) (defAux ()) $ |
| 56 |
Op $ |
| 57 |
Screma w scan_arrs scan_soac |
| 58 |
) |
| 59 |
$ varsRes |
| 60 |
$ patNames map_pat |
| 61 |
map_fun' = Lambda map_params map_rettype map_body |
| 62 |
|
| 63 |
res_pat' <- |
| 64 |
fmap basicPat $ |
| 65 |
mapM (newIdent' (<> "_transposed") . transposeIdentType) $ |
| 66 |
patIdents res_pat |
| 67 |
|
| 68 |
addStm . Let res_pat' map_aux . Op $ |
| 69 |
Screma map_w map_arrs' (mapSOAC map_fun') |
| 70 |
|
| 71 |
forM_ (zip (patIdents res_pat) (patIdents res_pat')) $ \(to, from) -> do |
| 72 |
let perm = [1, 0] ++ [2 .. arrayRank (identType from) - 1] |
| 73 |
addStm $ |
| 74 |
Let (basicPat [to]) (defAux ()) . BasicOp $ |
| 75 |
Rearrange (identName from) perm |
| 76 |
| otherwise = Nothing |
| 77 |
|
| 78 |
-- | Interchange Reduce With Inner Map. Tries to turn a @reduce(map)@ into a |
| 79 |
-- @map(reduce) |
| 80 |
irwim :: |
| 81 |
(MonadBuilder m, Rep m ~ SOACS) => |
| 82 |
Pat Type -> |
| 83 |
SubExp -> |
| 84 |
Commutativity -> |
| 85 |
Lambda SOACS -> |
| 86 |
[(SubExp, VName)] -> |
| 87 |
Maybe (m ()) |
| 88 |
irwim res_pat w comm red_fun red_input |
| 89 |
| Just (map_pat, map_aux, map_w, map_fun) <- rwimPossible red_fun = Just $ do |
| 90 |
let (accs, arrs) = unzip red_input |
| 91 |
arrs' <- transposedArrays arrs |
| 92 |
-- FIXME? Can we reasonably assume that the accumulator is a |
| 93 |
-- replicate? We also assume that it is non-empty. |
| 94 |
let indexAcc (Var v) = do |
| 95 |
v_t <- lookupType v |
| 96 |
letSubExp "acc" $ |
| 97 |
BasicOp $ |
| 98 |
Index v $ |
| 99 |
fullSlice v_t [DimFix $ intConst Int64 0] |
| 100 |
indexAcc Constant {} = |
| 101 |
error "irwim: array accumulator is a constant." |
| 102 |
accs' <- mapM indexAcc accs |
| 103 |
|
| 104 |
let (_red_acc_params, red_elem_params) = |
| 105 |
splitAt (length arrs) $ lambdaParams red_fun |
| 106 |
map_rettype = map rowType $ lambdaReturnType red_fun |
| 107 |
map_params = map (setParamOuterDimTo w) red_elem_params |
| 108 |
|
| 109 |
red_params = lambdaParams map_fun |
| 110 |
red_body = lambdaBody map_fun |
| 111 |
red_rettype = lambdaReturnType map_fun |
| 112 |
red_fun' = Lambda red_params red_rettype red_body |
| 113 |
red_input' = zip accs' $ map paramName map_params |
| 114 |
red_pat = stripPatOuterDim map_pat |
| 115 |
|
| 116 |
map_body <- |
| 117 |
case irwim red_pat w comm red_fun' red_input' of |
| 118 |
Nothing -> do |
| 119 |
reduce_soac <- reduceSOAC [Reduce comm red_fun' $ map fst red_input'] |
| 120 |
pure |
| 121 |
$ mkBody |
| 122 |
( oneStm $ |
| 123 |
Let red_pat (defAux ()) $ |
| 124 |
Op $ |
| 125 |
Screma w (map snd red_input') reduce_soac |
| 126 |
) |
| 127 |
$ varsRes |
| 128 |
$ patNames map_pat |
| 129 |
Just m -> localScope (scopeOfLParams map_params) $ do |
| 130 |
map_body_stms <- collectStms_ m |
| 131 |
pure $ mkBody map_body_stms $ varsRes $ patNames map_pat |
| 132 |
|
| 133 |
let map_fun' = Lambda map_params map_rettype map_body |
| 134 |
|
| 135 |
addStm . Let res_pat map_aux . Op . Screma map_w arrs' $ |
| 136 |
mapSOAC map_fun' |
| 137 |
| otherwise = Nothing |
| 138 |
|
| 139 |
-- | Does this reduce operator contain an inner map, and if so, what |
| 140 |
-- does that map look like? |
| 141 |
rwimPossible :: |
| 142 |
Lambda SOACS -> |
| 143 |
Maybe (Pat Type, StmAux (), SubExp, Lambda SOACS) |
| 144 |
rwimPossible fun |
| 145 |
| Body _ stms res <- lambdaBody fun, |
| 146 |
[stm] <- stmsToList stms, -- Body has a single binding |
| 147 |
map_pat <- stmPat stm, |
| 148 |
map Var (patNames map_pat) == map resSubExp res, -- Returned verbatim |
| 149 |
Op (Screma map_w map_arrs form) <- stmExp stm, |
| 150 |
Just map_fun <- isMapSOAC form, |
| 151 |
map paramName (lambdaParams fun) == map_arrs = |
| 152 |
Just (map_pat, stmAux stm, map_w, map_fun) |
| 153 |
| otherwise = |
| 154 |
Nothing |
| 155 |
|
| 156 |
transposedArrays :: (MonadBuilder m) => [VName] -> m [VName] |
| 157 |
transposedArrays arrs = forM arrs $ \arr -> do |
| 158 |
t <- lookupType arr |
| 159 |
let perm = [1, 0] ++ [2 .. arrayRank t - 1] |
| 160 |
letExp (baseString arr) $ BasicOp $ Rearrange arr perm |
| 161 |
|
| 162 |
removeParamOuterDim :: LParam SOACS -> LParam SOACS |
| 163 |
removeParamOuterDim param = |
| 164 |
let t = rowType $ paramType param |
| 165 |
in param {paramDec = t} |
| 166 |
|
| 167 |
setParamOuterDimTo :: SubExp -> LParam SOACS -> LParam SOACS |
| 168 |
setParamOuterDimTo w param = |
| 169 |
let t = setOuterDimTo w $ paramType param |
| 170 |
in param {paramDec = t} |
| 171 |
|
| 172 |
setIdentOuterDimTo :: SubExp -> Ident -> Ident |
| 173 |
setIdentOuterDimTo w ident = |
| 174 |
let t = setOuterDimTo w $ identType ident |
| 175 |
in ident {identType = t} |
| 176 |
|
| 177 |
setOuterDimTo :: SubExp -> Type -> Type |
| 178 |
setOuterDimTo w t = |
| 179 |
arrayOfRow (rowType t) w |
| 180 |
|
| 181 |
setPatOuterDimTo :: SubExp -> Pat Type -> Pat Type |
| 182 |
setPatOuterDimTo w pat = |
| 183 |
basicPat $ map (setIdentOuterDimTo w) $ patIdents pat |
| 184 |
|
| 185 |
transposeIdentType :: Ident -> Ident |
| 186 |
transposeIdentType ident = |
| 187 |
ident {identType = transposeType $ identType ident} |
| 188 |
|
| 189 |
stripIdentOuterDim :: Ident -> Ident |
| 190 |
stripIdentOuterDim ident = |
| 191 |
ident {identType = rowType $ identType ident} |
| 192 |
|
| 193 |
stripPatOuterDim :: Pat Type -> Pat Type |
| 194 |
stripPatOuterDim pat = |
| 195 |
basicPat $ map stripIdentOuterDim $ patIdents pat |