clash-lib-1.8.4: Clash: a functional hardware description language - As a library

Copyright | (C) 2012-2016 University of Twente 2016-2017 Myrtle Software Ltd 2017-2018 Google Inc. 2021-2022 QBayLogic B.V.
License | BSD2 (see the file LICENSE)
Maintainer | QBayLogic B.V. <devops@qbaylogic.com>
Safe Haskell | None
Language | Haskell2010

Clash.Normalize.Transformations.Reduce

Description

Transformations for compile-time reduction of expressions / primitives.

Synopsis

- reduceBinders :: Subst -> [LetBinding] -> [LetBinding] -> NormalizeSession (Subst, [LetBinding])
- reduceConst :: HasCallStack => NormRewrite
- reduceNonRepPrim :: HasCallStack => NormRewrite

# Documentation

reduceBinders :: Subst -> [LetBinding] -> [LetBinding] -> NormalizeSession (Subst, [LetBinding]) Source #

XXX: is given inverse topologically sorted binders, but returns topologically sorted binders

TODO: check further speed improvements:

1. Store the processed binders in a `Map Expr LetBinding`: * Trades O(1) `cons` and O(n)*aeqTerm `find` for: * O(log n)*aeqTerm `insert` and O(log n)*aeqTerm `lookup`
2. Store the processed binders in a `AEQTrie Expr LetBinding` * Trades O(1) `cons` and O(n)*aeqTerm `find` for: * O(e) `insert` and O(e) `lookup`

reduceConst :: HasCallStack => NormRewrite Source #

reduceNonRepPrim :: HasCallStack => NormRewrite Source #

Replace primitives by their "definition" if they would lead to let-bindings with a non-representable type when a function is in ANF. This happens for example when Clash.Size.Vector.map consumes or produces a vector of non-representable elements.

Basically what this transformation does is replace a primitive the completely unrolled recursive definition that it represents. e.g.

    zipWith ($) (xs :: Vec 2 (Int -> Int)) (ys :: Vec 2 Int)

is replaced by:

    let (x0  :: (Int -> Int))       = case xs  of (:>) _ x xr -> x
        (xr0 :: Vec 1 (Int -> Int)) = case xs  of (:>) _ x xr -> xr
        (x1  :: (Int -> Int)(       = case xr0 of (:>) _ x xr -> x
        (y0  :: Int)                = case ys  of (:>) _ y yr -> y
        (yr0 :: Vec 1 Int)          = case ys  of (:>) _ y yr -> xr
        (y1  :: Int                 = case yr0 of (:>) _ y yr -> y
    in  (($) x0 y0 :> ($) x1 y1 :> Nil)

Currently, it only handles the following functions:

- Clash.Sized.Vector.zipWith
- Clash.Sized.Vector.map
- Clash.Sized.Vector.traverse#
- Clash.Sized.Vector.fold
- Clash.Sized.Vector.foldr
- Clash.Sized.Vector.dfold
- Clash.Sized.Vector.(++)
- Clash.Sized.Vector.head
- Clash.Sized.Vector.tail
- Clash.Sized.Vector.last
- Clash.Sized.Vector.init
- Clash.Sized.Vector.unconcat
- Clash.Sized.Vector.transpose
- Clash.Sized.Vector.replicate
- Clash.Sized.Vector.replace_int
- Clash.Sized.Vector.imap
- Clash.Sized.Vector.dtfold
- Clash.Sized.RTree.tdfold
- Clash.Sized.RTree.treplicate
- Clash.Sized.Internal.BitVector.split#
- Clash.Sized.Internal.BitVector.eq#

Note [Unroll shouldSplit types] 1. Certain higher-order functions over Vec, such as map, have specialized code-paths to turn them into generate-for loops in HDL, instead of having to having to unroll/inline their recursive definitions, e.g. Clash.Sized.Vector.map

1. Clash, in general, translates Haskell product types to VHDL records. This mostly works out fine, there is however one exception: certain synthesis tools, and some HDL simulation tools (like verilator), do not like it when the clock (and certain other global control signals) is contained in a record type; they want them to be separate inputs to the entity/module. And Clash actually does some transformations to try to ensure that values of type Clock do not end up in a VHDL record type.

The problem is that the transformations in 2. never took into account the specialized code-paths in 1. Making the code-paths in 1. aware of the transformations in 2. is really not worth the effort for such a niche case. It's easier to just unroll the recursive definitions.

See https://github.com/clash-lang/clash-compiler/issues/1606