| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
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
- prettyStringOneLine :: Pretty a => a -> String
- prettyText :: Pretty a => a -> Text
- prettyTextOneLine :: 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
- stmAuxLoc :: Provenance
- 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
- | ArrayVal [PrimValue] PrimType
- | UnOp UnOp SubExp
- | BinOp BinOp SubExp SubExp
- | CmpOp CmpOp SubExp SubExp
- | ConvOp ConvOp SubExp
- | Assert SubExp (ErrorMsg SubExp)
- | Index VName (Slice SubExp)
- | Update Safety VName (Slice SubExp) SubExp
- | FlatIndex VName (FlatSlice SubExp)
- | FlatUpdate VName (FlatSlice SubExp) VName
- | Concat Int (NonEmpty VName) SubExp
- | Manifest VName [Int]
- | Iota SubExp SubExp SubExp IntType
- | Replicate Shape SubExp
- | Scratch PrimType [SubExp]
- | Reshape VName (NewShape SubExp)
- | Rearrange VName [Int]
- | UpdateAcc Safety 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
- = OpaqueNil
- | OpaqueTrace Text
- data DimSplice d = DimSplice Int Int (ShapeBase d)
- data NewShape d = NewShape {
- dimSplices :: [DimSplice d]
- newShape :: ShapeBase d
- type WithAccInput rep = (Shape, [VName], Maybe (Lambda rep, [SubExp]))
- data Exp rep
- data Case body = Case {}
- data LoopForm
- data MatchDec rt = MatchDec {
- matchReturns :: [rt]
- matchSort :: MatchSort
- data MatchSort
- data Safety
- data Lambda rep = Lambda {
- lambdaParams :: [LParam rep]
- lambdaReturnType :: [Type]
- lambdaBody :: Body rep
- data RetAls = RetAls {}
- 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, RetAls)]
- 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.
prettyStringOneLine :: Pretty a => a -> String Source #
Prettyprint a value to a String on a single line.
prettyText :: Pretty a => a -> Text Source #
Prettyprint a value to a Text, appropriately wrapped.
prettyTextOneLine :: Pretty a => a -> Text Source #
Prettyprint a value to a Text on a single line.
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.
Also has a different prettyprinting instance.
Constructors
| NoUniqueness |
Instances
The size of an array type as merely the number of dimensions, with no further information.
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
| Bifoldable TypeBase Source # | |
| Bifunctor TypeBase Source # | |
| Bitraversable TypeBase Source # | |
Defined in Futhark.IR.Syntax.Core Methods bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> TypeBase a b -> f (TypeBase c d) | |
| DeclExtTyped DeclExtType Source # | |
Defined in Futhark.IR.Prop.Types Methods | |
| DeclTyped DeclType Source # | |
Defined in Futhark.IR.Prop.Types Methods declTypeOf :: DeclType -> DeclType Source # | |
| ExtTyped DeclExtType Source # | |
Defined in Futhark.IR.Prop.Types Methods extTypeOf :: DeclExtType -> ExtType Source # | |
| ExtTyped ExtType Source # | |
| Typed DeclType Source # | |
| Typed Type Source # | |
| IsBodyType ExtType Source # | |
Defined in Futhark.IR.RetType Methods primBodyType :: PrimType -> ExtType Source # | |
| IsRetType DeclExtType Source # | |
Defined in Futhark.IR.RetType Methods primRetType :: PrimType -> DeclExtType Source # applyRetType :: Typed dec => [DeclExtType] -> [Param dec] -> [(SubExp, Type)] -> Maybe [DeclExtType] Source # | |
| Functor (TypeBase shape) Source # | |
| Foldable (TypeBase shape) Source # | |
Defined in Futhark.IR.Syntax.Core Methods fold :: Monoid m => TypeBase shape m -> m foldMap :: Monoid m => (a -> m) -> TypeBase shape a -> m foldMap' :: Monoid m => (a -> m) -> TypeBase shape a -> m foldr :: (a -> b -> b) -> b -> TypeBase shape a -> b foldr' :: (a -> b -> b) -> b -> TypeBase shape a -> b foldl :: (b -> a -> b) -> b -> TypeBase shape a -> b foldl' :: (b -> a -> b) -> b -> TypeBase shape a -> b foldr1 :: (a -> a -> a) -> TypeBase shape a -> a foldl1 :: (a -> a -> a) -> TypeBase shape a -> a toList :: TypeBase shape a -> [a] null :: TypeBase shape a -> Bool length :: TypeBase shape a -> Int elem :: Eq a => a -> TypeBase shape a -> Bool maximum :: Ord a => TypeBase shape a -> a minimum :: Ord a => TypeBase shape a -> a | |
| Traversable (TypeBase shape) Source # | |
Defined in Futhark.IR.Syntax.Core Methods traverse :: Applicative f => (a -> f b) -> TypeBase shape a -> f (TypeBase shape b) # sequenceA :: Applicative f => TypeBase shape (f a) -> f (TypeBase shape a) mapM :: Monad m => (a -> m b) -> TypeBase shape a -> m (TypeBase shape b) sequence :: Monad m => TypeBase shape (m a) -> m (TypeBase shape a) | |
| FreeIn shape => FreeIn (TypeBase shape u) Source # | |
| (FixExt shape, ArrayShape shape) => FixExt (TypeBase shape u) Source # | |
| Simplifiable shape => Simplifiable (TypeBase shape u) Source # | |
Defined in Futhark.Optimise.Simplify.Engine | |
| Rename shape => Rename (TypeBase shape u) Source # | |
| Substitute shape => Substitute (TypeBase shape u) Source # | |
Defined in Futhark.Transform.Substitute | |
| (Show shape, Show u) => Show (TypeBase shape u) Source # | |
| (Eq shape, Eq u) => Eq (TypeBase shape u) Source # | |
| (Ord shape, Ord u) => Ord (TypeBase shape u) Source # | |
Defined in Futhark.IR.Syntax.Core Methods compare :: TypeBase shape u -> TypeBase shape u -> Ordering (<) :: TypeBase shape u -> TypeBase shape u -> Bool (<=) :: TypeBase shape u -> TypeBase shape u -> Bool (>) :: TypeBase shape u -> TypeBase shape u -> Bool (>=) :: TypeBase shape u -> TypeBase shape u -> Bool max :: TypeBase shape u -> TypeBase shape u -> TypeBase shape u min :: TypeBase shape u -> TypeBase shape u -> TypeBase shape u | |
| Pretty u => Pretty (TypeBase ExtShape u) Source # | |
| Pretty u => Pretty (TypeBase Rank u) Source # | |
| Pretty u => Pretty (TypeBase Shape u) Source # | |
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
| Functor PatElem Source # | |
| Foldable PatElem Source # | |
Defined in Futhark.IR.Syntax.Core Methods fold :: Monoid m => PatElem m -> m foldMap :: Monoid m => (a -> m) -> PatElem a -> m foldMap' :: Monoid m => (a -> m) -> PatElem a -> m foldr :: (a -> b -> b) -> b -> PatElem a -> b foldr' :: (a -> b -> b) -> b -> PatElem a -> b foldl :: (b -> a -> b) -> b -> PatElem a -> b foldl' :: (b -> a -> b) -> b -> PatElem a -> b foldr1 :: (a -> a -> a) -> PatElem a -> a foldl1 :: (a -> a -> a) -> PatElem a -> a elem :: Eq a => a -> PatElem a -> Bool maximum :: Ord a => PatElem a -> a minimum :: Ord a => PatElem a -> a | |
| Traversable PatElem Source # | |
| AliasesOf dec => AliasesOf (PatElem dec) Source # | |
| FreeIn dec => FreeIn (PatElem dec) Source # | |
| Typed dec => Typed (PatElem dec) Source # | |
| Rename dec => Rename (PatElem dec) Source # | |
| Substitute dec => Substitute (PatElem dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Show dec => Show (PatElem dec) Source # | |
| Eq dec => Eq (PatElem dec) Source # | |
| Ord dec => Ord (PatElem dec) Source # | |
Defined in Futhark.IR.Syntax.Core | |
| Pretty t => Pretty (PatElem t) Source # | |
A pattern is conceptually just a list of names and their types.
Instances
| Functor Pat Source # | |
| 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 # | |
| FreeIn dec => FreeIn (Pat dec) Source # | |
| Rename dec => Rename (Pat dec) Source # | |
| Substitute dec => Substitute (Pat dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Monoid (Pat dec) Source # | |
| Semigroup (Pat dec) Source # | |
| Show dec => Show (Pat dec) Source # | |
| Eq dec => Eq (Pat dec) Source # | |
| Ord dec => Ord (Pat dec) Source # | |
| Pretty t => Pretty (Pat t) Source # | |
Auxilliary Information associated with a statement.
Constructors
| StmAux | |
Fields
| |
Instances
| Functor StmAux Source # | |
| Foldable StmAux Source # | |
Defined in Futhark.IR.Syntax Methods fold :: Monoid m => StmAux m -> m foldMap :: Monoid m => (a -> m) -> StmAux a -> m foldMap' :: Monoid m => (a -> m) -> StmAux a -> m foldr :: (a -> b -> b) -> b -> StmAux a -> b foldr' :: (a -> b -> b) -> b -> StmAux a -> b foldl :: (b -> a -> b) -> b -> StmAux a -> b foldl' :: (b -> a -> b) -> b -> StmAux a -> b foldr1 :: (a -> a -> a) -> StmAux a -> a foldl1 :: (a -> a -> a) -> StmAux a -> a elem :: Eq a => a -> StmAux a -> Bool maximum :: Ord a => StmAux a -> a | |
| Traversable StmAux Source # | |
| FreeIn dec => FreeIn (StmAux dec) Source # | |
| Rename dec => Rename (StmAux dec) Source # | |
| Substitute dec => Substitute (StmAux dec) Source # | |
Defined in Futhark.Transform.Substitute | |
| Monoid dec => Monoid (StmAux dec) Source # | |
| Semigroup dec => Semigroup (StmAux dec) Source # | |
| Show dec => Show (StmAux dec) Source # | |
| Eq dec => Eq (StmAux dec) Source # | |
| Ord dec => Ord (StmAux dec) Source # | |
| Pretty dec => Pretty (StmAux dec) Source # | |
A local variable binding.
Constructors
| Let | |
Instances
| Scoped rep (Stm rep) Source # | |
| Scoped rep (Stms 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 => Show (Stm rep) Source # | |
| RepTypes rep => Eq (Stm rep) Source # | |
| RepTypes rep => Ord (Stm rep) Source # | |
| PrettyRep rep => Pretty (Stm rep) Source # | |
| PrettyRep rep => Pretty (Stms rep) Source # | |
A pairing of a subexpression and some certificates.
Instances
| FreeIn SubExpRes Source # | |
| Simplifiable SubExpRes Source # | |
Defined in Futhark.Optimise.Simplify.Engine | |
| Rename SubExpRes Source # | |
| Substitute SubExpRes Source # | |
Defined in Futhark.Transform.Substitute | |
| Show SubExpRes Source # | |
| Eq SubExpRes Source # | |
| Ord SubExpRes Source # | |
Defined in Futhark.IR.Syntax | |
| Pretty SubExpRes Source # | |
A body consists of a sequence of statements, terminating in a list of result values.
Instances
| (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 => Show (Body rep) Source # | |
| RepTypes rep => Eq (Body rep) Source # | |
| RepTypes rep => Ord (Body rep) Source # | |
| PrettyRep rep => Pretty (Body rep) Source # | |
| 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., |
| ArrayVal [PrimValue] PrimType | A one-dimensional array literal that contains only constants.
This is a fast-path for representing very large array literals
that show up in some programs. The key rule for processing this
in compiler passes is that you should never need to look at the
individual elements. Has exactly the same semantics as an
|
| 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) | Turn a boolean into a certificate, halting the program with the given error message if the boolean is false. The error location comes from the provenance of the statement. |
| 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]] |
| Manifest VName [Int] | 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 |
|
| Scratch PrimType [SubExp] | Create array of given type and shape, with undefined elements. |
| Reshape VName (NewShape SubExp) | 1st arg is the input array, 2nd arg is new shape. |
| Rearrange VName [Int] | Permute the dimensions of the input array. The list
of integers is a list of dimensions (0-indexed), which
must be a permutation of |
| UpdateAcc Safety VName [SubExp] [SubExp] | Update an accumulator at the given index with the given
value. Consumes the accumulator and produces a new one. If
|
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
| Neg PrimType | Flip sign. Logical negation for booleans. |
| 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. |
| FPToBits FloatType | Convert floating point number to its bitwise representation. |
| BitsToFP FloatType | Convert bitwise representation to a floating point number. |
| 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. |
Split or join a range of dimensions. A reshaping operation consists of a sequence of these. The purpose is to maintain information about the original operations (flatten/unflatten), which can then be used for algebraic optimisations.
Constructors
| DimSplice Int Int (ShapeBase d) |
If If If Other cases can do arbitrary changes, but are harder for the compiler to analyse. |
Instances
| Functor DimSplice Source # | |
| Foldable DimSplice Source # | |
Defined in Futhark.IR.Syntax Methods fold :: Monoid m => DimSplice m -> m foldMap :: Monoid m => (a -> m) -> DimSplice a -> m foldMap' :: Monoid m => (a -> m) -> DimSplice a -> m foldr :: (a -> b -> b) -> b -> DimSplice a -> b foldr' :: (a -> b -> b) -> b -> DimSplice a -> b foldl :: (b -> a -> b) -> b -> DimSplice a -> b foldl' :: (b -> a -> b) -> b -> DimSplice a -> b foldr1 :: (a -> a -> a) -> DimSplice a -> a foldl1 :: (a -> a -> a) -> DimSplice a -> a elem :: Eq a => a -> DimSplice a -> Bool maximum :: Ord a => DimSplice a -> a minimum :: Ord a => DimSplice a -> a | |
| Traversable DimSplice Source # | |
| Show d => Show (DimSplice d) Source # | |
| Eq d => Eq (DimSplice d) Source # | |
| Ord d => Ord (DimSplice d) Source # | |
| Pretty d => Pretty (DimSplice d) Source # | |
A reshaping operation consists of a sequence of splices, as well as an annotation indicating the final shape.
Constructors
| NewShape | |
Fields
| |
Instances
| Functor NewShape Source # | |
| Foldable NewShape Source # | |
Defined in Futhark.IR.Syntax Methods fold :: Monoid m => NewShape m -> m foldMap :: Monoid m => (a -> m) -> NewShape a -> m foldMap' :: Monoid m => (a -> m) -> NewShape a -> m foldr :: (a -> b -> b) -> b -> NewShape a -> b foldr' :: (a -> b -> b) -> b -> NewShape a -> b foldl :: (b -> a -> b) -> b -> NewShape a -> b foldl' :: (b -> a -> b) -> b -> NewShape a -> b foldr1 :: (a -> a -> a) -> NewShape a -> a foldl1 :: (a -> a -> a) -> NewShape a -> a elem :: Eq a => a -> NewShape a -> Bool maximum :: Ord a => NewShape a -> a minimum :: Ord a => NewShape a -> a | |
| Traversable NewShape Source # | |
| FreeIn d => FreeIn (NewShape d) Source # | |
| Substitute d => Substitute (NewShape d) Source # | |
Defined in Futhark.Transform.Substitute | |
| Semigroup (NewShape d) Source # | |
| Show d => Show (NewShape d) Source # | |
| Eq d => Eq (NewShape d) Source # | |
| Ord d => Ord (NewShape d) Source # | |
| Pretty d => Pretty (NewShape d) Source # | |
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, RetAls)] Safety | |
| 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. |
| Loop [(FParam rep, SubExp)] LoopForm (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. In the lambda, the result
accumulators come first, and are ordered in a manner consistent with
that of the input (accumulator) arguments. The |
| Op (Op rep) |
Instances
| (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 => Show (Exp rep) Source # | |
| RepTypes rep => Eq (Exp rep) Source # | |
| RepTypes rep => Ord (Exp rep) Source # | |
| PrettyRep rep => Pretty (Exp rep) Source # | |
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
| Functor Case Source # | |
| 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 # | |
| FreeIn body => FreeIn (Case body) Source # | |
| Show body => Show (Case body) Source # | |
| Eq body => Eq (Case body) Source # | |
| Ord body => Ord (Case body) Source # | |
Defined in Futhark.IR.Syntax | |
| PrettyRep rep => Pretty (Case (Body rep)) Source # | |
For-loop or while-loop?
Data associated with a branch.
Constructors
| MatchDec | |
Fields
| |
Instances
| FreeIn a => FreeIn (MatchDec a) Source # | |
| Show rt => Show (MatchDec rt) Source # | |
| Eq rt => Eq (MatchDec rt) Source # | |
| Ord rt => Ord (MatchDec rt) Source # | |
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). |
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 # | |
| (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 => Show (Lambda rep) Source # | |
| RepTypes rep => Eq (Lambda rep) Source # | |
| RepTypes rep => Ord (Lambda rep) Source # | |
| PrettyRep rep => Pretty (Lambda rep) Source # | |
Information about the possible aliases of a function result.
Constructors
| RetAls | |
Definitions
A function or lambda parameter.
Constructors
| Param | |
Fields
| |
Instances
| Functor Param Source # | |
| 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 | |
| Traversable Param 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 | |
| Show dec => Show (Param dec) Source # | |
| Eq dec => Eq (Param dec) Source # | |
| Ord dec => Ord (Param dec) Source # | |
Defined in Futhark.IR.Syntax.Core | |
| Pretty t => Pretty (Param t) Source # | |
type FParam rep = Param (FParamInfo rep) Source #
A function and loop parameter.
type LParam rep = Param (LParamInfo rep) Source #
A lambda parameter.
Function definitions.
Constructors
| FunDef | |
Fields
| |
Instances
| Scoped rep (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 => Show (FunDef rep) Source # | |
| RepTypes rep => Eq (FunDef rep) Source # | |
| RepTypes rep => Ord (FunDef rep) Source # | |
| PrettyRep rep => Pretty (FunDef rep) Source # | |
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.