| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Futhark.IR.Syntax
Description
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
PrimType which can be combined in arrays (ignore Mem and
Acc for now). Types are represented as TypeBase, which is
parameterised by the shape of the array and whether we keep
uniqueness information. The Type alias, which is the most
commonly used, uses Shape and NoUniqueness.
This means that the records, tuples, and sum types of the source language are represented merely as collections of primitives and arrays. This is implemented in Futhark.Internalise, but the specifics are not important for writing passes on the core language. What is important is that many constructs that conceptually return tuples instead return multiple values. This is not merely syntactic sugar for a tuple: each of those values are eventually bound to distinct variables. The prettyprinter for the IR will typically print such collections of values or types in curly braces.
The system of primitive types is interesting in itself. See Language.Futhark.Primitive.
Overall AST design
Internally, the Futhark compiler core intermediate representation
resembles a traditional compiler for an imperative language more
than it resembles, say, a Haskell or ML compiler. All functions
are monomorphic (except for sizes), first-order, and defined at the
top level. Notably, the IR does not use continuation-passing
style (CPS) at any time. Instead it uses Administrative Normal
Form (ANF), where all subexpressions SubExp are either
constants PrimValue or variables VName. Variables are
represented as a human-readable 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 Names,
though.
The body of a function (FunDef) is a Body, which consists of
a sequence of statements (Stms) and a Result. Execution of a
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 Pat alongside an
expression Exp. A pattern is a sequence of name/type pairs.
For example, the source language expression let z = x + y - 1 in
z would in the core language be represented (in prettyprinted
form) as something like:
let {a_12} = x_10 + y_11
let {b_13} = a_12 - 1
in {b_13}
Representations
Most AST types (Stm, Exp, Prog, etc) are parameterised by a
type parameter rep. The representation specifies how to fill out
various polymorphic parts of the AST. For example, Exp has a
constructor Op whose payload depends on rep, via the use of a
type family called Op (a kind of type-level function) which is
applied to the rep. The SOACS representation
(Futhark.IR.SOACS) thus uses a rep called SOACS, and defines
that Op SOACS is a SOAC, while the Kernels representation
(Futhark.IR.Kernels) defines Op Kernels as some kind of kernel
construct. Similarly, various other decorations (e.g. what
information we store in a PatElem) are also type families.
The full list of possible decorations is defined as part of the
type class RepTypes (although other type families are also
used elsewhere in the compiler on an ad hoc basis).
Essentially, the rep type parameter functions as a kind of
proxy, saving us from having to parameterise the AST type with all
the different forms of decorations that we desire (it would easily
become a type with a dozen type parameters).
Some AST elements (such as Pat) do not take a rep type
parameter, but instead immediately the single type of decoration
that they contain. We only use the more complicated machinery when
needed.
Defining a new representation (or rep) thus requires you to define an empty datatype and implement a handful of type class instances for it. See the source of Futhark.IR.Seq for what is likely the simplest example.
Synopsis
- module Language.Futhark.Core
- prettyString :: Pretty a => a -> String
- prettyText :: Pretty a => a -> Text
- class Pretty a
- module Futhark.IR.Rep
- module Futhark.IR.Syntax.Core
- data Uniqueness
- data NoUniqueness = NoUniqueness
- newtype Rank = Rank Int
- class (Monoid a, Eq a, Ord a) => ArrayShape a where
- shapeRank :: a -> Int
- subShapeOf :: a -> a -> Bool
- data Space
- data TypeBase shape u
- data Diet
- data Ident = Ident {}
- data SubExp
- data PatElem dec = PatElem {
- patElemName :: VName
- patElemDec :: dec
- newtype Pat dec = Pat {}
- data StmAux dec = StmAux {
- stmAuxCerts :: !Certs
- stmAuxAttrs :: Attrs
- stmAuxDec :: dec
- data Stm rep = Let {}
- type Stms rep = Seq (Stm rep)
- data SubExpRes = SubExpRes {}
- type Result = [SubExpRes]
- data Body rep = Body {}
- data BasicOp
- = SubExp SubExp
- | Opaque OpaqueOp SubExp
- | ArrayLit [SubExp] Type
- | UnOp UnOp SubExp
- | BinOp BinOp SubExp SubExp
- | CmpOp CmpOp SubExp SubExp
- | ConvOp ConvOp SubExp
- | Assert SubExp (ErrorMsg SubExp) (SrcLoc, [SrcLoc])
- | Index VName (Slice SubExp)
- | Update Safety VName (Slice SubExp) SubExp
- | FlatIndex VName (FlatSlice SubExp)
- | FlatUpdate VName (FlatSlice SubExp) VName
- | Concat Int (NonEmpty VName) SubExp
- | Copy VName
- | Manifest [Int] VName
- | Iota SubExp SubExp SubExp IntType
- | Replicate Shape SubExp
- | Scratch PrimType [SubExp]
- | Reshape ReshapeKind Shape VName
- | Rearrange [Int] VName
- | Rotate [SubExp] VName
- | UpdateAcc VName [SubExp] [SubExp]
- data UnOp
- data BinOp
- = Add IntType Overflow
- | FAdd FloatType
- | Sub IntType Overflow
- | FSub FloatType
- | Mul IntType Overflow
- | FMul FloatType
- | UDiv IntType Safety
- | UDivUp IntType Safety
- | SDiv IntType Safety
- | SDivUp IntType Safety
- | FDiv FloatType
- | FMod FloatType
- | UMod IntType Safety
- | SMod IntType Safety
- | SQuot IntType Safety
- | SRem IntType Safety
- | SMin IntType
- | UMin IntType
- | FMin FloatType
- | SMax IntType
- | UMax IntType
- | FMax FloatType
- | Shl IntType
- | LShr IntType
- | AShr IntType
- | And IntType
- | Or IntType
- | Xor IntType
- | Pow IntType
- | FPow FloatType
- | LogAnd
- | LogOr
- data CmpOp
- data ConvOp
- data OpaqueOp
- data ReshapeKind
- type WithAccInput rep = (Shape, [VName], Maybe (Lambda rep, [SubExp]))
- data Exp rep
- data Case body = Case {}
- data LoopForm rep
- data MatchDec rt = MatchDec {
- matchReturns :: [rt]
- matchSort :: MatchSort
- data MatchSort
- data Safety
- data Lambda rep = Lambda {
- lambdaParams :: [LParam rep]
- lambdaBody :: Body rep
- lambdaReturnType :: [Type]
- data Param dec = Param {
- paramAttrs :: Attrs
- paramName :: VName
- paramDec :: dec
- type FParam rep = Param (FParamInfo rep)
- type LParam rep = Param (LParamInfo rep)
- data FunDef rep = FunDef {
- funDefEntryPoint :: Maybe EntryPoint
- funDefAttrs :: Attrs
- funDefName :: Name
- funDefRetType :: [RetType rep]
- funDefParams :: [FParam rep]
- funDefBody :: Body rep
- data EntryParam = EntryParam {}
- data EntryResult = EntryResult {}
- type EntryPoint = (Name, [EntryParam], [EntryResult])
- data Prog rep = Prog {
- progTypes :: OpaqueTypes
- progConsts :: Stms rep
- progFuns :: [FunDef rep]
- oneStm :: Stm rep -> Stms rep
- stmsFromList :: [Stm rep] -> Stms rep
- stmsToList :: Stms rep -> [Stm rep]
- stmsHead :: Stms rep -> Maybe (Stm rep, Stms rep)
- stmsLast :: Stms lore -> Maybe (Stms lore, Stm lore)
- subExpRes :: SubExp -> SubExpRes
- subExpsRes :: [SubExp] -> Result
- varRes :: VName -> SubExpRes
- varsRes :: [VName] -> Result
- subExpResVName :: SubExpRes -> Maybe VName
Documentation
module Language.Futhark.Core
prettyString :: Pretty a => a -> String Source #
Prettyprint a value to a String, appropriately wrapped.
Minimal complete definition
Instances
module Futhark.IR.Rep
module Futhark.IR.Syntax.Core
Types
data Uniqueness Source #
The uniqueness attribute of a type. This essentially indicates
whether or not in-place modifications are acceptable. With respect
to ordering, Unique is greater than Nonunique.
Constructors
| Nonunique | May have references outside current function. |
| Unique | No references outside current function. |
Instances
data NoUniqueness Source #
A fancier name for () - encodes no uniqueness information.
Constructors
| NoUniqueness |
Instances
The size of an array type as merely the number of dimensions, with no further information.
Instances
| Monoid Rank Source # | |
| Semigroup Rank Source # | |
| Show Rank Source # | |
| ArrayShape Rank Source # | |
| Rename Rank Source # | |
| Substitute Rank Source # | |
Defined in Futhark.Transform.Substitute | |
| Eq Rank Source # | |
| Ord Rank Source # | |
| Pretty Rank Source # | |
Defined in Futhark.IR.Pretty | |
| Pretty u => Pretty (TypeBase Rank u) Source # | |
class (Monoid a, Eq a, Ord a) => ArrayShape a where Source #
A class encompassing types containing array shape information.
Methods
shapeRank :: a -> Int Source #
Return the rank of an array with the given size.
subShapeOf :: a -> a -> Bool Source #
Check whether one shape if a subset of another shape.
Instances
The memory space of a block. If DefaultSpace, this is the "default"
space, whatever that is. The exact meaning of the SpaceId
depends on the backend used. In GPU kernels, for example, this is
used to distinguish between constant, global and shared memory
spaces. In GPU-enabled host code, it is used to distinguish
between host memory (DefaultSpace) and GPU space.
Constructors
| DefaultSpace | |
| Space SpaceId | |
| ScalarSpace [SubExp] PrimType | A special kind of memory that is a statically sized array of some primitive type. Used for private memory on GPUs. |
data TypeBase shape u Source #
The type of a value. When comparing types for equality with
==, shapes must match.
Constructors
| Prim PrimType | |
| Acc VName Shape [Type] u | Token, index space, element type, and uniqueness. |
| Array PrimType shape u | |
| Mem Space |
Instances
Information about which parts of a value/type are consumed. For
example, we might say that a function taking three arguments of
types ([int], *[int], [int]) has diet [Observe, Consume,
Observe].
Constructors
| Consume | Consumes this value. |
| Observe | Only observes value in this position, does not consume. A result may alias this. |
| ObservePrim | As |
Abstract syntax tree
An identifier consists of its name and the type of the value bound to the identifier.
A subexpression is either a scalar constant or a variable. One important property is that evaluation of a subexpression is guaranteed to complete in constant time.
Instances
An element of a pattern - consisting of a name and an addditional parametric decoration. This decoration is what is expected to contain the type of the resulting variable.
Constructors
| PatElem | |
Fields
| |
Instances
A pattern is conceptually just a list of names and their types.
Instances
| Foldable Pat Source # | |
Defined in Futhark.IR.Syntax Methods fold :: Monoid m => Pat m -> m # foldMap :: Monoid m => (a -> m) -> Pat a -> m # foldMap' :: Monoid m => (a -> m) -> Pat a -> m # foldr :: (a -> b -> b) -> b -> Pat a -> b # foldr' :: (a -> b -> b) -> b -> Pat a -> b # foldl :: (b -> a -> b) -> b -> Pat a -> b # foldl' :: (b -> a -> b) -> b -> Pat a -> b # foldr1 :: (a -> a -> a) -> Pat a -> a # foldl1 :: (a -> a -> a) -> Pat a -> a # elem :: Eq a => a -> Pat a -> Bool # maximum :: Ord a => Pat a -> a # | |
| Traversable Pat Source # | |
| Functor Pat Source # | |
| Monoid (Pat dec) Source # | |
| Semigroup (Pat dec) Source # | |
| Show dec => Show (Pat dec) Source # | |
| FreeIn dec => FreeIn (Pat dec) Source # | |
| Rename dec => Rename (Pat dec) Source # | |
| Substitute dec => Substitute (Pat dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Eq dec => Eq (Pat dec) Source # | |
| Ord dec => Ord (Pat dec) Source # | |
| Pretty t => Pretty (Pat t) Source # | |
Defined in Futhark.IR.Pretty | |
Auxilliary Information associated with a statement.
Constructors
| StmAux | |
Fields
| |
Instances
| Semigroup dec => Semigroup (StmAux dec) Source # | |
| Show dec => Show (StmAux dec) Source # | |
| FreeIn dec => FreeIn (StmAux dec) Source # | |
| Rename dec => Rename (StmAux dec) Source # | |
| Substitute dec => Substitute (StmAux dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Eq dec => Eq (StmAux dec) Source # | |
| Ord dec => Ord (StmAux dec) Source # | |
A local variable binding.
Constructors
| Let | |
Instances
| Scoped rep (Stm rep) Source # | |
| Scoped rep (Stms rep) Source # | |
| RepTypes rep => Show (Stm rep) Source # | |
| (FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Stm rep) Source # | |
| FreeIn (Stm rep) => FreeIn (Stms rep) Source # | |
| Renameable rep => Rename (Stm rep) Source # | |
| Substitutable rep => Substitute (Stm rep) Source # | |
Defined in Futhark.Transform.Substitute | |
| Substitute (Stm rep) => Substitute (Stms rep) Source # | |
Defined in Futhark.Transform.Substitute | |
| RepTypes rep => Eq (Stm rep) Source # | |
| RepTypes rep => Ord (Stm rep) Source # | |
| PrettyRep rep => Pretty (Stm rep) Source # | |
Defined in Futhark.IR.Pretty | |
| PrettyRep rep => Pretty (Stms rep) Source # | |
Defined in Futhark.IR.Pretty | |
A pairing of a subexpression and some certificates.
Instances
| Show SubExpRes Source # | |
| FreeIn SubExpRes Source # | |
| Simplifiable SubExpRes Source # | |
Defined in Futhark.Optimise.Simplify.Engine | |
| Rename SubExpRes Source # | |
| Substitute SubExpRes Source # | |
Defined in Futhark.Transform.Substitute | |
| Eq SubExpRes Source # | |
| Ord SubExpRes Source # | |
| Pretty SubExpRes Source # | |
Defined in Futhark.IR.Pretty | |
A body consists of a number of bindings, terminating in a result (essentially a tuple literal).
Instances
| RepTypes rep => Show (Body rep) Source # | |
| (FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Body rep) Source # | |
| Renameable rep => Rename (Body rep) Source # | |
| Substitutable rep => Substitute (Body rep) Source # | |
Defined in Futhark.Transform.Substitute | |
| RepTypes rep => Eq (Body rep) Source # | |
| RepTypes rep => Ord (Body rep) Source # | |
Defined in Futhark.IR.Syntax | |
| PrettyRep rep => Pretty (Body rep) Source # | |
Defined in Futhark.IR.Pretty | |
| PrettyRep rep => Pretty (Case (Body rep)) Source # | |
A primitive operation that returns something of known size and does not itself contain any bindings.
Constructors
| SubExp SubExp | A variable or constant. |
| Opaque OpaqueOp SubExp | Semantically and operationally just identity, but is invisible/impenetrable to optimisations (hopefully). This partially a hack to avoid optimisation (so, to work around compiler limitations), but is also used to implement tracing and other operations that are semantically invisible, but have some sort of effect (brrr). |
| ArrayLit [SubExp] Type | Array literals, e.g., |
| 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. |
| Index VName (Slice SubExp) | The certificates for bounds-checking are part of the |
| Update Safety VName (Slice SubExp) SubExp | An in-place update of the given array at the given position.
Consumes the array. If |
| FlatIndex VName (FlatSlice SubExp) | |
| FlatUpdate VName (FlatSlice SubExp) VName | |
| Concat Int (NonEmpty VName) SubExp | concat(0, [1] :| [[2, 3, 4], [5, 6]], 6) = [1, 2, 3, 4, 5, 6] Concatenates the non-empty list of concat(1, [[1,2], [3, 4]] :| [[[5,6]], [[7, 8]]], 4) = [[1, 2, 5, 6], [3, 4, 7, 8]] |
| 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. |
| Iota SubExp SubExp SubExp IntType |
The |
| 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. |
| Reshape ReshapeKind Shape 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 |
| 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. |
| UpdateAcc VName [SubExp] [SubExp] | Update an accumulator at the given index with the given value. Consumes the accumulator and produces a new one. |
Various unary operators. It is a bit ad-hoc what is a unary operator and what is a built-in function. Perhaps these should all go away eventually.
Constructors
| Not | E.g., |
| Complement IntType | E.g., |
| Abs IntType |
|
| FAbs FloatType |
|
| SSignum IntType | Signed sign function: |
| USignum IntType | Unsigned sign function: |
| FSignum FloatType | Floating-point sign function. |
Binary operators. These correspond closely to the binary operators in LLVM. Most are parametrised by their expected input and output types.
Constructors
| Add IntType Overflow | Integer addition. |
| FAdd FloatType | Floating-point addition. |
| Sub IntType Overflow | Integer subtraction. |
| FSub FloatType | Floating-point subtraction. |
| Mul IntType Overflow | Integer multiplication. |
| FMul FloatType | Floating-point multiplication. |
| UDiv IntType Safety | Unsigned integer division. Rounds towards negativity infinity. Note: this is different from LLVM. |
| UDivUp IntType Safety | Unsigned integer division. Rounds towards positive infinity. |
| SDiv IntType Safety | Signed integer division. Rounds towards negativity infinity. Note: this is different from LLVM. |
| SDivUp IntType Safety | Signed integer division. Rounds towards positive infinity. |
| FDiv FloatType | Floating-point division. |
| FMod FloatType | Floating-point modulus. |
| UMod IntType Safety | Unsigned integer modulus; the countepart to |
| SMod IntType Safety | Signed integer modulus; the countepart to |
| SQuot IntType Safety | Signed integer division. Rounds towards zero. This
corresponds to the |
| SRem IntType Safety | Signed integer division. Rounds towards zero. This
corresponds to the |
| SMin IntType | Returns the smallest of two signed integers. |
| UMin IntType | Returns the smallest of two unsigned integers. |
| FMin FloatType | Returns the smallest of two floating-point numbers. |
| SMax IntType | Returns the greatest of two signed integers. |
| UMax IntType | Returns the greatest of two unsigned integers. |
| FMax FloatType | Returns the greatest of two floating-point numbers. |
| Shl IntType | Left-shift. |
| LShr IntType | Logical right-shift, zero-extended. |
| AShr IntType | Arithmetic right-shift, sign-extended. |
| And IntType | Bitwise and. |
| Or IntType | Bitwise or. |
| Xor IntType | Bitwise exclusive-or. |
| Pow IntType | Integer exponentiation. |
| FPow FloatType | Floating-point exponentiation. |
| LogAnd | Boolean and - not short-circuiting. |
| LogOr | Boolean or - not short-circuiting. |
Comparison operators are like BinOps, but they always return a
boolean value. The somewhat ugly constructor names are straight
out of LLVM.
Constructors
| CmpEq PrimType | All types equality. |
| CmpUlt IntType | Unsigned less than. |
| CmpUle IntType | Unsigned less than or equal. |
| CmpSlt IntType | Signed less than. |
| CmpSle IntType | Signed less than or equal. |
| FCmpLt FloatType | Floating-point less than. |
| FCmpLe FloatType | Floating-point less than or equal. |
| CmpLlt | Boolean less than. |
| CmpLle | Boolean less than or equal. |
Conversion operators try to generalise the from t0 x to t1
instructions from LLVM.
Constructors
| ZExt IntType IntType | Zero-extend the former integer type to the latter. If the new type is smaller, the result is a truncation. |
| SExt IntType IntType | Sign-extend the former integer type to the latter. If the new type is smaller, the result is a truncation. |
| FPConv FloatType FloatType | Convert value of the former floating-point type to the latter. If the new type is smaller, the result is a truncation. |
| FPToUI FloatType IntType | Convert a floating-point value to the nearest unsigned integer (rounding towards zero). |
| FPToSI FloatType IntType | Convert a floating-point value to the nearest signed integer (rounding towards zero). |
| UIToFP IntType FloatType | Convert an unsigned integer to a floating-point value. |
| SIToFP IntType FloatType | Convert a signed integer to a floating-point value. |
| IToB IntType | Convert an integer to a boolean value. Zero becomes false; anything else is true. |
| BToI IntType | Convert a boolean to an integer. True is converted to 1 and False to 0. |
| FToB FloatType | Convert a float to a boolean value. Zero becomes false; | anything else is true. |
| BToF FloatType | Convert a boolean to a float. True is converted to 1 and False to 0. |
Apart from being Opaque, what else is going on here?
Constructors
| OpaqueNil | No special operation. |
| OpaqueTrace Text | Print the argument, prefixed by this string. |
data ReshapeKind Source #
Which kind of reshape is this?
Constructors
| ReshapeCoerce | New shape is dynamically same as original. |
| ReshapeArbitrary | Any kind of reshaping. |
Instances
| Show ReshapeKind Source # | |
Defined in Futhark.IR.Syntax Methods showsPrec :: Int -> ReshapeKind -> ShowS # show :: ReshapeKind -> String # showList :: [ReshapeKind] -> ShowS # | |
| Eq ReshapeKind Source # | |
Defined in Futhark.IR.Syntax | |
| Ord ReshapeKind Source # | |
Defined in Futhark.IR.Syntax Methods compare :: ReshapeKind -> ReshapeKind -> Ordering # (<) :: ReshapeKind -> ReshapeKind -> Bool # (<=) :: ReshapeKind -> ReshapeKind -> Bool # (>) :: ReshapeKind -> ReshapeKind -> Bool # (>=) :: ReshapeKind -> ReshapeKind -> Bool # max :: ReshapeKind -> ReshapeKind -> ReshapeKind # min :: ReshapeKind -> ReshapeKind -> ReshapeKind # | |
type WithAccInput rep = (Shape, [VName], Maybe (Lambda rep, [SubExp])) Source #
The input to a WithAcc construct. Comprises the index space of
the accumulator, the underlying arrays, and possibly a combining
function.
The root Futhark expression type. The Op constructor contains
a rep-specific operation. Do-loops, branches and function calls
are special. Everything else is a simple BasicOp.
Constructors
| BasicOp BasicOp | A simple (non-recursive) operation. |
| Apply Name [(SubExp, Diet)] [RetType rep] (Safety, SrcLoc, [SrcLoc]) | |
| Match [SubExp] [Case (Body rep)] (Body rep) (MatchDec (BranchType rep)) | A match statement picks a branch by comparing the given subexpressions (called the scrutinee) with the pattern in each of the cases. If none of the cases match, the /default body/ is picked. |
| DoLoop [(FParam rep, SubExp)] (LoopForm rep) (Body rep) |
|
| WithAcc [WithAccInput rep] (Lambda rep) | Create accumulators backed by the given arrays (which are
consumed) and pass them to the lambda, which must return the
updated accumulators and possibly some extra values. The
accumulators are turned back into arrays. The |
| Op (Op rep) |
Instances
| RepTypes rep => Show (Exp rep) Source # | |
| (FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Exp rep) Source # | |
| Renameable rep => Rename (Exp rep) Source # | |
| Substitutable rep => Substitute (Exp rep) Source # | |
Defined in Futhark.Transform.Substitute | |
| RepTypes rep => Eq (Exp rep) Source # | |
| RepTypes rep => Ord (Exp rep) Source # | |
| PrettyRep rep => Pretty (Exp rep) Source # | |
Defined in Futhark.IR.Pretty | |
A non-default case in a Match statement. The number of
elements in the pattern must match the number of scrutinees. A
Nothing value indicates that we don't care about it (i.e. a
wildcard).
Instances
| Foldable Case Source # | |
Defined in Futhark.IR.Syntax Methods fold :: Monoid m => Case m -> m # foldMap :: Monoid m => (a -> m) -> Case a -> m # foldMap' :: Monoid m => (a -> m) -> Case a -> m # foldr :: (a -> b -> b) -> b -> Case a -> b # foldr' :: (a -> b -> b) -> b -> Case a -> b # foldl :: (b -> a -> b) -> b -> Case a -> b # foldl' :: (b -> a -> b) -> b -> Case a -> b # foldr1 :: (a -> a -> a) -> Case a -> a # foldl1 :: (a -> a -> a) -> Case a -> a # elem :: Eq a => a -> Case a -> Bool # maximum :: Ord a => Case a -> a # | |
| Traversable Case Source # | |
| Functor Case Source # | |
| Show body => Show (Case body) Source # | |
| FreeIn body => FreeIn (Case body) Source # | |
| Eq body => Eq (Case body) Source # | |
| Ord body => Ord (Case body) Source # | |
| PrettyRep rep => Pretty (Case (Body rep)) Source # | |
For-loop or while-loop?
Instances
| Scoped rep (LoopForm rep) Source # | |
| RepTypes rep => Show (LoopForm rep) Source # | |
| FreeIn (LParamInfo rep) => FreeIn (LoopForm rep) Source # | |
| RepTypes rep => Eq (LoopForm rep) Source # | |
| RepTypes rep => Ord (LoopForm rep) Source # | |
Defined in Futhark.IR.Syntax | |
Data associated with a branch.
Constructors
| MatchDec | |
Fields
| |
Instances
| Show rt => Show (MatchDec rt) Source # | |
| FreeIn a => FreeIn (MatchDec a) Source # | |
| Eq rt => Eq (MatchDec rt) Source # | |
| Ord rt => Ord (MatchDec rt) Source # | |
Defined in Futhark.IR.Syntax | |
What kind of branch is this? This has no semantic meaning, but provides hints to simplifications.
Constructors
| MatchNormal | An ordinary branch. |
| MatchFallback | 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. |
| MatchEquiv | 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). |
Instances
| Show MatchSort Source # | |
| Eq MatchSort Source # | |
| Ord MatchSort Source # | |
Whether something is safe or unsafe (mostly function calls, and
in the context of whether operations are dynamically checked).
When we inline an Unsafe function, we remove all safety checks in
its body. The Ord instance picks Unsafe as being less than
Safe.
For operations like integer division, a safe division will not explode the computer in case of division by zero, but instead return some unspecified value. This always involves a run-time check, so generally the unsafe variant is what the compiler will insert, but guarded by an explicit assertion elsewhere. Safe operations are useful when the optimiser wants to move e.g. a division to a location where the divisor may be zero, but where the result will only be used when it is non-zero (so it doesn't matter what result is provided with a zero divisor, as long as the program keeps running).
Anonymous function for use in a SOAC.
Constructors
| Lambda | |
Fields
| |
Instances
| Scoped rep (Lambda rep) Source # | |
| RepTypes rep => Show (Lambda rep) Source # | |
| (FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (Lambda rep) Source # | |
| Renameable rep => Rename (Lambda rep) Source # | |
| Substitutable rep => Substitute (Lambda rep) Source # | |
Defined in Futhark.Transform.Substitute | |
| RepTypes rep => Eq (Lambda rep) Source # | |
| RepTypes rep => Ord (Lambda rep) Source # | |
| PrettyRep rep => Pretty (Lambda rep) Source # | |
Defined in Futhark.IR.Pretty | |
Definitions
A function or lambda parameter.
Constructors
| Param | |
Instances
| Foldable Param Source # | |
Defined in Futhark.IR.Syntax.Core Methods fold :: Monoid m => Param m -> m # foldMap :: Monoid m => (a -> m) -> Param a -> m # foldMap' :: Monoid m => (a -> m) -> Param a -> m # foldr :: (a -> b -> b) -> b -> Param a -> b # foldr' :: (a -> b -> b) -> b -> Param a -> b # foldl :: (b -> a -> b) -> b -> Param a -> b # foldl' :: (b -> a -> b) -> b -> Param a -> b # foldr1 :: (a -> a -> a) -> Param a -> a # foldl1 :: (a -> a -> a) -> Param a -> a # elem :: Eq a => a -> Param a -> Bool # maximum :: Ord a => Param a -> a # minimum :: Ord a => Param a -> a # | |
| Traversable Param Source # | |
| Functor Param Source # | |
| Show dec => Show (Param dec) Source # | |
| FreeIn dec => FreeIn (Param dec) Source # | |
| DeclTyped dec => DeclTyped (Param dec) Source # | |
Defined in Futhark.IR.Prop.Types Methods declTypeOf :: Param dec -> DeclType Source # | |
| Typed dec => Typed (Param dec) Source # | |
| Rename dec => Rename (Param dec) Source # | |
| Substitute dec => Substitute (Param dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Eq dec => Eq (Param dec) Source # | |
| Ord dec => Ord (Param dec) Source # | |
| Pretty t => Pretty (Param t) Source # | |
Defined in Futhark.IR.Pretty | |
type FParam rep = Param (FParamInfo rep) Source #
A function and loop parameter.
type LParam rep = Param (LParamInfo rep) Source #
A lambda parameter.
Function Declarations
Constructors
| FunDef | |
Fields
| |
Instances
| Scoped rep (FunDef rep) Source # | |
| RepTypes rep => Show (FunDef rep) Source # | |
| (FreeDec (ExpDec rep), FreeDec (BodyDec rep), FreeIn (FParamInfo rep), FreeIn (LParamInfo rep), FreeIn (LetDec rep), FreeIn (RetType rep), FreeIn (BranchType rep), FreeIn (Op rep)) => FreeIn (FunDef rep) Source # | |
| Renameable rep => Rename (FunDef rep) Source # | |
| RepTypes rep => Eq (FunDef rep) Source # | |
| RepTypes rep => Ord (FunDef rep) Source # | |
| PrettyRep rep => Pretty (FunDef rep) Source # | |
Defined in Futhark.IR.Pretty | |
data EntryParam Source #
An entry point parameter, comprising its name and original type.
Constructors
| EntryParam | |
Fields | |
Instances
| Show EntryParam Source # | |
Defined in Futhark.IR.Syntax Methods showsPrec :: Int -> EntryParam -> ShowS # show :: EntryParam -> String # showList :: [EntryParam] -> ShowS # | |
| Eq EntryParam Source # | |
Defined in Futhark.IR.Syntax | |
| Ord EntryParam Source # | |
Defined in Futhark.IR.Syntax Methods compare :: EntryParam -> EntryParam -> Ordering # (<) :: EntryParam -> EntryParam -> Bool # (<=) :: EntryParam -> EntryParam -> Bool # (>) :: EntryParam -> EntryParam -> Bool # (>=) :: EntryParam -> EntryParam -> Bool # max :: EntryParam -> EntryParam -> EntryParam # min :: EntryParam -> EntryParam -> EntryParam # | |
| Pretty EntryParam Source # | |
Defined in Futhark.IR.Pretty | |
data EntryResult Source #
An entry point result type.
Constructors
| EntryResult | |
Fields | |
Instances
| Show EntryResult Source # | |
Defined in Futhark.IR.Syntax Methods showsPrec :: Int -> EntryResult -> ShowS # show :: EntryResult -> String # showList :: [EntryResult] -> ShowS # | |
| Eq EntryResult Source # | |
Defined in Futhark.IR.Syntax | |
| Ord EntryResult Source # | |
Defined in Futhark.IR.Syntax Methods compare :: EntryResult -> EntryResult -> Ordering # (<) :: EntryResult -> EntryResult -> Bool # (<=) :: EntryResult -> EntryResult -> Bool # (>) :: EntryResult -> EntryResult -> Bool # (>=) :: EntryResult -> EntryResult -> Bool # max :: EntryResult -> EntryResult -> EntryResult # min :: EntryResult -> EntryResult -> EntryResult # | |
| Pretty EntryResult Source # | |
Defined in Futhark.IR.Pretty | |
type EntryPoint = (Name, [EntryParam], [EntryResult]) Source #
Information about the inputs and outputs (return value) of an entry point.
An entire Futhark program.
Constructors
| Prog | |
Fields
| |
Utils
stmsFromList :: [Stm rep] -> Stms rep Source #
Convert a statement list to a statement sequence.
stmsToList :: Stms rep -> [Stm rep] Source #
Convert a statement sequence to a statement list.
stmsHead :: Stms rep -> Maybe (Stm rep, Stms rep) Source #
The first statement in the sequence, if any.