From 1eec255e60f2854b4dd1fa212f02d57eb31c9f19 Mon Sep 17 00:00:00 2001
From: KrystalDelusion <krystinedawn@yosyshq.com>
Date: Thu, 8 Dec 2022 05:54:08 +1300
Subject: Removing manual files

---
 manual/CHAPTER_Basics.tex | 839 ----------------------------------------------
 1 file changed, 839 deletions(-)
 delete mode 100644 manual/CHAPTER_Basics.tex

(limited to 'manual/CHAPTER_Basics.tex')

diff --git a/manual/CHAPTER_Basics.tex b/manual/CHAPTER_Basics.tex
deleted file mode 100644
index 5c60b7305..000000000
--- a/manual/CHAPTER_Basics.tex
+++ /dev/null
@@ -1,839 +0,0 @@
-
-\chapter{Basic Principles}
-\label{chapter:basics}
-
-This chapter contains a short introduction to the basic principles of digital
-circuit synthesis.
-
-\section{Levels of Abstraction}
-
-Digital circuits can be represented at different levels of abstraction.
-During the design process a circuit is usually first specified using a higher
-level abstraction. Implementation can then be understood as finding a
-functionally equivalent representation at a lower abstraction level.  When
-this is done automatically using software, the term {\it synthesis} is used.
-
-So synthesis is the automatic conversion of a high-level representation of a
-circuit to a functionally equivalent low-level representation of a circuit.
-Figure~\ref{fig:Basics_abstractions} lists the different levels of abstraction
-and how they relate to different kinds of synthesis.
-
-\begin{figure}[b!]
-	\hfil
-	\begin{tikzpicture}
-			\tikzstyle{lvl} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=15em]
-			\node[lvl] (sys) {System Level};
-			\node[lvl] (hl) [below of=sys] {High Level};
-			\node[lvl] (beh) [below of=hl] {Behavioral Level};
-			\node[lvl] (rtl) [below of=beh] {Register-Transfer Level (RTL)};
-			\node[lvl] (lg) [below of=rtl] {Logical Gate Level};
-			\node[lvl] (pg) [below of=lg] {Physical Gate Level};
-			\node[lvl] (sw) [below of=pg] {Switch Level};
-
-			\draw[dotted] (sys.east)  -- ++(1,0) coordinate (sysx);
-			\draw[dotted] (hl.east)  -- ++(1,0) coordinate (hlx);
-			\draw[dotted] (beh.east) -- ++(1,0) coordinate (behx);
-			\draw[dotted] (rtl.east) -- ++(1,0) coordinate (rtlx);
-			\draw[dotted] (lg.east)  -- ++(1,0) coordinate (lgx);
-			\draw[dotted] (pg.east)  -- ++(1,0) coordinate (pgx);
-			\draw[dotted] (sw.east)  -- ++(1,0) coordinate (swx);
-
-			\draw[gray,|->] (sysx) -- node[right] {System Design} (hlx);
-			\draw[|->|] (hlx) -- node[right] {High Level Synthesis (HLS)} (behx);
-			\draw[->|] (behx) -- node[right] {Behavioral Synthesis} (rtlx);
-			\draw[->|] (rtlx) -- node[right] {RTL Synthesis} (lgx);
-			\draw[->|] (lgx) -- node[right] {Logic Synthesis} (pgx);
-			\draw[gray,->|] (pgx) -- node[right] {Cell Library} (swx);
-
-			\draw[dotted] (behx) -- ++(5,0) coordinate (a);
-			\draw[dotted] (pgx) -- ++(5,0) coordinate (b);
-			\draw[|->|] (a) -- node[right] {Yosys} (b);
-	\end{tikzpicture}
-	\caption{Different levels of abstraction and synthesis.}
-	\label{fig:Basics_abstractions}
-\end{figure}
-
-Regardless of the way a lower level representation of a circuit is
-obtained (synthesis or manual design), the lower level representation is usually
-verified by comparing simulation results of the lower level and the higher level
-representation \footnote{In recent years formal equivalence
-checking also became an important verification method for validating RTL and
-lower abstraction representation of the design.}.
-Therefore even if no synthesis is used, there must still be a simulatable
-representation of the circuit in all levels to allow for verification of the
-design.
-
-Note: The exact meaning of terminology such as ``High-Level'' is of course not
-fixed over time. For example the HDL ``ABEL'' was first introduced in 1985 as ``A High-Level
-Design Language for Programmable Logic Devices'' \cite{ABEL}, but would not
-be considered a ``High-Level Language'' today.
-
-\subsection{System Level}
-
-The System Level abstraction of a system only looks at its biggest building
-blocks like CPUs and computing cores. At this level the circuit is usually described
-using traditional programming languages like C/C++ or Matlab. Sometimes special
-software libraries are used that are aimed at simulation circuits on the system
-level, such as SystemC.
-
-Usually no synthesis tools are used to automatically transform a system level
-representation of a circuit to a lower-level representation. But system level
-design tools exist that can be used to connect system level building blocks.
-
-The IEEE 1685-2009 standard defines the IP-XACT file format that can be used to
-represent designs on the system level and building blocks that can be used in
-such system level designs. \cite{IP-XACT}
-
-\subsection{High Level}
-
-The high-level abstraction of a system (sometimes referred to as {\it
-algorithmic} level) is also often represented using traditional programming
-languages, but with a reduced feature set. For example when representing a
-design at the high level abstraction in C, pointers can only be used to mimic
-concepts that can be found in hardware, such as memory interfaces. Full
-featured dynamic memory management is not allowed as it has no corresponding
-concept in digital circuits.
-
-Tools exist to synthesize high level code (usually in the form of C/C++/SystemC
-code with additional metadata) to behavioural HDL code (usually in the form of
-Verilog or VHDL code). Aside from the many commercial tools for high level synthesis
-there are also a number of FOSS tools for high level synthesis
-\citeweblink{C_to_Verilog} \citeweblink{LegUp}.
-
-\subsection{Behavioural Level}
-
-At the behavioural abstraction level a language aimed at hardware description such
-as Verilog or VHDL is used to describe the circuit, but so-called {\it behavioural
-modelling} is used in at least part of the circuit description. In behavioural
-modelling there must be a language feature that allows for imperative programming to be used to
-describe data paths and registers. This is the {\tt always}-block in Verilog and
-the {\tt process}-block in VHDL.
-
-In behavioural modelling, code fragments are provided together with a {\it
-sensitivity list}; a list of signals and conditions. In simulation, the code
-fragment is executed whenever a signal in the sensitivity list changes its
-value or a condition in the sensitivity list is triggered. A synthesis tool
-must be able to transfer this representation into an appropriate datapath followed
-by the appropriate types of register.
-
-For example consider the following Verilog code fragment:
-
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-always @(posedge clk)
-	y <= a + b;
-\end{lstlisting}
-
-In simulation the statement \lstinline[language=Verilog]{y <= a + b} is executed whenever
-a positive edge on the signal \lstinline[language=Verilog]{clk} is detected. The synthesis
-result however will contain an adder that calculates the sum \lstinline[language=Verilog]{a + b}
-all the time, followed by a d-type flip-flop with the adder output on its D-input and the
-signal \lstinline[language=Verilog]{y} on its Q-output.
-
-Usually the imperative code fragments used in behavioural modelling can contain
-statements for conditional execution (\lstinline[language=Verilog]{if}- and
-\lstinline[language=Verilog]{case}-statements in Verilog) as well as loops,
-as long as those loops can be completely unrolled.
-
-Interestingly there seems to be no other FOSS Tool that is capable of
-performing Verilog or VHDL behavioural syntheses besides Yosys (see
-App.~\ref{chapter:sota}).
-
-\subsection{Register-Transfer Level (RTL)}
-
-On the Register-Transfer Level the design is represented by combinatorial data
-paths and registers (usually d-type flip flops). The following Verilog code fragment
-is equivalent to the previous Verilog example, but is in RTL representation:
-
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-assign tmp = a + b;       // combinatorial data path
-
-always @(posedge clk)     // register
-	y <= tmp;
-\end{lstlisting}
-
-A design in RTL representation is usually stored using HDLs like Verilog and VHDL. But only
-a very limited subset of features is used, namely minimalistic {\tt always}-blocks (Verilog)
-or {\tt process}-blocks (VHDL) that model the register type used and unconditional assignments
-for the datapath logic. The use of HDLs on this level simplifies simulation as no additional
-tools are required to simulate a design in RTL representation.
-
-Many optimizations and analyses can be performed best at the RTL level. Examples include FSM
-detection and optimization, identification of memories or other larger building blocks
-and identification of shareable resources.
-
-Note that RTL is the first abstraction level in which the circuit is represented as a
-graph of circuit elements (registers and combinatorial cells) and signals. Such a graph,
-when encoded as list of cells and connections, is called a netlist.
-
-RTL synthesis is easy as each circuit node element in the netlist can simply be replaced
-with an equivalent gate-level circuit. However, usually the term {\it RTL synthesis} does
-not only refer to synthesizing an RTL netlist to a gate level netlist but also to performing
-a number of highly sophisticated optimizations within the RTL representation, such as
-the examples listed above.
-
-A number of FOSS tools exist that can perform isolated tasks within the domain of RTL
-synthesis steps. But there seems to be no FOSS tool that covers a wide range of RTL
-synthesis operations.
-
-\subsection{Logical Gate Level}
-
-At the logical gate level the design is represented by a netlist that uses only
-cells from a small number of single-bit cells, such as basic logic gates (AND,
-OR, NOT, XOR, etc.) and registers (usually D-Type Flip-flops).
-
-A number of netlist formats exists that can be used on this level, e.g.~the Electronic Design
-Interchange Format (EDIF), but for ease of simulation often a HDL netlist is used. The latter
-is a HDL file (Verilog or VHDL) that only uses the most basic language constructs for instantiation
-and connecting of cells.
-
-There are two challenges in logic synthesis: First finding opportunities for optimizations
-within the gate level netlist and second the optimal (or at least good) mapping of the logic
-gate netlist to an equivalent netlist of physically available gate types.
-
-The simplest approach to logic synthesis is {\it two-level logic synthesis}, where a logic function
-is converted into a sum-of-products representation, e.g.~using a Karnaugh map.
-This is a simple approach, but has exponential worst-case effort and cannot make efficient use of
-physical gates other than AND/NAND-, OR/NOR- and NOT-Gates.
-
-Therefore modern logic synthesis tools utilize much more complicated {\it multi-level logic
-synthesis} algorithms \cite{MultiLevelLogicSynth}. Most of these algorithms convert the
-logic function to a Binary-Decision-Diagram (BDD) or And-Inverter-Graph (AIG) and work from that
-representation. The former has the advantage that it has a unique normalized form. The latter has
-much better worst case performance and is therefore better suited for the synthesis of large
-logic functions.
-
-Good FOSS tools exists for multi-level logic synthesis \citeweblink{ABC}
-\citeweblink{AIGER} \citeweblink{MVSIS}.
-
-Yosys contains basic logic synthesis functionality but can also use ABC
-\citeweblink{ABC} for the logic synthesis step. Using ABC is recommended.
-
-\subsection{Physical Gate Level}
-
-On the physical gate level only gates are used that are physically available on
-the target architecture. In some cases this may only be NAND, NOR and NOT gates as well as
-D-Type registers. In other cases this might include cells that are more complex than the cells
-used at the logical gate level (e.g.~complete half-adders). In the case of an FPGA-based
-design the physical gate level representation is a netlist of LUTs with optional output
-registers, as these are the basic building blocks of FPGA logic cells.
-
-For the synthesis tool chain this abstraction is usually the lowest level. In
-case of an ASIC-based design the cell library might contain further information on
-how the physical cells map to individual switches (transistors).
-
-\subsection{Switch Level}
-
-A switch level representation of a circuit is a netlist utilizing single transistors as cells.
-Switch level modelling is possible in Verilog and VHDL, but is seldom used in modern designs,
-as in modern digital ASIC or FPGA flows the physical gates are considered the atomic build blocks
-of the logic circuit.
-
-\subsection{Yosys}
-
-Yosys is a Verilog HDL synthesis tool. This means that it takes a behavioural
-design description as input and generates an RTL, logical gate or physical gate
-level description of the design as output.  Yosys' main strengths are behavioural
-and RTL synthesis. A wide range of commands (synthesis passes) exist
-within Yosys that can be used to perform a wide range of synthesis tasks within
-the domain of behavioural, rtl and logic synthesis. Yosys is designed to be
-extensible and therefore is a good basis for implementing custom synthesis
-tools for specialised tasks.
-
-\section{Features of Synthesizable Verilog}
-
-The subset of Verilog \cite{Verilog2005} that is synthesizable is specified in
-a separate IEEE standards document, the IEEE standard 1364.1-2002 \cite{VerilogSynth}.
-This standard also describes how certain language constructs are to be interpreted in
-the scope of synthesis.
-
-This section provides a quick overview of the most important features of
-synthesizable Verilog, structured in order of increasing complexity.
-
-\subsection{Structural Verilog}
-
-{\it Structural Verilog} (also known as {\it Verilog Netlists}) is a Netlist in
-Verilog syntax. Only the following language constructs are used in this case:
-
-\begin{itemize}
-\item Constant values
-\item Wire and port declarations
-\item Static assignments of signals to other signals
-\item Cell instantiations
-\end{itemize}
-
-Many tools (especially at the back end of the synthesis chain) only support
-structural Verilog as input. ABC is an example of such a tool. Unfortunately
-there is no standard specifying what {\it Structural Verilog} actually is,
-leading to some confusion about what syntax constructs are supported in
-structural Verilog when it comes to features such as attributes or multi-bit
-signals.
-
-\subsection{Expressions in Verilog}
-
-In all situations where Verilog accepts a constant value or signal name,
-expressions using arithmetic operations such as
-\lstinline[language=Verilog]{+}, \lstinline[language=Verilog]{-} and \lstinline[language=Verilog]{*},
-boolean operations such as
-\lstinline[language=Verilog]{&} (AND), \lstinline[language=Verilog]{|} (OR) and \lstinline[language=Verilog]{^} (XOR)
-and many others (comparison operations, unary operator, etc.) can also be used.
-
-During synthesis these operators are replaced by cells that implement the respective function.
-
-Many FOSS tools that claim to be able to process Verilog in fact only support
-basic structural Verilog and simple expressions. Yosys can be used to convert
-full featured synthesizable Verilog to this simpler subset, thus enabling such
-applications to be used with a richer set of Verilog features.
-
-\subsection{Behavioural Modelling}
-
-Code that utilizes the Verilog {\tt always} statement is using {\it Behavioural
-Modelling}. In behavioural modelling, a circuit is described by means of imperative
-program code that is executed on certain events, namely any change, a rising
-edge, or a falling edge of a signal. This is a very flexible construct during
-simulation but is only synthesizable when one of the following is modelled:
-
-\begin{itemize}
-\item {\bf Asynchronous or latched logic} \\
-In this case the sensitivity list must contain all expressions that are used within
-the {\tt always} block. The syntax \lstinline[language=Verilog]{@*} can be used
-for these cases. Examples of this kind include:
-
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-// asynchronous
-always @* begin
-	if (add_mode)
-		y <= a + b;
-	else
-		y <= a - b;
-end
-
-// latched
-always @* begin
-	if (!hold)
-		y <= a + b;
-end
-\end{lstlisting}
-
-Note that latched logic is often considered bad style and in many cases just
-the result of sloppy HDL design. Therefore many synthesis tools generate warnings
-whenever latched logic is generated.
-
-\item {\bf Synchronous logic (with optional synchronous reset)} \\
-This is logic with d-type flip-flops on the output. In this case the sensitivity
-list must only contain the respective clock edge. Example:
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-// counter with synchronous reset
-always @(posedge clk) begin
-	if (reset)
-		y <= 0;
-	else
-		y <= y + 1;
-end
-\end{lstlisting}
-
-\item {\bf Synchronous logic with asynchronous reset} \\
-This is logic with d-type flip-flops with asynchronous resets on the output. In
-this case the sensitivity list must only contain the respective clock and reset edges.
-The values assigned in the reset branch must be constant. Example:
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-// counter with asynchronous reset
-always @(posedge clk, posedge reset) begin
-	if (reset)
-		y <= 0;
-	else
-		y <= y + 1;
-end
-\end{lstlisting}
-\end{itemize}
-
-Many synthesis tools support a wider subset of flip-flops that can be modelled
-using {\tt always}-statements (including Yosys). But only the ones listed above
-are covered by the Verilog synthesis standard and when writing new designs one
-should limit herself or himself to these cases.
-
-In behavioural modelling, blocking assignments (=) and non-blocking assignments
-(<=) can be used. The concept of blocking vs.~non-blocking assignment is one
-of the most misunderstood constructs in Verilog \cite{Cummings00}.
-
-The blocking assignment behaves exactly like an assignment in any imperative
-programming language, while with the non-blocking assignment the right hand side
-of the assignment is evaluated immediately but the actual update of the left
-hand side register is delayed until the end of the time-step. For example the Verilog
-code \lstinline[language=Verilog]{a <= b; b <= a;} exchanges the values of
-the two registers. See Sec.~\ref{sec:blocking_nonblocking} for a more
-detailed description of this behaviour.
-
-\subsection{Functions and Tasks}
-
-Verilog supports {\it Functions} and {\it Tasks} to bundle statements that are
-used in multiple places (similar to {\it Procedures} in imperative programming).
-Both constructs can be implemented easily by substituting the function/task-call
-with the body of the function or task.
-
-\subsection{Conditionals, Loops and Generate-Statements}
-
-Verilog supports \lstinline[language=Verilog]{if-else}-statements and
-\lstinline[language=Verilog]{for}-loops inside \lstinline[language=Verilog]{always}-statements.
-
-It also supports both features in \lstinline[language=Verilog]{generate}-statements
-on the module level. This can be used to selectively enable or disable parts of the
-module based on the module parameters (\lstinline[language=Verilog]{if-else})
-or to generate a set of similar subcircuits (\lstinline[language=Verilog]{for}).
-
-While the \lstinline[language=Verilog]{if-else}-statement
-inside an always-block is part of behavioural modelling, the three other cases
-are (at least for a synthesis tool) part of a built-in macro processor. Therefore it must
-be possible for the synthesis tool to completely unroll all loops and evaluate the
-condition in all \lstinline[language=Verilog]{if-else}-statement in
-\lstinline[language=Verilog]{generate}-statements using const-folding.
-
-Examples for this can be found in Fig.~\ref{fig:StateOfTheArt_for} and
-Fig.~\ref{fig:StateOfTheArt_gen} in App.~\ref{chapter:sota}.
-
-\subsection{Arrays and Memories}
-
-Verilog supports arrays. This is in general a synthesizable language feature.
-In most cases arrays can be synthesized by generating addressable memories.
-However, when complex or asynchronous access patterns are used, it is not
-possible to model an array as memory. In these cases the array must
-be modelled using individual signals for each word and all accesses to the array
-must be implemented using large multiplexers.
-
-In some cases it would be possible to model an array using memories, but it
-is not desired. Consider the following delay circuit:
-\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
-module (clk, in_data, out_data);
-
-parameter BITS = 8;
-parameter STAGES = 4;
-
-input clk;
-input [BITS-1:0] in_data;
-output [BITS-1:0] out_data;
-reg [BITS-1:0] ffs [STAGES-1:0];
-
-integer i;
-always @(posedge clk) begin
-	ffs[0] <= in_data;
-	for (i = 1; i < STAGES; i = i+1)
-		ffs[i] <= ffs[i-1];
-end
-
-assign out_data = ffs[STAGES-1];
-
-endmodule
-\end{lstlisting}
-
-This could be implemented using an addressable memory with {\tt STAGES} input
-and output ports. A better implementation would be to use a simple chain of flip-flops
-(a so-called shift register).
-This better implementation can either be obtained by first creating a memory-based
-implementation and then optimizing it based on the static address signals for all ports
-or directly identifying such situations in the language front end and converting
-all memory accesses to direct accesses to the correct signals.
-
-\section{Challenges in Digital Circuit Synthesis}
-
-This section summarizes the most important challenges in digital circuit
-synthesis. Tools can be characterized by how well they address these topics.
-
-\subsection{Standards Compliance}
-
-The most important challenge is compliance with the HDL standards in question (in case
-of Verilog the IEEE Standards 1364.1-2002 and 1364-2005). This can be broken down in two
-items:
-
-\begin{itemize}
-\item Completeness of implementation of the standard
-\item Correctness of implementation of the standard
-\end{itemize}
-
-Completeness is mostly important to guarantee compatibility
-with existing HDL code. Once a design has been verified and tested, HDL designers
-are very reluctant regarding changes to the design, even if it is only about
-a few minor changes to work around a missing feature in a new synthesis tool.
-
-Correctness is crucial. In some areas this is obvious (such as
-correct synthesis of basic behavioural models). But it is also crucial for the
-areas that concern minor details of the standard, such as the exact rules
-for handling signed expressions, even when the HDL code does not target
-different synthesis tools. This is because (unlike software source code that
-is only processed by compilers), in most design flows HDL code is not only
-processed by the synthesis tool but also by one or more simulators and sometimes
-even a formal verification tool. It is key for this verification process
-that all these tools use the same interpretation for the HDL code.
-
-\subsection{Optimizations}
-
-Generally it is hard to give a one-dimensional description of how well a synthesis tool
-optimizes the design. First of all because not all optimizations are applicable to all
-designs and all synthesis tasks. Some optimizations work (best) on a coarse-grained level
-(with complex cells such as adders or multipliers) and others work (best) on a fine-grained
-level (single bit gates). Some optimizations target area and others target speed.
-Some work well on large designs while others don't scale well and can only be applied
-to small designs.
-
-A good tool is capable of applying a wide range of optimizations at different
-levels of abstraction and gives the designer control over which optimizations
-are performed (or skipped) and what the optimization goals are.
-
-\subsection{Technology Mapping}
-
-Technology mapping is the process of converting the design into a netlist of
-cells that are available in the target architecture. In an ASIC flow this might
-be the process-specific cell library provided by the fab. In an FPGA flow this
-might be LUT cells as well as special function units such as dedicated multipliers.
-In a coarse-grain flow this might even be more complex special function units.
-
-An open and vendor independent tool is especially of interest if it supports
-a wide range of different types of target architectures.
-
-\section{Script-Based Synthesis Flows}
-
-A digital design is usually started by implementing a high-level or
-system-level simulation of the desired function. This description is then
-manually transformed (or re-implemented) into a synthesizable lower-level
-description (usually at the behavioural level) and the equivalence of the
-two representations is verified by simulating both and comparing the simulation
-results.
-
-Then the synthesizable description is transformed to lower-level
-representations using a series of tools and the results are again verified
-using simulation. This process is illustrated in Fig.~\ref{fig:Basics_flow}.
-
-\begin{figure}[t!]
-	\hfil
-	\begin{tikzpicture}
-			\tikzstyle{manual} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=8em, node distance=10em]
-			\tikzstyle{auto} = [draw, fill=orange!10, rectangle, minimum height=2em, minimum width=8em, node distance=10em]
-
-			\node[manual] (sys) {\begin{minipage}{8em}
-				\center
-				System Level \\
-				Model
-			\end{minipage}};
-			\node[manual] (beh) [right of=sys] {\begin{minipage}{8em}
-				\center
-				Behavioral \\
-				Model
-			\end{minipage}};
-			\node[auto] (rtl) [right of=beh] {\begin{minipage}{8em}
-				\center
-				RTL \\
-				Model
-			\end{minipage}};
-			\node[auto] (gates) [right of=rtl] {\begin{minipage}{8em}
-				\center
-				Gate-Level \\
-				Model
-			\end{minipage}};
-
-			\draw[-latex] (beh) edge[double, bend left] node[above] {synthesis} (rtl);
-			\draw[-latex] (rtl) edge[double, bend left] node[above] {synthesis} (gates);
-
-			\draw[latex-latex] (sys) edge[bend right] node[below] {verify} (beh);
-			\draw[latex-latex] (beh) edge[bend right] node[below] {verify} (rtl);
-			\draw[latex-latex] (rtl) edge[bend right] node[below] {verify} (gates);
-	\end{tikzpicture}
-	\caption{Typical design flow. Green boxes represent manually created models. Orange boxes represent
-	models generated by synthesis tools.}
-	\label{fig:Basics_flow}
-\end{figure}
-
-In this example the System Level Model and the Behavioural Model are both
-manually written design files. After the equivalence of system level model
-and behavioural model has been verified, the lower level representations of the
-design can be generated using synthesis tools. Finally the RTL Model and
-the Gate-Level Model are verified and the design process is finished.
-
-However, in any real-world design effort there will be multiple iterations for
-this design process. The reason for this can be the late change of a design
-requirement or the fact that the analysis of a low-abstraction model (e.g.~gate-level
-timing analysis) revealed that a design change is required in order to meet
-the design requirements (e.g.~maximum possible clock speed).
-
-Whenever the behavioural model or the system level model is
-changed their equivalence must be re-verified by re-running the simulations
-and comparing the results. Whenever the behavioural model is changed the
-synthesis must be re-run and the synthesis results must be re-verified.
-
-In order to guarantee reproducibility it is important to be able to re-run all
-automatic steps in a design project with a fixed set of settings easily.
-Because of this, usually all programs used in a synthesis flow can be
-controlled using scripts. This means that all functions are available via
-text commands. When such a tool provides a GUI, this is complementary to,
-and not instead of, a command line interface.
-
-Usually a synthesis flow in an UNIX/Linux environment would be controlled by a
-shell script that calls all required tools (synthesis and simulation/verification
-in this example) in the correct order. Each of these tools would be called with
-a script file containing commands for the respective tool. All settings required
-for the tool would be provided by these script files so that no manual interaction
-would be necessary. These script files are considered design sources and should
-be kept under version control just like the source code of the system level and the
-behavioural model.
-
-\section{Methods from Compiler Design}
-
-Some parts of synthesis tools involve problem domains that are traditionally known from
-compiler design. This section addresses some of these domains.
-
-\subsection{Lexing and Parsing}
-
-The best known concepts from compiler design are probably {\it lexing} and {\it parsing}.
-These are two methods that together can be used to process complex computer languages
-easily. \cite{Dragonbook}
-
-A {\it lexer} consumes single characters from the input and generates a stream of {\it lexical
-tokens} that consist of a {\it type} and a {\it value}. For example the Verilog input
-``\lstinline[language=Verilog]{assign foo = bar + 42;}'' might be translated by the lexer
-to the list of lexical tokens given in Tab.~\ref{tab:Basics_tokens}.
-
-\begin{table}[t]
-\hfil
-\begin{tabular}{ll}
-Token-Type & Token-Value \\
-\hline
-\tt TOK\_ASSIGN & - \\
-\tt TOK\_IDENTIFIER & ``{\tt foo}'' \\
-\tt TOK\_EQ & - \\
-\tt TOK\_IDENTIFIER & ``{\tt bar}'' \\
-\tt TOK\_PLUS & - \\
-\tt TOK\_NUMBER & 42 \\
-\tt TOK\_SEMICOLON & - \\
-\end{tabular}
-\caption{Exemplary token list for the statement ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.}
-\label{tab:Basics_tokens}
-\end{table}
-
-The lexer is usually generated by a lexer generator (e.g.~{\tt flex} \citeweblink{flex}) from a
-description file that is using regular expressions to specify the text pattern that should match
-the individual tokens.
-
-The lexer is also responsible for skipping ignored characters (such as whitespace outside string
-constants and comments in the case of Verilog) and converting the original text snippet to a token
-value.
-
-Note that individual keywords use different token types (instead of a keyword type with different
-token values). This is because the parser usually can only use the Token-Type to make a decision on
-the grammatical role of a token.
-
-The parser then transforms the list of tokens into a parse tree that closely resembles the productions
-from the computer languages grammar. As the lexer, the parser is also typically generated by a code
-generator (e.g.~{\tt bison} \citeweblink{bison}) from a grammar description in Backus-Naur Form (BNF).
-
-Let's consider the following BNF (in Bison syntax):
-
-\begin{lstlisting}[numbers=left,frame=single]
-assign_stmt: TOK_ASSIGN TOK_IDENTIFIER TOK_EQ expr TOK_SEMICOLON;
-expr: TOK_IDENTIFIER | TOK_NUMBER | expr TOK_PLUS expr;
-\end{lstlisting}
-
-\begin{figure}[b!]
-	\hfil
-	\begin{tikzpicture}
-			\tikzstyle{node} = [draw, fill=green!10, ellipse, minimum height=2em, minimum width=8em, node distance=10em]
-
-			\draw (+0,+1) node[node] (n1) {\tt assign\_stmt};
-
-			\draw (-6,-1) node[node] (n11) {\tt TOK\_ASSIGN};
-			\draw (-3,-2) node[node] (n12) {\tt TOK\_IDENTIFIER};
-			\draw (+0,-1) node[node] (n13) {\tt TOK\_EQ};
-			\draw (+3,-2) node[node] (n14) {\tt expr};
-			\draw (+6,-1) node[node] (n15) {\tt TOK\_SEMICOLON};
-
-			\draw (-1,-4) node[node] (n141) {\tt expr};
-			\draw (+3,-4) node[node] (n142) {\tt TOK\_PLUS};
-			\draw (+7,-4) node[node] (n143) {\tt expr};
-
-			\draw (-1,-5.5) node[node] (n1411) {\tt TOK\_IDENTIFIER};
-			\draw (+7,-5.5) node[node] (n1431) {\tt TOK\_NUMBER};
-
-			\draw[-latex] (n1) -- (n11);
-			\draw[-latex] (n1) -- (n12);
-			\draw[-latex] (n1) -- (n13);
-			\draw[-latex] (n1) -- (n14);
-			\draw[-latex] (n1) -- (n15);
-
-			\draw[-latex] (n14) -- (n141);
-			\draw[-latex] (n14) -- (n142);
-			\draw[-latex] (n14) -- (n143);
-
-			\draw[-latex] (n141) -- (n1411);
-			\draw[-latex] (n143) -- (n1431);
-	\end{tikzpicture}
-	\caption{Example parse tree for the Verilog expression ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.}
-	\label{fig:Basics_parsetree}
-\end{figure}
-
-The parser converts the token list to the parse tree in Fig.~\ref{fig:Basics_parsetree}. Note that the parse
-tree never actually exists as a whole as data structure in memory. Instead the parser calls user-specified
-code snippets (so-called {\it reduce-functions}) for all inner nodes of the parse tree in depth-first order.
-
-In some very simple applications (e.g.~code generation for stack machines) it is possible to perform the
-task at hand directly in the reduce functions. But usually the reduce functions are only used to build an in-memory
-data structure with the relevant information from the parse tree. This data structure is called an {\it abstract
-syntax tree} (AST).
-
-The exact format for the abstract syntax tree is application specific (while the format of the parse tree and token
-list are mostly dictated by the grammar of the language at hand). Figure~\ref{fig:Basics_ast} illustrates what an
-AST for the parse tree in Fig.~\ref{fig:Basics_parsetree} could look like.
-
-Usually the AST is then converted into yet another representation that is more suitable for further processing.
-In compilers this is often an assembler-like three-address-code intermediate representation. \cite{Dragonbook}
-
-\begin{figure}[t]
-	\hfil
-	\begin{tikzpicture}
-			\tikzstyle{node} = [draw, fill=green!10, ellipse, minimum height=2em, minimum width=8em, node distance=10em]
-
-			\draw (+0,+0) node[node] (n1) {\tt ASSIGN};
-
-			\draw (-2,-2) node[node] (n11) {\tt ID: foo};
-			\draw (+2,-2) node[node] (n12) {\tt PLUS};
-
-			\draw (+0,-4) node[node] (n121) {\tt ID: bar};
-			\draw (+4,-4) node[node] (n122) {\tt CONST: 42};
-
-			\draw[-latex] (n1) -- (n11);
-			\draw[-latex] (n1) -- (n12);
-
-			\draw[-latex] (n12) -- (n121);
-			\draw[-latex] (n12) -- (n122);
-	\end{tikzpicture}
-	\caption{Example abstract syntax tree for the Verilog expression ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.}
-	\label{fig:Basics_ast}
-\end{figure}
-
-\subsection{Multi-Pass Compilation}
-
-Complex problems are often best solved when split up into smaller problems. This is certainly true
-for compilers as well as for synthesis tools. The components responsible for solving the smaller problems can
-be connected in two different ways: through {\it Single-Pass Pipelining} and by using {\it Multiple Passes}.
-
-Traditionally a parser and lexer are connected using the pipelined approach: The lexer provides a function that
-is called by the parser. This function reads data from the input until a complete lexical token has been read. Then
-this token is returned to the parser. So the lexer does not first generate a complete list of lexical tokens
-and then pass it to the parser. Instead they run concurrently and the parser can consume tokens as
-the lexer produces them.
-
-The single-pass pipelining approach has the advantage of lower memory footprint (at no time must the complete design
-be kept in memory) but has the disadvantage of tighter coupling between the interacting components.
-
-Therefore single-pass pipelining should only be used when the lower memory footprint is required or the
-components are also conceptually tightly coupled. The latter certainly is the case for a parser and its lexer.
-But when data is passed between two conceptually loosely coupled components it is often
-beneficial to use a multi-pass approach.
-
-In the multi-pass approach the first component processes all the data and the result is stored in a in-memory
-data structure. Then the second component is called with this data. This reduces complexity, as only one
-component is running at a time. It also improves flexibility as components can be exchanged easier.
-
-Most modern compilers are multi-pass compilers.
-
-\iffalse
-\subsection{Static Single Assignment Form}
-
-In imperative programming (and behavioural HDL design) it is possible to assign the same variable multiple times.
-This can either mean that the variable is independently used in two different contexts or that the final value
-of the variable depends on a condition.
-
-The following examples show C code in which one variable is used independently in two different contexts:
-
-\begin{minipage}{7.7cm}
-\begin{lstlisting}[numbers=left,frame=single,language=C++]
-void demo1()
-{
-	int a = 1;
-	printf("%d\n", a);
-
-	a = 2;
-	printf("%d\n", a);
-}
-\end{lstlisting}
-\end{minipage}
-\hfil
-\begin{minipage}{7.7cm}
-\begin{lstlisting}[frame=single,language=C++]
-void demo1()
-{
-	int a = 1;
-	printf("%d\n", a);
-
-	int b = 2;
-	printf("%d\n", b);
-}
-\end{lstlisting}
-\end{minipage}
-
-\begin{minipage}{7.7cm}
-\begin{lstlisting}[numbers=left,frame=single,language=C++]
-void demo2(bool foo)
-{
-	int a;
-	if (foo) {
-		a = 23;
-		printf("%d\n", a);
-	} else {
-		a = 42;
-		printf("%d\n", a);
-	}
-}
-\end{lstlisting}
-\end{minipage}
-\hfil
-\begin{minipage}{7.7cm}
-\begin{lstlisting}[frame=single,language=C++]
-void demo2(bool foo)
-{
-	int a, b;
-	if (foo) {
-		a = 23;
-		printf("%d\n", a);
-	} else {
-		b = 42;
-		printf("%d\n", b);
-	}
-}
-\end{lstlisting}
-\end{minipage}
-
-In both examples the left version (only variable \lstinline[language=C++]{a}) and the right version (variables
-\lstinline[language=Verilog]{a} and \lstinline[language=Verilog]{b}) are equivalent. Therefore it is
-desired for further processing to bring the code in an equivalent form for both cases.
-
-In the following example the variable is assigned twice but it cannot be easily replaced by two variables:
-
-\begin{lstlisting}[frame=single,language=C++]
-void demo3(bool foo)
-{
-	int a = 23
-	if (foo)
-		a = 42;
-	printf("%d\n", a);
-}
-\end{lstlisting}
-
-Static single assignment (SSA) form is a representation of imperative code that uses identical representations
-for the left and right version of demos 1 and 2, but can still represent demo 3. In SSA form each assignment
-assigns a new variable (usually written with an index). But it also introduces a special $\Phi$-function to
-merge the different instances of a variable when needed. In C-pseudo-code the demo 3 would be written as follows
-using SSA from:
-
-\begin{lstlisting}[frame=single,language=C++]
-void demo3(bool foo)
-{
-	int a_1, a_2, a_3;
-	a_1 = 23
-	if (foo)
-		a_2 = 42;
-	a_3 = phi(a_1, a_2);
-	printf("%d\n", a_3);
-}
-\end{lstlisting}
-
-The $\Phi$-function is usually interpreted as ``these variables must be stored
-in the same memory location'' during code generation. Most modern compilers for imperative languages
-such as C/C++ use SSA form for at least some of its passes as it is very easy to manipulate and analyse.
-\fi
-
-- 
cgit v1.2.3

