{-# LANGUAGE Strict #-}
{-# LANGUAGE TypeFamilies #-}

-- | = Definition of the Futhark core language IR
--
-- For actually /constructing/ ASTs, see "Futhark.Construct".
--
-- == Types and values
--
-- The core language type system is much more restricted than the core
-- language.  This is a theme that repeats often.  The only types that
-- are supported in the core language are various primitive types
-- t'PrimType' which can be combined in arrays (ignore v'Mem' and
-- v'Acc' for now).  Types are represented as t'TypeBase', which is
-- parameterised by the shape of the array and whether we keep
-- uniqueness information.  The t'Type' alias, which is the most
-- commonly used, uses t'Shape' and t'NoUniqueness'.
--
-- This means that the records, tuples, and sum types of the source
-- language are represented merely as collections of primitives and
-- arrays.  This is implemented in "Futhark.Internalise", but the
-- specifics are not important for writing passes on the core
-- language.  What /is/ important is that many constructs that
-- conceptually return tuples instead return /multiple values/.  This
-- is not merely syntactic sugar for a tuple: each of those values are
-- eventually bound to distinct variables.  The prettyprinter for the
-- IR will typically print such collections of values or types in
-- curly braces.
--
-- The system of primitive types is interesting in itself.  See
-- "Language.Futhark.Primitive".
--
-- == Overall AST design
--
-- Internally, the Futhark compiler core intermediate representation
-- resembles a traditional compiler for an imperative language more
-- than it resembles, say, a Haskell or ML compiler.  All functions
-- are monomorphic (except for sizes), first-order, and defined at the
-- top level.  Notably, the IR does /not/ use continuation-passing
-- style (CPS) at any time.  Instead it uses Administrative Normal
-- Form (ANF), where all subexpressions t'SubExp' are either
-- constants 'PrimValue' or variables 'VName'.  Variables are
-- represented as a human-readable t'Name' (which doesn't matter to
-- the compiler) as well as a numeric /tag/, which is what the
-- compiler actually looks at.  All variable names when prettyprinted
-- are of the form @foo_123@.  Function names are just t'Name's,
-- though.
--
-- The body of a function ('FunDef') is a t'Body', which consists of
-- a sequence of statements ('Stms') and a t'Result'.  Execution of a
-- t'Body' consists of executing all of the statements, then returning
-- the values of the variables indicated by the result.
--
-- A statement ('Stm') consists of a t'Pat' alongside an
-- expression 'Exp'.  A pattern is a sequence of name/type pairs.
--
-- For example, the source language expression @let z = x + y - 1 in
-- z@ would in the core language be represented (in prettyprinted
-- form) as something like:
--
-- @
-- let {a_12} = x_10 + y_11
-- let {b_13} = a_12 - 1
-- in {b_13}
-- @
--
-- == Representations
--
-- Most AST types ('Stm', 'Exp', t'Prog', etc) are parameterised by a
-- type parameter @rep@.  The representation specifies how to fill out
-- various polymorphic parts of the AST.  For example, 'Exp' has a
-- constructor v'Op' whose payload depends on @rep@, via the use of a
-- type family called t'Op' (a kind of type-level function) which is
-- applied to the @rep@.  The SOACS representation
-- ("Futhark.IR.SOACS") thus uses a rep called @SOACS@, and defines
-- that @Op SOACS@ is a SOAC, while the Kernels representation
-- ("Futhark.IR.Kernels") defines @Op Kernels@ as some kind of kernel
-- construct.  Similarly, various other decorations (e.g. what
-- information we store in a t'PatElem') are also type families.
--
-- The full list of possible decorations is defined as part of the
-- type class 'RepTypes' (although other type families are also
-- used elsewhere in the compiler on an ad hoc basis).
--
-- Essentially, the @rep@ type parameter functions as a kind of
-- proxy, saving us from having to parameterise the AST type with all
-- the different forms of decorations that we desire (it would easily
-- become a type with a dozen type parameters).
--
-- Some AST elements (such as 'Pat') do not take a @rep@ type
-- parameter, but instead immediately the single type of decoration
-- that they contain.  We only use the more complicated machinery when
-- needed.
--
-- Defining a new representation (or /rep/) thus requires you to
-- define an empty datatype and implement a handful of type class
-- instances for it.  See the source of "Futhark.IR.Seq"
-- for what is likely the simplest example.
module Futhark.IR.Syntax
  ( module Language.Futhark.Core,
    prettyString,
    prettyText,
    Pretty,
    module Futhark.IR.Rep,
    module Futhark.IR.Syntax.Core,

    -- * Types
    Uniqueness (..),
    NoUniqueness (..),
    Rank (..),
    ArrayShape (..),
    Space (..),
    TypeBase (..),
    Diet (..),

    -- * Abstract syntax tree
    Ident (..),
    SubExp (..),
    PatElem (..),
    Pat (..),
    StmAux (..),
    Stm (..),
    Stms,
    SubExpRes (..),
    Result,
    Body (..),
    BasicOp (..),
    UnOp (..),
    BinOp (..),
    CmpOp (..),
    ConvOp (..),
    OpaqueOp (..),
    ReshapeKind (..),
    WithAccInput,
    Exp (..),
    Case (..),
    LoopForm (..),
    MatchDec (..),
    MatchSort (..),
    Safety (..),
    Lambda (..),
    RetAls (..),

    -- * Definitions
    Param (..),
    FParam,
    LParam,
    FunDef (..),
    EntryParam (..),
    EntryResult (..),
    EntryPoint,
    Prog (..),

    -- * Utils
    oneStm,
    stmsFromList,
    stmsToList,
    stmsHead,
    stmsLast,
    subExpRes,
    subExpsRes,
    varRes,
    varsRes,
    subExpResVName,
  )
where

import Control.Category
import Data.Foldable
import Data.List.NonEmpty (NonEmpty (..))
import Data.Sequence qualified as Seq
import Data.Text qualified as T
import Data.Traversable (fmapDefault, foldMapDefault)
import Futhark.IR.Rep
import Futhark.IR.Syntax.Core
import Futhark.Util.Pretty (Pretty, prettyString, prettyText)
import Language.Futhark.Core
import Prelude hiding (id, (.))

-- | A pattern is conceptually just a list of names and their types.
newtype Pat dec = Pat {forall dec. Pat dec -> [PatElem dec]
patElems :: [PatElem dec]}
  deriving (Eq (Pat dec)
Eq (Pat dec)
-> (Pat dec -> Pat dec -> Ordering)
-> (Pat dec -> Pat dec -> Bool)
-> (Pat dec -> Pat dec -> Bool)
-> (Pat dec -> Pat dec -> Bool)
-> (Pat dec -> Pat dec -> Bool)
-> (Pat dec -> Pat dec -> Pat dec)
-> (Pat dec -> Pat dec -> Pat dec)
-> Ord (Pat dec)
Pat dec -> Pat dec -> Bool
Pat dec -> Pat dec -> Ordering
Pat dec -> Pat dec -> Pat dec
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
forall {dec}. Ord dec => Eq (Pat dec)
forall dec. Ord dec => Pat dec -> Pat dec -> Bool
forall dec. Ord dec => Pat dec -> Pat dec -> Ordering
forall dec. Ord dec => Pat dec -> Pat dec -> Pat dec
$ccompare :: forall dec. Ord dec => Pat dec -> Pat dec -> Ordering
compare :: Pat dec -> Pat dec -> Ordering
$c< :: forall dec. Ord dec => Pat dec -> Pat dec -> Bool
< :: Pat dec -> Pat dec -> Bool
$c<= :: forall dec. Ord dec => Pat dec -> Pat dec -> Bool
<= :: Pat dec -> Pat dec -> Bool
$c> :: forall dec. Ord dec => Pat dec -> Pat dec -> Bool
> :: Pat dec -> Pat dec -> Bool
$c>= :: forall dec. Ord dec => Pat dec -> Pat dec -> Bool
>= :: Pat dec -> Pat dec -> Bool
$cmax :: forall dec. Ord dec => Pat dec -> Pat dec -> Pat dec
max :: Pat dec -> Pat dec -> Pat dec
$cmin :: forall dec. Ord dec => Pat dec -> Pat dec -> Pat dec
min :: Pat dec -> Pat dec -> Pat dec
Ord, Int -> Pat dec -> ShowS
[Pat dec] -> ShowS
Pat dec -> String
(Int -> Pat dec -> ShowS)
-> (Pat dec -> String) -> ([Pat dec] -> ShowS) -> Show (Pat dec)
forall dec. Show dec => Int -> Pat dec -> ShowS
forall dec. Show dec => [Pat dec] -> ShowS
forall dec. Show dec => Pat dec -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall dec. Show dec => Int -> Pat dec -> ShowS
showsPrec :: Int -> Pat dec -> ShowS
$cshow :: forall dec. Show dec => Pat dec -> String
show :: Pat dec -> String
$cshowList :: forall dec. Show dec => [Pat dec] -> ShowS
showList :: [Pat dec] -> ShowS
Show, Pat dec -> Pat dec -> Bool
(Pat dec -> Pat dec -> Bool)
-> (Pat dec -> Pat dec -> Bool) -> Eq (Pat dec)
forall dec. Eq dec => Pat dec -> Pat dec -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall dec. Eq dec => Pat dec -> Pat dec -> Bool
== :: Pat dec -> Pat dec -> Bool
$c/= :: forall dec. Eq dec => Pat dec -> Pat dec -> Bool
/= :: Pat dec -> Pat dec -> Bool
Eq)

instance Semigroup (Pat dec) where
  Pat [PatElem dec]
xs <> :: Pat dec -> Pat dec -> Pat dec
<> Pat [PatElem dec]
ys = [PatElem dec] -> Pat dec
forall dec. [PatElem dec] -> Pat dec
Pat ([PatElem dec]
xs [PatElem dec] -> [PatElem dec] -> [PatElem dec]
forall a. Semigroup a => a -> a -> a
<> [PatElem dec]
ys)

instance Monoid (Pat dec) where
  mempty :: Pat dec
mempty = [PatElem dec] -> Pat dec
forall dec. [PatElem dec] -> Pat dec
Pat [PatElem dec]
forall a. Monoid a => a
mempty

instance Functor Pat where
  fmap :: forall a b. (a -> b) -> Pat a -> Pat b
fmap = (a -> b) -> Pat a -> Pat b
forall (t :: * -> *) a b. Traversable t => (a -> b) -> t a -> t b
fmapDefault

instance Foldable Pat where
  foldMap :: forall m a. Monoid m => (a -> m) -> Pat a -> m
foldMap = (a -> m) -> Pat a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault

instance Traversable Pat where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Pat a -> f (Pat b)
traverse a -> f b
f (Pat [PatElem a]
xs) =
    [PatElem b] -> Pat b
forall dec. [PatElem dec] -> Pat dec
Pat ([PatElem b] -> Pat b) -> f [PatElem b] -> f (Pat b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (PatElem a -> f (PatElem b)) -> [PatElem a] -> f [PatElem b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse ((a -> f b) -> PatElem a -> f (PatElem b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PatElem a -> f (PatElem b)
traverse a -> f b
f) [PatElem a]
xs

-- | Auxilliary Information associated with a statement.
data StmAux dec = StmAux
  { forall dec. StmAux dec -> Certs
stmAuxCerts :: !Certs,
    forall dec. StmAux dec -> Attrs
stmAuxAttrs :: Attrs,
    forall dec. StmAux dec -> dec
stmAuxDec :: dec
  }
  deriving (Eq (StmAux dec)
Eq (StmAux dec)
-> (StmAux dec -> StmAux dec -> Ordering)
-> (StmAux dec -> StmAux dec -> Bool)
-> (StmAux dec -> StmAux dec -> Bool)
-> (StmAux dec -> StmAux dec -> Bool)
-> (StmAux dec -> StmAux dec -> Bool)
-> (StmAux dec -> StmAux dec -> StmAux dec)
-> (StmAux dec -> StmAux dec -> StmAux dec)
-> Ord (StmAux dec)
StmAux dec -> StmAux dec -> Bool
StmAux dec -> StmAux dec -> Ordering
StmAux dec -> StmAux dec -> StmAux dec
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
forall {dec}. Ord dec => Eq (StmAux dec)
forall dec. Ord dec => StmAux dec -> StmAux dec -> Bool
forall dec. Ord dec => StmAux dec -> StmAux dec -> Ordering
forall dec. Ord dec => StmAux dec -> StmAux dec -> StmAux dec
$ccompare :: forall dec. Ord dec => StmAux dec -> StmAux dec -> Ordering
compare :: StmAux dec -> StmAux dec -> Ordering
$c< :: forall dec. Ord dec => StmAux dec -> StmAux dec -> Bool
< :: StmAux dec -> StmAux dec -> Bool
$c<= :: forall dec. Ord dec => StmAux dec -> StmAux dec -> Bool
<= :: StmAux dec -> StmAux dec -> Bool
$c> :: forall dec. Ord dec => StmAux dec -> StmAux dec -> Bool
> :: StmAux dec -> StmAux dec -> Bool
$c>= :: forall dec. Ord dec => StmAux dec -> StmAux dec -> Bool
>= :: StmAux dec -> StmAux dec -> Bool
$cmax :: forall dec. Ord dec => StmAux dec -> StmAux dec -> StmAux dec
max :: StmAux dec -> StmAux dec -> StmAux dec
$cmin :: forall dec. Ord dec => StmAux dec -> StmAux dec -> StmAux dec
min :: StmAux dec -> StmAux dec -> StmAux dec
Ord, Int -> StmAux dec -> ShowS
[StmAux dec] -> ShowS
StmAux dec -> String
(Int -> StmAux dec -> ShowS)
-> (StmAux dec -> String)
-> ([StmAux dec] -> ShowS)
-> Show (StmAux dec)
forall dec. Show dec => Int -> StmAux dec -> ShowS
forall dec. Show dec => [StmAux dec] -> ShowS
forall dec. Show dec => StmAux dec -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall dec. Show dec => Int -> StmAux dec -> ShowS
showsPrec :: Int -> StmAux dec -> ShowS
$cshow :: forall dec. Show dec => StmAux dec -> String
show :: StmAux dec -> String
$cshowList :: forall dec. Show dec => [StmAux dec] -> ShowS
showList :: [StmAux dec] -> ShowS
Show, StmAux dec -> StmAux dec -> Bool
(StmAux dec -> StmAux dec -> Bool)
-> (StmAux dec -> StmAux dec -> Bool) -> Eq (StmAux dec)
forall dec. Eq dec => StmAux dec -> StmAux dec -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall dec. Eq dec => StmAux dec -> StmAux dec -> Bool
== :: StmAux dec -> StmAux dec -> Bool
$c/= :: forall dec. Eq dec => StmAux dec -> StmAux dec -> Bool
/= :: StmAux dec -> StmAux dec -> Bool
Eq)

instance (Semigroup dec) => Semigroup (StmAux dec) where
  StmAux Certs
cs1 Attrs
attrs1 dec
dec1 <> :: StmAux dec -> StmAux dec -> StmAux dec
<> StmAux Certs
cs2 Attrs
attrs2 dec
dec2 =
    Certs -> Attrs -> dec -> StmAux dec
forall dec. Certs -> Attrs -> dec -> StmAux dec
StmAux (Certs
cs1 Certs -> Certs -> Certs
forall a. Semigroup a => a -> a -> a
<> Certs
cs2) (Attrs
attrs1 Attrs -> Attrs -> Attrs
forall a. Semigroup a => a -> a -> a
<> Attrs
attrs2) (dec
dec1 dec -> dec -> dec
forall a. Semigroup a => a -> a -> a
<> dec
dec2)

-- | A local variable binding.
data Stm rep = Let
  { -- | Pat.
    forall rep. Stm rep -> Pat (LetDec rep)
stmPat :: Pat (LetDec rep),
    -- | Auxiliary information statement.
    forall rep. Stm rep -> StmAux (ExpDec rep)
stmAux :: StmAux (ExpDec rep),
    -- | Expression.
    forall rep. Stm rep -> Exp rep
stmExp :: Exp rep
  }

deriving instance (RepTypes rep) => Ord (Stm rep)

deriving instance (RepTypes rep) => Show (Stm rep)

deriving instance (RepTypes rep) => Eq (Stm rep)

-- | A sequence of statements.
type Stms rep = Seq.Seq (Stm rep)

-- | A single statement.
oneStm :: Stm rep -> Stms rep
oneStm :: forall rep. Stm rep -> Stms rep
oneStm = Stm rep -> Seq (Stm rep)
forall a. a -> Seq a
Seq.singleton

-- | Convert a statement list to a statement sequence.
stmsFromList :: [Stm rep] -> Stms rep
stmsFromList :: forall rep. [Stm rep] -> Stms rep
stmsFromList = [Stm rep] -> Seq (Stm rep)
forall a. [a] -> Seq a
Seq.fromList

-- | Convert a statement sequence to a statement list.
stmsToList :: Stms rep -> [Stm rep]
stmsToList :: forall rep. Stms rep -> [Stm rep]
stmsToList = Seq (Stm rep) -> [Stm rep]
forall a. Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

-- | The first statement in the sequence, if any.
stmsHead :: Stms rep -> Maybe (Stm rep, Stms rep)
stmsHead :: forall rep. Stms rep -> Maybe (Stm rep, Stms rep)
stmsHead Stms rep
stms = case Stms rep -> ViewL (Stm rep)
forall a. Seq a -> ViewL a
Seq.viewl Stms rep
stms of
  Stm rep
stm Seq.:< Stms rep
stms' -> (Stm rep, Stms rep) -> Maybe (Stm rep, Stms rep)
forall a. a -> Maybe a
Just (Stm rep
stm, Stms rep
stms')
  ViewL (Stm rep)
Seq.EmptyL -> Maybe (Stm rep, Stms rep)
forall a. Maybe a
Nothing

-- | The last statement in the sequence, if any.
stmsLast :: Stms lore -> Maybe (Stms lore, Stm lore)
stmsLast :: forall lore. Stms lore -> Maybe (Stms lore, Stm lore)
stmsLast Stms lore
stms = case Stms lore -> ViewR (Stm lore)
forall a. Seq a -> ViewR a
Seq.viewr Stms lore
stms of
  Stms lore
stms' Seq.:> Stm lore
stm -> (Stms lore, Stm lore) -> Maybe (Stms lore, Stm lore)
forall a. a -> Maybe a
Just (Stms lore
stms', Stm lore
stm)
  ViewR (Stm lore)
Seq.EmptyR -> Maybe (Stms lore, Stm lore)
forall a. Maybe a
Nothing

-- | A pairing of a subexpression and some certificates.
data SubExpRes = SubExpRes
  { SubExpRes -> Certs
resCerts :: Certs,
    SubExpRes -> SubExp
resSubExp :: SubExp
  }
  deriving (SubExpRes -> SubExpRes -> Bool
(SubExpRes -> SubExpRes -> Bool)
-> (SubExpRes -> SubExpRes -> Bool) -> Eq SubExpRes
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: SubExpRes -> SubExpRes -> Bool
== :: SubExpRes -> SubExpRes -> Bool
$c/= :: SubExpRes -> SubExpRes -> Bool
/= :: SubExpRes -> SubExpRes -> Bool
Eq, Eq SubExpRes
Eq SubExpRes
-> (SubExpRes -> SubExpRes -> Ordering)
-> (SubExpRes -> SubExpRes -> Bool)
-> (SubExpRes -> SubExpRes -> Bool)
-> (SubExpRes -> SubExpRes -> Bool)
-> (SubExpRes -> SubExpRes -> Bool)
-> (SubExpRes -> SubExpRes -> SubExpRes)
-> (SubExpRes -> SubExpRes -> SubExpRes)
-> Ord SubExpRes
SubExpRes -> SubExpRes -> Bool
SubExpRes -> SubExpRes -> Ordering
SubExpRes -> SubExpRes -> SubExpRes
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 :: SubExpRes -> SubExpRes -> Ordering
compare :: SubExpRes -> SubExpRes -> Ordering
$c< :: SubExpRes -> SubExpRes -> Bool
< :: SubExpRes -> SubExpRes -> Bool
$c<= :: SubExpRes -> SubExpRes -> Bool
<= :: SubExpRes -> SubExpRes -> Bool
$c> :: SubExpRes -> SubExpRes -> Bool
> :: SubExpRes -> SubExpRes -> Bool
$c>= :: SubExpRes -> SubExpRes -> Bool
>= :: SubExpRes -> SubExpRes -> Bool
$cmax :: SubExpRes -> SubExpRes -> SubExpRes
max :: SubExpRes -> SubExpRes -> SubExpRes
$cmin :: SubExpRes -> SubExpRes -> SubExpRes
min :: SubExpRes -> SubExpRes -> SubExpRes
Ord, Int -> SubExpRes -> ShowS
[SubExpRes] -> ShowS
SubExpRes -> String
(Int -> SubExpRes -> ShowS)
-> (SubExpRes -> String)
-> ([SubExpRes] -> ShowS)
-> Show SubExpRes
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> SubExpRes -> ShowS
showsPrec :: Int -> SubExpRes -> ShowS
$cshow :: SubExpRes -> String
show :: SubExpRes -> String
$cshowList :: [SubExpRes] -> ShowS
showList :: [SubExpRes] -> ShowS
Show)

-- | Construct a 'SubExpRes' with no certificates.
subExpRes :: SubExp -> SubExpRes
subExpRes :: SubExp -> SubExpRes
subExpRes = Certs -> SubExp -> SubExpRes
SubExpRes Certs
forall a. Monoid a => a
mempty

-- | Construct a 'SubExpRes' from a variable name.
varRes :: VName -> SubExpRes
varRes :: VName -> SubExpRes
varRes = SubExp -> SubExpRes
subExpRes (SubExp -> SubExpRes) -> (VName -> SubExp) -> VName -> SubExpRes
forall b c a. (b -> c) -> (a -> b) -> a -> c
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. VName -> SubExp
Var

-- | Construct a 'Result' from subexpressions.
subExpsRes :: [SubExp] -> Result
subExpsRes :: [SubExp] -> [SubExpRes]
subExpsRes = (SubExp -> SubExpRes) -> [SubExp] -> [SubExpRes]
forall a b. (a -> b) -> [a] -> [b]
map SubExp -> SubExpRes
subExpRes

-- | Construct a 'Result' from variable names.
varsRes :: [VName] -> Result
varsRes :: [VName] -> [SubExpRes]
varsRes = (VName -> SubExpRes) -> [VName] -> [SubExpRes]
forall a b. (a -> b) -> [a] -> [b]
map VName -> SubExpRes
varRes

-- | The 'VName' of a 'SubExpRes', if it exists.
subExpResVName :: SubExpRes -> Maybe VName
subExpResVName :: SubExpRes -> Maybe VName
subExpResVName (SubExpRes Certs
_ (Var VName
v)) = VName -> Maybe VName
forall a. a -> Maybe a
Just VName
v
subExpResVName SubExpRes
_ = Maybe VName
forall a. Maybe a
Nothing

-- | The result of a body is a sequence of subexpressions.
type Result = [SubExpRes]

-- | A body consists of a number of bindings, terminating in a result
-- (essentially a tuple literal).
data Body rep = Body
  { forall rep. Body rep -> BodyDec rep
bodyDec :: BodyDec rep,
    forall rep. Body rep -> Stms rep
bodyStms :: Stms rep,
    forall rep. Body rep -> [SubExpRes]
bodyResult :: Result
  }

deriving instance (RepTypes rep) => Ord (Body rep)

deriving instance (RepTypes rep) => Show (Body rep)

deriving instance (RepTypes rep) => Eq (Body rep)

-- | Apart from being Opaque, what else is going on here?
data OpaqueOp
  = -- | No special operation.
    OpaqueNil
  | -- | Print the argument, prefixed by this string.
    OpaqueTrace T.Text
  deriving (OpaqueOp -> OpaqueOp -> Bool
(OpaqueOp -> OpaqueOp -> Bool)
-> (OpaqueOp -> OpaqueOp -> Bool) -> Eq OpaqueOp
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: OpaqueOp -> OpaqueOp -> Bool
== :: OpaqueOp -> OpaqueOp -> Bool
$c/= :: OpaqueOp -> OpaqueOp -> Bool
/= :: OpaqueOp -> OpaqueOp -> Bool
Eq, Eq OpaqueOp
Eq OpaqueOp
-> (OpaqueOp -> OpaqueOp -> Ordering)
-> (OpaqueOp -> OpaqueOp -> Bool)
-> (OpaqueOp -> OpaqueOp -> Bool)
-> (OpaqueOp -> OpaqueOp -> Bool)
-> (OpaqueOp -> OpaqueOp -> Bool)
-> (OpaqueOp -> OpaqueOp -> OpaqueOp)
-> (OpaqueOp -> OpaqueOp -> OpaqueOp)
-> Ord OpaqueOp
OpaqueOp -> OpaqueOp -> Bool
OpaqueOp -> OpaqueOp -> Ordering
OpaqueOp -> OpaqueOp -> OpaqueOp
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 :: OpaqueOp -> OpaqueOp -> Ordering
compare :: OpaqueOp -> OpaqueOp -> Ordering
$c< :: OpaqueOp -> OpaqueOp -> Bool
< :: OpaqueOp -> OpaqueOp -> Bool
$c<= :: OpaqueOp -> OpaqueOp -> Bool
<= :: OpaqueOp -> OpaqueOp -> Bool
$c> :: OpaqueOp -> OpaqueOp -> Bool
> :: OpaqueOp -> OpaqueOp -> Bool
$c>= :: OpaqueOp -> OpaqueOp -> Bool
>= :: OpaqueOp -> OpaqueOp -> Bool
$cmax :: OpaqueOp -> OpaqueOp -> OpaqueOp
max :: OpaqueOp -> OpaqueOp -> OpaqueOp
$cmin :: OpaqueOp -> OpaqueOp -> OpaqueOp
min :: OpaqueOp -> OpaqueOp -> OpaqueOp
Ord, Int -> OpaqueOp -> ShowS
[OpaqueOp] -> ShowS
OpaqueOp -> String
(Int -> OpaqueOp -> ShowS)
-> (OpaqueOp -> String) -> ([OpaqueOp] -> ShowS) -> Show OpaqueOp
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> OpaqueOp -> ShowS
showsPrec :: Int -> OpaqueOp -> ShowS
$cshow :: OpaqueOp -> String
show :: OpaqueOp -> String
$cshowList :: [OpaqueOp] -> ShowS
showList :: [OpaqueOp] -> ShowS
Show)

-- | Which kind of reshape is this?
data ReshapeKind
  = -- | New shape is dynamically same as original.
    ReshapeCoerce
  | -- | Any kind of reshaping.
    ReshapeArbitrary
  deriving (ReshapeKind -> ReshapeKind -> Bool
(ReshapeKind -> ReshapeKind -> Bool)
-> (ReshapeKind -> ReshapeKind -> Bool) -> Eq ReshapeKind
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: ReshapeKind -> ReshapeKind -> Bool
== :: ReshapeKind -> ReshapeKind -> Bool
$c/= :: ReshapeKind -> ReshapeKind -> Bool
/= :: ReshapeKind -> ReshapeKind -> Bool
Eq, Eq ReshapeKind
Eq ReshapeKind
-> (ReshapeKind -> ReshapeKind -> Ordering)
-> (ReshapeKind -> ReshapeKind -> Bool)
-> (ReshapeKind -> ReshapeKind -> Bool)
-> (ReshapeKind -> ReshapeKind -> Bool)
-> (ReshapeKind -> ReshapeKind -> Bool)
-> (ReshapeKind -> ReshapeKind -> ReshapeKind)
-> (ReshapeKind -> ReshapeKind -> ReshapeKind)
-> Ord ReshapeKind
ReshapeKind -> ReshapeKind -> Bool
ReshapeKind -> ReshapeKind -> Ordering
ReshapeKind -> ReshapeKind -> ReshapeKind
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 :: ReshapeKind -> ReshapeKind -> Ordering
compare :: ReshapeKind -> ReshapeKind -> Ordering
$c< :: ReshapeKind -> ReshapeKind -> Bool
< :: ReshapeKind -> ReshapeKind -> Bool
$c<= :: ReshapeKind -> ReshapeKind -> Bool
<= :: ReshapeKind -> ReshapeKind -> Bool
$c> :: ReshapeKind -> ReshapeKind -> Bool
> :: ReshapeKind -> ReshapeKind -> Bool
$c>= :: ReshapeKind -> ReshapeKind -> Bool
>= :: ReshapeKind -> ReshapeKind -> Bool
$cmax :: ReshapeKind -> ReshapeKind -> ReshapeKind
max :: ReshapeKind -> ReshapeKind -> ReshapeKind
$cmin :: ReshapeKind -> ReshapeKind -> ReshapeKind
min :: ReshapeKind -> ReshapeKind -> ReshapeKind
Ord, Int -> ReshapeKind -> ShowS
[ReshapeKind] -> ShowS
ReshapeKind -> String
(Int -> ReshapeKind -> ShowS)
-> (ReshapeKind -> String)
-> ([ReshapeKind] -> ShowS)
-> Show ReshapeKind
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> ReshapeKind -> ShowS
showsPrec :: Int -> ReshapeKind -> ShowS
$cshow :: ReshapeKind -> String
show :: ReshapeKind -> String
$cshowList :: [ReshapeKind] -> ShowS
showList :: [ReshapeKind] -> ShowS
Show)

-- | A primitive operation that returns something of known size and
-- does not itself contain any bindings.
data BasicOp
  = -- | A variable or constant.
    SubExp SubExp
  | -- | Semantically and operationally just identity, but is
    -- invisible/impenetrable to optimisations (hopefully).  This
    -- partially a hack to avoid optimisation (so, to work around
    -- compiler limitations), but is also used to implement tracing
    -- and other operations that are semantically invisible, but have
    -- some sort of effect (brrr).
    Opaque OpaqueOp SubExp
  | -- | Array literals, e.g., @[ [1+x, 3], [2, 1+4] ]@.
    -- Second arg is the element type of the rows of the array.
    ArrayLit [SubExp] Type
  | -- | Unary operation.
    UnOp UnOp SubExp
  | -- | Binary operation.
    BinOp BinOp SubExp SubExp
  | -- | Comparison - result type is always boolean.
    CmpOp CmpOp SubExp SubExp
  | -- | Conversion "casting".
    ConvOp ConvOp SubExp
  | -- | Turn a boolean into a certificate, halting the program with the
    -- given error message if the boolean is false.
    Assert SubExp (ErrorMsg SubExp) (SrcLoc, [SrcLoc])
  | -- | The certificates for bounds-checking are part of the 'Stm'.
    Index VName (Slice SubExp)
  | -- | An in-place update of the given array at the given position.
    -- Consumes the array.  If 'Safe', perform a run-time bounds check
    -- and ignore the write if out of bounds (like @Scatter@).
    Update Safety VName (Slice SubExp) SubExp
  | FlatIndex VName (FlatSlice SubExp)
  | FlatUpdate VName (FlatSlice SubExp) VName
  | -- | @concat(0, [1] :| [[2, 3, 4], [5, 6]], 6) = [1, 2, 3, 4, 5, 6]@
    --
    -- Concatenates the non-empty list of 'VName' resulting in an
    -- array of length t'SubExp'. The 'Int' argument is used to
    -- specify the dimension along which the arrays are
    -- concatenated. For instance:
    --
    -- @concat(1, [[1,2], [3, 4]] :| [[[5,6]], [[7, 8]]], 4) = [[1, 2, 5, 6], [3, 4, 7, 8]]@
    Concat Int (NonEmpty VName) SubExp
  | -- | Manifest an array with dimensions represented in the given
    -- order.  The result will not alias anything.
    Manifest [Int] VName
  | -- Array construction.

    -- | @iota(n, x, s) = [x,x+s,..,x+(n-1)*s]@.
    --
    -- The t'IntType' indicates the type of the array returned and the
    -- offset/stride arguments, but not the length argument.
    Iota SubExp SubExp SubExp IntType
  | -- | @replicate([3][2],1) = [[1,1], [1,1], [1,1]]@.  The result
    -- has no aliases.  Copy a value by passing an empty shape.
    Replicate Shape SubExp
  | -- | Create array of given type and shape, with undefined elements.
    Scratch PrimType [SubExp]
  | -- | 1st arg is the new shape, 2nd arg is the input array.
    Reshape ReshapeKind Shape VName
  | -- | Permute the dimensions of the input array.  The list
    -- of integers is a list of dimensions (0-indexed), which
    -- must be a permutation of @[0,n-1]@, where @n@ is the
    -- number of dimensions in the input array.
    Rearrange [Int] VName
  | -- | Update an accumulator at the given index with the given value.
    -- Consumes the accumulator and produces a new one.
    UpdateAcc VName [SubExp] [SubExp]
  deriving (BasicOp -> BasicOp -> Bool
(BasicOp -> BasicOp -> Bool)
-> (BasicOp -> BasicOp -> Bool) -> Eq BasicOp
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BasicOp -> BasicOp -> Bool
== :: BasicOp -> BasicOp -> Bool
$c/= :: BasicOp -> BasicOp -> Bool
/= :: BasicOp -> BasicOp -> Bool
Eq, Eq BasicOp
Eq BasicOp
-> (BasicOp -> BasicOp -> Ordering)
-> (BasicOp -> BasicOp -> Bool)
-> (BasicOp -> BasicOp -> Bool)
-> (BasicOp -> BasicOp -> Bool)
-> (BasicOp -> BasicOp -> Bool)
-> (BasicOp -> BasicOp -> BasicOp)
-> (BasicOp -> BasicOp -> BasicOp)
-> Ord BasicOp
BasicOp -> BasicOp -> Bool
BasicOp -> BasicOp -> Ordering
BasicOp -> BasicOp -> BasicOp
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 :: BasicOp -> BasicOp -> Ordering
compare :: BasicOp -> BasicOp -> Ordering
$c< :: BasicOp -> BasicOp -> Bool
< :: BasicOp -> BasicOp -> Bool
$c<= :: BasicOp -> BasicOp -> Bool
<= :: BasicOp -> BasicOp -> Bool
$c> :: BasicOp -> BasicOp -> Bool
> :: BasicOp -> BasicOp -> Bool
$c>= :: BasicOp -> BasicOp -> Bool
>= :: BasicOp -> BasicOp -> Bool
$cmax :: BasicOp -> BasicOp -> BasicOp
max :: BasicOp -> BasicOp -> BasicOp
$cmin :: BasicOp -> BasicOp -> BasicOp
min :: BasicOp -> BasicOp -> BasicOp
Ord, Int -> BasicOp -> ShowS
[BasicOp] -> ShowS
BasicOp -> String
(Int -> BasicOp -> ShowS)
-> (BasicOp -> String) -> ([BasicOp] -> ShowS) -> Show BasicOp
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> BasicOp -> ShowS
showsPrec :: Int -> BasicOp -> ShowS
$cshow :: BasicOp -> String
show :: BasicOp -> String
$cshowList :: [BasicOp] -> ShowS
showList :: [BasicOp] -> ShowS
Show)

-- | The input to a 'WithAcc' construct.  Comprises the index space of
-- the accumulator, the underlying arrays, and possibly a combining
-- function.
type WithAccInput rep =
  (Shape, [VName], Maybe (Lambda rep, [SubExp]))

-- | A non-default case in a 'Match' statement.  The number of
-- elements in the pattern must match the number of scrutinees.  A
-- 'Nothing' value indicates that we don't care about it (i.e. a
-- wildcard).
data Case body = Case {forall body. Case body -> [Maybe PrimValue]
casePat :: [Maybe PrimValue], forall body. Case body -> body
caseBody :: body}
  deriving (Case body -> Case body -> Bool
(Case body -> Case body -> Bool)
-> (Case body -> Case body -> Bool) -> Eq (Case body)
forall body. Eq body => Case body -> Case body -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall body. Eq body => Case body -> Case body -> Bool
== :: Case body -> Case body -> Bool
$c/= :: forall body. Eq body => Case body -> Case body -> Bool
/= :: Case body -> Case body -> Bool
Eq, Eq (Case body)
Eq (Case body)
-> (Case body -> Case body -> Ordering)
-> (Case body -> Case body -> Bool)
-> (Case body -> Case body -> Bool)
-> (Case body -> Case body -> Bool)
-> (Case body -> Case body -> Bool)
-> (Case body -> Case body -> Case body)
-> (Case body -> Case body -> Case body)
-> Ord (Case body)
Case body -> Case body -> Bool
Case body -> Case body -> Ordering
Case body -> Case body -> Case body
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
forall {body}. Ord body => Eq (Case body)
forall body. Ord body => Case body -> Case body -> Bool
forall body. Ord body => Case body -> Case body -> Ordering
forall body. Ord body => Case body -> Case body -> Case body
$ccompare :: forall body. Ord body => Case body -> Case body -> Ordering
compare :: Case body -> Case body -> Ordering
$c< :: forall body. Ord body => Case body -> Case body -> Bool
< :: Case body -> Case body -> Bool
$c<= :: forall body. Ord body => Case body -> Case body -> Bool
<= :: Case body -> Case body -> Bool
$c> :: forall body. Ord body => Case body -> Case body -> Bool
> :: Case body -> Case body -> Bool
$c>= :: forall body. Ord body => Case body -> Case body -> Bool
>= :: Case body -> Case body -> Bool
$cmax :: forall body. Ord body => Case body -> Case body -> Case body
max :: Case body -> Case body -> Case body
$cmin :: forall body. Ord body => Case body -> Case body -> Case body
min :: Case body -> Case body -> Case body
Ord, Int -> Case body -> ShowS
[Case body] -> ShowS
Case body -> String
(Int -> Case body -> ShowS)
-> (Case body -> String)
-> ([Case body] -> ShowS)
-> Show (Case body)
forall body. Show body => Int -> Case body -> ShowS
forall body. Show body => [Case body] -> ShowS
forall body. Show body => Case body -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall body. Show body => Int -> Case body -> ShowS
showsPrec :: Int -> Case body -> ShowS
$cshow :: forall body. Show body => Case body -> String
show :: Case body -> String
$cshowList :: forall body. Show body => [Case body] -> ShowS
showList :: [Case body] -> ShowS
Show)

instance Functor Case where
  fmap :: forall a b. (a -> b) -> Case a -> Case b
fmap = (a -> b) -> Case a -> Case b
forall (t :: * -> *) a b. Traversable t => (a -> b) -> t a -> t b
fmapDefault

instance Foldable Case where
  foldMap :: forall m a. Monoid m => (a -> m) -> Case a -> m
foldMap = (a -> m) -> Case a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
foldMapDefault

instance Traversable Case where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Case a -> f (Case b)
traverse a -> f b
f (Case [Maybe PrimValue]
vs a
b) = [Maybe PrimValue] -> b -> Case b
forall body. [Maybe PrimValue] -> body -> Case body
Case [Maybe PrimValue]
vs (b -> Case b) -> f b -> f (Case b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
b

-- | Information about the possible aliases of a function result.
data RetAls = RetAls
  { -- | Which of the parameters may be aliased, numbered from zero.
    RetAls -> [Int]
paramAls :: [Int],
    -- | Which of the other results may be aliased, numbered from
    -- zero.  This must be a reflexive relation.
    RetAls -> [Int]
otherAls :: [Int]
  }
  deriving (RetAls -> RetAls -> Bool
(RetAls -> RetAls -> Bool)
-> (RetAls -> RetAls -> Bool) -> Eq RetAls
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: RetAls -> RetAls -> Bool
== :: RetAls -> RetAls -> Bool
$c/= :: RetAls -> RetAls -> Bool
/= :: RetAls -> RetAls -> Bool
Eq, Eq RetAls
Eq RetAls
-> (RetAls -> RetAls -> Ordering)
-> (RetAls -> RetAls -> Bool)
-> (RetAls -> RetAls -> Bool)
-> (RetAls -> RetAls -> Bool)
-> (RetAls -> RetAls -> Bool)
-> (RetAls -> RetAls -> RetAls)
-> (RetAls -> RetAls -> RetAls)
-> Ord RetAls
RetAls -> RetAls -> Bool
RetAls -> RetAls -> Ordering
RetAls -> RetAls -> RetAls
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 :: RetAls -> RetAls -> Ordering
compare :: RetAls -> RetAls -> Ordering
$c< :: RetAls -> RetAls -> Bool
< :: RetAls -> RetAls -> Bool
$c<= :: RetAls -> RetAls -> Bool
<= :: RetAls -> RetAls -> Bool
$c> :: RetAls -> RetAls -> Bool
> :: RetAls -> RetAls -> Bool
$c>= :: RetAls -> RetAls -> Bool
>= :: RetAls -> RetAls -> Bool
$cmax :: RetAls -> RetAls -> RetAls
max :: RetAls -> RetAls -> RetAls
$cmin :: RetAls -> RetAls -> RetAls
min :: RetAls -> RetAls -> RetAls
Ord, Int -> RetAls -> ShowS
[RetAls] -> ShowS
RetAls -> String
(Int -> RetAls -> ShowS)
-> (RetAls -> String) -> ([RetAls] -> ShowS) -> Show RetAls
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> RetAls -> ShowS
showsPrec :: Int -> RetAls -> ShowS
$cshow :: RetAls -> String
show :: RetAls -> String
$cshowList :: [RetAls] -> ShowS
showList :: [RetAls] -> ShowS
Show)

instance Monoid RetAls where
  mempty :: RetAls
mempty = [Int] -> [Int] -> RetAls
RetAls [Int]
forall a. Monoid a => a
mempty [Int]
forall a. Monoid a => a
mempty

instance Semigroup RetAls where
  RetAls [Int]
pals1 [Int]
rals1 <> :: RetAls -> RetAls -> RetAls
<> RetAls [Int]
pals2 [Int]
rals2 =
    [Int] -> [Int] -> RetAls
RetAls ([Int]
pals1 [Int] -> [Int] -> [Int]
forall a. Semigroup a => a -> a -> a
<> [Int]
pals2) ([Int]
rals1 [Int] -> [Int] -> [Int]
forall a. Semigroup a => a -> a -> a
<> [Int]
rals2)

-- | The root Futhark expression type.  The v'Op' constructor contains
-- a rep-specific operation.  Do-loops, branches and function calls
-- are special.  Everything else is a simple t'BasicOp'.
data Exp rep
  = -- | A simple (non-recursive) operation.
    BasicOp BasicOp
  | Apply Name [(SubExp, Diet)] [(RetType rep, RetAls)] (Safety, SrcLoc, [SrcLoc])
  | -- | A match statement picks a branch by comparing the given
    -- subexpressions (called the /scrutinee/) with the pattern in
    -- each of the cases.  If none of the cases match, the /default
    -- body/ is picked.
    Match [SubExp] [Case (Body rep)] (Body rep) (MatchDec (BranchType rep))
  | -- | @loop {a} = {v} (for i < n|while b) do b@.
    Loop [(FParam rep, SubExp)] (LoopForm rep) (Body rep)
  | -- | Create accumulators backed by the given arrays (which are
    -- consumed) and pass them to the lambda, which must return the
    -- updated accumulators and possibly some extra values.  The
    -- accumulators are turned back into arrays.  The t'Shape' is the
    -- write index space.  The corresponding arrays must all have this
    -- shape outermost.  This construct is not part of t'BasicOp'
    -- because we need the @rep@ parameter.
    WithAcc [WithAccInput rep] (Lambda rep)
  | Op (Op rep)

deriving instance (RepTypes rep) => Eq (Exp rep)

deriving instance (RepTypes rep) => Show (Exp rep)

deriving instance (RepTypes rep) => Ord (Exp rep)

-- | For-loop or while-loop?
data LoopForm rep
  = ForLoop
      VName
      -- ^ The loop iterator var
      IntType
      -- ^ The type of the loop iterator var
      SubExp
      -- ^ The number of iterations.
      [(LParam rep, VName)]
  | WhileLoop VName

deriving instance (RepTypes rep) => Eq (LoopForm rep)

deriving instance (RepTypes rep) => Show (LoopForm rep)

deriving instance (RepTypes rep) => Ord (LoopForm rep)

-- | Data associated with a branch.
data MatchDec rt = MatchDec
  { forall rt. MatchDec rt -> [rt]
matchReturns :: [rt],
    forall rt. MatchDec rt -> MatchSort
matchSort :: MatchSort
  }
  deriving (MatchDec rt -> MatchDec rt -> Bool
(MatchDec rt -> MatchDec rt -> Bool)
-> (MatchDec rt -> MatchDec rt -> Bool) -> Eq (MatchDec rt)
forall rt. Eq rt => MatchDec rt -> MatchDec rt -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall rt. Eq rt => MatchDec rt -> MatchDec rt -> Bool
== :: MatchDec rt -> MatchDec rt -> Bool
$c/= :: forall rt. Eq rt => MatchDec rt -> MatchDec rt -> Bool
/= :: MatchDec rt -> MatchDec rt -> Bool
Eq, Int -> MatchDec rt -> ShowS
[MatchDec rt] -> ShowS
MatchDec rt -> String
(Int -> MatchDec rt -> ShowS)
-> (MatchDec rt -> String)
-> ([MatchDec rt] -> ShowS)
-> Show (MatchDec rt)
forall rt. Show rt => Int -> MatchDec rt -> ShowS
forall rt. Show rt => [MatchDec rt] -> ShowS
forall rt. Show rt => MatchDec rt -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall rt. Show rt => Int -> MatchDec rt -> ShowS
showsPrec :: Int -> MatchDec rt -> ShowS
$cshow :: forall rt. Show rt => MatchDec rt -> String
show :: MatchDec rt -> String
$cshowList :: forall rt. Show rt => [MatchDec rt] -> ShowS
showList :: [MatchDec rt] -> ShowS
Show, Eq (MatchDec rt)
Eq (MatchDec rt)
-> (MatchDec rt -> MatchDec rt -> Ordering)
-> (MatchDec rt -> MatchDec rt -> Bool)
-> (MatchDec rt -> MatchDec rt -> Bool)
-> (MatchDec rt -> MatchDec rt -> Bool)
-> (MatchDec rt -> MatchDec rt -> Bool)
-> (MatchDec rt -> MatchDec rt -> MatchDec rt)
-> (MatchDec rt -> MatchDec rt -> MatchDec rt)
-> Ord (MatchDec rt)
MatchDec rt -> MatchDec rt -> Bool
MatchDec rt -> MatchDec rt -> Ordering
MatchDec rt -> MatchDec rt -> MatchDec rt
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
forall {rt}. Ord rt => Eq (MatchDec rt)
forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Bool
forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Ordering
forall rt. Ord rt => MatchDec rt -> MatchDec rt -> MatchDec rt
$ccompare :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Ordering
compare :: MatchDec rt -> MatchDec rt -> Ordering
$c< :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Bool
< :: MatchDec rt -> MatchDec rt -> Bool
$c<= :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Bool
<= :: MatchDec rt -> MatchDec rt -> Bool
$c> :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Bool
> :: MatchDec rt -> MatchDec rt -> Bool
$c>= :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> Bool
>= :: MatchDec rt -> MatchDec rt -> Bool
$cmax :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> MatchDec rt
max :: MatchDec rt -> MatchDec rt -> MatchDec rt
$cmin :: forall rt. Ord rt => MatchDec rt -> MatchDec rt -> MatchDec rt
min :: MatchDec rt -> MatchDec rt -> MatchDec rt
Ord)

-- | What kind of branch is this?  This has no semantic meaning, but
-- provides hints to simplifications.
data MatchSort
  = -- | An ordinary branch.
    MatchNormal
  | -- | A branch where the "true" case is what we are
    -- actually interested in, and the "false" case is only
    -- present as a fallback for when the true case cannot
    -- be safely evaluated.  The compiler is permitted to
    -- optimise away the branch if the true case contains
    -- only safe statements.
    MatchFallback
  | -- | Both of these branches are semantically equivalent,
    -- and it is fine to eliminate one if it turns out to
    -- have problems (e.g. contain things we cannot generate
    -- code for).
    MatchEquiv
  deriving (MatchSort -> MatchSort -> Bool
(MatchSort -> MatchSort -> Bool)
-> (MatchSort -> MatchSort -> Bool) -> Eq MatchSort
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: MatchSort -> MatchSort -> Bool
== :: MatchSort -> MatchSort -> Bool
$c/= :: MatchSort -> MatchSort -> Bool
/= :: MatchSort -> MatchSort -> Bool
Eq, Int -> MatchSort -> ShowS
[MatchSort] -> ShowS
MatchSort -> String
(Int -> MatchSort -> ShowS)
-> (MatchSort -> String)
-> ([MatchSort] -> ShowS)
-> Show MatchSort
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> MatchSort -> ShowS
showsPrec :: Int -> MatchSort -> ShowS
$cshow :: MatchSort -> String
show :: MatchSort -> String
$cshowList :: [MatchSort] -> ShowS
showList :: [MatchSort] -> ShowS
Show, Eq MatchSort
Eq MatchSort
-> (MatchSort -> MatchSort -> Ordering)
-> (MatchSort -> MatchSort -> Bool)
-> (MatchSort -> MatchSort -> Bool)
-> (MatchSort -> MatchSort -> Bool)
-> (MatchSort -> MatchSort -> Bool)
-> (MatchSort -> MatchSort -> MatchSort)
-> (MatchSort -> MatchSort -> MatchSort)
-> Ord MatchSort
MatchSort -> MatchSort -> Bool
MatchSort -> MatchSort -> Ordering
MatchSort -> MatchSort -> MatchSort
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 :: MatchSort -> MatchSort -> Ordering
compare :: MatchSort -> MatchSort -> Ordering
$c< :: MatchSort -> MatchSort -> Bool
< :: MatchSort -> MatchSort -> Bool
$c<= :: MatchSort -> MatchSort -> Bool
<= :: MatchSort -> MatchSort -> Bool
$c> :: MatchSort -> MatchSort -> Bool
> :: MatchSort -> MatchSort -> Bool
$c>= :: MatchSort -> MatchSort -> Bool
>= :: MatchSort -> MatchSort -> Bool
$cmax :: MatchSort -> MatchSort -> MatchSort
max :: MatchSort -> MatchSort -> MatchSort
$cmin :: MatchSort -> MatchSort -> MatchSort
min :: MatchSort -> MatchSort -> MatchSort
Ord)

-- | Anonymous function for use in a SOAC.
data Lambda rep = Lambda
  { forall rep. Lambda rep -> [LParam rep]
lambdaParams :: [LParam rep],
    forall rep. Lambda rep -> Body rep
lambdaBody :: Body rep,
    forall rep. Lambda rep -> [Type]
lambdaReturnType :: [Type]
  }

deriving instance (RepTypes rep) => Eq (Lambda rep)

deriving instance (RepTypes rep) => Show (Lambda rep)

deriving instance (RepTypes rep) => Ord (Lambda rep)

-- | A function and loop parameter.
type FParam rep = Param (FParamInfo rep)

-- | A lambda parameter.
type LParam rep = Param (LParamInfo rep)

-- | Function Declarations
data FunDef rep = FunDef
  { -- | Contains a value if this function is
    -- an entry point.
    forall rep. FunDef rep -> Maybe EntryPoint
funDefEntryPoint :: Maybe EntryPoint,
    forall rep. FunDef rep -> Attrs
funDefAttrs :: Attrs,
    forall rep. FunDef rep -> Name
funDefName :: Name,
    forall rep. FunDef rep -> [(RetType rep, RetAls)]
funDefRetType :: [(RetType rep, RetAls)],
    forall rep. FunDef rep -> [FParam rep]
funDefParams :: [FParam rep],
    forall rep. FunDef rep -> Body rep
funDefBody :: Body rep
  }

deriving instance (RepTypes rep) => Eq (FunDef rep)

deriving instance (RepTypes rep) => Show (FunDef rep)

deriving instance (RepTypes rep) => Ord (FunDef rep)

-- | An entry point parameter, comprising its name and original type.
data EntryParam = EntryParam
  { EntryParam -> Name
entryParamName :: Name,
    EntryParam -> Uniqueness
entryParamUniqueness :: Uniqueness,
    EntryParam -> EntryPointType
entryParamType :: EntryPointType
  }
  deriving (EntryParam -> EntryParam -> Bool
(EntryParam -> EntryParam -> Bool)
-> (EntryParam -> EntryParam -> Bool) -> Eq EntryParam
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: EntryParam -> EntryParam -> Bool
== :: EntryParam -> EntryParam -> Bool
$c/= :: EntryParam -> EntryParam -> Bool
/= :: EntryParam -> EntryParam -> Bool
Eq, Int -> EntryParam -> ShowS
[EntryParam] -> ShowS
EntryParam -> String
(Int -> EntryParam -> ShowS)
-> (EntryParam -> String)
-> ([EntryParam] -> ShowS)
-> Show EntryParam
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> EntryParam -> ShowS
showsPrec :: Int -> EntryParam -> ShowS
$cshow :: EntryParam -> String
show :: EntryParam -> String
$cshowList :: [EntryParam] -> ShowS
showList :: [EntryParam] -> ShowS
Show, Eq EntryParam
Eq EntryParam
-> (EntryParam -> EntryParam -> Ordering)
-> (EntryParam -> EntryParam -> Bool)
-> (EntryParam -> EntryParam -> Bool)
-> (EntryParam -> EntryParam -> Bool)
-> (EntryParam -> EntryParam -> Bool)
-> (EntryParam -> EntryParam -> EntryParam)
-> (EntryParam -> EntryParam -> EntryParam)
-> Ord EntryParam
EntryParam -> EntryParam -> Bool
EntryParam -> EntryParam -> Ordering
EntryParam -> EntryParam -> EntryParam
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 :: EntryParam -> EntryParam -> Ordering
compare :: EntryParam -> EntryParam -> Ordering
$c< :: EntryParam -> EntryParam -> Bool
< :: EntryParam -> EntryParam -> Bool
$c<= :: EntryParam -> EntryParam -> Bool
<= :: EntryParam -> EntryParam -> Bool
$c> :: EntryParam -> EntryParam -> Bool
> :: EntryParam -> EntryParam -> Bool
$c>= :: EntryParam -> EntryParam -> Bool
>= :: EntryParam -> EntryParam -> Bool
$cmax :: EntryParam -> EntryParam -> EntryParam
max :: EntryParam -> EntryParam -> EntryParam
$cmin :: EntryParam -> EntryParam -> EntryParam
min :: EntryParam -> EntryParam -> EntryParam
Ord)

-- | An entry point result type.
data EntryResult = EntryResult
  { EntryResult -> Uniqueness
entryResultUniqueness :: Uniqueness,
    EntryResult -> EntryPointType
entryResultType :: EntryPointType
  }
  deriving (EntryResult -> EntryResult -> Bool
(EntryResult -> EntryResult -> Bool)
-> (EntryResult -> EntryResult -> Bool) -> Eq EntryResult
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: EntryResult -> EntryResult -> Bool
== :: EntryResult -> EntryResult -> Bool
$c/= :: EntryResult -> EntryResult -> Bool
/= :: EntryResult -> EntryResult -> Bool
Eq, Int -> EntryResult -> ShowS
[EntryResult] -> ShowS
EntryResult -> String
(Int -> EntryResult -> ShowS)
-> (EntryResult -> String)
-> ([EntryResult] -> ShowS)
-> Show EntryResult
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> EntryResult -> ShowS
showsPrec :: Int -> EntryResult -> ShowS
$cshow :: EntryResult -> String
show :: EntryResult -> String
$cshowList :: [EntryResult] -> ShowS
showList :: [EntryResult] -> ShowS
Show, Eq EntryResult
Eq EntryResult
-> (EntryResult -> EntryResult -> Ordering)
-> (EntryResult -> EntryResult -> Bool)
-> (EntryResult -> EntryResult -> Bool)
-> (EntryResult -> EntryResult -> Bool)
-> (EntryResult -> EntryResult -> Bool)
-> (EntryResult -> EntryResult -> EntryResult)
-> (EntryResult -> EntryResult -> EntryResult)
-> Ord EntryResult
EntryResult -> EntryResult -> Bool
EntryResult -> EntryResult -> Ordering
EntryResult -> EntryResult -> EntryResult
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 :: EntryResult -> EntryResult -> Ordering
compare :: EntryResult -> EntryResult -> Ordering
$c< :: EntryResult -> EntryResult -> Bool
< :: EntryResult -> EntryResult -> Bool
$c<= :: EntryResult -> EntryResult -> Bool
<= :: EntryResult -> EntryResult -> Bool
$c> :: EntryResult -> EntryResult -> Bool
> :: EntryResult -> EntryResult -> Bool
$c>= :: EntryResult -> EntryResult -> Bool
>= :: EntryResult -> EntryResult -> Bool
$cmax :: EntryResult -> EntryResult -> EntryResult
max :: EntryResult -> EntryResult -> EntryResult
$cmin :: EntryResult -> EntryResult -> EntryResult
min :: EntryResult -> EntryResult -> EntryResult
Ord)

-- | Information about the inputs and outputs (return value) of an entry
-- point.
type EntryPoint = (Name, [EntryParam], [EntryResult])

-- | An entire Futhark program.
data Prog rep = Prog
  { -- | The opaque types used in entry points.  This information is
    -- used to generate extra API functions for
    -- construction and deconstruction of values of these types.
    forall rep. Prog rep -> OpaqueTypes
progTypes :: OpaqueTypes,
    -- | Top-level constants that are computed at program startup, and
    -- which are in scope inside all functions.
    forall rep. Prog rep -> Stms rep
progConsts :: Stms rep,
    -- | The functions comprising the program.  All functions are also
    -- available in scope in the definitions of the constants, so be
    -- careful not to introduce circular dependencies (not currently
    -- checked).
    forall rep. Prog rep -> [FunDef rep]
progFuns :: [FunDef rep]
  }
  deriving (Prog rep -> Prog rep -> Bool
(Prog rep -> Prog rep -> Bool)
-> (Prog rep -> Prog rep -> Bool) -> Eq (Prog rep)
forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
== :: Prog rep -> Prog rep -> Bool
$c/= :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
/= :: Prog rep -> Prog rep -> Bool
Eq, Eq (Prog rep)
Eq (Prog rep)
-> (Prog rep -> Prog rep -> Ordering)
-> (Prog rep -> Prog rep -> Bool)
-> (Prog rep -> Prog rep -> Bool)
-> (Prog rep -> Prog rep -> Bool)
-> (Prog rep -> Prog rep -> Bool)
-> (Prog rep -> Prog rep -> Prog rep)
-> (Prog rep -> Prog rep -> Prog rep)
-> Ord (Prog rep)
Prog rep -> Prog rep -> Bool
Prog rep -> Prog rep -> Ordering
Prog rep -> Prog rep -> Prog rep
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
forall rep. RepTypes rep => Eq (Prog rep)
forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
forall rep. RepTypes rep => Prog rep -> Prog rep -> Ordering
forall rep. RepTypes rep => Prog rep -> Prog rep -> Prog rep
$ccompare :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Ordering
compare :: Prog rep -> Prog rep -> Ordering
$c< :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
< :: Prog rep -> Prog rep -> Bool
$c<= :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
<= :: Prog rep -> Prog rep -> Bool
$c> :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
> :: Prog rep -> Prog rep -> Bool
$c>= :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Bool
>= :: Prog rep -> Prog rep -> Bool
$cmax :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Prog rep
max :: Prog rep -> Prog rep -> Prog rep
$cmin :: forall rep. RepTypes rep => Prog rep -> Prog rep -> Prog rep
min :: Prog rep -> Prog rep -> Prog rep
Ord, Int -> Prog rep -> ShowS
[Prog rep] -> ShowS
Prog rep -> String
(Int -> Prog rep -> ShowS)
-> (Prog rep -> String) -> ([Prog rep] -> ShowS) -> Show (Prog rep)
forall rep. RepTypes rep => Int -> Prog rep -> ShowS
forall rep. RepTypes rep => [Prog rep] -> ShowS
forall rep. RepTypes rep => Prog rep -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall rep. RepTypes rep => Int -> Prog rep -> ShowS
showsPrec :: Int -> Prog rep -> ShowS
$cshow :: forall rep. RepTypes rep => Prog rep -> String
show :: Prog rep -> String
$cshowList :: forall rep. RepTypes rep => [Prog rep] -> ShowS
showList :: [Prog rep] -> ShowS
Show)