CLaSH.Normalize.Transformations

Transformations of the Normalization process

Documentation

appProp :: NormRewrite

Propagate arguments of application inwards; except for Lam where the argument becomes let-bound.

bindNonRep :: NormRewrite

Inline non-recursive, non-representable, non-join-point, let-bindings

liftNonRep :: NormRewrite

Lift non-representable let-bindings

caseLet :: NormRewrite

Lift the let-bindings out of the subject of a Case-decomposition

caseCon :: NormRewrite

Specialize a Case-decomposition (replace by the RHS of an alternative) if the subject is (an application of) a DataCon; or if there is only a single alternative that doesn't reference variables bound by the pattern.

caseCase :: NormRewrite

Move a Case-decomposition from the subject of a Case-decomposition to the alternatives

inlineNonRep :: NormRewrite

Inline function with a non-representable result if it's the subject of a Case-decomposition

typeSpec :: NormRewrite

Specialize functions on their type

nonRepSpec :: NormRewrite

Specialize functions on their non-representable argument

etaExpansionTL :: NormRewrite

Eta-expand top-level lambda's (DON'T use in a traversal!)

nonRepANF :: NormRewrite

Bring an application of a DataCon or Primitive in ANF, when the argument is is considered non-representable

bindConstantVar :: NormRewrite

Inline let-bindings when the RHS is either a local variable reference or is constant

constantSpec :: NormRewrite

Specialise functions on arguments which are constant

makeANF :: NormRewrite

Turn an expression into a modified ANF-form. As opposed to standard ANF, constants do not become let-bound.

deadCode :: NormRewrite

Remove unused let-bindings

topLet :: NormRewrite

Ensure that top-level lambda's eventually bind a let-expression of which the body is a variable-reference.

recToLetRec :: NormRewrite

Turn a normalized recursive function, where the recursive calls only pass along the unchanged original arguments, into let-recursive function. This means that all recursive calls are replaced by the same variable reference as found in the body of the top-level let-expression.

inlineClosed :: NormRewrite

Inline nullary/closed functions

inlineHO :: NormRewrite

Inline a function with functional arguments

inlineSmall :: NormRewrite

Inline small functions

simpleCSE :: NormRewrite

Simplified CSE, only works on let-bindings, works from top to bottom

reduceConst :: NormRewrite

reduceNonRepPrim :: 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.map
• CLaSH.Sized.Vector.zipWith
• CLaSH.Sized.Vector.traverse#
• CLaSH.Sized.Vector.foldr
• CLaSH.Sized.Vector.fold
• CLaSH.Sized.Vector.dfold
• CLaSH.Sized.Vector.(++)
• CLaSH.Sized.Vector.head
• CLaSH.Sized.Vector.tail
• CLaSH.Sized.Vector.unconcat
• CLaSH.Sized.Vector.transpose
• CLaSH.Sized.Vector.replicate

caseFlat :: NormRewrite

Flatten ridiculous case-statements generated by GHC

For case-statements in haskell of the form:

f :: Unsigned 4 -> Unsigned 4
f x = case x of
  0 -> 3
  1 -> 2
  2 -> 1
  3 -> 0

GHC generates Core that looks like:

f = (x :: Unsigned 4) -> case x == fromInteger 3 of
                            False -> case x == fromInteger 2 of
                              False -> case x == fromInteger 1 of
                                False -> case x == fromInteger 0 of
                                  False -> error "incomplete case"
                                  True  -> fromInteger 3
                                True -> fromInteger 2
                              True -> fromInteger 1
                            True -> fromInteger 0

Which would result in a priority decoder circuit where a normal decoder circuit was desired.

This transformation transforms the above Core to the saner:

f = (x :: Unsigned 4) -> case x of
       _ -> error "incomplete case"
       0 -> fromInteger 3
       1 -> fromInteger 2
       2 -> fromInteger 1
       3 -> fromInteger 0

disjointExpressionConsolidation :: NormRewrite

This transformation lifts applications of global binders out of alternatives of case-statements.

e.g. It converts:

case x of
  A -> f 3 y
  B -> f x x
  C -> h x

into:

let f_arg0 = case x of {A -> 3; B -> x}
    f_arg1 = case x of {A -> y; B -> x}
    f_out  = f f_arg0 f_arg1
in  case x of
      A -> f_out
      B -> f_out
      C -> h x

removeUnusedExpr :: NormRewrite