forsyde-deep-0.2.0: src/ForSyDe/Deep/Netlist.hs
{-# LANGUAGE DeriveDataTypeable, GeneralizedNewtypeDeriving #-}
-----------------------------------------------------------------------------
-- |
-- Module : ForSyDe.Deep.Netlist
-- Copyright : (c) ES Group, KTH/ICT/ES 2007-2013
-- License : BSD-style (see the file LICENSE)
--
-- Maintainer : forsyde-dev@ict.kth.se
-- Stability : experimental
-- Portability : portable
--
-- This module provides a definition for the netlist of a system description,
-- which is used as the intermediate representation of the embedded compiler.
--
-- The netlist is modelled as a directed cyclic graph whose nodes
-- are shared using Observable Sharing ("ForSyDe.OSharing").
--
-- /This module is based on Lava2000/: <http://www.cs.chalmers.se/~koen/Lava/>
--
-----------------------------------------------------------------------------
module ForSyDe.Deep.Netlist where
import ForSyDe.Deep.Ids
import ForSyDe.Deep.OSharing (URef, newURef, readURef)
import {-# SOURCE #-} ForSyDe.Deep.System.SysDef
(SysDef(..), PrimSysDef(..), oIface)
import ForSyDe.Deep.Process.ProcFun (TypedProcFun(..))
import ForSyDe.Deep.ForSyDeErr
import ForSyDe.Deep.Process.ProcVal (ProcVal(..))
import Data.Dynamic
import Data.Typeable.FSDTypeRepLib
-----------
-- Netlist
-----------
-- | The netlist of a system is modelled as a directed cyclic graph but is
-- really equivalently implemented as a set of (possibly overlapping) trees
-- capable of sharing nodes between them.
--
-- There is no specific data structure for the netlist itself. Instead, a
-- netlist is simply represented by its outputs. Each output is the root node
-- of a tree ('NlTree'). The NlTrees can (and probably will) have common nodes.
--
-- It is important to note that, due to the use of trees, the only way to
-- traverse a 'Netlist' is from its outputs to its inputs.
newtype Netlist container = Netlist {netlistOuts :: (container NlTree)}
----------
-- NlNode
----------
-- | A node of the netlist can be either a process, component instances or
-- special nodes to help traversing the graph.
--
-- Since the netlist graph is implemented with trees, they only store
-- information about their inputs (which are their child nodes in the tree).
data NlNode inputi =
-- Ports
InPort PortId | -- ^ Input Ports of the system
-- Processes
Proc ProcId (NlProc inputi)
-- | A process node
-- Note that vectors and transformed to lists puls an Int parameter
-- indicating its size
data NlProc inputi =
-- Constant signal
Const ProcVal | -- ^ A signal with constant value
-- During all its periods
-- | mapSY and zipWithSY processes
ZipWithNSY (TypedProcFun Dynamic) -- Process function in dynamic form
[inputi] |
-- | Vector version of zipWithNSY
ZipWithxSY (TypedProcFun ([Dynamic] -> Dynamic)) -- Process function
-- with dynamic arguments
[inputi] |
-- ^ Inverse of ZipWithNSY
UnzipNSY [FSDTypeRep] -- Type of the elements in the input tuple
-- (type of outputs)
(Dynamic -> [Dynamic]) -- Dynamic version of the unzipping function
-- for the concrete, monomorphic types
-- of the process
inputi |
-- | Vector version of UnzipSY
UnzipxSY FSDTypeRep -- Type of elements in the input vector
-- (and type of the outputs)
Int -- Size of output vector (Number of output signals)
(Dynamic -> [Dynamic])
inputi |
-- | delaySY process
DelaySY ProcVal inputi |
-- A System Instance is considered a special process
-- | System Instance
SysIns PrimSysDef [inputi]
---------
-- NlEdge
---------
-- FIXME: The NLNodeOut should merely be an integer
-- | The node connection is carried out by directed edges modelled as
-- Unsafe Unmutable References (allowing to share nodes) connected
-- in the output->input direction (remember we are using trees).
-- Since the node to which the edge is directed can have various outputs
-- (e.g a system instance) the edge is tagged to indicate to what
-- output it refers to.
data NlEdge node = NlEdge (ForSyDe.Deep.OSharing.URef node) NlNodeOut
-- FIXME: output tags are ugly, create a variant of NlNode which takes outputs in account
-- | The different outputs which the different nodes can have
data NlNodeOut = InPortOut |
ConstOut |
ZipWithNSYOut |
ZipWithxSYOut |
UnzipNSYOut Int |
UnzipxSYOut Int |
DelaySYOut |
SysInsOut PortId
deriving (Show, Eq)
-- | Get the output tags of a node
outTags :: NlNode a -> [NlNodeOut]
outTags (InPort _) = [InPortOut]
outTags (Proc _ proc) =
case proc of
Const _ -> [ConstOut]
ZipWithNSY _ _ -> [ZipWithNSYOut]
ZipWithxSY _ _ -> [ZipWithxSYOut]
UnzipNSY types _ _ -> map UnzipNSYOut [1..length types]
UnzipxSY _ nout _ _ -> map UnzipxSYOut [1..nout]
DelaySY _ _ -> [DelaySYOut]
SysIns primSysDefRef _ ->
map (SysInsOut . fst) ((oIface . readURef . unPrimSysDef) primSysDefRef)
------------
-- NlTree
------------
-- | We tie the knot to connect nodes through 'NlEdge's, building a Tree which
-- can have shared nodes.
--
-- That is done by storing 'NlTree's as the the input information of each node
-- of the tree. Child nodes of the tree are closer to the inputs of the system
-- and parents are closer to the outputs.
newtype NlTree = NlTree {rootEdge :: (NlEdge (NlNode NlTree))}
-----------
-- NlSignal
-----------
-- | A 'NlTree', or more preciselly its root 'NlEdge', is after all, how
-- signals are implemented in the netlist.
type NlSignal = NlTree
-- | Get the tag of a signal
nlSignalNlOut :: NlSignal -> NlNodeOut
nlSignalNlOut (NlTree (NlEdge _ tag)) = tag
---------
-- Signal
---------
-- | A signal can be seen as wire which carries values of certain type
-- and which can be connected and processed by the two computational
-- entities of a ForSyDe system: processes and block instances.
--
-- A Signal is internally represented as an edge of the graph representing
-- the system netlist.
-- The phantom type parameter ensures type-consistency for the signal
-- processing functions.
newtype Signal a = Signal {unSignal :: NlSignal}
deriving Typeable
-------------------
-- Helper functions
-------------------
-- FIXME: All these newWhatever functions probably shouldn't be here
-- | Generate a signal pointing to an 'InPort' node
newInPort :: PortId -> NlSignal
newInPort id = NlTree (NlEdge (newURef (InPort id)) InPortOut)
-- | Generate a reference to a new 'SysIns' node
newSysIns :: ProcId -> SysDef a -> [NlSignal]
-> URef (NlNode NlSignal)
newSysIns id (SysDef primSysDef) inputInfo =
newURef (Proc id (SysIns primSysDef inputInfo))
-- | Generate the output signal of a node
newNodeOutSig :: URef (NlNode NlSignal) -- ^ Reference to the node
-> NlNodeOut -- ^ Output tag
-> NlSignal
newNodeOutSig ref mTag = NlTree (NlEdge ref mTag)
-- | Evaluate the output of a process within a synchronous period
-- The inputs and outputs are given in dynamic form
eval :: NlNode Dynamic -> [(NlNodeOut, Dynamic)]
eval node = case node of
InPort _ -> intError evalStr (EvalErr "InPort")
Proc _ proc -> case proc of
Const pv -> [(ConstOut, dyn pv)]
ZipWithNSY fun dynArgs
-> [(ZipWithNSYOut, foldl1 dynApp ((tval fun) : dynArgs))]
ZipWithxSY fun dynListArg
-> [(ZipWithxSYOut, (tval fun) dynListArg)]
UnzipNSY _ fun dynArg
-> zipWith (\n dyn -> (UnzipNSYOut n, dyn))
[1..]
(fun dynArg)
UnzipxSY _ _ fun dynArg
-> zipWith (\n dyn -> (UnzipxSYOut n, dyn))
[1..]
(fun dynArg)
DelaySY _ _
-> intError evalStr (EvalErr "DelaySY")
SysIns _ _
-> intError evalStr (EvalErr "SysIns")
where evalStr = "ForSyDe.Netlist.eval"