\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 produce 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. This data structure
is consumed by a subsystem called {\it AST Frontend}\footnote{In Yosys the term {\it pass} is only used to
refer to commands that operate on the RTLIL data structure.}. This AST Frontend then generates a design in Yosys'
main internal format, the Register-Transfer-Level-Intermediate-Language (RTLIL) representation. It does that
by first performing a number of simplifications within the AST representation and then generating RTLIL from
the simplified AST data structure.
The RTLIL representation is used by all passes as input and outputs. This has the following advantages over
using different representational formats between different passes:
\begin{itemize}
\item The passes can be rearranged in a different order and passes can be removed or inserted.
\item Passes can simply pass-thru the parts of the design they don't change without the need
to convert between formats. In fact Yosys passes output the same data structure they received
as input and performs all changes in place.
\item All passes use the same interface, thus reducing the effort required to understand a pass
when reading the Yosys source code, e.g.~when adding additional features.
\end{itemize}
The RTLIL representation is basically a netlist representation with the following additional features:
\begin{itemize}
\item An internal cell library with fixed-function cells to represent RTL datapath and register cells as well
as logical gate-level cells (single-bit gates and registers).
\item Support for multi-bit values that can use individual bits from wires as well as constant bits to
represent coarse-grain netlists.
\item Support for basic behavioural constructs (if-then-else structures and multi-case switches with
a sensitivity list for updating the outputs).
\item Support for multi-port memories.
\end{itemize}
The use of RTLIL also has the disadvantage of having a very powerful format
between all passes, even when doing gate-level synthesis where the more
advanced features are not needed. In order to reduce complexity for passes that
operate on a low-level representation, these passes check the features used in
the input RTLIL and fail to run when unsupported high-level constructs are
used. In such cases a pass that transforms the higher-level constructs to
lower-level constructs must be called from the synthesis script first.
\section{Typical Use Case}
\label{sec:typusecase}
The following example script may be used in a synthesis flow to convert the behavioural Verilog code
from the input file {\tt design.v} to a gate-level netlist {\tt synth.v} using the cell library
described by the Liberty file \citeweblink{LibertyFormat} {\tt cells.lib}:
\begin{lstlisting}[language=sh,numbers=left,frame=single]
# read input file to internal representation
read_verilog design.v
# convert high-level behavioral parts ("processes") to d-type flip-flops and muxes
proc
# perform some simple optimizations
opt
# convert high-level memory constructs to d-type flip-flops and multiplexers
memory
# perform some simple optimizations
opt
# convert design to (logical) gate-level netlists
techmap
# perform some simple optimizations
opt
# map internal register types to the ones from the cell library
dfflibmap -liberty cells.lib
# use ABC to map remaining logic to cells from the cell library
abc -liberty cells.lib
# cleanup
opt
# write results to output file
write_verilog synth.v
\end{lstlisting}
A detailed description of the commands available in Yosys can be found in App.~\ref{commandref}.
8
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
|