1 2\chapter{The Verilog and AST Frontends} 3\label{chapter:verilog} 4 5This chapter provides an overview of the implementation of the Yosys Verilog 6and AST frontends. The Verilog frontend reads Verilog-2005 code and creates 7an abstract syntax tree (AST) representation of the input. This AST representation 8is then passed to the AST frontend that converts it to RTLIL data, as illustrated 9in 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 74The {\it Verilog frontend} converts the Verilog sources to an internal AST representation that closely resembles 75the 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 78The 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 82The Verilog preprocessor scans over the Verilog source code and interprets some of the Verilog compiler 83directives such as \lstinline[language=Verilog]{`include}, \lstinline[language=Verilog]{`define} and 84\lstinline[language=Verilog]{`ifdef}. 85 86It is implemented as a C++ function that is passed a file descriptor as input and returns the 87pre-processed Verilog code as a \lstinline[language=C++]{std::string}. 88 89The source code to the Verilog Preprocessor can be found in {\tt 90frontends/verilog/preproc.cc} in the Yosys source tree. 91 92\subsection{The Verilog Lexer} 93 94\begin{sloppypar} 95The Verilog Lexer is written using the lexer generator {\it flex} \citeweblink{flex}. Its source code 96can be found in {\tt frontends/verilog/verilog\_lexer.l} in the Yosys source tree. 97The lexer does little more than identifying all keywords and literals 98recognised by the Yosys Verilog frontend. 99\end{sloppypar} 100 101The lexer keeps track of the current location in the Verilog source code using 102some global variables. These variables are used by the constructor of AST nodes 103to annotate each node with the source code location it originated from. 104 105\begin{sloppypar} 106Finally 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 109use \lstinline[language=Verilog]{`ifdef} constructs instead of the Synsopsys 110translate\_on/off comments and attributes such as 111\lstinline[language=Verilog]{(* full_case *)} over ``\lstinline[language=Verilog]{// synopsys full_case}'' 112whenever possible.) 113\end{sloppypar} 114 115\subsection{The Verilog Parser} 116 117The Verilog Parser is written using the parser generator {\it bison} \citeweblink{bison}. Its source code 118can be found in {\tt frontends/verilog/verilog\_parser.y} in the Yosys source tree. 119 120It generates an AST using the \lstinline[language=C++]{AST::AstNode} data structure 121defined in {\tt frontends/ast/ast.h}. An \lstinline[language=C++]{AST::AstNode} object has 122the following properties: 123 124%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 125 126\begin{table}[b!] 127\hfil 128\begin{tabular}{>{\raggedright\arraybackslash}p{7cm}>{\raggedright\arraybackslash}p{8cm}} 129AST 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 137has 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} & 157Verilog Arrays \\ 158\hline 159% 160{\tt AST\_AUTOWIRE} & 161Created 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} & 171Parameter set in cell instantiation \\ 172\hline 173% 174{\tt AST\_ARGUMENT} & 175Port connection in cell instantiation \\ 176\hline 177% 178{\tt AST\_RANGE} & 179Bit-Index in a signal or element index in array \\ 180\hline 181% 182{\tt AST\_CONSTANT} & 183A literal value \\ 184\hline 185% 186{\tt AST\_CELLTYPE} & 187The type of cell in cell instantiation \\ 188\hline 189% 190{\tt AST\_IDENTIFIER} & 191An Identifier (signal name in expression or cell/task/etc. name in other contexts) \\ 192\hline 193% 194{\tt AST\_PREFIX} & 195Construct an identifier in the form {\tt <prefix>[<index>].<suffix>} (used only in 196advanced generate constructs) \\ 197\hline 198% 199{\tt AST\_FCALL}, 200{\tt AST\_TCALL} & 201Call to function or task \\ 202\hline 203% 204{\tt AST\_TO\_SIGNED}, 205{\tt AST\_TO\_UNSIGNED} & 206The \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}} 218AST Node Type & Corresponding Verilog Construct \\ 219\hline 220\hline 221\arrayrulecolor{gray} 222{\tt AST\_CONCAT} 223{\tt AST\_REPLICATE} & 224The \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} & 233The 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} & 245The 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} & 254Conversion 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} & 262The 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} & 275The 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} & 290The 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} & 301The 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} & 309The logic operators 310\lstinline[language=Verilog];&&;, 311\lstinline[language=Verilog];||; and 312\lstinline[language=Verilog];!; \\ 313\hline 314% 315{\tt AST\_TERNARY} & 316The ternary \lstinline[language=Verilog];?:;-operator \\ 317\hline 318% 319{\tt AST\_MEMRD} 320{\tt AST\_MEMWR} & 321Read and write memories. These nodes are generated by 322the AST simplifier for writes/reads to/from Verilog arrays. \\ 323\hline 324% 325{\tt AST\_ASSIGN} & 326An \lstinline[language=Verilog];assign; statement \\ 327\hline 328% 329{\tt AST\_CELL} & 330A cell instantiation \\ 331\hline 332% 333{\tt AST\_PRIMITIVE} & 334A 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} & 341Verilog \lstinline[language=Verilog];always;- and \lstinline[language=Verilog];initial;-blocks \\ 342\hline 343% 344{\tt AST\_BLOCK} & 345A \lstinline[language=Verilog];begin;-\lstinline[language=Verilog];end;-block \\ 346\hline 347% 348{\tt AST\_ASSIGN\_EQ}. 349{\tt AST\_ASSIGN\_LE} & 350Blocking (\lstinline[language=Verilog];=;) and nonblocking (\lstinline[language=Verilog];<=;) 351assignments 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} & 357The \lstinline[language=Verilog];case; (\lstinline[language=Verilog];if;) statements, conditions within a case 358and the default case respectively \\ 359\hline 360% 361{\tt AST\_FOR} & 362A \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} & 371The \lstinline[language=Verilog];genvar; and 372\lstinline[language=Verilog];generate; keywords and 373\lstinline[language=Verilog];for; and \lstinline[language=Verilog];if; within a 374generate block. \\ 375\hline 376% 377{\tt AST\_POSEDGE}, 378{\tt AST\_NEGEDGE}, 379{\tt AST\_EDGE} & 380Event 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} \\ 391This enum (\lstinline[language=C++]{AST::AstNodeType}) specifies the role of the node. 392Table~\ref{tab:Verilog_AstNodeType} contains a list of all node types. 393\item {\bf The child nodes} \\ 394This is a list of pointers to all children in the abstract syntax tree. 395\item {\bf Attributes} \\ 396As 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 398attribute values are again AST nodes. 399\item {\bf Node content} \\ 400Each node might have additional content data. A series of member variables exist to hold such data. 401For example the member \lstinline[language=C++]{std::string str} can hold a string value and is 402used e.g.~in the {\tt AST\_IDENTIFIER} node type to store the identifier name. 403\item {\bf Source code location} \\ 404Each \lstinline[language=C++]{AST::AstNode} is automatically annotated with the current 405source code location by the \lstinline[language=C++]{AST::AstNode} constructor. It is 406stored in the \lstinline[language=C++]{std::string filename} and \lstinline[language=C++]{int linenum} 407member variables. 408\end{itemize} 409 410The \lstinline[language=C++]{AST::AstNode} constructor can be called with up to 411two child nodes that are automatically added to the list of child nodes for the new object. 412This simplifies the creation of AST nodes for simple expressions a bit. For example the bison 413code 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 422The generated AST data structure is then passed directly to the AST frontend 423that performs the actual conversion to RTLIL. 424 425Note that the Yosys command {\tt read\_verilog} provides the options {\tt -yydebug} 426and {\tt -dump\_ast} that can be used to print the parse tree or abstract syntax tree 427respectively. 428 429\section{Transforming AST to RTLIL} 430 431The {\it AST Frontend} converts a set of modules in AST representation to 432modules in RTLIL representation and adds them to the current design. This is done 433in two steps: {\it simplification} and {\it RTLIL generation}. 434 435The source code to the AST frontend can be found in {\tt frontends/ast/} in the Yosys source tree. 436 437\subsection{AST Simplification} 438 439A full-featured AST is too complex to be transformed into RTLIL directly. Therefore it must 440first be brought into a simpler form. This is done by calling the \lstinline[language=C++]{AST::AstNode::simplify()} 441method of all {\tt AST\_MODULE} nodes in the AST. This initiates a recursive process that performs the following transformations 442on 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 451for each possible case. 452\item Detect array access patterns that are too complicated for the {\tt RTLIL::Memory} abstraction and replace them 453with 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 457In addition to these transformations, the simplifier also annotates the AST with additional information that is needed 458for 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 462is 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 464that contains the declaration of the identifier. If no declaration has been found, an {\tt AST\_AUTOWIRE} node 465is created and used for the annotation. 466\end{itemize} 467 468This produces an AST that is fairly easy to convert to the RTLIL format. 469 470\subsection{Generating RTLIL} 471 472After AST simplification, the \lstinline[language=C++]{AST::AstNode::genRTLIL()} method of each {\tt AST\_MODULE} node 473in the AST is called. This initiates a recursive process that generates equivalent RTLIL data for the AST data. 474 475The \lstinline[language=C++]{AST::AstNode::genRTLIL()} method returns an \lstinline[language=C++]{RTLIL::SigSpec} structure. 476For nodes that represent expressions (operators, constants, signals, etc.), the cells needed to implement the calculation 477described by the expression are created and the resulting signal is returned. That way it is easy to generate the circuits 478for large expressions using depth-first recursion. For nodes that do not represent an expression (such as {\tt 479AST\_CELL}), the corresponding circuit is generated and an empty \lstinline[language=C++]{RTLIL::SigSpec} is returned. 480 481\section{Synthesizing Verilog always Blocks} 482 483For 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} 485objects. 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}- 489or \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()} 492for 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 496within 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 501signal 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 504assigns 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 509assignments are used, \lstinline[language=C++]{AST::AstNode::genRTLIL()} is configured using global variables to use 510the temporary signals that hold the correct intermediate values whenever one of the previously assigned signals is used 511in an expression. 512\end{itemize} 513 514Unfortunately the generation of a correct \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} 515tree for behavioural code is a non-trivial task. The AST frontend solves the problem using the approach described on the following 516pages. 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] 519always @(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; 532end 533\end{lstlisting} 534 535This is translated by the Verilog and AST frontends into the following RTLIL code (attributes, cell parameters 536and wire declarations not included): 537 538\begin{lstlisting}[numbers=left,frame=single,language=rtlil] 539cell $logic_not $logic_not$<input>:4$2 540 connect \A \in1 541 connect \Y $logic_not$<input>:4$2_Y 542end 543cell $xor $xor$<input>:13$3 544 connect \A $1\out1[0:0] 545 connect \B \out2 546 connect \Y $xor$<input>:13$3_Y 547end 548process $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] 577end 578\end{lstlisting} 579 580Note 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} 582has 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 584on the right-hand-side expressions. 585 586The \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} 587tree 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 591evaluated and then the switches within the case are evaluated. (Note that the last assignment on line 13 of the 592Verilog code has been moved to the beginning of the RTLIL process to line 13 of the RTLIL listing.) 593 594I.e.~the special cases deeper in the switch hierarchy override the defaults on the upper levels. The assignments 595in lines 12 and 22 of the RTLIL code serve as an example for this. 596 597Note that in contrast to this, the order within the \lstinline[language=C++]{RTLIL::SwitchRule} objects 598within a \lstinline[language=C++]{RTLIL::CaseRule} is preserved with respect to the original AST and 599Verilog code. 600% 601\item \begin{sloppypar} 602The whole \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree 603describes an asynchronous circuit. I.e.~the decision tree formed by the switches can be seen independently for 604each assigned signal. Whenever one assigned signal changes, all signals that depend on the changed signals 605are to be updated. For example the assignments in lines 16 and 18 in the RTLIL code in fact influence the assignment 606in line 12, even though they are in the ``wrong order''. 607\end{sloppypar} 608\end{itemize} 609 610The only synchronous part of the process is in the \lstinline[language=C++]{RTLIL::SyncRule} object generated at line 61135 in the RTLIL code. The sync rule is the only part of the process where the original signals are assigned. The 612synchronization event from the original Verilog code has been translated into the synchronization type ({\tt posedge}) 613and signal ({\tt \textbackslash clock}) for the \lstinline[language=C++]{RTLIL::SyncRule} object. In the case of 614this simple example the \lstinline[language=C++]{RTLIL::SyncRule} object is later simply transformed into a set of 615d-type flip-flops and the \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree 616to a decision tree using multiplexers. 617 618\begin{sloppypar} 619In more complex examples (e.g.~asynchronous resets) the part of the 620\lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} 621tree that describes the asynchronous reset must first be transformed to the 622correct \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 627The \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} \\ 632These two variables hold the replacement pattern that should be used by \lstinline[language=C++]{AST::AstNode::genRTLIL()} 633for signals with blocking assignments. After initialization of \lstinline[language=C++]{AST_INTERNAL::ProcessGenerator} 634these two variables are empty. 635\end{sloppypar} 636% 637\item \lstinline[language=C++]{subst_lvalue_from} and \lstinline[language=C++]{subst_lvalue_to} \\ 638These two variables contain the mapping from left-hand-side signals ({\tt \textbackslash \it <name>}) to the current 639temporary signal for the same thing (initially {\tt \$0\textbackslash \it <name>}). 640% 641\item \lstinline[language=C++]{current_case} \\ 642A pointer to a \lstinline[language=C++]{RTLIL::CaseRule} object. Initially this is the root case of the 643generated \lstinline[language=C++]{RTLIL::Process}. 644\end{itemize} 645 646As the algorithm runs these variables are continuously modified as well as pushed 647to the stack and later restored to their earlier values by popping from the stack. 648 649On startup the ProcessGenerator generates a new 650\lstinline[language=C++]{RTLIL::Process} object with an empty root case and 651initializes its state variables as described above. Then the \lstinline[language=C++]{RTLIL::SyncRule} objects 652are 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 654AST for this process is evaluated recursively. 655 656During 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 662When an {\tt AST\_ASSIGN\_LE} node is discovered, the following actions are performed by the 663ProcessGenerator: 664 665\begin{itemize} 666\item The left-hand-side is evaluated using \lstinline[language=C++]{AST::AstNode::genRTLIL()} and mapped to 667a 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, 670the values of \lstinline[language=C++]{subst_rvalue_from} and \lstinline[language=C++]{subst_rvalue_to} are used to 671map 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} 674and 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 681When an {\tt AST\_ASSIGN\_EQ} node is discovered, the following actions are performed by 682the 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 689bits 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} 692and 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} 698When an {\tt AST\_CASE} node is discovered, the following actions are performed by 699the 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 708object 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 711saved 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 714in \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} 717and \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 721Then 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 726that 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 737new 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} 740to 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 751Finally 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} 761and 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} 767and 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} 770to \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 776With respect to nonblocking assignments the algorithm is easy: later assignments invalidate earlier assignments. 777For 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 780Note how all the \lstinline[language=C++]{_eq_}-variables become empty when no blocking assignments are used 781and many of the steps in the algorithm can then be ignored as a result of this. 782 783For a variable with blocking assignments the algorithm shows the following behaviour: First a new temporary variable 784is created. This new temporary variable is then registered as the assignment target for all assignments for this 785variable within the cases for this {\tt AST\_CASE} node. Then for each case the new temporary variable is first 786assigned the old temporary variable. This assignment is overwritten if the variable is actually assigned in this 787case and is kept as a default value otherwise. 788 789This yields an \lstinline[language=C++]{RTLIL::CaseRule} that assigns the new temporary variable in all branches. 790So when all cases have been processed a final assignment is added to the containing block that assigns the new 791temporary variable to the old one. Note how this step always overrides a previous assignment to the old temporary 792variable. Other than nonblocking assignments, the old assignment could still have an effect somewhere 793in 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 795the right-hand-side of the old assignment. 796 797\subsection{The proc pass} 798 799The 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 801model 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} \\ 805These two passes just clean up the \lstinline[language=C++]{RTLIL::Process} structure. The {\tt proc\_clean} 806pass removes empty parts (eg. empty assignments) from the process and {\tt proc\_rmdead} detects and removes 807unreachable branches from the process's decision trees. 808% 809\item {\tt proc\_arst} \\ 810This pass detects processes that describe d-type flip-flops with asynchronous 811resets and rewrites the process to better reflect what they are modelling: 812Before this pass, an asynchronous reset has two edge-sensitive sync rules and 813one top-level \C{RTLIL::SwitchRule} for the reset path. After this pass the 814sync rule for the reset is level-sensitive and the top-level 815\C{RTLIL::SwitchRule} has been removed. 816% 817\item {\tt proc\_mux} \\ 818This pass converts the \C{RTLIL::CaseRule}/\C{RTLIL::SwitchRule}-tree to a tree 819of multiplexers per written signal. After this, the \C{RTLIL::Process} structure only contains 820the \C{RTLIL::SyncRule}s that describe the output registers. 821% 822\item {\tt proc\_dff} \\ 823This pass replaces the \C{RTLIL::SyncRule}s to d-type flip-flops (with 824asynchronous resets if necessary). 825% 826\item {\tt proc\_dff} \\ 827This pass replaces the \C{RTLIL::MemWriteActions}s with {\tt \$memwr} cells. 828% 829\item {\tt proc\_clean} \\ 830A final call to {\tt proc\_clean} removes the now empty \C{RTLIL::Process} objects. 831\end{itemize} 832 833Performing these last processing steps in passes instead of in the Verilog frontend has two important benefits: 834 835First it improves the transparency of the process. Everything that happens in a separate pass is easier to debug, 836as the RTLIL data structures can be easily investigated before and after each of the steps. 837 838Second it improves flexibility. This scheme can easily be extended to support other types of storage-elements, such 839as sr-latches or d-latches, without having to extend the actual Verilog frontend. 840 841\section{Synthesizing Verilog Arrays} 842 843\begin{fixme} 844Add some information on the generation of {\tt \$memrd} and {\tt \$memwr} cells 845and how they are processed in the {\tt memory} pass. 846\end{fixme} 847 848\section{Synthesizing Parametric Designs} 849 850\begin{fixme} 851Add some information on the \lstinline[language=C++]{RTLIL::Module::derive()} method and how it 852is used to synthesize parametric modules via the {\tt hierarchy} pass. 853\end{fixme} 854 855