Added Yosys Manual

1 files changed, 289 insertions, 0 deletions

diff --git a/manual/CHAPTER_StateOfTheArt.tex b/manual/CHAPTER_StateOfTheArt.tex
new file mode 100644
index 00000000..d6a5c9b1
--- /dev/null
+++ b/manual/CHAPTER_StateOfTheArt.tex
@@ -0,0 +1,289 @@
+
+\chapter{Evaluation of other OSS Verilog Synthesis Tools}
+\label{chapter:sota}
+
+In this appendix\footnote{This appendix is an updated version of an
+unpublished student research paper. \cite{VerilogFossEval}}
+the existing FOSS Verilog synthesis tools\footnote{To the
+author's best knowledge, all relevant tools that existed at the time of this
+writing are included. But as there is no formal channel through which such
+tools are published it is hard to give any guarantees in that matter.} are
+evaluated. Extremely limited or application specific tools (e.g.~pure Verilog
+Netlist parsers) as well as Verilog simulators are not included. These existing
+solutions are tested using a set of representative Verilog code snippets. It is
+shown that no existing FOSS tool implements even close to a sufficient subset
+of Verilog to be usable as synthesis tool for a wide range existing Verilog code.
+
+The packages evaluated are:
+
+\begin{itemize}
+\item Icarus Verilog \citeweblink{Icarus}\footnote{Icarus Verilog is mainly a simulation
+tool but also supported synthesis up to version 0.8. Therefore version 0.8.7 is used
+for this evaluation.)}
+\item Verilog-to-Routing (VTR) / Odin-II \cite{vtr2012}\cite{Odin}\citeweblink{VTR}
+\item HDL Analyzer and Netlist Architect (HANA) \citeweblink{HANA}
+\item Verilog front-end to VIS (vl2mv) \cite{Cheng93vl2mv:a}\citeweblink{VIS}
+\end{itemize}
+
+In each of the following sections Verilog modules that test a certain Verilog
+language feature are presented and the support for these features is tested in all
+the tools mentioned above. It is evaluated whether the tools under test
+successfully generate netlists for the Verilog input and whether these netlists
+match the simulation behavior of the designs using testbenches.
+
+All test cases are verified to be synthesizeable using Xilinx XST from the Xilinx
+WebPACK \citeweblink{XilinxWebPACK} suite.
+
+Trivial features such as support for simple structural Verilog are not explicitly tested.
+
+Vl2mv and Odin-II generate output in the BLIF (Berkeley Logic Interchange
+Format) and BLIF-MV (an extended version of BLIF) formats respectively.
+ABC \citeweblink{ABC} is used to convert this output to Verilog for verification
+using testbenches.
+
+Icarus Verilog generates EDIF (Electronic Design Interchange Format) output
+utilizing LPM (Library of Parameterized Modules) cells. The EDIF files are
+converted to Verilog using edif2ngd and netgen from Xilinx WebPACK. A
+hand-written implementation of the LPM cells utilized by the generated netlists
+is used for verification.
+
+Following these functional tests, a quick analysis of the extensibility of the tools
+under test is provided in a separate section.
+
+The last section of this chapter finally concludes these series of evaluations
+with a summary of the results.
+
+\begin{figure}[t!]
+	\begin{minipage}{7.7cm}
+		\lstinputlisting[numbers=left,frame=single,language=Verilog]{FILES_StateOfTheArt/always01_pub.v}
+	\end{minipage}
+	\hfill
+	\begin{minipage}{7.7cm}
+		\lstinputlisting[frame=single,language=Verilog]{FILES_StateOfTheArt/always02_pub.v}
+	\end{minipage}
+	\caption{1st and 2nd Verilog always examples}
+	\label{fig:StateOfTheArt_always12}
+\end{figure}
+
+\begin{figure}[!]
+	\lstinputlisting[numbers=left,frame=single,language=Verilog]{FILES_StateOfTheArt/always03.v}
+	\caption{3rd Verilog always example}
+	\label{fig:StateOfTheArt_always3}
+\end{figure}
+
+\section{Always blocks and blocking vs.~nonblocking assignments}
+\label{sec:blocking_nonblocking}
+
+The ``always''-block is one of the most fundamental non-trivial Verilog
+language features.  It can be used to model a combinatorial path (with optional
+registers on the outputs) in a way that mimics a regular programming language.
+
+Within an always block, if- and case-statements can be used to model multiplexers.
+Blocking assignments ($=$) and nonblocking assignments ($<=$) are used to populate the
+leaf-nodes of these multiplexer trees. Unassigned leaf-nodes default to feedback
+paths that cause the output register to hold the previous value. More advanced
+synthesis tools often convert these feedback paths to register enable signals or
+even generate circuits with clock gating.
+
+Registers assigned with nonblocking assignments ($<=$) behave differently from
+variables in regular programming languages: In a simulation they are not
+updated immediately after being assigned.  Instead the right-hand sides are
+evaluated and the results stored in temporary memory locations. After all
+pending updates have been prepared in this way they are executed, thus yielding
+semi-parallel execution of all nonblocking assignments.
+
+For synthesis this means that every occurrence of that register in an expression
+addresses the output port of the corresponding register regardless of the question whether the register
+has been assigned a new value in an earlier command in the same always block.
+Therefore with nonblocking assignments the order of the assignments has no effect
+on the resulting circuit as long as the left-hand sides of the assignments are
+unique.
+
+The three example codes in Fig.~\ref{fig:StateOfTheArt_always12} and
+Fig.~\ref{fig:StateOfTheArt_always3} use all these features and can thus be used
+to test the synthesis tools capabilities to synthesize always blocks correctly.
+
+The first example is only using the most fundamental Verilog features. All
+tools under test were able to successfully synthesize this design.
+
+\begin{figure}[b!]
+	\lstinputlisting[numbers=left,frame=single,language=Verilog]{FILES_StateOfTheArt/arrays01.v}
+	\caption{Verilog array example}
+	\label{fig:StateOfTheArt_arrays}
+\end{figure}
+
+The 2nd example is functionally identical to the 1st one but is using an
+if-statement inside the always block. Odin-II fails to synthesize it and
+instead produces the following error message:
+
+\begin{verbatim}
+ERROR: (File: always02.v) (Line number: 13)
+You've defined the driver "count~0" twice
+\end{verbatim}
+
+Vl2mv does not produce an error message but outputs an invalid synthesis result
+that is not using the reset input at all.
+
+Icarus Verilog also doesn't produce an error message but generates an invalid output
+for this 2nd example. The code generated by Icarus Verilog only implements the reset
+path for the count register, effectively setting the output to constant 0.
+
+So of all tools under test only HANA was able to create correct synthesis results
+for the 2nd example.
+
+The 3rd example is using blocking and nonblocking assignments and many if statements.
+Odin also fails to synthesize this example:
+
+\begin{verbatim}
+ERROR: (File: always03.v) (Line number: 8)
+ODIN doesn't handle blocking statements in Sequential blocks
+\end{verbatim}
+
+HANA, Icarus Verilog and vl2mv create invalid synthesis results for the 3rd example.
+
+So unfortunately none of the tools under test provide a complete and correct
+implementation of blocking and nonblocking assignments.
+
+\section{Arrays for memory modelling}
+
+Verilog arrays are part of the synthesizeable subset of Verilog and are
+commonly used to model addressable memory. The Verilog code in
+Fig.~\ref{fig:StateOfTheArt_arrays} demonstrates this by implementing a single
+port memory.
+
+For this design HANA, vl2m and ODIN-II generate error messages indicating that
+arrays are not supported.
+
+\begin{figure}[t!]
+	\lstinputlisting[numbers=left,frame=single,language=Verilog]{FILES_StateOfTheArt/forgen01.v}
+	\caption{Verilog for loop example}
+	\label{fig:StateOfTheArt_for}
+\end{figure}
+
+Icarus Verilog produces an invalid output that is using the address only for
+reads. Instead of using the address input for writes, the generated design
+simply loads the data to all memory locations whenever the write-enable input
+is active, effectively turning the design into a single 4-bit D-Flip-Flop with
+enable input.
+
+As all tools under test already fail this simple test, there is nothing to gain
+by continuing tests on this aspect of Verilog synthesis such as synthesis of dual port
+memories, correct handling of write collisions, and so forth.
+
+\begin{figure}[t!]
+	\lstinputlisting[numbers=left,frame=single,language=Verilog]{FILES_StateOfTheArt/forgen02.v}
+	\caption{Verilog generate example}
+	\label{fig:StateOfTheArt_gen}
+\end{figure}
+
+\section{For-loops and generate blocks}
+
+For-loops and generate blocks are more advanced Verilog features. These features
+allow the circuit designer to add program code to her design that is evaluated
+during synthesis to generate (parts of) the circuits description; something that
+could only be done using a code generator otherwise.
+
+For-loops are only allowed in synthesizeable Verilog if they can be completely
+unrolled. Then they can be a powerful tool to generate array logic or static
+lookup tables. The code in Fig.~\ref{fig:StateOfTheArt_for} generates a circuit that
+tests a 5 bit value for being a prime number using a static lookup table.
+
+Generate blocks can be used to model array logic in complex parametric designs. The
+code in Fig.~\ref{fig:StateOfTheArt_gen} implements a ripple-carry adder with
+parametric width from simple assign-statements and logic operations using a Verilog
+generate block.
+
+All tools under test failed to synthesize both test cases. HANA creates invalid
+output in both cases. Icarus Verilog creates invalid output for the first
+test and fails with an error for the second case. The other two tools fail with
+error messages for both tests.
+
+\section{Extensibility}
+
+This section briefly discusses the extensibility of the tools under test and
+their internal data- and control-flow.  As all tools under test already failed
+to synthesize simple Verilog always-blocks correctly, not much resources have
+been spent on evaluating the extensibility of these tools and therefore only a
+very brief discussion of the topic is provided here.
+
+HANA synthesizes for a built-in library of standard cells using two passes over
+an AST representation of the Verilog input. This approach executes fast but
+limits the extensibility as everything happens in only two comparable complex
+AST walks and there is no universal intermediate representation that is flexible
+enough to be used in arbitrary optimizations.
+
+Odin-II and vl2m are both front ends to existing synthesis flows. As such they
+only try to quickly convert the Verilog input into the internal representation
+of their respective flows (BLIF). So extensibility is less of an issue here as
+potential extensions would likely be implemented in other components of the
+flow.
+
+Icarus Verilog is clearly designed to be a simulation tool rather than a
+synthesis tool. The synthesis part of Icarus Verilog is an ad-hoc add-on to
+Icarus Verilog that aims at converting an internal representation that is meant
+for generation of a virtual machine based simulation code to netlists.
+
+\section{Summary and Outlook}
+
+Table~\ref{tab:StateOfTheArt_sum} summarizes the tests performed. Clearly none
+of the tools under test make a serious attempt at providing a feature-complete
+implementation of Verilog. It can be argued that Odin-II performed best in the
+test as it never generated incorrect code but instead produced error messages
+indicating that unsupported Verilog features where used in the Verilog input.
+
+In conclusion, to the best knowledge of the author, there is no FOSS Verilog
+synthesis tool other than Yosys that is anywhere near feature completeness and
+therefore there is no other candidate for a generic Verilog front end and/or
+synthesis framework to be used as a basis for custom synthesis tools.
+
+Yosys could also replace vl2m and/or Odin-II in their respective flows or
+function as a pre-compiler that can translate full-featured Verilog code to the
+simple subset of Verilog that is understood by vl2m and Odin-II.
+
+Yosys is designed for extensibility. It can be used as-is to synthesize Verilog
+code to netlists, but its main purpose is to be used as basis for custom tools.
+Yosys is structured in a language dependent Verilog front end and language
+independent synthesis code (which is in itself structured in independent
+passes). This architecture will simplify implementing additional HDL front
+ends and/or additional synthesis passes.
+
+Chapter~\ref{chapter:eval} contains a more detailed evaluation of Yosys using real-world
+designes that are far out of reach for any of the other tools discussed in this appendix.
+
+\vskip2cm
+\begin{table}[h]
+	%             yosys       hana        vis         icarus      odin
+	% always01    ok          ok          ok          ok          ok
+	% always02    ok          ok          failed      failed      error
+	% always03    ok          failed      failed      missing     error
+	% arrays01    ok          error       error       failed      error
+	% forgen01    ok          failed      error       failed      error
+	% forgen02    ok          failed      error       error       error
+	\def\ok{\ding{52}}
+	\def\error{\ding{56}}
+	\def\failed{$\skull$}
+	\def\missing{$\skull$}
+	\rowcolors{2}{gray!25}{white}
+	\centerline{
+		\begin{tabular}{|l|cccc|c|}
+		\hline
+		& \bf HANA & \bf VIS / vl2m & \bf Icarus Verilog & \bf Odin-II & \bf Yosys \\
+		\hline
+		\tt always01 &  \ok       &  \ok       &  \ok       &  \ok     & \ok \\
+		\tt always02 &  \ok       &  \failed   &  \failed   &  \error  & \ok \\
+		\tt always03 &  \failed   &  \failed   &  \missing  &  \error  & \ok \\
+		\tt arrays01 &  \error    &  \error    &  \failed   &  \error  & \ok \\
+		\tt forgen01 &  \failed   &  \error    &  \failed   &  \error  & \ok \\
+		\tt forgen02 &  \failed   &  \error    &  \error    &  \error  & \ok \\
+		\hline
+		\end{tabular}
+	}
+	\centerline{
+		\ding{52} \dots passed \hskip2em
+		\ding{56} \dots produced error \hskip2em
+		$\skull$ \dots incorrect output
+	}
+	\caption{Summary of all test results}
+	\label{tab:StateOfTheArt_sum}
+\end{table}
+