manual/CHAPTER_Verilog.tex

   1
   2 \chapter{The Verilog and AST Frontends}
   3 \label{chapter:verilog}
   4
   5 This chapter provides an overview of the implementation of the Yosys Verilog
   6 and AST frontends. The Verilog frontend reads Verilog-2005 code and creates
   7 an abstract syntax tree (AST) representation of the input. This AST representation
   8 is then passed to the AST frontend that converts it to RTLIL data, as illustrated
   9 in Fig.~\ref{fig:Verilog_flow}.
  10
  11 \begin{figure}[b!]
  12         \hfil
  13         \begin{tikzpicture}
  14                 \tikzstyle{process} = [draw, fill=green!10, rectangle, minimum height=3em, minimum width=10em, node distance=5em, font={\ttfamily}]
  15                 \tikzstyle{data} = [draw, fill=blue!10, ellipse, minimum height=3em, minimum width=7em, node distance=5em, font={\ttfamily}]
  16
  17                 \node[data]    (n1)               {Verilog Source};
  18                 \node[process] (n2) [below of=n1] {Verilog Frontend};
  19                 \node[data]    (n3) [below of=n2] {AST};
  20                 \node[process] (n4) [below of=n3] {AST Frontend};
  21                 \node[data]    (n5) [below of=n4] {RTLIL};
  22
  23                 \draw[-latex] (n1) -- (n2);
  24                 \draw[-latex] (n2) -- (n3);
  25                 \draw[-latex] (n3) -- (n4);
  26                 \draw[-latex] (n4) -- (n5);
  27
  28                 \tikzstyle{details} = [draw, fill=yellow!5, rectangle, node distance=6cm, font={\ttfamily}]
  29
  30                 \node[details] (d1) [right of=n2] {\begin{minipage}{5cm}
  31                         \hfil
  32                         \begin{tikzpicture}
  33                                 \tikzstyle{subproc} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=10em, node distance=3em, font={\ttfamily}]
  34                                 \node (s0) {};
  35                                 \node[subproc] (s1) [below of=s0] {Preprocessor};
  36                                 \node[subproc] (s2) [below of=s1] {Lexer};
  37                                 \node[subproc] (s3) [below of=s2] {Parser};
  38                                 \node[node distance=3em] (s4) [below of=s3] {};
  39                                 \draw[-latex] (s0) -- (s1);
  40                                 \draw[-latex] (s1) -- (s2);
  41                                 \draw[-latex] (s2) -- (s3);
  42                                 \draw[-latex] (s3) -- (s4);
  43                         \end{tikzpicture}
  44                 \end{minipage}};
  45
  46                 \draw[dashed] (n2.north east) -- (d1.north west);
  47                 \draw[dashed] (n2.south east) -- (d1.south west);
  48
  49                 \node[details] (d2) [right of=n4] {\begin{minipage}{5cm}
  50                         \hfil
  51                         \begin{tikzpicture}
  52                                 \tikzstyle{subproc} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=10em, node distance=3em, font={\ttfamily}]
  53                                 \node (s0) {};
  54                                 \node[subproc] (s1) [below of=s0] {Simplifier};
  55                                 \node[subproc] (s2) [below of=s1] {RTLIL Generator};
  56                                 \node[node distance=3em] (s3) [below of=s2] {};
  57                                 \draw[-latex] (s0) -- (s1);
  58                                 \draw[-latex] (s1) -- (s2);
  59                                 \draw[-latex] (s2) -- (s3);
  60                         \end{tikzpicture}
  61                 \end{minipage}};
  62
  63                 \draw[dashed] (n4.north east) -- (d2.north west);
  64                 \draw[dashed] (n4.south east) -- (d2.south west);
  65
  66         \end{tikzpicture}
  67         \caption{Simplified Verilog to RTLIL data flow}
  68         \label{fig:Verilog_flow}
  69 \end{figure}
  70
  71
  72 \section{Transforming Verilog to AST}
  73
  74 The {\it Verilog frontend} converts the Verilog sources to an internal AST representation that closely resembles
  75 the structure of the original Verilog code. The Verilog frontend consists of three components, the
  76 {\it Preprocessor}, the {\it Lexer} and the {\it Parser}.
  77
  78 The source code to the Verilog frontend can be found in {\tt frontends/verilog/} in the Yosys source tree.
  79
  80 \subsection{The Verilog Preprocessor}
  81
  82 The Verilog preprocessor scans over the Verilog source code and interprets some of the Verilog compiler
  83 directives such as \lstinline[language=Verilog]{`include}, \lstinline[language=Verilog]{`define} and
  84 \lstinline[language=Verilog]{`ifdef}.
  85
  86 It is implemented as a C++ function that is passed a file descriptor as input and returns the
  87 pre-processed Verilog code as a \lstinline[language=C++]{std::string}.
  88
  89 The source code to the Verilog Preprocessor can be found in {\tt
  90 frontends/verilog/preproc.cc} in the Yosys source tree.
  91
  92 \subsection{The Verilog Lexer}
  93
  94 \begin{sloppypar}
  95 The Verilog Lexer is written using the lexer generator {\it flex} \citeweblink{flex}. Its source code
  96 can be found in {\tt frontends/verilog/verilog\_lexer.l} in the Yosys source tree.
  97 The lexer does little more than identifying all keywords and literals
  98 recognised by the Yosys Verilog frontend.
  99 \end{sloppypar}
 100
 101 The lexer keeps track of the current location in the Verilog source code using
 102 some global variables. These variables are used by the constructor of AST nodes
 103 to annotate each node with the source code location it originated from.
 104
 105 \begin{sloppypar}
 106 Finally the lexer identifies and handles special comments such as
 107 ``\lstinline[language=Verilog]{// synopsys translate_off}'' and
 108 ``\lstinline[language=Verilog]{// synopsys full_case}''. (It is recommended to
 109 use \lstinline[language=Verilog]{`ifdef} constructs instead of the Synsopsys
 110 translate\_on/off comments and attributes such as
 111 \lstinline[language=Verilog]{(* full_case *)} over ``\lstinline[language=Verilog]{// synopsys full_case}''
 112 whenever possible.)
 113 \end{sloppypar}
 114
 115 \subsection{The Verilog Parser}
 116
 117 The Verilog Parser is written using the parser generator {\it bison} \citeweblink{bison}. Its source code
 118 can be found in {\tt frontends/verilog/verilog\_parser.y} in the Yosys source tree.
 119
 120 It generates an AST using the \lstinline[language=C++]{AST::AstNode} data structure
 121 defined in {\tt frontends/ast/ast.h}. An \lstinline[language=C++]{AST::AstNode} object has
 122 the following properties:
 123
 124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 125
 126 \begin{table}[b!]
 127 \hfil
 128 \begin{tabular}{>{\raggedright\arraybackslash}p{7cm}>{\raggedright\arraybackslash}p{8cm}}
 129 AST Node Type & Corresponding Verilog Construct \\
 130 \hline
 131 \hline
 132 \arrayrulecolor{gray}
 133 {\tt AST\_NONE} & This Node type should never be used. \\
 134 \hline
 135 %
 136 {\tt AST\_DESIGN} & This node type is used for the top node of the AST tree. It
 137 has no corresponding Verilog construct. \\
 138 \hline
 139 %
 140 {\tt AST\_MODULE},
 141 {\tt AST\_TASK},
 142 {\tt AST\_FUNCTION} &
 143 \lstinline[language=Verilog];module;,
 144 \lstinline[language=Verilog];task; and
 145 \lstinline[language=Verilog];function; \\
 146 \hline
 147 %
 148 {\tt AST\_WIRE} &
 149 \lstinline[language=Verilog];input;,
 150 \lstinline[language=Verilog];output;,
 151 \lstinline[language=Verilog];wire;,
 152 \lstinline[language=Verilog];reg; and
 153 \lstinline[language=Verilog];integer; \\
 154 \hline
 155 %
 156 {\tt AST\_MEMORY}  &
 157 Verilog Arrays \\
 158 \hline
 159 %
 160 {\tt AST\_AUTOWIRE} &
 161 Created by the simplifier when an undeclared signal name is used. \\
 162 \hline
 163 %
 164 {\tt AST\_PARAMETER},
 165 {\tt AST\_LOCALPARAM} &
 166 \lstinline[language=Verilog];parameter; and
 167 \lstinline[language=Verilog];localparam; \\
 168 \hline
 169 %
 170 {\tt AST\_PARASET} &
 171 Parameter set in cell instantiation \\
 172 \hline
 173 %
 174 {\tt AST\_ARGUMENT} &
 175 Port connection in cell instantiation \\
 176 \hline
 177 %
 178 {\tt AST\_RANGE} &
 179 Bit-Index in a signal or element index in array \\
 180 \hline
 181 %
 182 {\tt AST\_CONSTANT} &
 183 A literal value \\
 184 \hline
 185 %
 186 {\tt AST\_CELLTYPE} &
 187 The type of cell in cell instantiation \\
 188 \hline
 189 %
 190 {\tt AST\_IDENTIFIER} &
 191 An Identifier (signal name in expression or cell/task/etc. name in other contexts) \\
 192 \hline
 193 %
 194 {\tt AST\_PREFIX} &
 195 Construct an identifier in the form {\tt <prefix>[<index>].<suffix>} (used only in
 196 advanced generate constructs) \\
 197 \hline
 198 %
 199 {\tt AST\_FCALL},
 200 {\tt AST\_TCALL} &
 201 Call to function or task \\
 202 \hline
 203 %
 204 {\tt AST\_TO\_SIGNED},
 205 {\tt AST\_TO\_UNSIGNED} &
 206 The \lstinline[language=Verilog];$signed(); and
 207 \lstinline[language=Verilog];$unsigned(); functions \\
 208 \hline
 209 \end{tabular}
 210 \caption{AST node types with their corresponding Verilog constructs. \\ (continued on next page)}
 211 \label{tab:Verilog_AstNodeType}
 212 \end{table}
 213
 214 \begin{table}[t!]
 215 \ContinuedFloat
 216 \hfil
 217 \begin{tabular}{>{\raggedright\arraybackslash}p{7cm}>{\raggedright\arraybackslash}p{8cm}}
 218 AST Node Type & Corresponding Verilog Construct \\
 219 \hline
 220 \hline
 221 \arrayrulecolor{gray}
 222 {\tt AST\_CONCAT}
 223 {\tt AST\_REPLICATE} &
 224 The \lstinline[language=Verilog];{...}; and
 225 \lstinline[language=Verilog];{...{...}}; operators \\
 226 \hline
 227 %
 228 {\tt AST\_BIT\_NOT},
 229 {\tt AST\_BIT\_AND},
 230 {\tt AST\_BIT\_OR},
 231 {\tt AST\_BIT\_XOR},
 232 {\tt AST\_BIT\_XNOR} &
 233 The bitwise operators \break
 234 \lstinline[language=Verilog];~;,
 235 \lstinline[language=Verilog];&;,
 236 \lstinline[language=Verilog];|;,
 237 \lstinline[language=Verilog];^; and
 238 \lstinline[language=Verilog];~^; \\
 239 \hline
 240 %
 241 {\tt AST\_REDUCE\_AND},
 242 {\tt AST\_REDUCE\_OR},
 243 {\tt AST\_REDUCE\_XOR},
 244 {\tt AST\_REDUCE\_XNOR} &
 245 The unary reduction operators \break
 246 \lstinline[language=Verilog];~;,
 247 \lstinline[language=Verilog];&;,
 248 \lstinline[language=Verilog];|;,
 249 \lstinline[language=Verilog];^; and
 250 \lstinline[language=Verilog];~^; \\
 251 \hline
 252 %
 253 {\tt AST\_REDUCE\_BOOL} &
 254 Conversion from multi-bit value to boolean value
 255 (equivalent to {\tt AST\_REDUCE\_OR}) \\
 256 \hline
 257 %
 258 {\tt AST\_SHIFT\_LEFT},
 259 {\tt AST\_SHIFT\_RIGHT},
 260 {\tt AST\_SHIFT\_SLEFT},
 261 {\tt AST\_SHIFT\_SRIGHT} &
 262 The shift operators \break
 263 \lstinline[language=Verilog];<<;,
 264 \lstinline[language=Verilog];>>;,
 265 \lstinline[language=Verilog];<<<; and
 266 \lstinline[language=Verilog];>>>; \\
 267 \hline
 268 %
 269 {\tt AST\_LT},
 270 {\tt AST\_LE},
 271 {\tt AST\_EQ},
 272 {\tt AST\_NE},
 273 {\tt AST\_GE},
 274 {\tt AST\_GT} &
 275 The relational operators \break
 276 \lstinline[language=Verilog];<;,
 277 \lstinline[language=Verilog];<=;,
 278 \lstinline[language=Verilog];==;,
 279 \lstinline[language=Verilog];!=;,
 280 \lstinline[language=Verilog];>=; and
 281 \lstinline[language=Verilog];>; \\
 282 \hline
 283 %
 284 {\tt AST\_ADD},
 285 {\tt AST\_SUB},
 286 {\tt AST\_MUL},
 287 {\tt AST\_DIV},
 288 {\tt AST\_MOD},
 289 {\tt AST\_POW} &
 290 The binary operators \break
 291 \lstinline[language=Verilog];+;,
 292 \lstinline[language=Verilog];-;,
 293 \lstinline[language=Verilog];*;,
 294 \lstinline[language=Verilog];/;,
 295 \lstinline[language=Verilog];%; and
 296 \lstinline[language=Verilog];**; \\
 297 \hline
 298 %
 299 {\tt AST\_POS},
 300 {\tt AST\_NEG} &
 301 The prefix operators
 302 \lstinline[language=Verilog];+; and
 303 \lstinline[language=Verilog];-; \\
 304 \hline
 305 %
 306 {\tt AST\_LOGIC\_AND},
 307 {\tt AST\_LOGIC\_OR},
 308 {\tt AST\_LOGIC\_NOT} &
 309 The logic operators
 310 \lstinline[language=Verilog];&&;,
 311 \lstinline[language=Verilog];||; and
 312 \lstinline[language=Verilog];!; \\
 313 \hline
 314 %
 315 {\tt AST\_TERNARY} &
 316 The ternary \lstinline[language=Verilog];?:;-operator \\
 317 \hline
 318 %
 319 {\tt AST\_MEMRD}
 320 {\tt AST\_MEMWR} &
 321 Read and write memories. These nodes are generated by
 322 the AST simplifier for writes/reads to/from Verilog arrays. \\
 323 \hline
 324 %
 325 {\tt AST\_ASSIGN} &
 326 An \lstinline[language=Verilog];assign; statement \\
 327 \hline
 328 %
 329 {\tt AST\_CELL} &
 330 A cell instantiation \\
 331 \hline
 332 %
 333 {\tt AST\_PRIMITIVE} &
 334 A primitive cell (\lstinline[language=Verilog];and;,
 335 \lstinline[language=Verilog];nand;,
 336 \lstinline[language=Verilog];or;, etc.) \\
 337 \hline
 338 %
 339 {\tt AST\_ALWAYS},
 340 {\tt AST\_INITIAL} &
 341 Verilog \lstinline[language=Verilog];always;- and \lstinline[language=Verilog];initial;-blocks \\
 342 \hline
 343 %
 344 {\tt AST\_BLOCK} &
 345 A \lstinline[language=Verilog];begin;-\lstinline[language=Verilog];end;-block \\
 346 \hline
 347 %
 348 {\tt AST\_ASSIGN\_EQ}.
 349 {\tt AST\_ASSIGN\_LE} &
 350 Blocking (\lstinline[language=Verilog];=;) and nonblocking (\lstinline[language=Verilog];<=;)
 351 assignments within an \lstinline[language=Verilog];always;- or \lstinline[language=Verilog];initial;-block \\
 352 \hline
 353 %
 354 {\tt AST\_CASE}.
 355 {\tt AST\_COND},
 356 {\tt AST\_DEFAULT} &
 357 The \lstinline[language=Verilog];case; (\lstinline[language=Verilog];if;) statements, conditions within a case
 358 and the default case respectively \\
 359 \hline
 360 %
 361 {\tt AST\_FOR} &
 362 A \lstinline[language=Verilog];for;-loop with an
 363 \lstinline[language=Verilog];always;- or
 364 \lstinline[language=Verilog];initial;-block \\
 365 \hline
 366 %
 367 {\tt AST\_GENVAR},
 368 {\tt AST\_GENBLOCK},
 369 {\tt AST\_GENFOR},
 370 {\tt AST\_GENIF} &
 371 The \lstinline[language=Verilog];genvar; and
 372 \lstinline[language=Verilog];generate; keywords and
 373 \lstinline[language=Verilog];for; and \lstinline[language=Verilog];if; within a
 374 generate block. \\
 375 \hline
 376 %
 377 {\tt AST\_POSEDGE},
 378 {\tt AST\_NEGEDGE},
 379 {\tt AST\_EDGE} &
 380 Event conditions for \lstinline[language=Verilog];always; blocks. \\
 381 \hline
 382 \end{tabular}
 383 \caption{AST node types with their corresponding Verilog constructs. \\ (continuation from previous page)}
 384 \label{tab:Verilog_AstNodeTypeCont}
 385 \end{table}
 386
 387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 388
 389 \begin{itemize}
 390 \item {\bf The node type} \\
 391 This enum (\lstinline[language=C++]{AST::AstNodeType}) specifies the role of the node.
 392 Table~\ref{tab:Verilog_AstNodeType} contains a list of all node types.
 393 \item {\bf The child nodes} \\
 394 This is a list of pointers to all children in the abstract syntax tree.
 395 \item {\bf Attributes} \\
 396 As almost every AST node might have Verilog attributes assigned to it, the
 397 \lstinline[language=C++]{AST::AstNode} has direct support for attributes. Note that the
 398 attribute values are again AST nodes.
 399 \item {\bf Node content} \\
 400 Each node might have additional content data. A series of member variables exist to hold such data.
 401 For example the member \lstinline[language=C++]{std::string str} can hold a string value and is
 402 used e.g.~in the {\tt AST\_IDENTIFIER} node type to store the identifier name.
 403 \item {\bf Source code location} \\
 404 Each \lstinline[language=C++]{AST::AstNode} is automatically annotated with the current
 405 source code location by the \lstinline[language=C++]{AST::AstNode} constructor. It is
 406 stored in the \lstinline[language=C++]{std::string filename} and \lstinline[language=C++]{int linenum}
 407 member variables.
 408 \end{itemize}
 409
 410 The \lstinline[language=C++]{AST::AstNode} constructor can be called with up to
 411 two child nodes that are automatically added to the list of child nodes for the new object.
 412 This simplifies the creation of AST nodes for simple expressions a bit. For example the bison
 413 code for parsing multiplications:
 414
 415 \begin{lstlisting}[numbers=left,frame=single]
 416         basic_expr '*' attr basic_expr {
 417                 $$ = new AstNode(AST_MUL, $1, $4);
 418                 append_attr($$, $3);
 419         } |
 420 \end{lstlisting}
 421
 422 The generated AST data structure is then passed directly to the AST frontend
 423 that performs the actual conversion to RTLIL.
 424
 425 Note that the Yosys command {\tt read\_verilog} provides the options {\tt -yydebug}
 426 and {\tt -dump\_ast} that can be used to print the parse tree or abstract syntax tree
 427 respectively.
 428
 429 \section{Transforming AST to RTLIL}
 430
 431 The {\it AST Frontend} converts a set of modules in AST representation to
 432 modules in RTLIL representation and adds them to the current design. This is done
 433 in two steps: {\it simplification} and {\it RTLIL generation}.
 434
 435 The source code to the AST frontend can be found in {\tt frontends/ast/} in the Yosys source tree.
 436
 437 \subsection{AST Simplification}
 438
 439 A full-featured AST is too complex to be transformed into RTLIL directly. Therefore it must
 440 first be brought into a simpler form. This is done by calling the \lstinline[language=C++]{AST::AstNode::simplify()}
 441 method of all {\tt AST\_MODULE} nodes in the AST. This initiates a recursive process that performs the following transformations
 442 on the AST data structure:
 443
 444 \begin{itemize}
 445 \item Inline all task and function calls.
 446 \item Evaluate all \lstinline[language=Verilog]{generate}-statements and unroll all \lstinline[language=Verilog]{for}-loops.
 447 \item Perform const folding where it is necessary (e.g.~in the value part of {\tt AST\_PARAMETER}, {\tt AST\_LOCALPARAM},
 448 {\tt AST\_PARASET} and {\tt AST\_RANGE} nodes).
 449 \item Replace {\tt AST\_PRIMITIVE} nodes with appropriate {\tt AST\_ASSIGN} nodes.
 450 \item Replace dynamic bit ranges in the left-hand-side of assignments with {\tt AST\_CASE} nodes with {\tt AST\_COND} children
 451 for each possible case.
 452 \item Detect array access patterns that are too complicated for the {\tt RTLIL::Memory} abstraction and replace them
 453 with a set of signals and cases for all reads and/or writes.
 454 \item Otherwise replace array accesses with {\tt AST\_MEMRD} and {\tt AST\_MEMWR} nodes.
 455 \end{itemize}
 456
 457 In addition to these transformations, the simplifier also annotates the AST with additional information that is needed
 458 for the RTLIL generator, namely:
 459
 460 \begin{itemize}
 461 \item All ranges (width of signals and bit selections) are not only const folded but (when a constant value
 462 is found) are also written to member variables in the {\tt AST\_RANGE} node.
 463 \item All identifiers are resolved and all {\tt AST\_IDENTIFIER} nodes are annotated with a pointer to the AST node
 464 that contains the declaration of the identifier. If no declaration has been found, an {\tt AST\_AUTOWIRE} node
 465 is created and used for the annotation.
 466 \end{itemize}
 467
 468 This produces an AST that is fairly easy to convert to the RTLIL format.
 469
 470 \subsection{Generating RTLIL}
 471
 472 After AST simplification, the \lstinline[language=C++]{AST::AstNode::genRTLIL()} method of each {\tt AST\_MODULE} node
 473 in the AST is called. This initiates a recursive process that generates equivalent RTLIL data for the AST data.
 474
 475 The \lstinline[language=C++]{AST::AstNode::genRTLIL()} method returns an \lstinline[language=C++]{RTLIL::SigSpec} structure.
 476 For nodes that represent expressions (operators, constants, signals, etc.), the cells needed to implement the calculation
 477 described by the expression are created and the resulting signal is returned. That way it is easy to generate the circuits
 478 for large expressions using depth-first recursion. For nodes that do not represent an expression (such as {\tt
 479 AST\_CELL}), the corresponding circuit is generated and an empty \lstinline[language=C++]{RTLIL::SigSpec} is returned.
 480
 481 \section{Synthesizing Verilog always Blocks}
 482
 483 For behavioural Verilog code (code utilizing \lstinline[language=Verilog]{always}- and
 484 \lstinline[language=Verilog]{initial}-blocks) it is necessary to also generate \lstinline[language=C++]{RTLIL::Process}
 485 objects. This is done in the following way:
 486
 487 \begin{itemize}
 488 \item Whenever \lstinline[language=C++]{AST::AstNode::genRTLIL()} encounters an \lstinline[language=Verilog]{always}-
 489 or \lstinline[language=Verilog]{initial}-block, it creates an instance of
 490 \lstinline[language=Verilog]{AST_INTERNAL::ProcessGenerator}. This object then generates the
 491 \lstinline[language=C++]{RTLIL::Process} object for the block. It also calls \lstinline[language=C++]{AST::AstNode::genRTLIL()}
 492 for all right-hand-side expressions contained within the block.
 493 %
 494 \begin{sloppypar}
 495 \item First the  \lstinline[language=Verilog]{AST_INTERNAL::ProcessGenerator} creates a list of all signals assigned
 496 within the block. It then creates a set of temporary signals using the naming scheme {\tt \$\it<number>\tt
 497 \textbackslash\it <original\_name>} for each of the assigned signals.
 498 \end{sloppypar}
 499 %
 500 \item Then an \lstinline[language=C++]{RTLIL::Process} is created that assigns all intermediate values for each left-hand-side
 501 signal to the temporary signal in its \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree.
 502 %
 503 \item Finally a \lstinline[language=C++]{RTLIL::SyncRule} is created for the \lstinline[language=C++]{RTLIL::Process} that
 504 assigns the temporary signals for the final values to the actual signals.
 505 %
 506 \item A process may also contain memory writes. A \lstinline[language=C++]{RTLIL::MemWriteAction} is created for each of them.
 507 %
 508 \item Calls to \lstinline[language=C++]{AST::AstNode::genRTLIL()} are generated for right hand sides as needed. When blocking
 509 assignments are used, \lstinline[language=C++]{AST::AstNode::genRTLIL()} is configured using global variables to use
 510 the temporary signals that hold the correct intermediate values whenever one of the previously assigned signals is used
 511 in an expression.
 512 \end{itemize}
 513
 514 Unfortunately the generation of a correct \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule}
 515 tree for behavioural code is a non-trivial task. The AST frontend solves the problem using the approach described on the following
 516 pages. The following example illustrates what the algorithm is supposed to do. Consider the following Verilog code:
 517
 518 \begin{lstlisting}[numbers=left,frame=single,language=Verilog]
 519 always @(posedge clock) begin
 520         out1 = in1;
 521         if (in2)
 522                 out1 = !out1;
 523         out2 <= out1;
 524         if (in3)
 525                 out2 <= out2;
 526         if (in4)
 527                 if (in5)
 528                         out3 <= in6;
 529                 else
 530                         out3 <= in7;
 531         out1 = out1 ^ out2;
 532 end
 533 \end{lstlisting}
 534
 535 This is translated by the Verilog and AST frontends into the following RTLIL code (attributes, cell parameters
 536 and wire declarations not included):
 537
 538 \begin{lstlisting}[numbers=left,frame=single,language=rtlil]
 539 cell $logic_not $logic_not$<input>:4$2
 540   connect \A \in1
 541   connect \Y $logic_not$<input>:4$2_Y
 542 end
 543 cell $xor $xor$<input>:13$3
 544   connect \A $1\out1[0:0]
 545   connect \B \out2
 546   connect \Y $xor$<input>:13$3_Y
 547 end
 548 process $proc$<input>:1$1
 549   assign $0\out3[0:0] \out3
 550   assign $0\out2[0:0] $1\out1[0:0]
 551   assign $0\out1[0:0] $xor$<input>:13$3_Y
 552   switch \in2
 553     case 1'1
 554       assign $1\out1[0:0] $logic_not$<input>:4$2_Y
 555     case
 556       assign $1\out1[0:0] \in1
 557   end
 558   switch \in3
 559     case 1'1
 560       assign $0\out2[0:0] \out2
 561     case
 562   end
 563   switch \in4
 564     case 1'1
 565       switch \in5
 566         case 1'1
 567           assign $0\out3[0:0] \in6
 568         case
 569           assign $0\out3[0:0] \in7
 570       end
 571     case
 572   end
 573   sync posedge \clock
 574     update \out1 $0\out1[0:0]
 575     update \out2 $0\out2[0:0]
 576     update \out3 $0\out3[0:0]
 577 end
 578 \end{lstlisting}
 579
 580 Note that the two operators are translated into separate cells outside the generated process. The signal
 581 \lstinline[language=Verilog]{out1} is assigned using blocking assignments and therefore \lstinline[language=Verilog]{out1}
 582 has been replaced with a different signal in all expressions after the initial assignment. The signal
 583 \lstinline[language=Verilog]{out2} is assigned using nonblocking assignments and therefore is not substituted
 584 on the right-hand-side expressions.
 585
 586 The \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule}
 587 tree must be interpreted the following way:
 588
 589 \begin{itemize}
 590 \item On each case level (the body of the process is the {\it root case}), first the actions on this level are
 591 evaluated and then the switches within the case are evaluated. (Note that the last assignment on line 13 of the
 592 Verilog code has been moved to the beginning of the RTLIL process to line 13 of the RTLIL listing.)
 593
 594 I.e.~the special cases deeper in the switch hierarchy override the defaults on the upper levels. The assignments
 595 in lines 12 and 22 of the RTLIL code serve as an example for this.
 596
 597 Note that in contrast to this, the order within the \lstinline[language=C++]{RTLIL::SwitchRule} objects
 598 within a \lstinline[language=C++]{RTLIL::CaseRule} is preserved with respect to the original AST and
 599 Verilog code.
 600 %
 601 \item \begin{sloppypar}
 602 The whole \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree
 603 describes an asynchronous circuit. I.e.~the decision tree formed by the switches can be seen independently for
 604 each assigned signal. Whenever one assigned signal changes, all signals that depend on the changed signals
 605 are to be updated. For example the assignments in lines 16 and 18 in the RTLIL code in fact influence the assignment
 606 in line 12, even though they are in the ``wrong order''.
 607 \end{sloppypar}
 608 \end{itemize}
 609
 610 The only synchronous part of the process is in the \lstinline[language=C++]{RTLIL::SyncRule} object generated at line
 611 35 in the RTLIL code. The sync rule is the only part of the process where the original signals are assigned. The
 612 synchronization event from the original Verilog code has been translated into the synchronization type ({\tt posedge})
 613 and signal ({\tt \textbackslash clock}) for the \lstinline[language=C++]{RTLIL::SyncRule} object. In the case of
 614 this simple example the \lstinline[language=C++]{RTLIL::SyncRule} object is later simply transformed into a set of
 615 d-type flip-flops and the \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree
 616 to a decision tree using multiplexers.
 617
 618 \begin{sloppypar}
 619 In more complex examples (e.g.~asynchronous resets) the part of the
 620 \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule}
 621 tree that describes the asynchronous reset must first be transformed to the
 622 correct \lstinline[language=C++]{RTLIL::SyncRule} objects. This is done by the {\tt proc\_adff} pass.
 623 \end{sloppypar}
 624
 625 \subsection{The ProcessGenerator Algorithm}
 626
 627 The \lstinline[language=C++]{AST_INTERNAL::ProcessGenerator} uses the following internal state variables:
 628
 629 \begin{itemize}
 630 \item \begin{sloppypar}
 631 \lstinline[language=C++]{subst_rvalue_from} and \lstinline[language=C++]{subst_rvalue_to} \\
 632 These two variables hold the replacement pattern that should be used by \lstinline[language=C++]{AST::AstNode::genRTLIL()}
 633 for signals with blocking assignments. After initialization of \lstinline[language=C++]{AST_INTERNAL::ProcessGenerator}
 634 these two variables are empty.
 635 \end{sloppypar}
 636 %
 637 \item \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to} \\
 638 These two variables contain the mapping from left-hand-side signals ({\tt \textbackslash \it <name>}) to the current
 639 temporary signal for the same thing (initially {\tt \$0\textbackslash \it <name>}).
 640 %
 641 \item \lstinline[language=C++]{current_case} \\
 642 A pointer to a \lstinline[language=C++]{RTLIL::CaseRule} object. Initially this is the root case of the
 643 generated \lstinline[language=C++]{RTLIL::Process}.
 644 \end{itemize}
 645
 646 As the algorithm runs these variables are continuously modified as well as pushed
 647 to the stack and later restored to their earlier values by popping from the stack.
 648
 649 On startup the ProcessGenerator generates a new
 650 \lstinline[language=C++]{RTLIL::Process} object with an empty root case and
 651 initializes its state variables as described above. Then the \lstinline[language=C++]{RTLIL::SyncRule} objects
 652 are created using the synchronization events from the {\tt AST\_ALWAYS} node and the initial values of
 653 \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to}. Then the
 654 AST for this process is evaluated recursively.
 655
 656 During this recursive evaluation, three different relevant types of AST nodes can be discovered:
 657 {\tt AST\_ASSIGN\_LE} (nonblocking assignments), {\tt AST\_ASSIGN\_EQ} (blocking assignments) and
 658 {\tt AST\_CASE} (\lstinline[language=Verilog]{if} or \lstinline[language=Verilog]{case} statement).
 659
 660 \subsubsection{Handling of Nonblocking Assignments}
 661
 662 When an {\tt AST\_ASSIGN\_LE} node is discovered, the following actions are performed by the
 663 ProcessGenerator:
 664
 665 \begin{itemize}
 666 \item The left-hand-side is evaluated using \lstinline[language=C++]{AST::AstNode::genRTLIL()} and mapped to
 667 a temporary signal name using \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to}.
 668 %
 669 \item The right-hand-side is evaluated using \lstinline[language=C++]{AST::AstNode::genRTLIL()}. For this call,
 670 the values of \lstinline[language=C++]{subst_rvalue_from} and \lstinline[language=C++]{subst_rvalue_to} are used to
 671 map blocking-assigned signals correctly.
 672 %
 673 \item Remove all assignments to the same left-hand-side as this assignment from the \lstinline[language=C++]{current_case}
 674 and all cases within it.
 675 %
 676 \item Add the new assignment to the \lstinline[language=C++]{current_case}.
 677 \end{itemize}
 678
 679 \subsubsection{Handling of Blocking Assignments}
 680
 681 When an {\tt AST\_ASSIGN\_EQ} node is discovered, the following actions are performed by
 682 the ProcessGenerator:
 683
 684 \begin{itemize}
 685 \item Perform all the steps that would be performed for a nonblocking assignment (see above).
 686 %
 687 \item Remove the found left-hand-side (before lvalue mapping) from
 688 \lstinline[language=C++]{subst_rvalue_from} and also remove the respective
 689 bits from \lstinline[language=C++]{subst_rvalue_to}.
 690 %
 691 \item Append the found left-hand-side (before lvalue mapping) to \lstinline[language=C++]{subst_rvalue_from}
 692 and append the found right-hand-side to \lstinline[language=C++]{subst_rvalue_to}.
 693 \end{itemize}
 694
 695 \subsubsection{Handling of Cases and if-Statements}
 696
 697 \begin{sloppypar}
 698 When an {\tt AST\_CASE} node is discovered, the following actions are performed by
 699 the ProcessGenerator:
 700
 701 \begin{itemize}
 702 \item The values of \lstinline[language=C++]{subst_rvalue_from}, \lstinline[language=C++]{subst_rvalue_to},
 703 \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to} are pushed to the stack.
 704 %
 705 \item A new \lstinline[language=C++]{RTLIL::SwitchRule} object is generated, the selection expression is evaluated using
 706 \lstinline[language=C++]{AST::AstNode::genRTLIL()} (with the use of \lstinline[language=C++]{subst_rvalue_from} and
 707 \lstinline[language=C++]{subst_rvalue_to}) and added to the \lstinline[language=C++]{RTLIL::SwitchRule} object and the
 708 object is added to the \lstinline[language=C++]{current_case}.
 709 %
 710 \item All lvalues assigned to within the {\tt AST\_CASE} node using blocking assignments are collected and
 711 saved in the local variable \lstinline[language=C++]{this_case_eq_lvalue}.
 712 %
 713 \item New temporary signals are generated for all signals in \lstinline[language=C++]{this_case_eq_lvalue} and stored
 714 in \lstinline[language=C++]{this_case_eq_ltemp}.
 715 %
 716 \item The signals in \lstinline[language=C++]{this_case_eq_lvalue} are mapped using \lstinline[language=C++]{subst_rvalue_from}
 717 and \lstinline[language=C++]{subst_rvalue_to} and the resulting set of signals is stored in
 718 \lstinline[language=C++]{this_case_eq_rvalue}.
 719 \end{itemize}
 720
 721 Then the following steps are performed for each {\tt AST\_COND} node within the {\tt AST\_CASE} node:
 722
 723 \begin{itemize}
 724 \item Set \lstinline[language=C++]{subst_rvalue_from}, \lstinline[language=C++]{subst_rvalue_to},
 725 \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to} to the values
 726 that have been pushed to the stack.
 727 %
 728 \item Remove \lstinline[language=C++]{this_case_eq_lvalue} from
 729 \lstinline[language=C++]{subst_lvalue_from}/\lstinline[language=C++]{subst_lvalue_to}.
 730 %
 731 \item Append \lstinline[language=C++]{this_case_eq_lvalue} to \lstinline[language=C++]{subst_lvalue_from} and append
 732 \lstinline[language=C++]{this_case_eq_ltemp} to \lstinline[language=C++]{subst_lvalue_to}.
 733 %
 734 \item Push the value of \lstinline[language=C++]{current_case}.
 735 %
 736 \item Create a new \lstinline[language=C++]{RTLIL::CaseRule}. Set \lstinline[language=C++]{current_case} to the
 737 new object and add the new object to the \lstinline[language=C++]{RTLIL::SwitchRule} created above.
 738 %
 739 \item Add an assignment from \lstinline[language=C++]{this_case_eq_rvalue} to \lstinline[language=C++]{this_case_eq_ltemp}
 740 to the new \lstinline[language=C++]{current_case}.
 741 %
 742 \item Evaluate the compare value for this case using \lstinline[language=C++]{AST::AstNode::genRTLIL()} (with the use of
 743 \lstinline[language=C++]{subst_rvalue_from} and \lstinline[language=C++]{subst_rvalue_to}) modify the new
 744 \lstinline[language=C++]{current_case} accordingly.
 745 %
 746 \item Recursion into the children of the {\tt AST\_COND} node.
 747 %
 748 \item Restore \lstinline[language=C++]{current_case} by popping the old value from the stack.
 749 \end{itemize}
 750
 751 Finally the following steps are performed:
 752
 753 \begin{itemize}
 754 \item The values of \lstinline[language=C++]{subst_rvalue_from}, \lstinline[language=C++]{subst_rvalue_to},
 755 \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to} are popped from the stack.
 756 %
 757 \item The signals from \lstinline[language=C++]{this_case_eq_lvalue} are removed from the
 758 \lstinline[language=C++]{subst_rvalue_from}/\lstinline[language=C++]{subst_rvalue_to}-pair.
 759 %
 760 \item The value of \lstinline[language=C++]{this_case_eq_lvalue} is appended to \lstinline[language=C++]{subst_rvalue_from}
 761 and the value of \lstinline[language=C++]{this_case_eq_ltemp} is appended to \lstinline[language=C++]{subst_rvalue_to}.
 762 %
 763 \item Map the signals in \lstinline[language=C++]{this_case_eq_lvalue} using
 764 \lstinline[language=C++]{subst_lvalue_from}/\lstinline[language=C++]{subst_lvalue_to}.
 765 %
 766 \item Remove all assignments to signals in \lstinline[language=C++]{this_case_eq_lvalue} in \lstinline[language=C++]{current_case}
 767 and all cases within it.
 768 %
 769 \item Add an assignment from \lstinline[language=C++]{this_case_eq_ltemp} to \lstinline[language=C++]{this_case_eq_lvalue}
 770 to \lstinline[language=C++]{current_case}.
 771 \end{itemize}
 772 \end{sloppypar}
 773
 774 \subsubsection{Further Analysis of the Algorithm for Cases and if-Statements}
 775
 776 With respect to nonblocking assignments the algorithm is easy: later assignments invalidate earlier assignments.
 777 For each signal assigned using nonblocking assignments exactly one temporary variable is generated (with the
 778 {\tt \$0}-prefix) and this variable is used for all assignments of the variable.
 779
 780 Note how all the \lstinline[language=C++]{_eq_}-variables become empty when no blocking assignments are used
 781 and many of the steps in the algorithm can then be ignored as a result of this.
 782
 783 For a variable with blocking assignments the algorithm shows the following behaviour: First a new temporary variable
 784 is created. This new temporary variable is then registered as the assignment target for all assignments for this
 785 variable within the cases for this {\tt AST\_CASE} node. Then for each case the new temporary variable is first
 786 assigned the old temporary variable. This assignment is overwritten if the variable is actually assigned in this
 787 case and is kept as a default value otherwise.
 788
 789 This yields an \lstinline[language=C++]{RTLIL::CaseRule} that assigns the new temporary variable in all branches.
 790 So when all cases have been processed a final assignment is added to the containing block that assigns the new
 791 temporary variable to the old one. Note how this step always overrides a previous assignment to the old temporary
 792 variable. Other than nonblocking assignments, the old assignment could still have an effect somewhere
 793 in the design, as there have been calls to \lstinline[language=C++]{AST::AstNode::genRTLIL()} with a
 794 \lstinline[language=C++]{subst_rvalue_from}/\lstinline[language=C++]{subst_rvalue_to}-tuple that contained
 795 the right-hand-side of the old assignment.
 796
 797 \subsection{The proc pass}
 798
 799 The ProcessGenerator converts a behavioural model in AST representation to a behavioural model in
 800 \lstinline[language=C++]{RTLIL::Process} representation. The actual conversion from a behavioural
 801 model to an RTL representation is performed by the {\tt proc} pass and the passes it launches:
 802
 803 \begin{itemize}
 804 \item {\tt proc\_clean} and {\tt proc\_rmdead} \\
 805 These two passes just clean up the \lstinline[language=C++]{RTLIL::Process} structure. The {\tt proc\_clean}
 806 pass removes empty parts (eg. empty assignments) from the process and {\tt proc\_rmdead} detects and removes
 807 unreachable branches from the process's decision trees.
 808 %
 809 \item {\tt proc\_arst} \\
 810 This pass detects processes that describe d-type flip-flops with asynchronous
 811 resets and rewrites the process to better reflect what they are modelling:
 812 Before this pass, an asynchronous reset has two edge-sensitive sync rules and
 813 one top-level \C{RTLIL::SwitchRule} for the reset path. After this pass the
 814 sync rule for the reset is level-sensitive and the top-level
 815 \C{RTLIL::SwitchRule} has been removed.
 816 %
 817 \item {\tt proc\_mux} \\
 818 This pass converts the \C{RTLIL::CaseRule}/\C{RTLIL::SwitchRule}-tree to a tree
 819 of multiplexers per written signal. After this, the \C{RTLIL::Process} structure only contains
 820 the \C{RTLIL::SyncRule}s that describe the output registers.
 821 %
 822 \item {\tt proc\_dff} \\
 823 This pass replaces the \C{RTLIL::SyncRule}s to d-type flip-flops (with
 824 asynchronous resets if necessary).
 825 %
 826 \item {\tt proc\_dff} \\
 827 This pass replaces the \C{RTLIL::MemWriteActions}s with {\tt \$memwr} cells.
 828 %
 829 \item {\tt proc\_clean} \\
 830 A final call to {\tt proc\_clean} removes the now empty \C{RTLIL::Process} objects.
 831 \end{itemize}
 832
 833 Performing these last processing steps in passes instead of in the Verilog frontend has two important benefits:
 834
 835 First it improves the transparency of the process. Everything that happens in a separate pass is easier to debug,
 836 as the RTLIL data structures can be easily investigated before and after each of the steps.
 837
 838 Second it improves flexibility. This scheme can easily be extended to support other types of storage-elements, such
 839 as sr-latches or d-latches, without having to extend the actual Verilog frontend.
 840
 841 \section{Synthesizing Verilog Arrays}
 842
 843 \begin{fixme}
 844 Add some information on the generation of {\tt \$memrd} and {\tt \$memwr} cells
 845 and how they are processed in the {\tt memory} pass.
 846 \end{fixme}
 847
 848 \section{Synthesizing Parametric Designs}
 849
 850 \begin{fixme}
 851 Add some information on the \lstinline[language=C++]{RTLIL::Module::derive()} method and how it
 852 is used to synthesize parametric modules via the {\tt hierarchy} pass.
 853 \end{fixme}
 854