| 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
- 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.
Minimal complete definition
Instances
Defined in Futhark.IR.SegOpp a monadic action across the immediate childrex">Ea href="#v:typeOf">typeOf :: Futhark.IR.SegOp