Clash.Normalize.Transformations.Reduce

Transformations for compile-time reduction of expressions / primitives.

Documentation

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

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

reduceNonRepPrim :: HasCallStack => NormRewrite

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