manual/CHAPTER_Approach.tex

   1
   2 \chapter{Approach}
   3 \label{chapter:approach}
   4
   5 Yosys is a tool for synthesising (behavioural) Verilog HDL code to target architecture netlists. Yosys aims at a wide
   6 range of application domains and thus must be flexible and easy to adapt to new tasks. This chapter covers the general
   7 approach followed in the effort to implement this tool.
   8
   9 \section{Data- and Control-Flow}
  10
  11 The data- and control-flow of a typical synthesis tool is very similar to the data- and control-flow of a typical
  12 compiler: different subsystems are called in a predetermined order, each consuming the data generated by the
  13 last subsystem and generating the data for the next subsystem (see Fig.~\ref{fig:approach_flow}).
  14
  15 \begin{figure}[b]
  16         \hfil
  17         \begin{tikzpicture}
  18                 \path (-1.5,3) coordinate (cursor);
  19                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  20                 \draw[fill=orange!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Frontend} ++(1,3) coordinate (cursor);
  21                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  22                 \draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
  23                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  24                 \draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
  25                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  26                 \draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
  27                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  28                 \draw[fill=orange!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Backend} ++(1,3) coordinate (cursor);
  29                 \draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
  30
  31                 \path (-3,-0.5) coordinate (cursor);
  32                 \draw (cursor) -- node[below] {HDL} ++(3,0) coordinate (cursor);
  33                 \draw[|-|] (cursor) -- node[below] {Internal Format(s)} ++(8,0) coordinate (cursor);
  34                 \draw (cursor) -- node[below] {Netlist} ++(3,0);
  35
  36                 \path (-3,3.5) coordinate (cursor);
  37                 \draw[-] (cursor) -- node[above] {High-Level} ++(3,0) coordinate (cursor);
  38                 \draw[-] (cursor) -- ++(8,0) coordinate (cursor);
  39                 \draw[->] (cursor) -- node[above] {Low-Level} ++(3,0);
  40
  41         \end{tikzpicture}
  42         \caption{General data- and control-flow of a synthesis tool}
  43         \label{fig:approach_flow}
  44 \end{figure}
  45
  46 The first subsystem to be called is usually called a {\it frontend}. It does not process the data generated by
  47 another subsystem but instead reads the user input---in the case of a HDL synthesis tool, the behavioural
  48 HDL code.
  49
  50 The subsystems that consume data from previous subsystems and produce data for the next subsystems (usually in the
  51 same or a similar format) are called {\it passes}.
  52
  53 The last subsystem that is executed transforms the data generated by the last pass into a suitable output
  54 format and writes it to a disk file. This subsystem is usually called the {\it backend}.
  55
  56 In Yosys all frontends, passes and backends are directly available as commands in the synthesis script. Thus
  57 the user can easily create a custom synthesis flow just by calling passes in the right order in a synthesis
  58 script.
  59
  60 \section{Internal Formats in Yosys}
  61
  62 Yosys uses two different internal formats. The first is used to store an abstract syntax tree (AST) of a Verilog
  63 input file. This format is simply called {\it AST} and is generated by the Verilog Frontend. This data structure
  64 is consumed by a subsystem called {\it AST Frontend}\footnote{In Yosys the term {\it pass} is only used to
  65 refer to commands that operate on the RTLIL data structure.}. This AST Frontend then generates a design in Yosys'
  66 main internal format, the Register-Transfer-Level-Intermediate-Language (RTLIL) representation. It does that
  67 by first performing a number of simplifications within the AST representation and then generating RTLIL from
  68 the simplified AST data structure.
  69
  70 The RTLIL representation is used by all passes as input and outputs. This has the following advantages over
  71 using different representational formats between different passes:
  72
  73 \begin{itemize}
  74 \item The passes can be rearranged in a different order and passes can be removed or inserted.
  75 \item Passes can simply pass-thru the parts of the design they don't change without the need
  76       to convert between formats. In fact Yosys passes output the same data structure they received
  77       as input and performs all changes in place.
  78 \item All passes use the same interface, thus reducing the effort required to understand a pass
  79       when reading the Yosys source code, e.g.~when adding additional features.
  80 \end{itemize}
  81
  82 The RTLIL representation is basically a netlist representation with the following additional features:
  83
  84 \begin{itemize}
  85 \item An internal cell library with fixed-function cells to represent RTL datapath and register cells as well
  86 as logical gate-level cells (single-bit gates and registers).
  87 \item Support for multi-bit values that can use individual bits from wires as well as constant bits to
  88 represent coarse-grain netlists.
  89 \item Support for basic behavioural constructs (if-then-else structures and multi-case switches with
  90 a sensitivity list for updating the outputs).
  91 \item Support for multi-port memories.
  92 \end{itemize}
  93
  94 The use of RTLIL also has the disadvantage of having a very powerful format
  95 between all passes, even when doing gate-level synthesis where the more
  96 advanced features are not needed. In order to reduce complexity for passes that
  97 operate on a low-level representation, these passes check the features used in
  98 the input RTLIL and fail to run when unsupported high-level constructs are
  99 used. In such cases a pass that transforms the higher-level constructs to
 100 lower-level constructs must be called from the synthesis script first.
 101
 102 \section{Typical Use Case}
 103 \label{sec:typusecase}
 104
 105 The following example script may be used in a synthesis flow to convert the behavioural Verilog code
 106 from the input file {\tt design.v} to a gate-level netlist {\tt synth.v} using the cell library
 107 described by the Liberty file \citeweblink{LibertyFormat} {\tt cells.lib}:
 108
 109 \begin{lstlisting}[language=sh,numbers=left,frame=single]
 110 # read input file to internal representation
 111 read_verilog design.v
 112
 113 # convert high-level behavioral parts ("processes") to d-type flip-flops and muxes
 114 proc
 115
 116 # perform some simple optimizations
 117 opt
 118
 119 # convert high-level memory constructs to d-type flip-flops and multiplexers
 120 memory
 121
 122 # perform some simple optimizations
 123 opt
 124
 125 # convert design to (logical) gate-level netlists
 126 techmap
 127
 128 # perform some simple optimizations
 129 opt
 130
 131 # map internal register types to the ones from the cell library
 132 dfflibmap -liberty cells.lib
 133
 134 # use ABC to map remaining logic to cells from the cell library
 135 abc -liberty cells.lib
 136
 137 # cleanup
 138 opt
 139
 140 # write results to output file
 141 write_verilog synth.v
 142 \end{lstlisting}
 143
 144 A detailed description of the commands available in Yosys can be found in App.~\ref{commandref}.
 145