{-# LANGUAGE TypeFamilies, FlexibleContexts, FlexibleInstances, StandaloneDeriving #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE Strict #-}
{-# LANGUAGE Trustworthy #-}
-- | = 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 qualified Data.Set as S
import Data.Foldable
import qualified Data.Sequence as Seq
import Data.String
import Data.Traversable (fmapDefault, foldMapDefault)

import Language.Futhark.Core
import Futhark.IR.Decorations
import Futhark.IR.Syntax.Core

-- | 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
$cp1Ord :: Eq Attr
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 b c a. (b -> c) -> (a -> b) -> 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
$cp1Ord :: Eq Attrs
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
$cp1Monoid :: Semigroup Attrs
Monoid, b -> Attrs -> Attrs
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 :: 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 b c a. (b -> c) -> (a -> b) -> 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 { PatternT dec -> [PatElemT dec]
patternContextElements :: [PatElemT dec]
            -- ^ existential context (sizes and memory blocks)
          , PatternT dec -> [PatElemT dec]
patternValueElements   :: [PatElemT dec]
            -- ^ "real" values
          }
  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
$cp1Ord :: forall dec. Ord dec => Eq (PatternT dec)
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 :: (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 :: (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 :: (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 { StmAux dec -> Certificates
stmAuxCerts :: !Certificates
                         , StmAux dec -> Attrs
stmAuxAttrs :: Attrs
                         , 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
$cp1Ord :: forall dec. Ord dec => Eq (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
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
cs1Certificates -> Certificates -> Certificates
forall a. Semigroup a => a -> a -> a
<>Certificates
cs2) (Attrs
attrs1Attrs -> Attrs -> Attrs
forall a. Semigroup a => a -> a -> a
<>Attrs
attrs2) (dec
dec1dec -> dec -> dec
forall a. Semigroup a => a -> a -> a
<>dec
dec2)

-- | A local variable binding.
data Stm lore = Let { Stm lore -> Pattern lore
stmPattern :: Pattern lore
                      -- ^ Pattern.
                    , Stm lore -> StmAux (ExpDec lore)
stmAux :: StmAux (ExpDec lore)
                      -- ^ Auxiliary information statement.
                    , Stm lore -> Exp lore
stmExp :: Exp lore
                      -- ^ Expression.
                    }

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 :: Stm lore -> Stms lore
oneStm = Stm lore -> Stms lore
forall a. a -> Seq a
Seq.singleton

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

-- | Convert a statement sequence to a statement list.
stmsToList :: Stms lore -> [Stm lore]
stmsToList :: Stms lore -> [Stm lore]
stmsToList = Stms 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 :: 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 { BodyT lore -> BodyDec lore
bodyDec :: BodyDec lore
                       , BodyT lore -> Stms lore
bodyStms :: Stms 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 = DimCoercion d
                   -- ^ The new dimension is guaranteed to be numerically
                   -- equal to the old one.
                 | DimNew d
                   -- ^ The new dimension is not necessarily numerically
                   -- equal to the old one.
                 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
$cp1Ord :: forall d. Ord d => Eq (DimChange d)
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 :: (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 :: (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 :: (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
  = SubExp SubExp
    -- ^ A variable or constant.

  | Opaque 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).

  | ArrayLit  [SubExp] Type
    -- ^ Array literals, e.g., @[ [1+x, 3], [2, 1+4] ]@.
    -- Second arg is the element type of the rows of the array.
    -- Scalar operations

  | UnOp UnOp SubExp
    -- ^ Unary operation.

  | BinOp BinOp SubExp SubExp
    -- ^ Binary operation.

  | CmpOp CmpOp SubExp SubExp
    -- ^ Comparison - result type is always boolean.

  | ConvOp ConvOp SubExp
    -- ^ Conversion "casting".

  | Assert SubExp (ErrorMsg SubExp) (SrcLoc, [SrcLoc])
  -- ^ Turn a boolean into a certificate, halting the program with the
  -- given error message if the boolean is false.

  -- Primitive array operations

  | Index VName (Slice SubExp)
  -- ^ The certificates for bounds-checking are part of the 'Stm'.

  | Update VName (Slice SubExp) SubExp
  -- ^ An in-place update of the given array at the given position.
  -- Consumes the array.

  | Concat Int VName [VName] SubExp
  -- ^ @concat@0([1],[2, 3, 4]) = [1, 2, 3, 4]@.

  | Copy VName
  -- ^ Copy the given array.  The result will not alias anything.

  | Manifest [Int] VName
  -- ^ Manifest an array with dimensions represented in the given
  -- order.  The result will not alias anything.

  -- Array construction.
  | Iota SubExp SubExp SubExp IntType
  -- ^ @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.

  | Replicate Shape SubExp
  -- ^ @replicate([3][2],1) = [[1,1], [1,1], [1,1]]@

  | Scratch PrimType [SubExp]
  -- ^ Create array of given type and shape, with undefined elements.

  -- Array index space transformation.
  | Reshape (ShapeChange SubExp) VName
   -- ^ 1st arg is the new shape, 2nd arg is the input array *)

  | Rearrange [Int] 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.

  | Rotate [SubExp] 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.
  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
$cp1Ord :: Eq 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
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
  = BasicOp BasicOp
    -- ^ A simple (non-recursive) operation.

  | Apply  Name [(SubExp, Diet)] [RetType lore] (Safety, SrcLoc, [SrcLoc])

  | If     SubExp (BodyT lore) (BodyT lore) (IfDec (BranchType lore))

  | DoLoop [(FParam lore, SubExp)] [(FParam lore, SubExp)] (LoopForm lore) (BodyT lore)
    -- ^ @loop {a} = {v} (for i < n|while b) do b@.  The merge
    -- parameters are divided into context and value part.

  | 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 { IfDec rt -> [rt]
ifReturns :: [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
$cp1Ord :: forall rt. Ord rt => Eq (IfDec rt)
Ord)

-- | What kind of branch is this?  This has no semantic meaning, but
-- provides hints to simplifications.
data IfSort = IfNormal
              -- ^ An ordinary branch.
            | IfFallback
              -- ^ 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.
            | IfEquiv
              -- ^ 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).
            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
$cp1Ord :: Eq IfSort
Ord)

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

-- | Anonymous function for use in a SOAC.
data LambdaT lore = Lambda { LambdaT lore -> [LParam lore]
lambdaParams     :: [LParam lore]
                           , LambdaT lore -> BodyT lore
lambdaBody       :: BodyT 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 { FunDef lore -> Maybe EntryPoint
funDefEntryPoint :: Maybe EntryPoint
                            -- ^ Contains a value if this function is
                            -- an entry point.
                          , FunDef lore -> Attrs
funDefAttrs :: Attrs
                          , FunDef lore -> Name
funDefName :: Name
                          , FunDef lore -> [RetType lore]
funDefRetType :: [RetType lore]
                          , FunDef lore -> [FParam lore]
funDefParams :: [FParam 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 = TypeUnsigned
                      -- ^ Is an unsigned integer or array of unsigned
                      -- integers.
                    | TypeOpaque String Int
                      -- ^ A black box type comprising this many core
                      -- values.  The string is a human-readable
                      -- description with no other semantics.
                    | TypeDirect
                      -- ^ Maps directly.
                    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
$cp1Ord :: Eq EntryPointType
Ord)

-- | An entire Futhark program.
data Prog lore = Prog
  { Prog lore -> Stms lore
progConsts :: Stms lore
    -- ^ Top-level constants that are computed at program startup, and
    -- which are in scope inside all functions.

  , Prog lore -> [FunDef lore]
progFuns :: [FunDef 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).
  } 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
$cp1Ord :: forall lore. Decorations lore => Eq (Prog lore)
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)