Debian Codegraph @

src/Futhark/Pass/ExtractKernels/ISRWIM.hs

raw
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