futhark-0.25.27: An optimising compiler for a functional, array-oriented language.

Safe Haskell | Safe-Inferred
Language | GHC2021

Futhark.IR.Traversals

Contents

- Mapping
- Walking
- Ops

Description

Functions for generic traversals across Futhark syntax trees. The motivation for this module came from dissatisfaction with rewriting the same trivial tree recursions for every module. A possible alternative would be to use normal "Scrap your boilerplate"-techniques, but these are rejected for two reasons:

- They are too slow.
- More importantly, they do not tell you whether you have missed some cases.

Instead, this module defines various traversals of the Futhark syntax tree. The implementation is rather tedious, but the interface is easy to use.

A traversal of the Futhark syntax tree is expressed as a record of functions expressing the operations to be performed on the various types of nodes.

The Futhark.Transform.Rename module is a simple example of how to use this facility.

Synopsis

- data Mapper frep trep m = Mapper {
  - mapOnSubExp :: SubExp -> m SubExp
  - mapOnBody :: Scope trep -> Body frep -> m (Body trep)
  - mapOnVName :: VName -> m VName
  - mapOnRetType :: RetType frep -> m (RetType trep)
  - mapOnBranchType :: BranchType frep -> m (BranchType trep)
  - mapOnFParam :: FParam frep -> m (FParam trep)
  - mapOnLParam :: LParam frep -> m (LParam trep)
  - mapOnOp :: Op frep -> m (Op trep)
  }
- identityMapper :: forall rep m. Monad m => Mapper rep rep m
- mapExpM :: Monad m => Mapper frep trep m -> Exp frep -> m (Exp trep)
- mapExp :: Mapper frep trep Identity -> Exp frep -> Exp trep
- data Walker rep m = Walker {
  - walkOnSubExp :: SubExp -> m ()
  - walkOnBody :: Scope rep -> Body rep -> m ()
  - walkOnVName :: VName -> m ()
  - walkOnRetType :: RetType rep -> m ()
  - walkOnBranchType :: BranchType rep -> m ()
  - walkOnFParam :: FParam rep -> m ()
  - walkOnLParam :: LParam rep -> m ()
  - walkOnOp :: Op rep -> m ()
  }
- identityWalker :: forall rep m. Monad m => Walker rep m
- walkExpM :: Monad m => Walker rep m -> Exp rep -> m ()
- class TraverseOpStms rep where
  - traverseOpStms :: Monad m => OpStmsTraverser m (Op rep) rep
- type OpStmsTraverser m op rep = (Scope rep -> Stms rep -> m (Stms rep)) -> op -> m op
- traverseLambdaStms :: Monad m => OpStmsTraverser m (Lambda rep) rep

# Mapping

data Mapper frep trep m Source #

Express a monad mapping operation on a syntax node. Each element of this structure expresses the operation to be performed on a given child.

Constructors

Mapper |

Fields

- mapOnSubExp :: SubExp -> m SubExp
- mapOnBody :: Scope trep -> Body frep -> m (Body trep)

  Most bodies are enclosed in a scope, which is passed along for convenience.

- mapOnVName :: VName -> m VName
- mapOnRetType :: RetType frep -> m (RetType trep)
- mapOnBranchType :: BranchType frep -> m (BranchType trep)
- mapOnFParam :: FParam frep -> m (FParam trep)
- mapOnLParam :: LParam frep -> m (LParam trep)
- mapOnOp :: Op frep -> m (Op trep)

identityMapper :: forall rep m. Monad m => Mapper rep rep m Source #

A mapper that simply returns the tree verbatim.

mapExpM :: Monad m => Mapper frep trep m -> Exp frep -> m (Exp trep) Source #

Map a monadic action across the immediate children of an expression. Importantly, the mapping does not descend recursively into subexpressions. The mapping is done left-to-right.

mapExp :: Mapper frep trep Identity -> Exp frep -> Exp trep Source #

Like `mapExpM`, but in the `Identity` monad.

# Walking

data Walker rep m Source #

Express a monad expression on a syntax node. Each element of this structure expresses the action to be performed on a given child.

Constructors

Walker |

Fields

- walkOnSubExp :: SubExp -> m ()
- walkOnBody :: Scope rep -> Body rep -> m ()
- walkOnVName :: VName -> m ()
- walkOnRetType :: RetType rep -> m ()
- walkOnBranchType :: BranchType rep -> m ()
- walkOnFParam :: FParam rep -> m ()
- walkOnLParam :: LParam rep -> m ()
- walkOnOp :: Op rep -> m ()

identityWalker :: forall rep m. Monad m => Walker rep m Source #

A no-op traversal.

walkExpM :: Monad m => Walker rep m -> Exp rep -> m () Source #

As `mapExpM`, but do not construct a result AST.

# Ops

class TraverseOpStms rep where Source #

This representation supports an `OpStmsTraverser` for its `Op`. This is used for some simplification rules.

Methods

traverseOpStms :: Monad m => OpStmsTraverser m (Op rep) rep Source #

Transform every sub-`Stms` of this op.

#### Instances

Instances details

TraverseOpStms Seq Source # |
Instance details Defined in Futhark.IR.Seq Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op Seq) Seq Source #
TraverseOpStms SeqMem Source # |
Instance details Defined in Futhark.IR.SeqMem Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op SeqMem) SeqMem Source #
TraverseOpStms (Wise GPU) Source # |
Instance details Defined in Futhark.IR.GPU.Simplify Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise GPU)) (Wise GPU) Source #
TraverseOpStms (Wise GPUMem) Source # |
Instance details Defined in Futhark.IR.GPUMem Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise GPUMem)) (Wise GPUMem) Source #
TraverseOpStms (Wise MC) Source # |
Instance details Defined in Futhark.IR.MC Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise MC)) (Wise MC) Source #
TraverseOpStms (Wise MCMem) Source # |
Instance details Defined in Futhark.IR.MCMem Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise MCMem)) (Wise MCMem) Source #
TraverseOpStms (Wise SOACS) Source # |
Instance details Defined in Futhark.IR.SOACS.Simplify Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise SOACS)) (Wise SOACS) Source #
TraverseOpStms (Wise Seq) Source # |
Instance details Defined in Futhark.IR.Seq Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise Seq)) (Wise Seq) Source #
TraverseOpStms (Wise SeqMem) Source # |
Instance details Defined in Futhark.IR.SeqMem Methods traverseOpStms :: Monad m => OpStmsTraverser m (Op (Wise SeqMem)) (Wise SeqMem) Source #

type OpStmsTraverser m op rep = (Scope rep -> Stms rep -> m (Stms rep)) -> op -> m op Source #

A function for monadically traversing any sub-statements of the given op for some representation.

traverseLambdaStms :: Monad m => OpStmsTraverser m (Lambda rep) rep Source #

A helper for defining `traverseOpStms`.