{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Strict #-}
{-# LANGUAGE Trustworthy #-}
{-# 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' 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
-- "Futhark.IR.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'Pattern' alongside an
-- expression 'ExpT'.  A pattern contains a "context" part and a
-- "value" part.  The context is used for things like the size of
-- arrays in the value part whose size is existential.
--
-- 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}
-- @
--
-- == Lores
--
-- Most AST types ('Stm', 'ExpT', t'Prog', etc) are parameterised by a
-- type parameter with the somewhat silly name @lore@.  The lore
-- specifies how to fill out various polymorphic parts of the AST.
-- For example, 'ExpT' has a constructor v'Op' whose payload depends
-- on @lore@, via the use of a type family called t'Op' (a kind of
-- type-level function) which is applied to the @lore@.  The SOACS
-- representation ("Futhark.IR.SOACS") thus uses a lore
-- 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'PatElemT')
-- are also type families.
--
-- The full list of possible decorations is defined as part of the
-- type class 'Decorations' (although other type families are also
-- used elsewhere in the compiler on an ad hoc basis).
--
-- Essentially, the @lore@ 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).
--
-- Defining a new representation (or /lore/) 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,
    module Futhark.IR.Decorations,
    module Futhark.IR.Syntax.Core,

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

    -- * Attributes
    Attr (..),
    Attrs (..),
    oneAttr,
    inAttrs,
    withoutAttrs,

    -- * Abstract syntax tree
    Ident (..),
    SubExp (..),
    PatElem,
    PatElemT (..),
    PatternT (..),
    Pattern,
    StmAux (..),
    Stm (..),
    Stms,
    Result,
    BodyT (..),
    Body,
    BasicOp (..),
    UnOp (..),
    BinOp (..),
    CmpOp (..),
    ConvOp (..),
    DimChange (..),
    ShapeChange,
    ExpT (..),
    Exp,
    LoopForm (..),
    IfDec (..),
    IfSort (..),
    Safety (..),
    LambdaT (..),
    Lambda,

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

    -- * Utils
    oneStm,
    stmsFromList,
    stmsToList,
    stmsHead,
  )
where

import Control.Category
import Data.Foldable
import qualified Data.Sequence as Seq
import qualified Data.Set as S
import Data.String
import Data.Traversable (fmapDefault, foldMapDefault)
import Futhark.IR.Decorations
import Futhark.IR.Syntax.Core
import Language.Futhark.Core
import Prelude hiding (id, (.))

-- | A single attribute.
data Attr
  = AttrAtom Name
  | AttrComp Name [Attr]
  deriving (Eq Attr
Eq Attr
-> (Attr -> Attr -> Ordering)
-> (Attr -> Attr -> Bool)
-> (Attr -> Attr -> Bool)
-> (Attr -> Attr -> Bool)
-> (Attr -> Attr -> Bool)
-> (Attr -> Attr -> Attr)
-> (Attr -> Attr -> Attr)
-> Ord Attr
Attr -> Attr -> Bool
Attr -> Attr -> Ordering
Attr -> Attr -> Attr
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
min :: Attr -> Attr -> Attr
$cmin :: Attr -> Attr -> Attr
max :: Attr -> Attr -> Attr
$cmax :: Attr -> Attr -> Attr
>= :: Attr -> Attr -> Bool
$c>= :: Attr -> Attr -> Bool
> :: Attr -> Attr -> Bool
$c> :: Attr -> Attr -> Bool
<= :: Attr -> Attr -> Bool
$c<= :: Attr -> Attr -> Bool
< :: Attr -> Attr -> Bool
$c< :: Attr -> Attr -> Bool
compare :: Attr -> Attr -> Ordering
$ccompare :: Attr -> Attr -> Ordering
Ord, Int -> Attr -> ShowS
[Attr] -> ShowS
Attr -> String
(Int -> Attr -> ShowS)
-> (Attr -> String) -> ([Attr] -> ShowS) -> Show Attr
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Attr] -> ShowS
$cshowList :: [Attr] -> ShowS
show :: Attr -> String
$cshow :: Attr -> String
showsPrec :: Int -> Attr -> ShowS
$cshowsPrec :: Int -> Attr -> ShowS
Show, Attr -> Attr -> Bool
(Attr -> Attr -> Bool) -> (Attr -> Attr -> Bool) -> Eq Attr
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Attr -> Attr -> Bool
$c/= :: Attr -> Attr -> Bool
== :: Attr -> Attr -> Bool
$c== :: Attr -> Attr -> Bool
Eq)

instance IsString Attr where
  fromString :: String -> Attr
fromString = Name -> Attr
AttrAtom (Name -> Attr) -> (String -> Name) -> String -> Attr
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. String -> Name
forall a. IsString a => String -> a
fromString

-- | Every statement is associated with a set of attributes, which can
-- have various effects throughout the compiler.
newtype Attrs = Attrs {Attrs -> Set Attr
unAttrs :: S.Set Attr}
  deriving (Eq Attrs
Eq Attrs
-> (Attrs -> Attrs -> Ordering)
-> (Attrs -> Attrs -> Bool)
-> (Attrs -> Attrs -> Bool)
-> (Attrs -> Attrs -> Bool)
-> (Attrs -> Attrs -> Bool)
-> (Attrs -> Attrs -> Attrs)
-> (Attrs -> Attrs -> Attrs)
-> Ord Attrs
Attrs -> Attrs -> Bool
Attrs -> Attrs -> Ordering
Attrs -> Attrs -> Attrs
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
min :: Attrs -> Attrs -> Attrs
$cmin :: Attrs -> Attrs -> Attrs
max :: Attrs -> Attrs -> Attrs
$cmax :: Attrs -> Attrs -> Attrs
>= :: Attrs -> Attrs -> Bool
$c>= :: Attrs -> Attrs -> Bool
> :: Attrs -> Attrs -> Bool
$c> :: Attrs -> Attrs -> Bool
<= :: Attrs -> Attrs -> Bool
$c<= :: Attrs -> Attrs -> Bool
< :: Attrs -> Attrs -> Bool
$c< :: Attrs -> Attrs -> Bool
compare :: Attrs -> Attrs -> Ordering
$ccompare :: Attrs -> Attrs -> Ordering
Ord, Int -> Attrs -> ShowS
[Attrs] -> ShowS
Attrs -> String
(Int -> Attrs -> ShowS)
-> (Attrs -> String) -> ([Attrs] -> ShowS) -> Show Attrs
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Attrs] -> ShowS
$cshowList :: [Attrs] -> ShowS
show :: Attrs -> String
$cshow :: Attrs -> String
showsPrec :: Int -> Attrs -> ShowS
$cshowsPrec :: Int -> Attrs -> ShowS
Show, Attrs -> Attrs -> Bool
(Attrs -> Attrs -> Bool) -> (Attrs -> Attrs -> Bool) -> Eq Attrs
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Attrs -> Attrs -> Bool
$c/= :: Attrs -> Attrs -> Bool
== :: Attrs -> Attrs -> Bool
$c== :: Attrs -> Attrs -> Bool
Eq, Semigroup Attrs
Attrs
Semigroup Attrs
-> Attrs
-> (Attrs -> Attrs -> Attrs)
-> ([Attrs] -> Attrs)
-> Monoid Attrs
[Attrs] -> Attrs
Attrs -> Attrs -> Attrs
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
mconcat :: [Attrs] -> Attrs
$cmconcat :: [Attrs] -> Attrs
mappend :: Attrs -> Attrs -> Attrs
$cmappend :: Attrs -> Attrs -> Attrs
mempty :: Attrs
$cmempty :: Attrs
Monoid, NonEmpty Attrs -> Attrs
Attrs -> Attrs -> Attrs
(Attrs -> Attrs -> Attrs)
-> (NonEmpty Attrs -> Attrs)
-> (forall b. Integral b => b -> Attrs -> Attrs)
-> Semigroup Attrs
forall b. Integral b => b -> Attrs -> Attrs
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
stimes :: forall b. Integral b => b -> Attrs -> Attrs
$cstimes :: forall b. Integral b => b -> Attrs -> Attrs
sconcat :: NonEmpty Attrs -> Attrs
$csconcat :: NonEmpty Attrs -> Attrs
<> :: Attrs -> Attrs -> Attrs
$c<> :: Attrs -> Attrs -> Attrs
Semigroup)

-- | Construct 'Attrs' from a single 'Attr'.
oneAttr :: Attr -> Attrs
oneAttr :: Attr -> Attrs
oneAttr = Set Attr -> Attrs
Attrs (Set Attr -> Attrs) -> (Attr -> Set Attr) -> Attr -> Attrs
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Attr -> Set Attr
forall a. a -> Set a
S.singleton

-- | Is the given attribute to be found in the attribute set?
inAttrs :: Attr -> Attrs -> Bool
inAttrs :: Attr -> Attrs -> Bool
inAttrs Attr
attr (Attrs Set Attr
attrs) = Attr
attr Attr -> Set Attr -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set Attr
attrs

-- | @x `withoutAttrs` y@ gives @x@ except for any attributes also in @y@.
withoutAttrs :: Attrs -> Attrs -> Attrs
withoutAttrs :: Attrs -> Attrs -> Attrs
withoutAttrs (Attrs Set Attr
x) (Attrs Set Attr
y) = Set Attr -> Attrs
Attrs (Set Attr -> Attrs) -> Set Attr -> Attrs
forall a b. (a -> b) -> a -> b
$ Set Attr
x Set Attr -> Set Attr -> Set Attr
forall a. Ord a => Set a -> Set a -> Set a
`S.difference` Set Attr
y

-- | A type alias for namespace control.
type PatElem lore = PatElemT (LetDec lore)

-- | A pattern is conceptually just a list of names and their types.
data PatternT dec = Pattern
  { -- | existential context (sizes and memory blocks)
    forall dec. PatternT dec -> [PatElemT dec]
patternContextElements :: [PatElemT dec],
    -- | "real" values
    forall dec. PatternT dec -> [PatElemT dec]
patternValueElements :: [PatElemT dec]
  }
  deriving (Eq (PatternT dec)
Eq (PatternT dec)
-> (PatternT dec -> PatternT dec -> Ordering)
-> (PatternT dec -> PatternT dec -> Bool)
-> (PatternT dec -> PatternT dec -> Bool)
-> (PatternT dec -> PatternT dec -> Bool)
-> (PatternT dec -> PatternT dec -> Bool)
-> (PatternT dec -> PatternT dec -> PatternT dec)
-> (PatternT dec -> PatternT dec -> PatternT dec)
-> Ord (PatternT dec)
PatternT dec -> PatternT dec -> Bool
PatternT dec -> PatternT dec -> Ordering
PatternT dec -> PatternT dec -> PatternT 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 (PatternT dec)
forall dec. Ord dec => PatternT dec -> PatternT dec -> Bool
forall dec. Ord dec => PatternT dec -> PatternT dec -> Ordering
forall dec. Ord dec => PatternT dec -> PatternT dec -> PatternT dec
min :: PatternT dec -> PatternT dec -> PatternT dec
$cmin :: forall dec. Ord dec => PatternT dec -> PatternT dec -> PatternT dec
max :: PatternT dec -> PatternT dec -> PatternT dec
$cmax :: forall dec. Ord dec => PatternT dec -> PatternT dec -> PatternT dec
>= :: PatternT dec -> PatternT dec -> Bool
$c>= :: forall dec. Ord dec => PatternT dec -> PatternT dec -> Bool
> :: PatternT dec -> PatternT dec -> Bool
$c> :: forall dec. Ord dec => PatternT dec -> PatternT dec -> Bool
<= :: PatternT dec -> PatternT dec -> Bool
$c<= :: forall dec. Ord dec => PatternT dec -> PatternT dec -> Bool
< :: PatternT dec -> PatternT dec -> Bool
$c< :: forall dec. Ord dec => PatternT dec -> PatternT dec -> Bool
compare :: PatternT dec -> PatternT dec -> Ordering
$ccompare :: forall dec. Ord dec => PatternT dec -> PatternT dec -> Ordering
Ord, Int -> PatternT dec -> ShowS
[PatternT dec] -> ShowS
PatternT dec -> String
(Int -> PatternT dec -> ShowS)
-> (PatternT dec -> String)
-> ([PatternT dec] -> ShowS)
-> Show (PatternT dec)
forall dec. Show dec => Int -> PatternT dec -> ShowS
forall dec. Show dec => [PatternT dec] -> ShowS
forall dec. Show dec => PatternT dec -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PatternT dec] -> ShowS
$cshowList :: forall dec. Show dec => [PatternT dec] -> ShowS
show :: PatternT dec -> String
$cshow :: forall dec. Show dec => PatternT dec -> String
showsPrec :: Int -> PatternT dec -> ShowS
$cshowsPrec :: forall dec. Show dec => Int -> PatternT dec -> ShowS
Show, PatternT dec -> PatternT dec -> Bool
(PatternT dec -> PatternT dec -> Bool)
-> (PatternT dec -> PatternT dec -> Bool) -> Eq (PatternT dec)
forall dec. Eq dec => PatternT dec -> PatternT dec -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PatternT dec -> PatternT dec -> Bool
$c/= :: forall dec. Eq dec => PatternT dec -> PatternT dec -> Bool
== :: PatternT dec -> PatternT dec -> Bool
$c== :: forall dec. Eq dec => PatternT dec -> PatternT dec -> Bool
Eq)

instance Semigroup (PatternT dec) where
  Pattern [PatElemT dec]
cs1 [PatElemT dec]
vs1 <> :: PatternT dec -> PatternT dec -> PatternT dec
<> Pattern [PatElemT dec]
cs2 [PatElemT dec]
vs2 = [PatElemT dec] -> [PatElemT dec] -> PatternT dec
forall dec. [PatElemT dec] -> [PatElemT dec] -> PatternT dec
Pattern ([PatElemT dec]
cs1 [PatElemT dec] -> [PatElemT dec] -> [PatElemT dec]
forall a. [a] -> [a] -> [a]
++ [PatElemT dec]
cs2) ([PatElemT dec]
vs1 [PatElemT dec] -> [PatElemT dec] -> [PatElemT dec]
forall a. [a] -> [a] -> [a]
++ [PatElemT dec]
vs2)

instance Monoid (PatternT dec) where
  mempty :: PatternT dec
mempty = [PatElemT dec] -> [PatElemT dec] -> PatternT dec
forall dec. [PatElemT dec] -> [PatElemT dec] -> PatternT dec
Pattern [] []

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

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

instance Traversable PatternT where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PatternT a -> f (PatternT b)
traverse a -> f b
f (Pattern [PatElemT a]
ctx [PatElemT a]
vals) =
    [PatElemT b] -> [PatElemT b] -> PatternT b
forall dec. [PatElemT dec] -> [PatElemT dec] -> PatternT dec
Pattern ([PatElemT b] -> [PatElemT b] -> PatternT b)
-> f [PatElemT b] -> f ([PatElemT b] -> PatternT b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (PatElemT a -> f (PatElemT b)) -> [PatElemT a] -> f [PatElemT b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f b) -> PatElemT a -> f (PatElemT b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f) [PatElemT a]
ctx f ([PatElemT b] -> PatternT b) -> f [PatElemT b] -> f (PatternT b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (PatElemT a -> f (PatElemT b)) -> [PatElemT a] -> f [PatElemT b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f b) -> PatElemT a -> f (PatElemT b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f) [PatElemT a]
vals

-- | A type alias for namespace control.
type Pattern lore = PatternT (LetDec lore)

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

instance Semigroup dec => Semigroup (StmAux dec) where
  StmAux Certificates
cs1 Attrs
attrs1 dec
dec1 <> :: StmAux dec -> StmAux dec -> StmAux dec
<> StmAux Certificates
cs2 Attrs
attrs2 dec
dec2 =
    Certificates -> Attrs -> dec -> StmAux dec
forall dec. Certificates -> Attrs -> dec -> StmAux dec
StmAux (Certificates
cs1 Certificates -> Certificates -> Certificates
forall a. Semigroup a => a -> a -> a
<> Certificates
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 lore = Let
  { -- | Pattern.
    forall lore. Stm lore -> Pattern lore
stmPattern :: Pattern lore,
    -- | Auxiliary information statement.
    forall lore. Stm lore -> StmAux (ExpDec lore)
stmAux :: StmAux (ExpDec lore),
    -- | Expression.
    forall lore. Stm lore -> Exp lore
stmExp :: Exp lore
  }

deriving instance Decorations lore => Ord (Stm lore)

deriving instance Decorations lore => Show (Stm lore)

deriving instance Decorations lore => Eq (Stm lore)

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

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

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

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

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

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

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

deriving instance Decorations lore => Ord (BodyT lore)

deriving instance Decorations lore => Show (BodyT lore)

deriving instance Decorations lore => Eq (BodyT lore)

-- | Type alias for namespace reasons.
type Body = BodyT

-- | The new dimension in a 'Reshape'-like operation.  This allows us to
-- disambiguate "real" reshapes, that change the actual shape of the
-- array, from type coercions that are just present to make the types
-- work out.  The two constructors are considered equal for purposes of 'Eq'.
data DimChange d
  = -- | The new dimension is guaranteed to be numerically
    -- equal to the old one.
    DimCoercion d
  | -- | The new dimension is not necessarily numerically
    -- equal to the old one.
    DimNew d
  deriving (Eq (DimChange d)
Eq (DimChange d)
-> (DimChange d -> DimChange d -> Ordering)
-> (DimChange d -> DimChange d -> Bool)
-> (DimChange d -> DimChange d -> Bool)
-> (DimChange d -> DimChange d -> Bool)
-> (DimChange d -> DimChange d -> Bool)
-> (DimChange d -> DimChange d -> DimChange d)
-> (DimChange d -> DimChange d -> DimChange d)
-> Ord (DimChange d)
DimChange d -> DimChange d -> Bool
DimChange d -> DimChange d -> Ordering
DimChange d -> DimChange d -> DimChange d
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 {d}. Ord d => Eq (DimChange d)
forall d. Ord d => DimChange d -> DimChange d -> Bool
forall d. Ord d => DimChange d -> DimChange d -> Ordering
forall d. Ord d => DimChange d -> DimChange d -> DimChange d
min :: DimChange d -> DimChange d -> DimChange d
$cmin :: forall d. Ord d => DimChange d -> DimChange d -> DimChange d
max :: DimChange d -> DimChange d -> DimChange d
$cmax :: forall d. Ord d => DimChange d -> DimChange d -> DimChange d
>= :: DimChange d -> DimChange d -> Bool
$c>= :: forall d. Ord d => DimChange d -> DimChange d -> Bool
> :: DimChange d -> DimChange d -> Bool
$c> :: forall d. Ord d => DimChange d -> DimChange d -> Bool
<= :: DimChange d -> DimChange d -> Bool
$c<= :: forall d. Ord d => DimChange d -> DimChange d -> Bool
< :: DimChange d -> DimChange d -> Bool
$c< :: forall d. Ord d => DimChange d -> DimChange d -> Bool
compare :: DimChange d -> DimChange d -> Ordering
$ccompare :: forall d. Ord d => DimChange d -> DimChange d -> Ordering
Ord, Int -> DimChange d -> ShowS
[DimChange d] -> ShowS
DimChange d -> String
(Int -> DimChange d -> ShowS)
-> (DimChange d -> String)
-> ([DimChange d] -> ShowS)
-> Show (DimChange d)
forall d. Show d => Int -> DimChange d -> ShowS
forall d. Show d => [DimChange d] -> ShowS
forall d. Show d => DimChange d -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DimChange d] -> ShowS
$cshowList :: forall d. Show d => [DimChange d] -> ShowS
show :: DimChange d -> String
$cshow :: forall d. Show d => DimChange d -> String
showsPrec :: Int -> DimChange d -> ShowS
$cshowsPrec :: forall d. Show d => Int -> DimChange d -> ShowS
Show)

instance Eq d => Eq (DimChange d) where
  DimCoercion d
x == :: DimChange d -> DimChange d -> Bool
== DimNew d
y = d
x d -> d -> Bool
forall a. Eq a => a -> a -> Bool
== d
y
  DimCoercion d
x == DimCoercion d
y = d
x d -> d -> Bool
forall a. Eq a => a -> a -> Bool
== d
y
  DimNew d
x == DimCoercion d
y = d
x d -> d -> Bool
forall a. Eq a => a -> a -> Bool
== d
y
  DimNew d
x == DimNew d
y = d
x d -> d -> Bool
forall a. Eq a => a -> a -> Bool
== d
y

instance Functor DimChange where
  fmap :: forall a b. (a -> b) -> DimChange a -> DimChange b
fmap a -> b
f (DimCoercion a
d) = b -> DimChange b
forall d. d -> DimChange d
DimCoercion (b -> DimChange b) -> b -> DimChange b
forall a b. (a -> b) -> a -> b
$ a -> b
f a
d
  fmap a -> b
f (DimNew a
d) = b -> DimChange b
forall d. d -> DimChange d
DimNew (b -> DimChange b) -> b -> DimChange b
forall a b. (a -> b) -> a -> b
$ a -> b
f a
d

instance Foldable DimChange where
  foldMap :: forall m a. Monoid m => (a -> m) -> DimChange a -> m
foldMap a -> m
f (DimCoercion a
d) = a -> m
f a
d
  foldMap a -> m
f (DimNew a
d) = a -> m
f a
d

instance Traversable DimChange where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> DimChange a -> f (DimChange b)
traverse a -> f b
f (DimCoercion a
d) = b -> DimChange b
forall d. d -> DimChange d
DimCoercion (b -> DimChange b) -> f b -> f (DimChange b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
d
  traverse a -> f b
f (DimNew a
d) = b -> DimChange b
forall d. d -> DimChange d
DimNew (b -> DimChange b) -> f b -> f (DimChange b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
d

-- | A list of 'DimChange's, indicating the new dimensions of an array.
type ShapeChange d = [DimChange d]

-- | 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 is
    -- just a hack to avoid optimisation (so, to work around compiler
    -- limitations).
    Opaque 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])
  | -- Primitive array operations

    -- | 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.
    Update VName (Slice SubExp) SubExp
  | -- | @concat@0([1],[2, 3, 4]) = [1, 2, 3, 4]@.
    Concat Int VName [VName] SubExp
  | -- | Copy the given array.  The result will not alias anything.
    Copy VName
  | -- | 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]]@
    Replicate Shape SubExp
  | -- | Create array of given type and shape, with undefined elements.
    Scratch PrimType [SubExp]
  | -- Array index space transformation.

    -- | 1st arg is the new shape, 2nd arg is the input array *)
    Reshape (ShapeChange SubExp) 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
  | -- | Rotate the dimensions of the input array.  The list of
    -- subexpressions specify how much each dimension is rotated.  The
    -- length of this list must be equal to the rank of the array.
    Rotate [SubExp] 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
/= :: BasicOp -> BasicOp -> Bool
$c/= :: BasicOp -> BasicOp -> Bool
== :: BasicOp -> BasicOp -> Bool
$c== :: 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
min :: BasicOp -> BasicOp -> BasicOp
$cmin :: BasicOp -> BasicOp -> BasicOp
max :: BasicOp -> BasicOp -> BasicOp
$cmax :: BasicOp -> BasicOp -> BasicOp
>= :: BasicOp -> BasicOp -> Bool
$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
compare :: BasicOp -> BasicOp -> Ordering
$ccompare :: BasicOp -> BasicOp -> Ordering
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
showList :: [BasicOp] -> ShowS
$cshowList :: [BasicOp] -> ShowS
show :: BasicOp -> String
$cshow :: BasicOp -> String
showsPrec :: Int -> BasicOp -> ShowS
$cshowsPrec :: Int -> BasicOp -> ShowS
Show)

-- | The root Futhark expression type.  The v'Op' constructor contains
-- a lore-specific operation.  Do-loops, branches and function calls
-- are special.  Everything else is a simple t'BasicOp'.
data ExpT lore
  = -- | A simple (non-recursive) operation.
    BasicOp BasicOp
  | Apply Name [(SubExp, Diet)] [RetType lore] (Safety, SrcLoc, [SrcLoc])
  | If SubExp (BodyT lore) (BodyT lore) (IfDec (BranchType lore))
  | -- | @loop {a} = {v} (for i < n|while b) do b@.  The merge
    -- parameters are divided into context and value part.
    DoLoop [(FParam lore, SubExp)] [(FParam lore, SubExp)] (LoopForm lore) (BodyT lore)
  | -- | 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 'Shape' is the
    -- write index space.  The corresponding arrays must all have this
    -- shape outermost.  This construct is not part of 'BasicOp'
    -- because we need the @lore@ parameter.
    WithAcc [(Shape, [VName], Maybe (Lambda lore, [SubExp]))] (Lambda lore)
  | Op (Op lore)

deriving instance Decorations lore => Eq (ExpT lore)

deriving instance Decorations lore => Show (ExpT lore)

deriving instance Decorations lore => Ord (ExpT lore)

-- | For-loop or while-loop?
data LoopForm lore
  = ForLoop VName IntType SubExp [(LParam lore, VName)]
  | WhileLoop VName

deriving instance Decorations lore => Eq (LoopForm lore)

deriving instance Decorations lore => Show (LoopForm lore)

deriving instance Decorations lore => Ord (LoopForm lore)

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

-- | What kind of branch is this?  This has no semantic meaning, but
-- provides hints to simplifications.
data IfSort
  = -- | An ordinary branch.
    IfNormal
  | -- | 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.
    IfFallback
  | -- | 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).
    IfEquiv
  deriving (IfSort -> IfSort -> Bool
(IfSort -> IfSort -> Bool)
-> (IfSort -> IfSort -> Bool) -> Eq IfSort
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: IfSort -> IfSort -> Bool
$c/= :: IfSort -> IfSort -> Bool
== :: IfSort -> IfSort -> Bool
$c== :: IfSort -> IfSort -> Bool
Eq, Int -> IfSort -> ShowS
[IfSort] -> ShowS
IfSort -> String
(Int -> IfSort -> ShowS)
-> (IfSort -> String) -> ([IfSort] -> ShowS) -> Show IfSort
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [IfSort] -> ShowS
$cshowList :: [IfSort] -> ShowS
show :: IfSort -> String
$cshow :: IfSort -> String
showsPrec :: Int -> IfSort -> ShowS
$cshowsPrec :: Int -> IfSort -> ShowS
Show, Eq IfSort
Eq IfSort
-> (IfSort -> IfSort -> Ordering)
-> (IfSort -> IfSort -> Bool)
-> (IfSort -> IfSort -> Bool)
-> (IfSort -> IfSort -> Bool)
-> (IfSort -> IfSort -> Bool)
-> (IfSort -> IfSort -> IfSort)
-> (IfSort -> IfSort -> IfSort)
-> Ord IfSort
IfSort -> IfSort -> Bool
IfSort -> IfSort -> Ordering
IfSort -> IfSort -> IfSort
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
min :: IfSort -> IfSort -> IfSort
$cmin :: IfSort -> IfSort -> IfSort
max :: IfSort -> IfSort -> IfSort
$cmax :: IfSort -> IfSort -> IfSort
>= :: IfSort -> IfSort -> Bool
$c>= :: IfSort -> IfSort -> Bool
> :: IfSort -> IfSort -> Bool
$c> :: IfSort -> IfSort -> Bool
<= :: IfSort -> IfSort -> Bool
$c<= :: IfSort -> IfSort -> Bool
< :: IfSort -> IfSort -> Bool
$c< :: IfSort -> IfSort -> Bool
compare :: IfSort -> IfSort -> Ordering
$ccompare :: IfSort -> IfSort -> Ordering
Ord)

-- | A type alias for namespace control.
type Exp = ExpT

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

deriving instance Decorations lore => Eq (LambdaT lore)

deriving instance Decorations lore => Show (LambdaT lore)

deriving instance Decorations lore => Ord (LambdaT lore)

-- | Type alias for namespacing reasons.
type Lambda = LambdaT

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

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

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

deriving instance Decorations lore => Eq (FunDef lore)

deriving instance Decorations lore => Show (FunDef lore)

deriving instance Decorations lore => Ord (FunDef lore)

-- | Information about the parameters and return value of an entry
-- point.  The first element is for parameters, the second for return
-- value.
type EntryPoint = ([EntryPointType], [EntryPointType])

-- | Every entry point argument and return value has an annotation
-- indicating how it maps to the original source program type.
data EntryPointType
  = -- | Is an unsigned integer or array of unsigned
    -- integers.
    TypeUnsigned
  | -- | A black box type comprising this many core
    -- values.  The string is a human-readable
    -- description with no other semantics.
    TypeOpaque String Int
  | -- | Maps directly.
    TypeDirect
  deriving (EntryPointType -> EntryPointType -> Bool
(EntryPointType -> EntryPointType -> Bool)
-> (EntryPointType -> EntryPointType -> Bool) -> Eq EntryPointType
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: EntryPointType -> EntryPointType -> Bool
$c/= :: EntryPointType -> EntryPointType -> Bool
== :: EntryPointType -> EntryPointType -> Bool
$c== :: EntryPointType -> EntryPointType -> Bool
Eq, Int -> EntryPointType -> ShowS
[EntryPointType] -> ShowS
EntryPointType -> String
(Int -> EntryPointType -> ShowS)
-> (EntryPointType -> String)
-> ([EntryPointType] -> ShowS)
-> Show EntryPointType
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [EntryPointType] -> ShowS
$cshowList :: [EntryPointType] -> ShowS
show :: EntryPointType -> String
$cshow :: EntryPointType -> String
showsPrec :: Int -> EntryPointType -> ShowS
$cshowsPrec :: Int -> EntryPointType -> ShowS
Show, Eq EntryPointType
Eq EntryPointType
-> (EntryPointType -> EntryPointType -> Ordering)
-> (EntryPointType -> EntryPointType -> Bool)
-> (EntryPointType -> EntryPointType -> Bool)
-> (EntryPointType -> EntryPointType -> Bool)
-> (EntryPointType -> EntryPointType -> Bool)
-> (EntryPointType -> EntryPointType -> EntryPointType)
-> (EntryPointType -> EntryPointType -> EntryPointType)
-> Ord EntryPointType
EntryPointType -> EntryPointType -> Bool
EntryPointType -> EntryPointType -> Ordering
EntryPointType -> EntryPointType -> EntryPointType
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
min :: EntryPointType -> EntryPointType -> EntryPointType
$cmin :: EntryPointType -> EntryPointType -> EntryPointType
max :: EntryPointType -> EntryPointType -> EntryPointType
$cmax :: EntryPointType -> EntryPointType -> EntryPointType
>= :: EntryPointType -> EntryPointType -> Bool
$c>= :: EntryPointType -> EntryPointType -> Bool
> :: EntryPointType -> EntryPointType -> Bool
$c> :: EntryPointType -> EntryPointType -> Bool
<= :: EntryPointType -> EntryPointType -> Bool
$c<= :: EntryPointType -> EntryPointType -> Bool
< :: EntryPointType -> EntryPointType -> Bool
$c< :: EntryPointType -> EntryPointType -> Bool
compare :: EntryPointType -> EntryPointType -> Ordering
$ccompare :: EntryPointType -> EntryPointType -> Ordering
Ord)

-- | An entire Futhark program.
data Prog lore = Prog
  { -- | Top-level constants that are computed at program startup, and
    -- which are in scope inside all functions.
    forall lore. Prog lore -> Stms lore
progConsts :: Stms lore,
    -- | The functions comprising the program.  All funtions are also
    -- available in scope in the definitions of the constants, so be
    -- careful not to introduce circular dependencies (not currently
    -- checked).
    forall lore. Prog lore -> [FunDef lore]
progFuns :: [FunDef lore]
  }
  deriving (Prog lore -> Prog lore -> Bool
(Prog lore -> Prog lore -> Bool)
-> (Prog lore -> Prog lore -> Bool) -> Eq (Prog lore)
forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Prog lore -> Prog lore -> Bool
$c/= :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
== :: Prog lore -> Prog lore -> Bool
$c== :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
Eq, Eq (Prog lore)
Eq (Prog lore)
-> (Prog lore -> Prog lore -> Ordering)
-> (Prog lore -> Prog lore -> Bool)
-> (Prog lore -> Prog lore -> Bool)
-> (Prog lore -> Prog lore -> Bool)
-> (Prog lore -> Prog lore -> Bool)
-> (Prog lore -> Prog lore -> Prog lore)
-> (Prog lore -> Prog lore -> Prog lore)
-> Ord (Prog lore)
Prog lore -> Prog lore -> Bool
Prog lore -> Prog lore -> Ordering
Prog lore -> Prog lore -> Prog lore
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 lore. Decorations lore => Eq (Prog lore)
forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
forall lore. Decorations lore => Prog lore -> Prog lore -> Ordering
forall lore.
Decorations lore =>
Prog lore -> Prog lore -> Prog lore
min :: Prog lore -> Prog lore -> Prog lore
$cmin :: forall lore.
Decorations lore =>
Prog lore -> Prog lore -> Prog lore
max :: Prog lore -> Prog lore -> Prog lore
$cmax :: forall lore.
Decorations lore =>
Prog lore -> Prog lore -> Prog lore
>= :: Prog lore -> Prog lore -> Bool
$c>= :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
> :: Prog lore -> Prog lore -> Bool
$c> :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
<= :: Prog lore -> Prog lore -> Bool
$c<= :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
< :: Prog lore -> Prog lore -> Bool
$c< :: forall lore. Decorations lore => Prog lore -> Prog lore -> Bool
compare :: Prog lore -> Prog lore -> Ordering
$ccompare :: forall lore. Decorations lore => Prog lore -> Prog lore -> Ordering
Ord, Int -> Prog lore -> ShowS
[Prog lore] -> ShowS
Prog lore -> String
(Int -> Prog lore -> ShowS)
-> (Prog lore -> String)
-> ([Prog lore] -> ShowS)
-> Show (Prog lore)
forall lore. Decorations lore => Int -> Prog lore -> ShowS
forall lore. Decorations lore => [Prog lore] -> ShowS
forall lore. Decorations lore => Prog lore -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Prog lore] -> ShowS
$cshowList :: forall lore. Decorations lore => [Prog lore] -> ShowS
show :: Prog lore -> String
$cshow :: forall lore. Decorations lore => Prog lore -> String
showsPrec :: Int -> Prog lore -> ShowS
$cshowsPrec :: forall lore. Decorations lore => Int -> Prog lore -> ShowS
Show)