clash-lib-1.9.0: 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.
LicenseBSD2 (see the file LICENSE)
MaintainerQBayLogic B.V. <devops@qbaylogic.com>
Safe HaskellNone
LanguageHaskell2010

Clash.Normalize.Transformations.Reduce

Description

Transformations for compile-time reduction of expressions / primitives.

Synopsis

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

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