packages feed

futhark-0.29.1: src/Futhark/Pass/Flatten/Intrablock.hs

{-# LANGUAGE TypeFamilies #-}

module Futhark.Pass.Flatten.Intrablock
  ( IntrablockResult (..),
    intrablockParallelise,
    intraMinInnerPar,
    InBlockMapTransformer,
  )
where

import Control.Monad
import Control.Monad.RWS
import Control.Monad.State
import Data.Bitraversable
import Data.Map qualified as M
import Data.Maybe
import Data.Set qualified as S
import Futhark.Analysis.PrimExp.Convert
import Futhark.IR.GPU hiding (HistOp)
import Futhark.IR.SOACS
import Futhark.MonadFreshNames
import Futhark.Pass.Flatten.Distribute
import Futhark.Pass.Flatten.General
import Futhark.Pass.Flatten.PreProcess (preprocessLambda)
import Futhark.Tools
import Futhark.Transform.Rename
import Futhark.Transform.ToGPU
import Prelude hiding (log)

-- | The minimum amount of inner parallelism we require (by default)
-- in intra-group versions.
intraMinInnerPar :: Int64
intraMinInnerPar = 32

data IntrablockResult = IntrablockResult
  { intraMinPar :: SubExp,
    intraAvailPar :: SubExp,
    intraThreadBlockSize :: Count BlockSize SubExp,
    intraPreludeStms :: Stms GPU,
    intraKernelStms :: Stms GPU,
    intraResultNames :: [VName]
  }

type InBlockMapTransformer =
  SegLevel ->
  Pat Type ->
  SubExp ->
  [VName] ->
  Lambda SOACS ->
  FlattenM ()

foldBinOp' :: (MonadBuilder m) => BinOp -> [SubExp] -> m (Exp (Rep m))
foldBinOp' _ [] = eSubExp $ intConst Int64 1
foldBinOp' bop (x : xs) = foldBinOp bop x xs

-- | Extract the intra-block parallelism used by the body, paired with whether
-- it is virtualised.
findParallelism :: KernelBody GPU -> [([SubExp], SegVirt)]
findParallelism = S.toList . flip execState mempty . onKernelBody
  where
    onKernelBody = mapM_ onStm . bodyStms
    onBody = mapM_ onStm . bodyStms
    onStm stm = walkExpM walker $ stmExp stm
    walker =
      (identityWalker @GPU)
        { walkOnBody = const onBody,
          walkOnOp = onOp
        }
    onOp (SegOp op) = do
      modify $ S.insert (segSpaceDims $ segSpace op, segVirt (segLevel op))
      onKernelBody $ segBody op
    onOp _ = pure ()

onlyNonVirt :: [(a, SegVirt)] -> [a]
onlyNonVirt = mapMaybe f
  where
    f (_, SegVirt) = Nothing
    f (ws, _) = Just ws

computeThreadBlockSize ::
  [([SubExp], SegVirt)] ->
  FlattenM (SubExp, Count BlockSize SubExp)
computeThreadBlockSize wss = do
  let prod = letSubExp "one_intra_par" <=< foldBinOp' (Mul Int64 OverflowUndef)
  ws <- mapM (bitraverse prod pure) $ filter (not . null . fst) wss

  -- The amount of parallelism available *in the worst case* is equal to the
  -- smallest parallel loop.
  intra_avail_par <-
    letSubExp "intra_avail_par" =<< foldBinOp' (SMin Int64) (map fst ws)

  -- If we have purely virtualised SegOps, then the thread block size can be set
  -- freely, but otherwise it must fit all the non-virtualised SegOps. Note that
  -- in the virtualised case, we do not cap the block size by the actual
  -- exploitable parallelism. This is to ensure that the block size is
  -- statically known when the kernel is compiled, which can result in much
  -- better code generation.
  tblock_size <-
    case onlyNonVirt ws of
      [] -> getSize "tblock_size" SizeThreadBlock
      ws' -> letSubExp "tblock_size" =<< foldBinOp' (SMax Int64) (intConst Int64 1 : ws')
  pure (intra_avail_par, Count tblock_size)

-- | Check whether this result is actually something that is acceptable to use:
-- the parallel dimensions must all be bound outside the kernel, as nonuniform
-- parallelism cannot be exploited inside a thread block.
noNonuniformPar :: Names -> FlattenM IntrablockResult -> FlattenM (Maybe IntrablockResult)
noNonuniformPar pars m = do
  outside_scope <- askScope
  if allNames (`M.member` outside_scope) pars
    then Just <$> m
    else pure Nothing

intrablockParallelise ::
  InBlockMapTransformer ->
  Segments ->
  DistEnv ->
  DistInputs ->
  [DistResult] ->
  Pat Type ->
  StmAux () ->
  SubExp ->
  [VName] ->
  Lambda SOACS ->
  FlattenM (Maybe IntrablockResult)
intrablockParallelise map_in_block segments env inps dist_res _pat aux w arrs lam0 = do
  gpu_scope <- askScope
  let pp_scope = castScope $ scopeOfDistInputs inps <> gpu_scope
  lam <- renameLambda =<< preprocessLambda pp_scope lam0

  let result_ts =
        [ t `arrayOfShape` segmentsShape segments
        | DistResult _ (DistType _ _ t) _ <- dist_res
        ]

  -- Reconstruct the per-enclosing-segment inputs, so they can be read at the
  -- appropriate indices inside the kernel.
  (param_inputs, input_prelude_stms) <-
    collectStms $
      zipWithM (prepareRegularMapInput segments env inps) (lambdaParams lam) arrs

  -- A free variable of the map body is a per-enclosing-segment value: it is
  -- brought into the body's scope as a distributed input and reconstructed at
  -- the outer indices inside the kernel (via 'readInBlockInputs' below). With no
  -- enclosing segments, however, it is an ordinary top-level value already in
  -- the kernel's outer scope, so there is nothing to reconstruct - hence the
  -- empty 'free_inputs', which makes both the scope extension and the read below
  -- vanish.
  free_inputs <- if null segments then pure [] else freeInputsFor inps lam
  kbody <-
    localScope (scopeOfDistInputs free_inputs <> scopeOfLParams (lambdaParams lam)) $
      intrablockParalleliseBody map_in_block (lambdaBody lam)

  nested_pat <-
    fmap Pat $
      zipWith PatElem
        <$> mapM (newName . distResName) dist_res
        <*> pure result_ts

  let new_segments = segments <> pure w
      wss = findParallelism kbody

  noNonuniformPar (freeIn $ map fst wss) $ do
    ((intra_avail_par, tblock_size, kspace, num_tblocks), prelude_stms) <-
      collectStms $ do
        (intra_avail_par, tblock_size) <-
          computeThreadBlockSize wss
        -- CalcNumBlocks needs a "thread count" to cap the actual number of
        -- blocks. Tell a white lie here that is good enough, hopefully.
        num_threads <-
          letSubExp "num_threads" <=< toExp $
            product $
              pe64 (unCount tblock_size) : map pe64 new_segments
        num_tblocks <- getGridSize "intrablock" num_threads tblock_size
        gtids <- mapM (const $ newVName "gtid") new_segments
        kspace <- mkSegSpace $ zip gtids new_segments
        pure (intra_avail_par, tblock_size, kspace, num_tblocks)

    read_input_stms <-
      collectStms_ . localScope (scopeOfSegSpace kspace <> scopeOf input_prelude_stms <> scopeOf prelude_stms) $ do
        let SegSpace _ gtids_and_dims = kspace
            full_is = map (Var . fst) gtids_and_dims
            outer_is = take (segmentsRank segments) full_is
        readInBlockInputs segments env outer_is free_inputs
        readInBlockInputs new_segments mempty full_is param_inputs

    let kbody' = kbody {bodyStms = read_input_stms <> bodyStms kbody}
        rts = map (length new_segments `stripArray`) result_ts
        grid = KernelGrid num_tblocks tblock_size
        lvl = SegBlock SegVirt (Just grid)
        kstm = Let nested_pat aux $ Op $ SegOp $ SegMap lvl kspace rts kbody'

    pure $
      IntrablockResult
        { intraMinPar = intra_avail_par,
          intraAvailPar = intra_avail_par,
          intraThreadBlockSize = tblock_size,
          intraPreludeStms = input_prelude_stms <> prelude_stms,
          intraKernelStms = oneStm kstm,
          intraResultNames = patNames nested_pat
        }

readInBlockInputs :: Segments -> DistEnv -> [SubExp] -> DistInputs -> FlattenM ()
readInBlockInputs segments env is inputs =
  mapM_ onInput inputs
  where
    onInput (v, inp) = do
      v' <- readInputVar segments env is inputs v
      let t = distInputType inp
      if isAcc t
        then
          letBindNames [v] $ BasicOp $ SubExp $ Var v'
        else
          if arrayRank t > 0
            then
              letBindNames [v] $ BasicOp $ Replicate mempty $ Var v'
            else
              letBindNames [v] $ BasicOp $ SubExp $ Var v'

prepareRegularMapInput ::
  Segments ->
  DistEnv ->
  DistInputs ->
  Param Type ->
  VName ->
  FlattenM (VName, DistInput)
prepareRegularMapInput segments env inps p arr = do
  t <- lookupInputType inps arr
  let expectedShape = segmentsShape segments <> arrayShape t
      lvl = SegThread SegVirt Nothing
  arr_rep <- liftVarRegular lvl segments inps env expectedShape arr
  pure (paramName p, DistInputFree arr_rep (paramType p))

freeInputsFor :: DistInputs -> Lambda SOACS -> FlattenM DistInputs
freeInputsFor inps lam =
  do
    let free = freeIn lam
    free_sizes <-
      foldMap freeIn <$> mapM (lookupInputType inps) (namesToList free)
    pure
      [ (v, inp)
      | v <- namesToList $ free <> free_sizes,
        Just inp <- [lookup v inps]
      ]

intrablockBody :: InBlockMapTransformer -> Body SOACS -> FlattenM (Body GPU)
intrablockBody map_in_block body = do
  stms <- collectStms_ $ intrablockStms map_in_block $ bodyStms body
  pure $ mkBody stms $ bodyResult body

intrablockLambda :: InBlockMapTransformer -> Lambda SOACS -> FlattenM (Lambda GPU)
intrablockLambda map_in_block lam =
  mkLambda (lambdaParams lam) $
    bodyBind =<< intrablockBody map_in_block (lambdaBody lam)

intrablockWithAccInput :: InBlockMapTransformer -> WithAccInput SOACS -> FlattenM (WithAccInput GPU)
intrablockWithAccInput _ (shape, arrs, Nothing) =
  pure (shape, arrs, Nothing)
intrablockWithAccInput map_in_block (shape, arrs, Just (lam, nes)) = do
  lam' <- intrablockLambda map_in_block lam
  pure (shape, arrs, Just (lam', nes))

bindPatToRes :: Pat Type -> [VName] -> FlattenM ()
bindPatToRes pat res = forM_ (zip (patNames pat) res) $ \(pe_v, v) ->
  letBindNames [pe_v] $ BasicOp $ SubExp $ Var v

intrablockStm :: InBlockMapTransformer -> Stm SOACS -> FlattenM ()
intrablockStm map_in_block stm@(Let pat aux e) = do
  scope <- askScope
  let lvl = SegThreadInBlock SegVirt

  case e of
    Loop merge form loopbody ->
      localScope (scopeOfLoopForm form <> scopeOfFParams (map fst merge)) $ do
        loopbody' <- intrablockBody map_in_block loopbody
        certifying (stmAuxCerts aux) . letBind pat $
          Loop merge form loopbody'
    Match cond cases defbody ifdec -> do
      cases' <- mapM (traverse $ intrablockBody map_in_block) cases
      defbody' <- intrablockBody map_in_block defbody
      certifying (stmAuxCerts aux) . letBind pat $
        Match cond cases' defbody' ifdec
    WithAcc inputs lam -> do
      inputs' <- mapM (intrablockWithAccInput map_in_block) inputs
      lam' <- intrablockLambda map_in_block lam
      certifying (stmAuxCerts aux) . letBind pat $ WithAcc inputs' lam'
    Op (Screma w arrs form)
      | Just lam <- isMapSOAC form ->
          map_in_block lvl pat w arrs lam
    Op (Screma w arrs form)
      | Just (post_lam, scans, mapfun) <- isMaposcanomapSOAC form,
        -- FIXME: Futhark.CodeGen.ImpGen.GPU.Block.compileBlockScan
        -- cannot handle multiple scan operators yet.
        Scan scanfun nes <- singleScan scans -> do
          let scanfun' = soacsLambdaToGPU scanfun
              mapfun' = soacsLambdaToGPU mapfun
              post_op = soacsLambdaToGPU post_lam
          bindPatToRes pat <=< certifying (stmAuxCerts aux) $
            genUniformSegScanomapWithPost lvl (pure w) "intra_maposcanomap" scanfun' mempty nes post_op mapfun' arrs (const $ pure ())
    Op (Screma w arrs form)
      | Just (reds, map_lam) <- isRedomapSOAC form -> do
          let onRed red =
                let red_lam = redLambda red
                    comm
                      | commutativeLambda red_lam = Commutative
                      | otherwise = redComm red
                 in Reduce comm (soacsLambdaToGPU red_lam) (redNeutral red)
              reds_gpu = map onRed reds
              map_lam' = soacsLambdaToGPU map_lam
          bindPatToRes pat <=< certifying (stmAuxCerts aux) $
            genUniformSegRed lvl "intra_redomap" (pure w) reds_gpu mempty map_lam' arrs (const $ pure ())
    Op (Screma w arrs form) ->
      -- This screma is too complicated for us to immediately do
      -- anything, so split it up and try again.
      mapM_ (intrablockStm map_in_block) . fmap (certify (stmAuxCerts aux)) . snd
        =<< runBuilderT (dissectScrema pat w form arrs) (scopeForSOACs scope)
    Op (Hist w arrs ops bucket_fun) -> do
      let bucket_fun' = soacsLambdaToGPU bucket_fun
      bindPatToRes pat <=< certifying (stmAuxCerts aux) $
        genUniformSegHist lvl "Uniform_segHist" (pure w) ops bucket_fun' arrs (const $ pure ())
    Op (Stream w arrs accs lam) -> do
      types <- asksScope castScope
      intrablockStms map_in_block
        =<< runBuilderT_ (sequentialStreamWholeArray pat w accs lam arrs) types
    _ ->
      addStm $ soacsStmToGPU stm

intrablockStms :: InBlockMapTransformer -> Stms SOACS -> FlattenM ()
intrablockStms map_in_block = mapM_ $ intrablockStm map_in_block

intrablockParalleliseBody ::
  InBlockMapTransformer ->
  Body SOACS ->
  FlattenM (KernelBody GPU)
intrablockParalleliseBody map_in_block body = do
  kstms <- collectStms_ $ intrablockStms map_in_block $ bodyStms body
  pure $ Body () kstms $ map ret $ bodyResult body
  where
    ret (SubExpRes cs se) = Returns ResultMaySimplify cs se