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