diff options
Diffstat (limited to 'src/VeriFuzz/Graph')
-rw-r--r-- | src/VeriFuzz/Graph/ASTGen.hs | 86 | ||||
-rw-r--r-- | src/VeriFuzz/Graph/CodeGen.hs | 60 | ||||
-rw-r--r-- | src/VeriFuzz/Graph/Random.hs | 58 | ||||
-rw-r--r-- | src/VeriFuzz/Graph/RandomAlt.hs | 29 |
4 files changed, 233 insertions, 0 deletions
diff --git a/src/VeriFuzz/Graph/ASTGen.hs b/src/VeriFuzz/Graph/ASTGen.hs new file mode 100644 index 0000000..2b241e1 --- /dev/null +++ b/src/VeriFuzz/Graph/ASTGen.hs @@ -0,0 +1,86 @@ +{-| +Module : VeriFuzz.Graph.ASTGen +Description : Generates the AST from the graph directly. +Copyright : (c) 2018-2019, Yann Herklotz Grave +License : BSD-3 +Maintainer : ymherklotz [at] gmail [dot] com +Stability : experimental +Portability : POSIX + +Generates the AST from the graph directly. +-} + +module VeriFuzz.Graph.ASTGen where + +import Data.Foldable (fold) +import Data.Graph.Inductive (LNode, Node) +import qualified Data.Graph.Inductive as G +import Data.Maybe (catMaybes) +import qualified Data.Text as T +import VeriFuzz.Circuit +import VeriFuzz.Internal.Gen +import VeriFuzz.Internal.Shared +import VeriFuzz.Verilog.AST +import VeriFuzz.Verilog.Helpers + +-- | Converts a 'CNode' to an 'Identifier'. +frNode :: Node -> Identifier +frNode = Identifier . fromNode + +-- | Converts a 'Gate' to a 'BinaryOperator', which should be a bijective +-- mapping. +fromGate :: Gate -> BinaryOperator +fromGate And = BinAnd +fromGate Or = BinOr +fromGate Xor = BinXor + +inputsC :: Circuit -> [Node] +inputsC c = + inputs (getCircuit c) + +outputsC :: Circuit -> [Node] +outputsC c = + outputs (getCircuit c) + +genPortsAST :: (Circuit -> [Node]) -> Circuit -> [Port] +genPortsAST f c = + port . frNode <$> f c + where + port = Port Wire 4 + +-- | Generates the nested expression AST, so that it can then generate the +-- assignment expressions. +genAssignExpr :: Gate -> [Node] -> Maybe Expr +genAssignExpr g [] = Nothing +genAssignExpr g [n] = Just . Id $ frNode n +genAssignExpr g (n:ns) = BinOp wire op <$> genAssignExpr g ns + where + wire = Id $ frNode n + op = fromGate g + +-- | Generate the continuous assignment AST for a particular node. If it does +-- not have any nodes that link to it then return 'Nothing', as that means that +-- the assignment will just be empty. +genContAssignAST :: Circuit -> LNode Gate -> Maybe ModItem +genContAssignAST c (n, g) = ModCA . ContAssign name <$> genAssignExpr g nodes + where + gr = getCircuit c + nodes = G.pre gr n + name = frNode n + +genAssignAST :: Circuit -> [ModItem] +genAssignAST c = catMaybes $ genContAssignAST c <$> nodes + where + gr = getCircuit c + nodes = G.labNodes gr + +genModuleDeclAST :: Circuit -> ModDecl +genModuleDeclAST c = ModDecl id output ports items + where + id = Identifier "gen_module" + ports = genPortsAST inputsC c + output = [Port Wire 90 "y"] + items = genAssignAST c ++ [ModCA . ContAssign "y" . fold $ portToExpr <$> ports] + +generateAST :: Circuit -> VerilogSrc +generateAST c = VerilogSrc [Description $ genModuleDeclAST c] diff --git a/src/VeriFuzz/Graph/CodeGen.hs b/src/VeriFuzz/Graph/CodeGen.hs new file mode 100644 index 0000000..0d23044 --- /dev/null +++ b/src/VeriFuzz/Graph/CodeGen.hs @@ -0,0 +1,60 @@ +{-| +Module : VeriFuzz.Graph.Random +Description : Code generation directly from DAG. +Copyright : (c) 2018-2019, Yann Herklotz Grave +License : BSD-3 +Maintainer : ymherklotz [at] gmail [dot] com +Stability : experimental +Portability : POSIX + +Define the code generation directly from the random DAG. +-} + +module VeriFuzz.Graph.CodeGen + ( generate + ) where + +import Data.Foldable (fold) +import Data.Graph.Inductive (Graph, LNode, Node, indeg, labNodes, + nodes, outdeg, pre) +import Data.Maybe (fromMaybe) +import Data.Text (Text) +import qualified Data.Text as T +import VeriFuzz.Circuit +import VeriFuzz.Internal.Gen +import VeriFuzz.Internal.Shared + +toOperator :: Gate -> Text +toOperator And = " & " +toOperator Or = " | " +toOperator Xor = " ^ " + +statList :: Gate -> [Node] -> Maybe Text +statList g n = toStr <$> safe tail n + where + toStr = fold . fmap ((<> toOperator g) . fromNode) + +lastEl :: [Node] -> Maybe Text +lastEl n = fromNode <$> safe head n + +toStmnt :: (Graph gr) => gr Gate e -> LNode Gate -> Text +toStmnt graph (n, g) = + fromMaybe T.empty $ Just " assign " <> Just (fromNode n) + <> Just " = " <> statList g nodeL <> lastEl nodeL <> Just ";\n" + where + nodeL = pre graph n + +generate :: (Graph gr) => gr Gate e -> Text +generate graph = + "module generated_module(\n" + <> fold (imap " input wire " ",\n" inp) + <> T.intercalate ",\n" (imap " output wire " "" out) + <> ");\n" + <> fold (toStmnt graph <$> labNodes graph) + <> "endmodule\n\nmodule main;\n initial\n begin\n " + <> "$display(\"Hello, world\");\n $finish;\n " + <> "end\nendmodule" + where + inp = inputs graph + out = outputs graph + imap b e = fmap ((\s -> b <> s <> e) . fromNode) diff --git a/src/VeriFuzz/Graph/Random.hs b/src/VeriFuzz/Graph/Random.hs new file mode 100644 index 0000000..0514f6d --- /dev/null +++ b/src/VeriFuzz/Graph/Random.hs @@ -0,0 +1,58 @@ +{-| +Module : VeriFuzz.Graph.Random +Description : Random generation for DAG +Copyright : (c) 2018-2019, Yann Herklotz Grave +License : BSD-3 +Maintainer : ymherklotz [at] gmail [dot] com +Stability : experimental +Portability : POSIX + +Define the random generation for the directed acyclic graph. +-} + +module VeriFuzz.Graph.Random where + +import Data.Graph.Inductive (Context, Graph, LEdge) +import qualified Data.Graph.Inductive as G +import Data.Graph.Inductive.PatriciaTree (Gr) +import Data.List (nub) +import Test.QuickCheck (Arbitrary, Gen) +import qualified Test.QuickCheck as QC + +dupFolder :: (Eq a, Eq b) => Context a b -> [Context a b] -> [Context a b] +dupFolder cont ns = + unique cont : ns + where + unique (a, b, c, d) = (nub a, b, c, nub d) + +-- | Remove duplicates. +rDups :: (Eq a, Eq b) => Gr a b -> Gr a b +rDups g = G.buildGr $ G.ufold dupFolder [] g + +-- | Gen instance to create an arbitrary edge, where the edges are limited by +-- `n` that is passed to it. +arbitraryEdge :: (Arbitrary e) => Int -> Gen (LEdge e) +arbitraryEdge n = do + x <- with $ \a -> a < n && a > 0 && a /= n-1 + y <- with $ \a -> x < a && a < n && a > 0 + z <- QC.arbitrary + return (x, y, z) + where + with = QC.suchThat $ QC.resize n QC.arbitrary + +-- | Gen instance for a random acyclic DAG. +randomDAG :: (Arbitrary l, Arbitrary e, Eq l, Eq e) + => Gen (Gr l e) -- ^ The generated graph. It uses Arbitrary to + -- generate random instances of each node +randomDAG = do + list <- QC.infiniteListOf QC.arbitrary + l <- QC.infiniteListOf aE + QC.sized (\n -> return . G.mkGraph (nodes list n) $ take (10*n) l) + where + nodes l n = zip [0..n] $ take n l + aE = QC.sized arbitraryEdge + +-- | Generate a random acyclic DAG with an IO instance. +genRandomDAG :: (Arbitrary l, Arbitrary e, Eq l, Eq e) + => IO (Gr l e) +genRandomDAG = QC.generate randomDAG diff --git a/src/VeriFuzz/Graph/RandomAlt.hs b/src/VeriFuzz/Graph/RandomAlt.hs new file mode 100644 index 0000000..d9ee138 --- /dev/null +++ b/src/VeriFuzz/Graph/RandomAlt.hs @@ -0,0 +1,29 @@ +{-|p +Module : VeriFuzz.Graph.RandomAlt +Description : RandomAlt generation for DAG +Copyright : (c) 2018-2019, Yann Herklotz Grave +License : BSD-3 +Maintainer : ymherklotz [at] gmail [dot] com +Stability : experimental +Portability : POSIX + +Define the random generation for the directed acyclic graph. +-} + +module VeriFuzz.Graph.RandomAlt where + +import Data.Graph.Inductive (Graph, LEdge, mkGraph) +import qualified Data.Graph.Inductive.Arbitrary as G +import Data.Graph.Inductive.PatriciaTree (Gr) +import Test.QuickCheck (Arbitrary, Gen) +import qualified Test.QuickCheck as QC + +randomDAG :: (Arbitrary l, Arbitrary e) + => Gen (Gr l e) +randomDAG = + G.looplessGraph <$> QC.arbitrary + +-- | Generate a random acyclic DAG with an IO instance. +genRandomDAG :: (Arbitrary l, Arbitrary e) + => IO (Gr l e) +genRandomDAG = QC.generate randomDAG |