Debian Codegraph @

src/Futhark/IR/GPU/Simplify.hs

raw
1 {-# LANGUAGE TypeFamilies #-}
2 {-# OPTIONS_GHC -fno-warn-orphans #-}
3
4 module Futhark.IR.GPU.Simplify
5 ( simplifyGPU,
6 simplifyLambda,
7 GPU,
8
9 -- * Building blocks
10 simplifyKernelOp,
11 )
12 where
13
14 import Futhark.Analysis.SymbolTable qualified as ST
15 import Futhark.Analysis.UsageTable qualified as UT
16 import Futhark.IR.GPU
17 import Futhark.IR.SOACS.Simplify qualified as SOAC
18 import Futhark.MonadFreshNames
19 import Futhark.Optimise.Simplify qualified as Simplify
20 import Futhark.Optimise.Simplify.Engine qualified as Engine
21 import Futhark.Optimise.Simplify.Rep
22 import Futhark.Optimise.Simplify.Rule
23 import Futhark.Optimise.Simplify.Rules
24 import Futhark.Pass
25 import Futhark.Tools
26 import Futhark.Util (focusNth)
27
28 simpleGPU :: Simplify.SimpleOps GPU
29 simpleGPU = Simplify.bindableSimpleOps $ simplifyKernelOp SOAC.simplifySOAC
30
31 simplifyGPU :: Prog GPU -> PassM (Prog GPU)
32 simplifyGPU =
33 Simplify.simplifyProg simpleGPU kernelRules Simplify.noExtraHoistBlockers
34
35 simplifyLambda ::
36 (HasScope GPU m, MonadFreshNames m) =>
37 Lambda GPU ->
38 m (Lambda GPU)
39 simplifyLambda =
40 Simplify.simplifyLambda simpleGPU kernelRules Engine.noExtraHoistBlockers
41
42 simplifyKernelOp ::
43 ( Engine.SimplifiableRep rep,
44 BodyDec rep ~ ()
45 ) =>
46 Simplify.SimplifyOp rep (op (Wise rep)) ->
47 HostOp op (Wise rep) ->
48 Engine.SimpleM rep (HostOp op (Wise rep), Stms (Wise rep))
49 simplifyKernelOp f (OtherOp op) = do
50 (op', stms) <- f op
51 pure (OtherOp op', stms)
52 simplifyKernelOp _ (SegOp op) = do
53 (op', hoisted) <- simplifySegOp op
54 pure (SegOp op', hoisted)
55 simplifyKernelOp _ (SizeOp (GetSize key size_class)) =
56 pure (SizeOp $ GetSize key size_class, mempty)
57 simplifyKernelOp _ (SizeOp (GetSizeMax size_class)) =
58 pure (SizeOp $ GetSizeMax size_class, mempty)
59 simplifyKernelOp _ (SizeOp (CmpSizeLe key size_class x)) = do
60 x' <- Engine.simplify x
61 pure (SizeOp $ CmpSizeLe key size_class x', mempty)
62 simplifyKernelOp _ (SizeOp (CalcNumBlocks w max_num_tblocks tblock_size)) = do
63 w' <- Engine.simplify w
64 pure (SizeOp $ CalcNumBlocks w' max_num_tblocks tblock_size, mempty)
65 simplifyKernelOp _ (GPUBody ts body) = do
66 ts' <- Engine.simplify ts
67 (hoisted, body') <-
68 Engine.simplifyBody keepOnGPU mempty (map (const mempty) ts) body
69 pure (GPUBody ts' body', hoisted)
70 where
71 keepOnGPU _ _ = keepExpOnGPU . stmExp
72 keepExpOnGPU (BasicOp Index {}) = True
73 keepExpOnGPU (BasicOp (ArrayLit _ t)) | primType t = True
74 keepExpOnGPU Loop {} = True
75 keepExpOnGPU _ = False
76
77 instance TraverseOpStms (Wise GPU) where
78 traverseOpStms = traverseHostOpStms traverseSOACStms
79
80 instance BuilderOps (Wise GPU)
81
82 instance HasSegOp (Wise GPU) where
83 type SegOpLevel (Wise GPU) = SegLevel
84 asSegOp (SegOp op) = Just op
85 asSegOp _ = Nothing
86 segOp = SegOp
87
88 instance SOAC.HasSOAC (Wise GPU) where
89 asSOAC (OtherOp soac) = Just soac
90 asSOAC _ = Nothing
91 soacOp = OtherOp
92
93 kernelRules :: RuleBook (Wise GPU)
94 kernelRules =
95 standardRules
96 <> segOpRules
97 <> ruleBook
98 [ RuleOp SOAC.simplifyKnownIterationSOAC,
99 RuleOp SOAC.removeReplicateMapping,
100 RuleOp SOAC.liftIdentityMapping,
101 RuleOp SOAC.simplifyMapIota,
102 RuleOp SOAC.removeUnusedSOACInput,
103 RuleBasicOp removeScalarCopy
104 ]
105 [ RuleBasicOp removeUnnecessaryCopy,
106 RuleOp removeDeadGPUBodyResult
107 ]
108
109 -- | Remove the unused return values of a GPUBody.
110 removeDeadGPUBodyResult :: BottomUpRuleOp (Wise GPU)
111 removeDeadGPUBodyResult (_, used) pat aux (GPUBody types body)
112 | -- Figure out which of the names in 'pat' are used...
113 pat_used <- map (`UT.isUsedDirectly` used) $ patNames pat,
114 -- If they are not all used, then this rule applies.
115 not (and pat_used) =
116 -- Remove the parts of the GPUBody results that correspond to dead
117 -- return value bindings. Note that this leaves dead code in the
118 -- kernel, but that will be removed later.
119 let pick :: [a] -> [a]
120 pick = map snd . filter fst . zip pat_used
121 pat' = pick (patElems pat)
122 types' = pick types
123 body' = body {bodyResult = pick (bodyResult body)}
124 in Simplify $ auxing aux $ letBind (Pat pat') $ Op $ GPUBody types' body'
125 | otherwise = Skip
126 removeDeadGPUBodyResult _ _ _ _ = Skip
127
128 -- If we see an Update with a scalar where the value to be written is
129 -- the result of indexing some other array, then we convert it into an
130 -- Update with a slice of that array. This matters when the arrays
131 -- are far away (on the GPU, say), because it avoids a copy of the
132 -- scalar to and from the host.
133 removeScalarCopy :: (BuilderOps rep) => TopDownRuleBasicOp rep
134 removeScalarCopy vtable pat aux (Update safety arr_x (Slice slice_x) (Var v))
135 | Just _ <- sliceIndices (Slice slice_x),
136 Just (Index arr_y (Slice slice_y), cs_y) <- ST.lookupBasicOp v vtable,
137 ST.available arr_y vtable,
138 not $ ST.aliases arr_x arr_y vtable,
139 Just (slice_x_bef, DimFix i, []) <- focusNth (length slice_x - 1) slice_x,
140 Just (slice_y_bef, DimFix j, []) <- focusNth (length slice_y - 1) slice_y = Simplify $ do
141 let slice_x' = Slice $ slice_x_bef ++ [DimSlice i (intConst Int64 1) (intConst Int64 1)]
142 slice_y' = Slice $ slice_y_bef ++ [DimSlice j (intConst Int64 1) (intConst Int64 1)]
143 v' <- letExp (baseString v ++ "_slice") $ BasicOp $ Index arr_y slice_y'
144 certifying cs_y . auxing aux $
145 letBind pat $
146 BasicOp $
147 Update safety arr_x slice_x' $
148 Var v'
149 removeScalarCopy _ _ _ _ =
150 Skip