1 2\chapter{Basic Principles} 3\label{chapter:basics} 4 5This chapter contains a short introduction to the basic principles of digital 6circuit synthesis. 7 8\section{Levels of Abstraction} 9 10Digital circuits can be represented at different levels of abstraction. 11During the design process a circuit is usually first specified using a higher 12level abstraction. Implementation can then be understood as finding a 13functionally equivalent representation at a lower abstraction level. When 14this is done automatically using software, the term {\it synthesis} is used. 15 16So synthesis is the automatic conversion of a high-level representation of a 17circuit to a functionally equivalent low-level representation of a circuit. 18Figure~\ref{fig:Basics_abstractions} lists the different levels of abstraction 19and how they relate to different kinds of synthesis. 20 21\begin{figure}[b!] 22 \hfil 23 \begin{tikzpicture} 24 \tikzstyle{lvl} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=15em] 25 \node[lvl] (sys) {System Level}; 26 \node[lvl] (hl) [below of=sys] {High Level}; 27 \node[lvl] (beh) [below of=hl] {Behavioral Level}; 28 \node[lvl] (rtl) [below of=beh] {Register-Transfer Level (RTL)}; 29 \node[lvl] (lg) [below of=rtl] {Logical Gate Level}; 30 \node[lvl] (pg) [below of=lg] {Physical Gate Level}; 31 \node[lvl] (sw) [below of=pg] {Switch Level}; 32 33 \draw[dotted] (sys.east) -- ++(1,0) coordinate (sysx); 34 \draw[dotted] (hl.east) -- ++(1,0) coordinate (hlx); 35 \draw[dotted] (beh.east) -- ++(1,0) coordinate (behx); 36 \draw[dotted] (rtl.east) -- ++(1,0) coordinate (rtlx); 37 \draw[dotted] (lg.east) -- ++(1,0) coordinate (lgx); 38 \draw[dotted] (pg.east) -- ++(1,0) coordinate (pgx); 39 \draw[dotted] (sw.east) -- ++(1,0) coordinate (swx); 40 41 \draw[gray,|->] (sysx) -- node[right] {System Design} (hlx); 42 \draw[|->|] (hlx) -- node[right] {High Level Synthesis (HLS)} (behx); 43 \draw[->|] (behx) -- node[right] {Behavioral Synthesis} (rtlx); 44 \draw[->|] (rtlx) -- node[right] {RTL Synthesis} (lgx); 45 \draw[->|] (lgx) -- node[right] {Logic Synthesis} (pgx); 46 \draw[gray,->|] (pgx) -- node[right] {Cell Library} (swx); 47 48 \draw[dotted] (behx) -- ++(5,0) coordinate (a); 49 \draw[dotted] (pgx) -- ++(5,0) coordinate (b); 50 \draw[|->|] (a) -- node[right] {Yosys} (b); 51 \end{tikzpicture} 52 \caption{Different levels of abstraction and synthesis.} 53 \label{fig:Basics_abstractions} 54\end{figure} 55 56Regardless of the way a lower level representation of a circuit is 57obtained (synthesis or manual design), the lower level representation is usually 58verified by comparing simulation results of the lower level and the higher level 59representation \footnote{In recent years formal equivalence 60checking also became an important verification method for validating RTL and 61lower abstraction representation of the design.}. 62Therefore even if no synthesis is used, there must still be a simulatable 63representation of the circuit in all levels to allow for verification of the 64design. 65 66Note: The exact meaning of terminology such as ``High-Level'' is of course not 67fixed over time. For example the HDL ``ABEL'' was first introduced in 1985 as ``A High-Level 68Design Language for Programmable Logic Devices'' \cite{ABEL}, but would not 69be considered a ``High-Level Language'' today. 70 71\subsection{System Level} 72 73The System Level abstraction of a system only looks at its biggest building 74blocks like CPUs and computing cores. At this level the circuit is usually described 75using traditional programming languages like C/C++ or Matlab. Sometimes special 76software libraries are used that are aimed at simulation circuits on the system 77level, such as SystemC. 78 79Usually no synthesis tools are used to automatically transform a system level 80representation of a circuit to a lower-level representation. But system level 81design tools exist that can be used to connect system level building blocks. 82 83The IEEE 1685-2009 standard defines the IP-XACT file format that can be used to 84represent designs on the system level and building blocks that can be used in 85such system level designs. \cite{IP-XACT} 86 87\subsection{High Level} 88 89The high-level abstraction of a system (sometimes referred to as {\it 90algorithmic} level) is also often represented using traditional programming 91languages, but with a reduced feature set. For example when representing a 92design at the high level abstraction in C, pointers can only be used to mimic 93concepts that can be found in hardware, such as memory interfaces. Full 94featured dynamic memory management is not allowed as it has no corresponding 95concept in digital circuits. 96 97Tools exist to synthesize high level code (usually in the form of C/C++/SystemC 98code with additional metadata) to behavioural HDL code (usually in the form of 99Verilog or VHDL code). Aside from the many commercial tools for high level synthesis 100there are also a number of FOSS tools for high level synthesis 101\citeweblink{C_to_Verilog} \citeweblink{LegUp}. 102 103\subsection{Behavioural Level} 104 105At the behavioural abstraction level a language aimed at hardware description such 106as Verilog or VHDL is used to describe the circuit, but so-called {\it behavioural 107modelling} is used in at least part of the circuit description. In behavioural 108modelling there must be a language feature that allows for imperative programming to be used to 109describe data paths and registers. This is the {\tt always}-block in Verilog and 110the {\tt process}-block in VHDL. 111 112In behavioural modelling, code fragments are provided together with a {\it 113sensitivity list}; a list of signals and conditions. In simulation, the code 114fragment is executed whenever a signal in the sensitivity list changes its 115value or a condition in the sensitivity list is triggered. A synthesis tool 116must be able to transfer this representation into an appropriate datapath followed 117by the appropriate types of register. 118 119For example consider the following Verilog code fragment: 120 121\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 122always @(posedge clk) 123 y <= a + b; 124\end{lstlisting} 125 126In simulation the statement \lstinline[language=Verilog]{y <= a + b} is executed whenever 127a positive edge on the signal \lstinline[language=Verilog]{clk} is detected. The synthesis 128result however will contain an adder that calculates the sum \lstinline[language=Verilog]{a + b} 129all the time, followed by a d-type flip-flop with the adder output on its D-input and the 130signal \lstinline[language=Verilog]{y} on its Q-output. 131 132Usually the imperative code fragments used in behavioural modelling can contain 133statements for conditional execution (\lstinline[language=Verilog]{if}- and 134\lstinline[language=Verilog]{case}-statements in Verilog) as well as loops, 135as long as those loops can be completely unrolled. 136 137Interestingly there seems to be no other FOSS Tool that is capable of 138performing Verilog or VHDL behavioural syntheses besides Yosys (see 139App.~\ref{chapter:sota}). 140 141\subsection{Register-Transfer Level (RTL)} 142 143On the Register-Transfer Level the design is represented by combinatorial data 144paths and registers (usually d-type flip flops). The following Verilog code fragment 145is equivalent to the previous Verilog example, but is in RTL representation: 146 147\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 148assign tmp = a + b; // combinatorial data path 149 150always @(posedge clk) // register 151 y <= tmp; 152\end{lstlisting} 153 154A design in RTL representation is usually stored using HDLs like Verilog and VHDL. But only 155a very limited subset of features is used, namely minimalistic {\tt always}-blocks (Verilog) 156or {\tt process}-blocks (VHDL) that model the register type used and unconditional assignments 157for the datapath logic. The use of HDLs on this level simplifies simulation as no additional 158tools are required to simulate a design in RTL representation. 159 160Many optimizations and analyses can be performed best at the RTL level. Examples include FSM 161detection and optimization, identification of memories or other larger building blocks 162and identification of shareable resources. 163 164Note that RTL is the first abstraction level in which the circuit is represented as a 165graph of circuit elements (registers and combinatorial cells) and signals. Such a graph, 166when encoded as list of cells and connections, is called a netlist. 167 168RTL synthesis is easy as each circuit node element in the netlist can simply be replaced 169with an equivalent gate-level circuit. However, usually the term {\it RTL synthesis} does 170not only refer to synthesizing an RTL netlist to a gate level netlist but also to performing 171a number of highly sophisticated optimizations within the RTL representation, such as 172the examples listed above. 173 174A number of FOSS tools exist that can perform isolated tasks within the domain of RTL 175synthesis steps. But there seems to be no FOSS tool that covers a wide range of RTL 176synthesis operations. 177 178\subsection{Logical Gate Level} 179 180At the logical gate level the design is represented by a netlist that uses only 181cells from a small number of single-bit cells, such as basic logic gates (AND, 182OR, NOT, XOR, etc.) and registers (usually D-Type Flip-flops). 183 184A number of netlist formats exists that can be used on this level, e.g.~the Electronic Design 185Interchange Format (EDIF), but for ease of simulation often a HDL netlist is used. The latter 186is a HDL file (Verilog or VHDL) that only uses the most basic language constructs for instantiation 187and connecting of cells. 188 189There are two challenges in logic synthesis: First finding opportunities for optimizations 190within the gate level netlist and second the optimal (or at least good) mapping of the logic 191gate netlist to an equivalent netlist of physically available gate types. 192 193The simplest approach to logic synthesis is {\it two-level logic synthesis}, where a logic function 194is converted into a sum-of-products representation, e.g.~using a Karnaugh map. 195This is a simple approach, but has exponential worst-case effort and cannot make efficient use of 196physical gates other than AND/NAND-, OR/NOR- and NOT-Gates. 197 198Therefore modern logic synthesis tools utilize much more complicated {\it multi-level logic 199synthesis} algorithms \cite{MultiLevelLogicSynth}. Most of these algorithms convert the 200logic function to a Binary-Decision-Diagram (BDD) or And-Inverter-Graph (AIG) and work from that 201representation. The former has the advantage that it has a unique normalized form. The latter has 202much better worst case performance and is therefore better suited for the synthesis of large 203logic functions. 204 205Good FOSS tools exists for multi-level logic synthesis \citeweblink{ABC} 206\citeweblink{AIGER} \citeweblink{MVSIS}. 207 208Yosys contains basic logic synthesis functionality but can also use ABC 209\citeweblink{ABC} for the logic synthesis step. Using ABC is recommended. 210 211\subsection{Physical Gate Level} 212 213On the physical gate level only gates are used that are physically available on 214the target architecture. In some cases this may only be NAND, NOR and NOT gates as well as 215D-Type registers. In other cases this might include cells that are more complex than the cells 216used at the logical gate level (e.g.~complete half-adders). In the case of an FPGA-based 217design the physical gate level representation is a netlist of LUTs with optional output 218registers, as these are the basic building blocks of FPGA logic cells. 219 220For the synthesis tool chain this abstraction is usually the lowest level. In 221case of an ASIC-based design the cell library might contain further information on 222how the physical cells map to individual switches (transistors). 223 224\subsection{Switch Level} 225 226A switch level representation of a circuit is a netlist utilizing single transistors as cells. 227Switch level modelling is possible in Verilog and VHDL, but is seldom used in modern designs, 228as in modern digital ASIC or FPGA flows the physical gates are considered the atomic build blocks 229of the logic circuit. 230 231\subsection{Yosys} 232 233Yosys is a Verilog HDL synthesis tool. This means that it takes a behavioural 234design description as input and generates an RTL, logical gate or physical gate 235level description of the design as output. Yosys' main strengths are behavioural 236and RTL synthesis. A wide range of commands (synthesis passes) exist 237within Yosys that can be used to perform a wide range of synthesis tasks within 238the domain of behavioural, rtl and logic synthesis. Yosys is designed to be 239extensible and therefore is a good basis for implementing custom synthesis 240tools for specialised tasks. 241 242\section{Features of Synthesizable Verilog} 243 244The subset of Verilog \cite{Verilog2005} that is synthesizable is specified in 245a separate IEEE standards document, the IEEE standard 1364.1-2002 \cite{VerilogSynth}. 246This standard also describes how certain language constructs are to be interpreted in 247the scope of synthesis. 248 249This section provides a quick overview of the most important features of 250synthesizable Verilog, structured in order of increasing complexity. 251 252\subsection{Structural Verilog} 253 254{\it Structural Verilog} (also known as {\it Verilog Netlists}) is a Netlist in 255Verilog syntax. Only the following language constructs are used in this case: 256 257\begin{itemize} 258\item Constant values 259\item Wire and port declarations 260\item Static assignments of signals to other signals 261\item Cell instantiations 262\end{itemize} 263 264Many tools (especially at the back end of the synthesis chain) only support 265structural Verilog as input. ABC is an example of such a tool. Unfortunately 266there is no standard specifying what {\it Structural Verilog} actually is, 267leading to some confusion about what syntax constructs are supported in 268structural Verilog when it comes to features such as attributes or multi-bit 269signals. 270 271\subsection{Expressions in Verilog} 272 273In all situations where Verilog accepts a constant value or signal name, 274expressions using arithmetic operations such as 275\lstinline[language=Verilog]{+}, \lstinline[language=Verilog]{-} and \lstinline[language=Verilog]{*}, 276boolean operations such as 277\lstinline[language=Verilog]{&} (AND), \lstinline[language=Verilog]{|} (OR) and \lstinline[language=Verilog]{^} (XOR) 278and many others (comparison operations, unary operator, etc.) can also be used. 279 280During synthesis these operators are replaced by cells that implement the respective function. 281 282Many FOSS tools that claim to be able to process Verilog in fact only support 283basic structural Verilog and simple expressions. Yosys can be used to convert 284full featured synthesizable Verilog to this simpler subset, thus enabling such 285applications to be used with a richer set of Verilog features. 286 287\subsection{Behavioural Modelling} 288 289Code that utilizes the Verilog {\tt always} statement is using {\it Behavioural 290Modelling}. In behavioural modelling, a circuit is described by means of imperative 291program code that is executed on certain events, namely any change, a rising 292edge, or a falling edge of a signal. This is a very flexible construct during 293simulation but is only synthesizable when one of the following is modelled: 294 295\begin{itemize} 296\item {\bf Asynchronous or latched logic} \\ 297In this case the sensitivity list must contain all expressions that are used within 298the {\tt always} block. The syntax \lstinline[language=Verilog]{@*} can be used 299for these cases. Examples of this kind include: 300 301\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 302// asynchronous 303always @* begin 304 if (add_mode) 305 y <= a + b; 306 else 307 y <= a - b; 308end 309 310// latched 311always @* begin 312 if (!hold) 313 y <= a + b; 314end 315\end{lstlisting} 316 317Note that latched logic is often considered bad style and in many cases just 318the result of sloppy HDL design. Therefore many synthesis tools generate warnings 319whenever latched logic is generated. 320 321\item {\bf Synchronous logic (with optional synchronous reset)} \\ 322This is logic with d-type flip-flops on the output. In this case the sensitivity 323list must only contain the respective clock edge. Example: 324\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 325// counter with synchronous reset 326always @(posedge clk) begin 327 if (reset) 328 y <= 0; 329 else 330 y <= y + 1; 331end 332\end{lstlisting} 333 334\item {\bf Synchronous logic with asynchronous reset} \\ 335This is logic with d-type flip-flops with asynchronous resets on the output. In 336this case the sensitivity list must only contain the respective clock and reset edges. 337The values assigned in the reset branch must be constant. Example: 338\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 339// counter with asynchronous reset 340always @(posedge clk, posedge reset) begin 341 if (reset) 342 y <= 0; 343 else 344 y <= y + 1; 345end 346\end{lstlisting} 347\end{itemize} 348 349Many synthesis tools support a wider subset of flip-flops that can be modelled 350using {\tt always}-statements (including Yosys). But only the ones listed above 351are covered by the Verilog synthesis standard and when writing new designs one 352should limit herself or himself to these cases. 353 354In behavioural modelling, blocking assignments (=) and non-blocking assignments 355(<=) can be used. The concept of blocking vs.~non-blocking assignment is one 356of the most misunderstood constructs in Verilog \cite{Cummings00}. 357 358The blocking assignment behaves exactly like an assignment in any imperative 359programming language, while with the non-blocking assignment the right hand side 360of the assignment is evaluated immediately but the actual update of the left 361hand side register is delayed until the end of the time-step. For example the Verilog 362code \lstinline[language=Verilog]{a <= b; b <= a;} exchanges the values of 363the two registers. See Sec.~\ref{sec:blocking_nonblocking} for a more 364detailed description of this behaviour. 365 366\subsection{Functions and Tasks} 367 368Verilog supports {\it Functions} and {\it Tasks} to bundle statements that are 369used in multiple places (similar to {\it Procedures} in imperative programming). 370Both constructs can be implemented easily by substituting the function/task-call 371with the body of the function or task. 372 373\subsection{Conditionals, Loops and Generate-Statements} 374 375Verilog supports \lstinline[language=Verilog]{if-else}-statements and 376\lstinline[language=Verilog]{for}-loops inside \lstinline[language=Verilog]{always}-statements. 377 378It also supports both features in \lstinline[language=Verilog]{generate}-statements 379on the module level. This can be used to selectively enable or disable parts of the 380module based on the module parameters (\lstinline[language=Verilog]{if-else}) 381or to generate a set of similar subcircuits (\lstinline[language=Verilog]{for}). 382 383While the \lstinline[language=Verilog]{if-else}-statement 384inside an always-block is part of behavioural modelling, the three other cases 385are (at least for a synthesis tool) part of a built-in macro processor. Therefore it must 386be possible for the synthesis tool to completely unroll all loops and evaluate the 387condition in all \lstinline[language=Verilog]{if-else}-statement in 388\lstinline[language=Verilog]{generate}-statements using const-folding. 389 390Examples for this can be found in Fig.~\ref{fig:StateOfTheArt_for} and 391Fig.~\ref{fig:StateOfTheArt_gen} in App.~\ref{chapter:sota}. 392 393\subsection{Arrays and Memories} 394 395Verilog supports arrays. This is in general a synthesizable language feature. 396In most cases arrays can be synthesized by generating addressable memories. 397However, when complex or asynchronous access patterns are used, it is not 398possible to model an array as memory. In these cases the array must 399be modelled using individual signals for each word and all accesses to the array 400must be implemented using large multiplexers. 401 402In some cases it would be possible to model an array using memories, but it 403is not desired. Consider the following delay circuit: 404\begin{lstlisting}[numbers=left,frame=single,language=Verilog] 405module (clk, in_data, out_data); 406 407parameter BITS = 8; 408parameter STAGES = 4; 409 410input clk; 411input [BITS-1:0] in_data; 412output [BITS-1:0] out_data; 413reg [BITS-1:0] ffs [STAGES-1:0]; 414 415integer i; 416always @(posedge clk) begin 417 ffs[0] <= in_data; 418 for (i = 1; i < STAGES; i = i+1) 419 ffs[i] <= ffs[i-1]; 420end 421 422assign out_data = ffs[STAGES-1]; 423 424endmodule 425\end{lstlisting} 426 427This could be implemented using an addressable memory with {\tt STAGES} input 428and output ports. A better implementation would be to use a simple chain of flip-flops 429(a so-called shift register). 430This better implementation can either be obtained by first creating a memory-based 431implementation and then optimizing it based on the static address signals for all ports 432or directly identifying such situations in the language front end and converting 433all memory accesses to direct accesses to the correct signals. 434 435\section{Challenges in Digital Circuit Synthesis} 436 437This section summarizes the most important challenges in digital circuit 438synthesis. Tools can be characterized by how well they address these topics. 439 440\subsection{Standards Compliance} 441 442The most important challenge is compliance with the HDL standards in question (in case 443of Verilog the IEEE Standards 1364.1-2002 and 1364-2005). This can be broken down in two 444items: 445 446\begin{itemize} 447\item Completeness of implementation of the standard 448\item Correctness of implementation of the standard 449\end{itemize} 450 451Completeness is mostly important to guarantee compatibility 452with existing HDL code. Once a design has been verified and tested, HDL designers 453are very reluctant regarding changes to the design, even if it is only about 454a few minor changes to work around a missing feature in a new synthesis tool. 455 456Correctness is crucial. In some areas this is obvious (such as 457correct synthesis of basic behavioural models). But it is also crucial for the 458areas that concern minor details of the standard, such as the exact rules 459for handling signed expressions, even when the HDL code does not target 460different synthesis tools. This is because (unlike software source code that 461is only processed by compilers), in most design flows HDL code is not only 462processed by the synthesis tool but also by one or more simulators and sometimes 463even a formal verification tool. It is key for this verification process 464that all these tools use the same interpretation for the HDL code. 465 466\subsection{Optimizations} 467 468Generally it is hard to give a one-dimensional description of how well a synthesis tool 469optimizes the design. First of all because not all optimizations are applicable to all 470designs and all synthesis tasks. Some optimizations work (best) on a coarse-grained level 471(with complex cells such as adders or multipliers) and others work (best) on a fine-grained 472level (single bit gates). Some optimizations target area and others target speed. 473Some work well on large designs while others don't scale well and can only be applied 474to small designs. 475 476A good tool is capable of applying a wide range of optimizations at different 477levels of abstraction and gives the designer control over which optimizations 478are performed (or skipped) and what the optimization goals are. 479 480\subsection{Technology Mapping} 481 482Technology mapping is the process of converting the design into a netlist of 483cells that are available in the target architecture. In an ASIC flow this might 484be the process-specific cell library provided by the fab. In an FPGA flow this 485might be LUT cells as well as special function units such as dedicated multipliers. 486In a coarse-grain flow this might even be more complex special function units. 487 488An open and vendor independent tool is especially of interest if it supports 489a wide range of different types of target architectures. 490 491\section{Script-Based Synthesis Flows} 492 493A digital design is usually started by implementing a high-level or 494system-level simulation of the desired function. This description is then 495manually transformed (or re-implemented) into a synthesizable lower-level 496description (usually at the behavioural level) and the equivalence of the 497two representations is verified by simulating both and comparing the simulation 498results. 499 500Then the synthesizable description is transformed to lower-level 501representations using a series of tools and the results are again verified 502using simulation. This process is illustrated in Fig.~\ref{fig:Basics_flow}. 503 504\begin{figure}[t!] 505 \hfil 506 \begin{tikzpicture} 507 \tikzstyle{manual} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=8em, node distance=10em] 508 \tikzstyle{auto} = [draw, fill=orange!10, rectangle, minimum height=2em, minimum width=8em, node distance=10em] 509 510 \node[manual] (sys) {\begin{minipage}{8em} 511 \center 512 System Level \\ 513 Model 514 \end{minipage}}; 515 \node[manual] (beh) [right of=sys] {\begin{minipage}{8em} 516 \center 517 Behavioral \\ 518 Model 519 \end{minipage}}; 520 \node[auto] (rtl) [right of=beh] {\begin{minipage}{8em} 521 \center 522 RTL \\ 523 Model 524 \end{minipage}}; 525 \node[auto] (gates) [right of=rtl] {\begin{minipage}{8em} 526 \center 527 Gate-Level \\ 528 Model 529 \end{minipage}}; 530 531 \draw[-latex] (beh) edge[double, bend left] node[above] {synthesis} (rtl); 532 \draw[-latex] (rtl) edge[double, bend left] node[above] {synthesis} (gates); 533 534 \draw[latex-latex] (sys) edge[bend right] node[below] {verify} (beh); 535 \draw[latex-latex] (beh) edge[bend right] node[below] {verify} (rtl); 536 \draw[latex-latex] (rtl) edge[bend right] node[below] {verify} (gates); 537 \end{tikzpicture} 538 \caption{Typical design flow. Green boxes represent manually created models. Orange boxes represent 539 models generated by synthesis tools.} 540 \label{fig:Basics_flow} 541\end{figure} 542 543In this example the System Level Model and the Behavioural Model are both 544manually written design files. After the equivalence of system level model 545and behavioural model has been verified, the lower level representations of the 546design can be generated using synthesis tools. Finally the RTL Model and 547the Gate-Level Model are verified and the design process is finished. 548 549However, in any real-world design effort there will be multiple iterations for 550this design process. The reason for this can be the late change of a design 551requirement or the fact that the analysis of a low-abstraction model (e.g.~gate-level 552timing analysis) revealed that a design change is required in order to meet 553the design requirements (e.g.~maximum possible clock speed). 554 555Whenever the behavioural model or the system level model is 556changed their equivalence must be re-verified by re-running the simulations 557and comparing the results. Whenever the behavioural model is changed the 558synthesis must be re-run and the synthesis results must be re-verified. 559 560In order to guarantee reproducibility it is important to be able to re-run all 561automatic steps in a design project with a fixed set of settings easily. 562Because of this, usually all programs used in a synthesis flow can be 563controlled using scripts. This means that all functions are available via 564text commands. When such a tool provides a GUI, this is complementary to, 565and not instead of, a command line interface. 566 567Usually a synthesis flow in an UNIX/Linux environment would be controlled by a 568shell script that calls all required tools (synthesis and simulation/verification 569in this example) in the correct order. Each of these tools would be called with 570a script file containing commands for the respective tool. All settings required 571for the tool would be provided by these script files so that no manual interaction 572would be necessary. These script files are considered design sources and should 573be kept under version control just like the source code of the system level and the 574behavioural model. 575 576\section{Methods from Compiler Design} 577 578Some parts of synthesis tools involve problem domains that are traditionally known from 579compiler design. This section addresses some of these domains. 580 581\subsection{Lexing and Parsing} 582 583The best known concepts from compiler design are probably {\it lexing} and {\it parsing}. 584These are two methods that together can be used to process complex computer languages 585easily. \cite{Dragonbook} 586 587A {\it lexer} consumes single characters from the input and generates a stream of {\it lexical 588tokens} that consist of a {\it type} and a {\it value}. For example the Verilog input 589``\lstinline[language=Verilog]{assign foo = bar + 42;}'' might be translated by the lexer 590to the list of lexical tokens given in Tab.~\ref{tab:Basics_tokens}. 591 592\begin{table}[t] 593\hfil 594\begin{tabular}{ll} 595Token-Type & Token-Value \\ 596\hline 597\tt TOK\_ASSIGN & - \\ 598\tt TOK\_IDENTIFIER & ``{\tt foo}'' \\ 599\tt TOK\_EQ & - \\ 600\tt TOK\_IDENTIFIER & ``{\tt bar}'' \\ 601\tt TOK\_PLUS & - \\ 602\tt TOK\_NUMBER & 42 \\ 603\tt TOK\_SEMICOLON & - \\ 604\end{tabular} 605\caption{Exemplary token list for the statement ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.} 606\label{tab:Basics_tokens} 607\end{table} 608 609The lexer is usually generated by a lexer generator (e.g.~{\tt flex} \citeweblink{flex}) from a 610description file that is using regular expressions to specify the text pattern that should match 611the individual tokens. 612 613The lexer is also responsible for skipping ignored characters (such as whitespace outside string 614constants and comments in the case of Verilog) and converting the original text snippet to a token 615value. 616 617Note that individual keywords use different token types (instead of a keyword type with different 618token values). This is because the parser usually can only use the Token-Type to make a decision on 619the grammatical role of a token. 620 621The parser then transforms the list of tokens into a parse tree that closely resembles the productions 622from the computer languages grammar. As the lexer, the parser is also typically generated by a code 623generator (e.g.~{\tt bison} \citeweblink{bison}) from a grammar description in Backus-Naur Form (BNF). 624 625Let's consider the following BNF (in Bison syntax): 626 627\begin{lstlisting}[numbers=left,frame=single] 628assign_stmt: TOK_ASSIGN TOK_IDENTIFIER TOK_EQ expr TOK_SEMICOLON; 629expr: TOK_IDENTIFIER | TOK_NUMBER | expr TOK_PLUS expr; 630\end{lstlisting} 631 632\begin{figure}[b!] 633 \hfil 634 \begin{tikzpicture} 635 \tikzstyle{node} = [draw, fill=green!10, ellipse, minimum height=2em, minimum width=8em, node distance=10em] 636 637 \draw (+0,+1) node[node] (n1) {\tt assign\_stmt}; 638 639 \draw (-6,-1) node[node] (n11) {\tt TOK\_ASSIGN}; 640 \draw (-3,-2) node[node] (n12) {\tt TOK\_IDENTIFIER}; 641 \draw (+0,-1) node[node] (n13) {\tt TOK\_EQ}; 642 \draw (+3,-2) node[node] (n14) {\tt expr}; 643 \draw (+6,-1) node[node] (n15) {\tt TOK\_SEMICOLON}; 644 645 \draw (-1,-4) node[node] (n141) {\tt expr}; 646 \draw (+3,-4) node[node] (n142) {\tt TOK\_PLUS}; 647 \draw (+7,-4) node[node] (n143) {\tt expr}; 648 649 \draw (-1,-5.5) node[node] (n1411) {\tt TOK\_IDENTIFIER}; 650 \draw (+7,-5.5) node[node] (n1431) {\tt TOK\_NUMBER}; 651 652 \draw[-latex] (n1) -- (n11); 653 \draw[-latex] (n1) -- (n12); 654 \draw[-latex] (n1) -- (n13); 655 \draw[-latex] (n1) -- (n14); 656 \draw[-latex] (n1) -- (n15); 657 658 \draw[-latex] (n14) -- (n141); 659 \draw[-latex] (n14) -- (n142); 660 \draw[-latex] (n14) -- (n143); 661 662 \draw[-latex] (n141) -- (n1411); 663 \draw[-latex] (n143) -- (n1431); 664 \end{tikzpicture} 665 \caption{Example parse tree for the Verilog expression ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.} 666 \label{fig:Basics_parsetree} 667\end{figure} 668 669The parser converts the token list to the parse tree in Fig.~\ref{fig:Basics_parsetree}. Note that the parse 670tree never actually exists as a whole as data structure in memory. Instead the parser calls user-specified 671code snippets (so-called {\it reduce-functions}) for all inner nodes of the parse tree in depth-first order. 672 673In some very simple applications (e.g.~code generation for stack machines) it is possible to perform the 674task at hand directly in the reduce functions. But usually the reduce functions are only used to build an in-memory 675data structure with the relevant information from the parse tree. This data structure is called an {\it abstract 676syntax tree} (AST). 677 678The exact format for the abstract syntax tree is application specific (while the format of the parse tree and token 679list are mostly dictated by the grammar of the language at hand). Figure~\ref{fig:Basics_ast} illustrates what an 680AST for the parse tree in Fig.~\ref{fig:Basics_parsetree} could look like. 681 682Usually the AST is then converted into yet another representation that is more suitable for further processing. 683In compilers this is often an assembler-like three-address-code intermediate representation. \cite{Dragonbook} 684 685\begin{figure}[t] 686 \hfil 687 \begin{tikzpicture} 688 \tikzstyle{node} = [draw, fill=green!10, ellipse, minimum height=2em, minimum width=8em, node distance=10em] 689 690 \draw (+0,+0) node[node] (n1) {\tt ASSIGN}; 691 692 \draw (-2,-2) node[node] (n11) {\tt ID: foo}; 693 \draw (+2,-2) node[node] (n12) {\tt PLUS}; 694 695 \draw (+0,-4) node[node] (n121) {\tt ID: bar}; 696 \draw (+4,-4) node[node] (n122) {\tt CONST: 42}; 697 698 \draw[-latex] (n1) -- (n11); 699 \draw[-latex] (n1) -- (n12); 700 701 \draw[-latex] (n12) -- (n121); 702 \draw[-latex] (n12) -- (n122); 703 \end{tikzpicture} 704 \caption{Example abstract syntax tree for the Verilog expression ``\lstinline[language=Verilog]{assign foo = bar + 42;}''.} 705 \label{fig:Basics_ast} 706\end{figure} 707 708\subsection{Multi-Pass Compilation} 709 710Complex problems are often best solved when split up into smaller problems. This is certainly true 711for compilers as well as for synthesis tools. The components responsible for solving the smaller problems can 712be connected in two different ways: through {\it Single-Pass Pipelining} and by using {\it Multiple Passes}. 713 714Traditionally a parser and lexer are connected using the pipelined approach: The lexer provides a function that 715is called by the parser. This function reads data from the input until a complete lexical token has been read. Then 716this token is returned to the parser. So the lexer does not first generate a complete list of lexical tokens 717and then pass it to the parser. Instead they run concurrently and the parser can consume tokens as 718the lexer produces them. 719 720The single-pass pipelining approach has the advantage of lower memory footprint (at no time must the complete design 721be kept in memory) but has the disadvantage of tighter coupling between the interacting components. 722 723Therefore single-pass pipelining should only be used when the lower memory footprint is required or the 724components are also conceptually tightly coupled. The latter certainly is the case for a parser and its lexer. 725But when data is passed between two conceptually loosely coupled components it is often 726beneficial to use a multi-pass approach. 727 728In the multi-pass approach the first component processes all the data and the result is stored in a in-memory 729data structure. Then the second component is called with this data. This reduces complexity, as only one 730component is running at a time. It also improves flexibility as components can be exchanged easier. 731 732Most modern compilers are multi-pass compilers. 733 734\iffalse 735\subsection{Static Single Assignment Form} 736 737In imperative programming (and behavioural HDL design) it is possible to assign the same variable multiple times. 738This can either mean that the variable is independently used in two different contexts or that the final value 739of the variable depends on a condition. 740 741The following examples show C code in which one variable is used independently in two different contexts: 742 743\begin{minipage}{7.7cm} 744\begin{lstlisting}[numbers=left,frame=single,language=C++] 745void demo1() 746{ 747 int a = 1; 748 printf("%d\n", a); 749 750 a = 2; 751 printf("%d\n", a); 752} 753\end{lstlisting} 754\end{minipage} 755\hfil 756\begin{minipage}{7.7cm} 757\begin{lstlisting}[frame=single,language=C++] 758void demo1() 759{ 760 int a = 1; 761 printf("%d\n", a); 762 763 int b = 2; 764 printf("%d\n", b); 765} 766\end{lstlisting} 767\end{minipage} 768 769\begin{minipage}{7.7cm} 770\begin{lstlisting}[numbers=left,frame=single,language=C++] 771void demo2(bool foo) 772{ 773 int a; 774 if (foo) { 775 a = 23; 776 printf("%d\n", a); 777 } else { 778 a = 42; 779 printf("%d\n", a); 780 } 781} 782\end{lstlisting} 783\end{minipage} 784\hfil 785\begin{minipage}{7.7cm} 786\begin{lstlisting}[frame=single,language=C++] 787void demo2(bool foo) 788{ 789 int a, b; 790 if (foo) { 791 a = 23; 792 printf("%d\n", a); 793 } else { 794 b = 42; 795 printf("%d\n", b); 796 } 797} 798\end{lstlisting} 799\end{minipage} 800 801In both examples the left version (only variable \lstinline[language=C++]{a}) and the right version (variables 802\lstinline[language=Verilog]{a} and \lstinline[language=Verilog]{b}) are equivalent. Therefore it is 803desired for further processing to bring the code in an equivalent form for both cases. 804 805In the following example the variable is assigned twice but it cannot be easily replaced by two variables: 806 807\begin{lstlisting}[frame=single,language=C++] 808void demo3(bool foo) 809{ 810 int a = 23 811 if (foo) 812 a = 42; 813 printf("%d\n", a); 814} 815\end{lstlisting} 816 817Static single assignment (SSA) form is a representation of imperative code that uses identical representations 818for the left and right version of demos 1 and 2, but can still represent demo 3. In SSA form each assignment 819assigns a new variable (usually written with an index). But it also introduces a special $\Phi$-function to 820merge the different instances of a variable when needed. In C-pseudo-code the demo 3 would be written as follows 821using SSA from: 822 823\begin{lstlisting}[frame=single,language=C++] 824void demo3(bool foo) 825{ 826 int a_1, a_2, a_3; 827 a_1 = 23 828 if (foo) 829 a_2 = 42; 830 a_3 = phi(a_1, a_2); 831 printf("%d\n", a_3); 832} 833\end{lstlisting} 834 835The $\Phi$-function is usually interpreted as ``these variables must be stored 836in the same memory location'' during code generation. Most modern compilers for imperative languages 837such as C/C++ use SSA form for at least some of its passes as it is very easy to manipulate and analyse. 838\fi 839 840