\chapter{Approach}
\label{chapter:approach}
Yosys is a tool for synthesising (behavioural) Verilog HDL code to target architecture netlists. Yosys aims at a wide
range of application domains and thus must be flexible and easy to adapt to new tasks. This chapter covers the general
approach followed in the effort to implement this tool.
\section{Data- and Control-Flow}
The data- and control-flow of a typical synthesis-tool is very similar to the data- and control-flow of a typical
compiler: different subsystems are called in a predetermined order, each consuming the data generated by the
last subsystem and generating the data for the next subsystem (see Fig.~\ref{fig:approach_flow}).
\begin{figure}[b]
\hfil
\begin{tikzpicture}
\path (-1.5,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\draw[fill=orange!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Frontend} ++(1,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\draw[fill=green!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Pass} ++(1,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\draw[fill=orange!10] ($ (cursor) + (1,-3) $) rectangle node[rotate=90] {Backend} ++(1,3) coordinate (cursor);
\draw[-latex] ($ (cursor) + (0,-1.5) $) -- ++(1,0);
\path (-3,-0.5) coordinate (cursor);
\draw (cursor) -- node[below] {HDL} ++(3,0) coordinate (cursor);
\draw[|-|] (cursor) -- node[below] {Internal Format(s)} ++(8,0) coordinate (cursor);
\draw (cursor) -- node[below] {Netlist} ++(3,0);
\path (-3,3.5) coordinate (cursor);
\draw[-] (cursor) -- node[above] {High-Level} ++(3,0) coordinate (cursor);
\draw[-] (cursor) -- ++(8,0) coordinate (cursor);
\draw[->] (cursor) -- node[above] {Low-Level} ++(3,0);
\end{tikzpicture}
\caption{General data- and control-flow of a synthesis tool}
\label{fig:approach_flow}
\end{figure}
The first subsystem to be called is usually called a {\it frontend}. It does not process the data generated by
another subsystem but instead reads the user input; in the case of a HDL synthesis tool the behavioural
HDL code.
The subsystems that consume data from previous subsystems and produces data for the next subsystems (usually in the
same or a similar format) are called {\it passes}.
The last subsystem that is executed transforms the data generated by the last pass into a suitable output
format and writes it to a disk file. This subsystem is usually called the {\it backend}.
In Yosys all frontends, passes and backends are directly available as commands in the synthesis script. Thus
the user can easily create a custom synthesis flow just by calling passes in the right order in a synthesis
script.
\section{Internal Formats in Yosys}
Yosys uses two different internal formats. The first is used to store an abstract syntax tree (AST) of a verilog
input file. This format is simply called {\it AST} and is generated by the Verilog Frontend