Debian Codegraph @

src/Futhark/IR/GPU/Op.hs

raw
1 {-# LANGUAGE TypeFamilies #-}
2 {-# LANGUAGE UndecidableInstances #-}
3
4 module Futhark.IR.GPU.Op
5 ( -- * Size operations
6 SizeOp (..),
7
8 -- * Host operations
9 HostOp (..),
10 traverseHostOpStms,
11 typeCheckHostOp,
12
13 -- * SegOp refinements
14 SegLevel (..),
15 segVirt,
16 SegVirt (..),
17 SegSeqDims (..),
18 KernelGrid (..),
19
20 -- * Reexports
21 module Futhark.IR.GPU.Sizes,
22 module Futhark.IR.SegOp,
23 )
24 where
25
26 import Control.Monad
27 import Data.Sequence qualified as SQ
28 import Data.Text qualified as T
29 import Futhark.Analysis.Alias qualified as Alias
30 import Futhark.Analysis.Metrics
31 import Futhark.Analysis.SymbolTable qualified as ST
32 import Futhark.IR
33 import Futhark.IR.Aliases (Aliases, CanBeAliased (..))
34 import Futhark.IR.GPU.Sizes
35 import Futhark.IR.Mem (OpReturns (..), extReturns)
36 import Futhark.IR.Prop.Aliases
37 import Futhark.IR.SegOp
38 import Futhark.IR.TypeCheck qualified as TC
39 import Futhark.Optimise.Simplify.Engine qualified as Engine
40 import Futhark.Optimise.Simplify.Rep
41 import Futhark.Transform.Rename
42 import Futhark.Transform.Substitute
43 import Futhark.Util.Pretty
44 ( commasep,
45 parens,
46 ppTuple',
47 pretty,
48 (<+>),
49 )
50 import Futhark.Util.Pretty qualified as PP
51
52 -- | These dimensions (indexed from 0, outermost) of the corresponding
53 -- 'SegSpace' should not be parallelised, but instead iterated
54 -- sequentially. For example, with a 'SegSeqDims' of @[0]@ and a
55 -- 'SegSpace' with dimensions @[n][m]@, there will be an outer loop
56 -- with @n@ iterations, while the @m@ dimension will be parallelised.
57 --
58 -- Semantically, this has no effect, but it may allow reductions in
59 -- memory usage or other low-level optimisations. Operationally, the
60 -- guarantee is that for a SegSeqDims of e.g. @[i,j,k]@, threads
61 -- running at any given moment will always have the same indexes along
62 -- the dimensions specified by @[i,j,k]@.
63 --
64 -- At the moment, this is only supported for 'SegNoVirtFull'
65 -- intra-block parallelism in GPU code, as we have not yet found it
66 -- useful anywhere else.
67 newtype SegSeqDims = SegSeqDims {segSeqDims :: [Int]}
68 deriving (Eq, Ord, Show)
69
70 -- | Do we need block-virtualisation when generating code for the
71 -- segmented operation? In most cases, we do, but for some simple
72 -- kernels, we compute the full number of blocks in advance, and then
73 -- virtualisation is an unnecessary (but generally very small)
74 -- overhead. This only really matters for fairly trivial but very
75 -- wide @map@ kernels where each thread performs constant-time work on
76 -- scalars.
77 data SegVirt
78 = SegVirt
79 | SegNoVirt
80 | -- | Not only do we not need virtualisation, but we _guarantee_
81 -- that all physical threads participate in the work. This can
82 -- save some checks in code generation.
83 SegNoVirtFull SegSeqDims
84 deriving (Eq, Ord, Show)
85
86 -- | The actual, physical grid dimensions used for the GPU kernel
87 -- running this 'SegOp'.
88 data KernelGrid = KernelGrid
89 { gridNumBlocks :: Count NumBlocks SubExp,
90 gridBlockSize :: Count BlockSize SubExp
91 }
92 deriving (Eq, Ord, Show)
93
94 -- | At which level the *body* of a t'SegOp' executes.
95 data SegLevel
96 = SegThread SegVirt (Maybe KernelGrid)
97 | SegBlock SegVirt (Maybe KernelGrid)
98 | SegThreadInBlock SegVirt
99 deriving (Eq, Ord, Show)
100
101 -- | The 'SegVirt' of the 'SegLevel'.
102 segVirt :: SegLevel -> SegVirt
103 segVirt (SegThread v _) = v
104 segVirt (SegBlock v _) = v
105 segVirt (SegThreadInBlock v) = v
106
107 instance PP.Pretty SegVirt where
108 pretty SegNoVirt = mempty
109 pretty (SegNoVirtFull dims) = "full" <+> pretty (segSeqDims dims)
110 pretty SegVirt = "virtualise"
111
112 instance PP.Pretty KernelGrid where
113 pretty (KernelGrid num_tblocks tblock_size) =
114 "grid="
115 <> pretty num_tblocks
116 <> PP.semi
117 <+> "blocksize="
118 <> pretty tblock_size
119
120 instance PP.Pretty SegLevel where
121 pretty (SegThread virt grid) =
122 PP.parens ("thread" <> PP.semi <+> pretty virt <> PP.semi <+> pretty grid)
123 pretty (SegBlock virt grid) =
124 PP.parens ("block" <> PP.semi <+> pretty virt <> PP.semi <+> pretty grid)
125 pretty (SegThreadInBlock virt) =
126 PP.parens ("inblock" <> PP.semi <+> pretty virt)
127
128 instance Engine.Simplifiable KernelGrid where
129 simplify (KernelGrid num_tblocks tblock_size) =
130 KernelGrid
131 <$> traverse Engine.simplify num_tblocks
132 <*> traverse Engine.simplify tblock_size
133
134 instance Engine.Simplifiable SegLevel where
135 simplify (SegThread virt grid) =
136 SegThread virt <$> Engine.simplify grid
137 simplify (SegBlock virt grid) =
138 SegBlock virt <$> Engine.simplify grid
139 simplify (SegThreadInBlock virt) =
140 pure $ SegThreadInBlock virt
141
142 instance Substitute KernelGrid where
143 substituteNames substs (KernelGrid num_tblocks tblock_size) =
144 KernelGrid
145 (substituteNames substs num_tblocks)
146 (substituteNames substs tblock_size)
147
148 instance Substitute SegLevel where
149 substituteNames substs (SegThread virt grid) =
150 SegThread virt (substituteNames substs grid)
151 substituteNames substs (SegBlock virt grid) =
152 SegBlock virt (substituteNames substs grid)
153 substituteNames _ (SegThreadInBlock virt) =
154 SegThreadInBlock virt
155
156 instance Rename SegLevel where
157 rename = substituteRename
158
159 instance FreeIn KernelGrid where
160 freeIn' (KernelGrid num_tblocks tblock_size) =
161 freeIn' (num_tblocks, tblock_size)
162
163 instance FreeIn SegLevel where
164 freeIn' (SegThread _virt grid) = freeIn' grid
165 freeIn' (SegBlock _virt grid) = freeIn' grid
166 freeIn' (SegThreadInBlock _virt) = mempty
167
168 -- | A simple size-level query or computation.
169 data SizeOp
170 = -- | Produce some runtime-configurable size.
171 GetSize Name SizeClass
172 | -- | The maximum size of some class.
173 GetSizeMax SizeClass
174 | -- | Compare size (likely a threshold) with some integer value.
175 CmpSizeLe Name SizeClass SubExp
176 | -- | @CalcNumBlocks w max_num_tblocks tblock_size@ calculates the
177 -- number of GPU threadblocks to use for an input of the given size.
178 -- The @Name@ is a size name. Note that @w@ is an i64 to avoid
179 -- overflow issues.
180 CalcNumBlocks SubExp Name SubExp
181 deriving (Eq, Ord, Show)
182
183 instance Substitute SizeOp where
184 substituteNames substs (CmpSizeLe name sclass x) =
185 CmpSizeLe name sclass (substituteNames substs x)
186 substituteNames substs (CalcNumBlocks w max_num_tblocks tblock_size) =
187 CalcNumBlocks
188 (substituteNames substs w)
189 max_num_tblocks
190 (substituteNames substs tblock_size)
191 substituteNames _ op = op
192
193 instance Rename SizeOp where
194 rename (CmpSizeLe name sclass x) =
195 CmpSizeLe name sclass <$> rename x
196 rename (CalcNumBlocks w max_num_tblocks tblock_size) =
197 CalcNumBlocks <$> rename w <*> pure max_num_tblocks <*> rename tblock_size
198 rename x = pure x
199
200 instance FreeIn SizeOp where
201 freeIn' (CmpSizeLe _ _ x) = freeIn' x
202 freeIn' (CalcNumBlocks w _ tblock_size) = freeIn' w <> freeIn' tblock_size
203 freeIn' _ = mempty
204
205 instance PP.Pretty SizeOp where
206 pretty (GetSize name size_class) =
207 "get_size" <> parens (commasep [pretty name, pretty size_class])
208 pretty (GetSizeMax size_class) =
209 "get_size_max" <> parens (commasep [pretty size_class])
210 pretty (CmpSizeLe name size_class x) =
211 "cmp_size"
212 <> parens (commasep [pretty name, pretty size_class])
213 <+> "<="
214 <+> pretty x
215 pretty (CalcNumBlocks w max_num_tblocks tblock_size) =
216 "calc_num_tblocks" <> parens (commasep [pretty w, pretty max_num_tblocks, pretty tblock_size])
217
218 instance OpMetrics SizeOp where
219 opMetrics GetSize {} = seen "GetSize"
220 opMetrics GetSizeMax {} = seen "GetSizeMax"
221 opMetrics CmpSizeLe {} = seen "CmpSizeLe"
222 opMetrics CalcNumBlocks {} = seen "CalcNumBlocks"
223
224 typeCheckSizeOp :: (TC.Checkable rep) => SizeOp -> TC.TypeM rep ()
225 typeCheckSizeOp GetSize {} = pure ()
226 typeCheckSizeOp GetSizeMax {} = pure ()
227 typeCheckSizeOp (CmpSizeLe _ _ x) = TC.require [Prim int64] x
228 typeCheckSizeOp (CalcNumBlocks w _ tblock_size) = do
229 TC.require [Prim int64] w
230 TC.require [Prim int64] tblock_size
231
232 -- | A host-level operation; parameterised by what else it can do.
233 data HostOp op rep
234 = -- | A segmented operation.
235 SegOp (SegOp SegLevel rep)
236 | SizeOp SizeOp
237 | OtherOp (op rep)
238 | -- | Code to run sequentially on the GPU,
239 -- in a single thread.
240 GPUBody [Type] (Body rep)
241 deriving (Eq, Ord, Show)
242
243 -- | A helper for defining 'TraverseOpStms'.
244 traverseHostOpStms ::
245 (Monad m) =>
246 OpStmsTraverser m (op rep) rep ->
247 OpStmsTraverser m (HostOp op rep) rep
248 traverseHostOpStms _ f (SegOp segop) = SegOp <$> traverseSegOpStms f segop
249 traverseHostOpStms _ _ (SizeOp sizeop) = pure $ SizeOp sizeop
250 traverseHostOpStms onOtherOp f (OtherOp other) = OtherOp <$> onOtherOp f other
251 traverseHostOpStms _ f (GPUBody ts body) = do
252 stms <- f mempty $ bodyStms body
253 pure $ GPUBody ts $ body {bodyStms = stms}
254
255 instance (ASTRep rep, Substitute (op rep)) => Substitute (HostOp op rep) where
256 substituteNames substs (SegOp op) =
257 SegOp $ substituteNames substs op
258 substituteNames substs (OtherOp op) =
259 OtherOp $ substituteNames substs op
260 substituteNames substs (SizeOp op) =
261 SizeOp $ substituteNames substs op
262 substituteNames substs (GPUBody ts body) =
263 GPUBody (substituteNames substs ts) (substituteNames substs body)
264
265 instance (ASTRep rep, Rename (op rep)) => Rename (HostOp op rep) where
266 rename (SegOp op) = SegOp <$> rename op
267 rename (OtherOp op) = OtherOp <$> rename op
268 rename (SizeOp op) = SizeOp <$> rename op
269 rename (GPUBody ts body) = GPUBody <$> rename ts <*> rename body
270
271 instance (IsOp op) => IsOp (HostOp op) where
272 safeOp (SegOp op) = safeOp op
273 safeOp (OtherOp op) = safeOp op
274 safeOp (SizeOp _) = True
275 safeOp (GPUBody _ body) = all (safeExp . stmExp) $ bodyStms body
276
277 cheapOp (SegOp op) = cheapOp op
278 cheapOp (OtherOp op) = cheapOp op
279 cheapOp (SizeOp _) = True
280 cheapOp (GPUBody types body) =
281 -- Current GPUBody usage only benefits from hoisting kernels that
282 -- transfer scalars to device.
283 SQ.null (bodyStms body) && all ((== 0) . arrayRank) types
284
285 opDependencies (SegOp op) = opDependencies op
286 opDependencies (OtherOp op) = opDependencies op
287 opDependencies (SizeOp op) = [freeIn op]
288 opDependencies (GPUBody _ body) =
289 replicate (length . bodyResult $ body) (freeIn body)
290
291 instance (TypedOp op) => TypedOp (HostOp op) where
292 opType (SegOp op) = opType op
293 opType (OtherOp op) = opType op
294 opType (SizeOp (GetSize _ _)) = pure [Prim int64]
295 opType (SizeOp (GetSizeMax _)) = pure [Prim int64]
296 opType (SizeOp CmpSizeLe {}) = pure [Prim Bool]
297 opType (SizeOp (CalcNumBlocks {})) = pure [Prim int64]
298 opType (GPUBody ts _) =
299 pure $ staticShapes $ map (`arrayOfRow` intConst Int64 1) ts
300
301 instance (AliasedOp op) => AliasedOp (HostOp op) where
302 opAliases (SegOp op) = opAliases op
303 opAliases (OtherOp op) = opAliases op
304 opAliases (SizeOp _) = [mempty]
305 opAliases (GPUBody ts _) = map (const mempty) ts
306
307 consumedInOp (SegOp op) = consumedInOp op
308 consumedInOp (OtherOp op) = consumedInOp op
309 consumedInOp (SizeOp _) = mempty
310 consumedInOp (GPUBody _ body) = consumedInBody body
311
312 instance (ASTRep rep, FreeIn (op rep)) => FreeIn (HostOp op rep) where
313 freeIn' (SegOp op) = freeIn' op
314 freeIn' (OtherOp op) = freeIn' op
315 freeIn' (SizeOp op) = freeIn' op
316 freeIn' (GPUBody ts body) = freeIn' ts <> freeIn' body
317
318 instance (CanBeAliased op) => CanBeAliased (HostOp op) where
319 addOpAliases aliases (SegOp op) = SegOp $ addOpAliases aliases op
320 addOpAliases aliases (GPUBody ts body) = GPUBody ts $ Alias.analyseBody aliases body
321 addOpAliases aliases (OtherOp op) = OtherOp $ addOpAliases aliases op
322 addOpAliases _ (SizeOp op) = SizeOp op
323
324 instance (CanBeWise op) => CanBeWise (HostOp op) where
325 addOpWisdom (SegOp op) = SegOp $ addOpWisdom op
326 addOpWisdom (OtherOp op) = OtherOp $ addOpWisdom op
327 addOpWisdom (SizeOp op) = SizeOp op
328 addOpWisdom (GPUBody ts body) = GPUBody ts $ informBody body
329
330 instance OpReturns (HostOp NoOp) where
331 opReturns (SegOp op) = segOpReturns op
332 opReturns k = extReturns <$> opType k
333
334 instance (ASTRep rep, ST.IndexOp (op rep)) => ST.IndexOp (HostOp op rep) where
335 indexOp vtable k (SegOp op) is = ST.indexOp vtable k op is
336 indexOp vtable k (OtherOp op) is = ST.indexOp vtable k op is
337 indexOp _ _ _ _ = Nothing
338
339 instance (PrettyRep rep, PP.Pretty (op rep)) => PP.Pretty (HostOp op rep) where
340 pretty (SegOp op) = pretty op
341 pretty (OtherOp op) = pretty op
342 pretty (SizeOp op) = pretty op
343 pretty (GPUBody ts body) =
344 "gpu" <+> PP.colon <+> ppTuple' (map pretty ts) <+> PP.nestedBlock "{" "}" (pretty body)
345
346 instance (OpMetrics (Op rep), OpMetrics (op rep)) => OpMetrics (HostOp op rep) where
347 opMetrics (SegOp op) = opMetrics op
348 opMetrics (OtherOp op) = opMetrics op
349 opMetrics (SizeOp op) = opMetrics op
350 opMetrics (GPUBody _ body) = inside "GPUBody" $ bodyMetrics body
351
352 instance (RephraseOp op) => RephraseOp (HostOp op) where
353 rephraseInOp r (SegOp op) = SegOp <$> rephraseInOp r op
354 rephraseInOp r (OtherOp op) = OtherOp <$> rephraseInOp r op
355 rephraseInOp _ (SizeOp op) = pure $ SizeOp op
356 rephraseInOp r (GPUBody ts body) = GPUBody ts <$> rephraseBody r body
357
358 checkGrid :: (TC.Checkable rep) => KernelGrid -> TC.TypeM rep ()
359 checkGrid grid = do
360 TC.require [Prim int64] $ unCount $ gridNumBlocks grid
361 TC.require [Prim int64] $ unCount $ gridBlockSize grid
362
363 checkSegLevel ::
364 (TC.Checkable rep) =>
365 Maybe SegLevel ->
366 SegLevel ->
367 TC.TypeM rep ()
368 checkSegLevel (Just SegBlock {}) (SegThreadInBlock _virt) =
369 pure ()
370 checkSegLevel _ (SegThreadInBlock _virt) =
371 TC.bad $ TC.TypeError "inblock SegOp not in block SegOp."
372 checkSegLevel (Just SegThread {}) _ =
373 TC.bad $ TC.TypeError "SegOps cannot occur when already at thread level."
374 checkSegLevel (Just SegThreadInBlock {}) _ =
375 TC.bad $ TC.TypeError "SegOps cannot occur when already at inblock level."
376 checkSegLevel _ (SegThread _virt Nothing) =
377 pure ()
378 checkSegLevel (Just _) SegThread {} =
379 TC.bad $ TC.TypeError "thread-level SegOp cannot be nested"
380 checkSegLevel Nothing (SegThread _virt grid) =
381 mapM_ checkGrid grid
382 checkSegLevel (Just _) SegBlock {} =
383 TC.bad $ TC.TypeError "block-level SegOp cannot be nested"
384 checkSegLevel Nothing (SegBlock _virt grid) =
385 mapM_ checkGrid grid
386
387 typeCheckHostOp ::
388 (TC.Checkable rep) =>
389 (SegLevel -> Op (Aliases rep) -> TC.TypeM rep ()) ->
390 Maybe SegLevel ->
391 (op (Aliases rep) -> TC.TypeM rep ()) ->
392 HostOp op (Aliases rep) ->
393 TC.TypeM rep ()
394 typeCheckHostOp checker lvl _ (SegOp op) =
395 TC.checkOpWith (checker $ segLevel op) $
396 typeCheckSegOp (checkSegLevel lvl) op
397 typeCheckHostOp _ Just {} _ GPUBody {} =
398 TC.bad $ TC.TypeError "GPUBody may not be nested in SegOps."
399 typeCheckHostOp _ _ f (OtherOp op) = f op
400 typeCheckHostOp _ _ _ (SizeOp op) = typeCheckSizeOp op
401 typeCheckHostOp _ Nothing _ (GPUBody ts body) = do
402 mapM_ TC.checkType ts
403 void $ TC.checkBody body
404 body_ts <-
405 extendedScope
406 (traverse subExpResType (bodyResult body))
407 (scopeOf (bodyStms body))
408 unless (body_ts == ts) . TC.bad . TC.TypeError . T.unlines $
409 [ "Expected type: " <> prettyTuple ts,
410 "Got body type: " <> prettyTuple body_ts
411 ]