    {-# LANGUAGE Strict #-}

    -- | A usage-table is sort of a bottom-up symbol table, describing how
    -- (and if) a variable is used.
    module Futhark.Analysis.UsageTable
      ( UsageTable,
        without,
        lookup,
        used,
        expand,
        isConsumed,
        isInResult,
        isUsedDirectly,
        isSize,
        usages,
        usage,
        consumedUsage,
        inResultUsage,
        sizeUsage,
        sizeUsages,
        withoutU,
        Usages,
        consumedU,
        presentU,
        usageInStm,
        usageInPat,
      )
    where

    import Data.Bits
    import Data.Foldable qualified as Foldable
    import Data.IntMap.Strict qualified as IM
    import Data.List qualified as L
    import Futhark.IR
    import Futhark.IR.Prop.Aliases
    import Prelude hiding (lookup)

    -- | A usage table.
    newtype UsageTable = UsageTable (IM.IntMap Usages)
      deriving (UsageTable -> UsageTable -> Bool
    (UsageTable -> UsageTable -> Bool)
    -> (UsageTable -> UsageTable -> Bool) -> Eq UsageTable
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: UsageTable -> UsageTable -> Bool
    == :: UsageTable -> UsageTable -> Bool
    $c/= :: UsageTable -> UsageTable -> Bool
    /= :: UsageTable -> UsageTable -> Bool
    Eq, Int -> UsageTable -> ShowS
    [UsageTable] -> ShowS
    UsageTable -> String
    (Int -> UsageTable -> ShowS)
    -> (UsageTable -> String)
    -> ([UsageTable] -> ShowS)
    -> Show UsageTable
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> UsageTable -> ShowS
    showsPrec :: Int -> UsageTable -> ShowS
    $cshow :: UsageTable -> String
    show :: UsageTable -> String
    $cshowList :: [UsageTable] -> ShowS
    showList :: [UsageTable] -> ShowS
    Show)

    instance Semigroup UsageTable where
      UsageTable IntMap Usages
    table1 <> :: UsageTable -> UsageTable -> UsageTable
    <> UsageTable IntMap Usages
    table2 =
        IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ (Usages -> Usages -> Usages)
    -> IntMap Usages -> IntMap Usages -> IntMap Usages
    forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    IM.unionWith Usages -> Usages -> Usages
    forall a. Semigroup a => a -> a -> a
    (<>) IntMap Usages
    table1 IntMap Usages
    table2

    instance Monoid UsageTable where
      mempty :: UsageTable
    mempty = IntMap Usages -> UsageTable
    UsageTable IntMap Usages
    forall a. Monoid a => a
    mempty

    -- | Remove these entries from the usage table.
    without :: UsageTable -> [VName] -> UsageTable
    without :: UsageTable -> [VName] -> UsageTable
    without (UsageTable IntMap Usages
    table) =
      IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable)
    -> ([VName] -> IntMap Usages) -> [VName] -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (IntMap Usages -> Int -> IntMap Usages)
    -> IntMap Usages -> [Int] -> IntMap Usages
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    Foldable.foldl ((Int -> IntMap Usages -> IntMap Usages)
    -> IntMap Usages -> Int -> IntMap Usages
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Int -> IntMap Usages -> IntMap Usages
    forall a. Int -> IntMap a -> IntMap a
    IM.delete) IntMap Usages
    table ([Int] -> IntMap Usages)
    -> ([VName] -> [Int]) -> [VName] -> IntMap Usages
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (VName -> Int) -> [VName] -> [Int]
    forall a b. (a -> b) -> [a] -> [b]
    map VName -> Int
    baseTag

    -- | Look up a variable in the usage table.
    lookup :: VName -> UsageTable -> Maybe Usages
    lookup :: VName -> UsageTable -> Maybe Usages
    lookup VName
    name (UsageTable IntMap Usages
    table) = Int -> IntMap Usages -> Maybe Usages
    forall a. Int -> IntMap a -> Maybe a
    IM.lookup (VName -> Int
    baseTag VName
    name) IntMap Usages
    table

    lookupPred :: (Usages -> Bool) -> VName -> UsageTable -> Bool
    lookupPred :: (Usages -> Bool) -> VName -> UsageTable -> Bool
    lookupPred Usages -> Bool
    f VName
    name = Bool -> (Usages -> Bool) -> Maybe Usages -> Bool
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Bool
    False Usages -> Bool
    f (Maybe Usages -> Bool)
    -> (UsageTable -> Maybe Usages) -> UsageTable -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . VName -> UsageTable -> Maybe Usages
    lookup VName
    name

    -- | Is the variable present in the usage table?  That is, has it been used?
    used :: VName -> UsageTable -> Bool
    used :: VName -> UsageTable -> Bool
    used = (Usages -> Bool) -> VName -> UsageTable -> Bool
    lookupPred ((Usages -> Bool) -> VName -> UsageTable -> Bool)
    -> (Usages -> Bool) -> VName -> UsageTable -> Bool
    forall a b. (a -> b) -> a -> b
    $ Bool -> Usages -> Bool
    forall a b. a -> b -> a
    const Bool
    True

    -- | Expand the usage table based on aliasing information.
    expand :: (VName -> Names) -> UsageTable -> UsageTable
    expand :: (VName -> Names) -> UsageTable -> UsageTable
    expand VName -> Names
    look (UsageTable IntMap Usages
    m) = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ (IntMap Usages -> (Int, Usages) -> IntMap Usages)
    -> IntMap Usages -> [(Int, Usages)] -> IntMap Usages
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    L.foldl' IntMap Usages -> (Int, Usages) -> IntMap Usages
    grow IntMap Usages
    m ([(Int, Usages)] -> IntMap Usages)
    -> [(Int, Usages)] -> IntMap Usages
    forall a b. (a -> b) -> a -> b
    $ IntMap Usages -> [(Int, Usages)]
    forall a. IntMap a -> [(Int, a)]
    IM.toList IntMap Usages
    m
      where
        grow :: IntMap Usages -> (Int, Usages) -> IntMap Usages
    grow IntMap Usages
    m' (Int
    k, Usages
    v) =
          (IntMap Usages -> VName -> IntMap Usages)
    -> IntMap Usages -> IntMap VName -> IntMap Usages
    forall b a. (b -> a -> b) -> b -> IntMap a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    L.foldl'
            (Usages -> IntMap Usages -> VName -> IntMap Usages
    forall {a}. Semigroup a => a -> IntMap a -> VName -> IntMap a
    grow'' (Usages -> IntMap Usages -> VName -> IntMap Usages)
    -> Usages -> IntMap Usages -> VName -> IntMap Usages
    forall a b. (a -> b) -> a -> b
    $ Usages
    v Usages -> Usages -> Usages
    `withoutU` Usages
    presentU)
            IntMap Usages
    m'
            (Names -> IntMap VName
    namesIntMap (Names -> IntMap VName) -> Names -> IntMap VName
    forall a b. (a -> b) -> a -> b
    $ VName -> Names
    look (VName -> Names) -> VName -> Names
    forall a b. (a -> b) -> a -> b
    $ Name -> Int -> VName
    VName (String -> Name
    nameFromString String
    "") Int
    k)
        grow'' :: a -> IntMap a -> VName -> IntMap a
    grow'' a
    v IntMap a
    m'' VName
    k = (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
    forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
    IM.insertWith a -> a -> a
    forall a. Semigroup a => a -> a -> a
    (<>) (VName -> Int
    baseTag VName
    k) a
    v IntMap a
    m''

    is :: Usages -> VName -> UsageTable -> Bool
    is :: Usages -> VName -> UsageTable -> Bool
    is = (Usages -> Bool) -> VName -> UsageTable -> Bool
    lookupPred ((Usages -> Bool) -> VName -> UsageTable -> Bool)
    -> (Usages -> Usages -> Bool)
    -> Usages
    -> VName
    -> UsageTable
    -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Usages -> Usages -> Bool
    matches

    -- | Has the variable been consumed?
    isConsumed :: VName -> UsageTable -> Bool
    isConsumed :: VName -> UsageTable -> Bool
    isConsumed = Usages -> VName -> UsageTable -> Bool
    is Usages
    consumedU

    -- | Has the variable been used in the 'Result' of a body?
    isInResult :: VName -> UsageTable -> Bool
    isInResult :: VName -> UsageTable -> Bool
    isInResult = Usages -> VName -> UsageTable -> Bool
    is Usages
    inResultU

    -- | Has the given name been used directly (i.e. could we rename it or
    -- remove it without anyone noticing?)
    isUsedDirectly :: VName -> UsageTable -> Bool
    isUsedDirectly :: VName -> UsageTable -> Bool
    isUsedDirectly = Usages -> VName -> UsageTable -> Bool
    is Usages
    presentU

    -- | Is this name used as the size of something (array or memory block)?
    isSize :: VName -> UsageTable -> Bool
    isSize :: VName -> UsageTable -> Bool
    isSize = Usages -> VName -> UsageTable -> Bool
    is Usages
    sizeU

    -- | Construct a usage table reflecting that these variables have been
    -- used.
    usages :: Names -> UsageTable
    usages :: Names -> UsageTable
    usages = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable)
    -> (Names -> IntMap Usages) -> Names -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (VName -> Usages) -> IntMap VName -> IntMap Usages
    forall a b. (a -> b) -> IntMap a -> IntMap b
    IM.map (Usages -> VName -> Usages
    forall a b. a -> b -> a
    const Usages
    presentU) (IntMap VName -> IntMap Usages)
    -> (Names -> IntMap VName) -> Names -> IntMap Usages
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Names -> IntMap VName
    namesIntMap

    -- | Construct a usage table where the given variable has been used in
    -- this specific way.
    usage :: VName -> Usages -> UsageTable
    usage :: VName -> Usages -> UsageTable
    usage VName
    name Usages
    uses = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ Int -> Usages -> IntMap Usages
    forall a. Int -> a -> IntMap a
    IM.singleton (VName -> Int
    baseTag VName
    name) Usages
    uses

    -- | Construct a usage table where the given variable has been consumed.
    consumedUsage :: VName -> UsageTable
    consumedUsage :: VName -> UsageTable
    consumedUsage VName
    name = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ Int -> Usages -> IntMap Usages
    forall a. Int -> a -> IntMap a
    IM.singleton (VName -> Int
    baseTag VName
    name) Usages
    consumedU

    -- | Construct a usage table where the given variable has been used in
    -- the 'Result' of a body.
    inResultUsage :: VName -> UsageTable
    inResultUsage :: VName -> UsageTable
    inResultUsage VName
    name = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ Int -> Usages -> IntMap Usages
    forall a. Int -> a -> IntMap a
    IM.singleton (VName -> Int
    baseTag VName
    name) Usages
    inResultU

    -- | Construct a usage table where the given variable has been used as
    -- an array or memory size.
    sizeUsage :: VName -> UsageTable
    sizeUsage :: VName -> UsageTable
    sizeUsage VName
    name = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable) -> IntMap Usages -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ Int -> Usages -> IntMap Usages
    forall a. Int -> a -> IntMap a
    IM.singleton (VName -> Int
    baseTag VName
    name) Usages
    sizeU

    -- | Construct a usage table where the given names have been used as
    -- an array or memory size.
    sizeUsages :: Names -> UsageTable
    sizeUsages :: Names -> UsageTable
    sizeUsages = IntMap Usages -> UsageTable
    UsageTable (IntMap Usages -> UsageTable)
    -> (Names -> IntMap Usages) -> Names -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (VName -> Usages) -> IntMap VName -> IntMap Usages
    forall a b. (a -> b) -> IntMap a -> IntMap b
    IM.map (Usages -> VName -> Usages
    forall a b. a -> b -> a
    const (Usages
    sizeU Usages -> Usages -> Usages
    forall a. Semigroup a => a -> a -> a
    <> Usages
    presentU)) (IntMap VName -> IntMap Usages)
    -> (Names -> IntMap VName) -> Names -> IntMap Usages
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Names -> IntMap VName
    namesIntMap

    -- | A description of how a single variable has been used.
    newtype Usages = Usages Int -- Bitmap representation for speed.
      deriving (Usages -> Usages -> Bool
    (Usages -> Usages -> Bool)
    -> (Usages -> Usages -> Bool) -> Eq Usages
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Usages -> Usages -> Bool
    == :: Usages -> Usages -> Bool
    $c/= :: Usages -> Usages -> Bool
    /= :: Usages -> Usages -> Bool
    Eq, Eq Usages
    Eq Usages =>
    (Usages -> Usages -> Ordering)
    -> (Usages -> Usages -> Bool)
    -> (Usages -> Usages -> Bool)
    -> (Usages -> Usages -> Bool)
    -> (Usages -> Usages -> Bool)
    -> (Usages -> Usages -> Usages)
    -> (Usages -> Usages -> Usages)
    -> Ord Usages
    Usages -> Usages -> Bool
    Usages -> Usages -> Ordering
    Usages -> Usages -> Usages
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: Usages -> Usages -> Ordering
    compare :: Usages -> Usages -> Ordering
    $c< :: Usages -> Usages -> Bool
    < :: Usages -> Usages -> Bool
    $c<= :: Usages -> Usages -> Bool
    <= :: Usages -> Usages -> Bool
    $c> :: Usages -> Usages -> Bool
    > :: Usages -> Usages -> Bool
    $c>= :: Usages -> Usages -> Bool
    >= :: Usages -> Usages -> Bool
    $cmax :: Usages -> Usages -> Usages
    max :: Usages -> Usages -> Usages
    $cmin :: Usages -> Usages -> Usages
    min :: Usages -> Usages -> Usages
    Ord, Int -> Usages -> ShowS
    [Usages] -> ShowS
    Usages -> String
    (Int -> Usages -> ShowS)
    -> (Usages -> String) -> ([Usages] -> ShowS) -> Show Usages
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Usages -> ShowS
    showsPrec :: Int -> Usages -> ShowS
    $cshow :: Usages -> String
    show :: Usages -> String
    $cshowList :: [Usages] -> ShowS
    showList :: [Usages] -> ShowS
    Show)

    instance Semigroup Usages where
      Usages Int
    x <> :: Usages -> Usages -> Usages
    <> Usages Int
    y = Int -> Usages
    Usages (Int -> Usages) -> Int -> Usages
    forall a b. (a -> b) -> a -> b
    $ Int
    x Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. Int
    y

    instance Monoid Usages where
      mempty :: Usages
    mempty = Int -> Usages
    Usages Int
    0

    -- | A kind of usage.
    consumedU, inResultU, presentU, sizeU :: Usages
    consumedU :: Usages
    consumedU = Int -> Usages
    Usages Int
    1
    inResultU :: Usages
    inResultU = Int -> Usages
    Usages Int
    2
    presentU :: Usages
    presentU = Int -> Usages
    Usages Int
    4
    sizeU :: Usages
    sizeU = Int -> Usages
    Usages Int
    8

    -- | Check whether the bits that are set in the first argument are
    -- also set in the second.
    matches :: Usages -> Usages -> Bool
    matches :: Usages -> Usages -> Bool
    matches (Usages Int
    x) (Usages Int
    y) = Int
    x Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == (Int
    x Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    y)

    -- | x - y, but for 'Usages'.
    withoutU :: Usages -> Usages -> Usages
    withoutU :: Usages -> Usages -> Usages
    withoutU (Usages Int
    x) (Usages Int
    y) = Int -> Usages
    Usages (Int -> Usages) -> Int -> Usages
    forall a b. (a -> b) -> a -> b
    $ Int
    x Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int -> Int
    forall a. Bits a => a -> a
    complement Int
    y

    usageInBody :: (Aliased rep) => Body rep -> UsageTable
    usageInBody :: forall rep. Aliased rep => Body rep -> UsageTable
    usageInBody = (VName -> UsageTable) -> [VName] -> UsageTable
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap VName -> UsageTable
    consumedUsage ([VName] -> UsageTable)
    -> (Body rep -> [VName]) -> Body rep -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Names -> [VName]
    namesToList (Names -> [VName]) -> (Body rep -> Names) -> Body rep -> [VName]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Body rep -> Names
    forall rep. Aliased rep => Body rep -> Names
    consumedInBody

    -- | Produce a usage table reflecting the use of the free variables in
    -- a single statement.
    usageInStm :: (Aliased rep) => Stm rep -> UsageTable
    usageInStm :: forall rep. Aliased rep => Stm rep -> UsageTable
    usageInStm (Let Pat (LetDec rep)
    pat StmAux (ExpDec rep)
    rep Exp rep
    e) =
      [UsageTable] -> UsageTable
    forall a. Monoid a => [a] -> a
    mconcat
        [ Pat (LetDec rep) -> UsageTable
    forall t. FreeIn t => Pat t -> UsageTable
    usageInPat Pat (LetDec rep)
    pat UsageTable -> [VName] -> UsageTable
    `without` Pat (LetDec rep) -> [VName]
    forall dec. Pat dec -> [VName]
    patNames Pat (LetDec rep)
    pat,
          Names -> UsageTable
    usages (Names -> UsageTable) -> Names -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ StmAux (ExpDec rep) -> Names
    forall a. FreeIn a => a -> Names
    freeIn StmAux (ExpDec rep)
    rep,
          Exp rep -> UsageTable
    forall rep. Aliased rep => Exp rep -> UsageTable
    usageInExp Exp rep
    e,
          Names -> UsageTable
    usages (Exp rep -> Names
    forall a. FreeIn a => a -> Names
    freeIn Exp rep
    e)
        ]

    -- | Usage table reflecting use in pattern.  In particular, free
    -- variables in the decorations are considered used as sizes, even if
    -- they are also bound in this pattern.
    usageInPat :: (FreeIn t) => Pat t -> UsageTable
    usageInPat :: forall t. FreeIn t => Pat t -> UsageTable
    usageInPat = Names -> UsageTable
    sizeUsages (Names -> UsageTable) -> (Pat t -> Names) -> Pat t -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (PatElem t -> Names) -> [PatElem t] -> Names
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap PatElem t -> Names
    forall a. FreeIn a => a -> Names
    freeIn ([PatElem t] -> Names) -> (Pat t -> [PatElem t]) -> Pat t -> Names
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Pat t -> [PatElem t]
    forall dec. Pat dec -> [PatElem dec]
    patElems

    usageInExp :: (Aliased rep) => Exp rep -> UsageTable
    usageInExp :: forall rep. Aliased rep => Exp rep -> UsageTable
    usageInExp (Apply Name
    _ [(SubExp, Diet)]
    args [(RetType rep, RetAls)]
    _ (Safety, SrcLoc, [SrcLoc])
    _) =
      [UsageTable] -> UsageTable
    forall a. Monoid a => [a] -> a
    mconcat [VName -> UsageTable
    consumedUsage VName
    v | (Var VName
    v, Diet
    Consume) <- [(SubExp, Diet)]
    args]
    usageInExp e :: Exp rep
    e@Loop {} =
      (VName -> UsageTable) -> [VName] -> UsageTable
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap VName -> UsageTable
    consumedUsage ([VName] -> UsageTable) -> [VName] -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ Names -> [VName]
    namesToList (Names -> [VName]) -> Names -> [VName]
    forall a b. (a -> b) -> a -> b
    $ Exp rep -> Names
    forall rep. Aliased rep => Exp rep -> Names
    consumedInExp Exp rep
    e
    usageInExp (Match [SubExp]
    _ [Case (Body rep)]
    cases Body rep
    defbody MatchDec (BranchType rep)
    _) =
      (Case (Body rep) -> UsageTable) -> [Case (Body rep)] -> UsageTable
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap (Body rep -> UsageTable
    forall rep. Aliased rep => Body rep -> UsageTable
    usageInBody (Body rep -> UsageTable)
    -> (Case (Body rep) -> Body rep) -> Case (Body rep) -> UsageTable
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Case (Body rep) -> Body rep
    forall body. Case body -> body
    caseBody) [Case (Body rep)]
    cases UsageTable -> UsageTable -> UsageTable
    forall a. Semigroup a => a -> a -> a
    <> Body rep -> UsageTable
    forall rep. Aliased rep => Body rep -> UsageTable
    usageInBody Body rep
    defbody
    usageInExp (WithAcc [WithAccInput rep]
    inputs Lambda rep
    lam) =
      (WithAccInput rep -> UsageTable)
    -> [WithAccInput rep] -> UsageTable
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap WithAccInput rep -> UsageTable
    forall {t :: * -> *} {a} {c}.
    Foldable t =>
    (a, t VName, c) -> UsageTable
    inputUsage [WithAccInput rep]
    inputs UsageTable -> UsageTable -> UsageTable
    forall a. Semigroup a => a -> a -> a
    <> Body rep -> UsageTable
    forall rep. Aliased rep => Body rep -> UsageTable
    usageInBody (Lambda rep -> Body rep
    forall rep. Lambda rep -> Body rep
    lambdaBody Lambda rep
    lam)
      where
        inputUsage :: (a, t VName, c) -> UsageTable
    inputUsage (a
    _, t VName
    arrs, c
    _) = (VName -> UsageTable) -> t VName -> UsageTable
    forall m a. Monoid m => (a -> m) -> t a -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    foldMap VName -> UsageTable
    consumedUsage t VName
    arrs
    usageInExp (BasicOp (Update Safety
    _ VName
    src Slice SubExp
    _ SubExp
    _)) =
      VName -> UsageTable
    consumedUsage VName
    src
    usageInExp (BasicOp (FlatUpdate VName
    src FlatSlice SubExp
    _ VName
    _)) =
      VName -> UsageTable
    consumedUsage VName
    src
    usageInExp (Op Op rep
    op) =
      [UsageTable] -> UsageTable
    forall a. Monoid a => [a] -> a
    mconcat ([UsageTable] -> UsageTable) -> [UsageTable] -> UsageTable
    forall a b. (a -> b) -> a -> b
    $ (VName -> UsageTable) -> [VName] -> [UsageTable]
    forall a b. (a -> b) -> [a] -> [b]
    map VName -> UsageTable
    consumedUsage (Names -> [VName]
    namesToList (Names -> [VName]) -> Names -> [VName]
    forall a b. (a -> b) -> a -> b
    $ Op rep -> Names
    forall rep. Aliased rep => OpC rep rep -> Names
    forall (op :: * -> *) rep.
    (AliasedOp op, Aliased rep) =>
    op rep -> Names
    consumedInOp Op rep
    op)
    usageInExp (BasicOp BasicOp
    _) = UsageTable
    forall a. Monoid a => a
    mempty