path: root/manual/CHAPTER_Verilog.tex

\chapter{The Verilog and AST Frontends}
\label{chapter:verilog}

This chapter provides an overview of the implementation of the Yosys Verilog
and AST frontends. The Verilog frontend reads Verilog-2005 code and creates
an abstract syntax tree (AST) representation of the input. This AST representation
is then passed to the AST frontend that converts it to RTLIL data, as illustrated
in Fig.~\ref{fig:Verilog_flow}.

\begin{figure}[b!]
	\hfil
	\begin{tikzpicture}
		\tikzstyle{process} = [draw, fill=green!10, rectangle, minimum height=3em, minimum width=10em, node distance=5em, font={\ttfamily}]
		\tikzstyle{data} = [draw, fill=blue!10, ellipse, minimum height=3em, minimum width=7em, node distance=5em, font={\ttfamily}]

		\node[data]    (n1)               {Verilog Source};
		\node[process] (n2) [below of=n1] {Verilog Frontend};
		\node[data]    (n3) [below of=n2] {AST};
		\node[process] (n4) [below of=n3] {AST Frontend};
		\node[data]    (n5) [below of=n4] {RTLIL};

		\draw[-latex] (n1) -- (n2);
		\draw[-latex] (n2) -- (n3);
		\draw[-latex] (n3) -- (n4);
		\draw[-latex] (n4) -- (n5);

		\tikzstyle{details} = [draw, fill=yellow!5, rectangle, node distance=6cm, font={\ttfamily}]

		\node[details] (d1) [right of=n2] {\begin{minipage}{5cm}
			\hfil
			\begin{tikzpicture}
				\tikzstyle{subproc} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=10em, node distance=3em, font={\ttfamily}]
				\node (s0) {};
				\node[subproc] (s1) [below of=s0] {Preprocessor};
				\node[subproc] (s2) [below of=s1] {Lexer};
				\node[subproc] (s3) [below of=s2] {Parser};
				\node[node distance=3em] (s4) [below of=s3] {};
				\draw[-latex] (s0) -- (s1);
				\draw[-latex] (s1) -- (s2);
				\draw[-latex] (s2) -- (s3);
				\draw[-latex] (s3) -- (s4);
			\end{tikzpicture}
		\end{minipage}};

		\draw[dashed] (n2.north east) -- (d1.north west);
		\draw[dashed] (n2.south east) -- (d1.south west);

		\node[details] (d2) [right of=n4] {\begin{minipage}{5cm}
			\hfil
			\begin{tikzpicture}
				\tikzstyle{subproc} = [draw, fill=green!10, rectangle, minimum height=2em, minimum width=10em, node distance=3em, font={\ttfamily}]
				\node (s0) {};
				\node[subproc] (s1) [below of=s0] {Simplifier};
				\node[subproc] (s2) [below of=s1] {RTLIL Generator};
				\node[node distance=3em] (s3) [below of=s2] {};
				\draw[-latex] (s0) -- (s1);
				\draw[-latex] (s1) -- (s2);
				\draw[-latex] (s2) -- (s3);
			\end{tikzpicture}
		\end{minipage}};

		\draw[dashed] (n4.north east) -- (d2.north west);
		\draw[dashed] (n4.south east) -- (d2.south west);

	\end{tikzpicture}
	\caption{Simplified Verilog to RTLIL data flow}
	\label{fig:Verilog_flow}
\end{figure}


\section{Transforming Verilog to AST}

The {\it Verilog frontend} converts the Verilog sources to an internal AST representation that closely resembles
the structure of the original Verilog code. The Verilog frontend consists of three components, the
{\it Preprocessor}, the {\it Lexer} and the {\it Parser}.

The source code to the Verilog frontend can be found in {\tt frontends/verilog/} in the Yosys source tree.

\subsection{The Verilog Preprocessor}

The Verilog preprocessor scans over the Verilog source code and interprets some of the Verilog compiler
directives such as \lstinline[language=Verilog]{`include}, \lstinline[language=Verilog]{`define} and
\lstinline[language=Verilog]{`ifdef}.

It is implemented as a C++ function that is passed a file descriptor as input and returns the
pre-processed Verilog code as a \lstinline[language=C++]{std::string}.

The source code to the Verilog Preprocessor can be found in {\tt
frontends/verilog/preproc.cc} in the Yosys source tree.

\subsection{The Verilog Lexer}

\begin{sloppypar}
The Verilog Lexer is written using the lexer generator {\it flex} \citeweblink{flex}. Its source code
can be found in {\tt frontends/verilog/lexer.l} in the Yosys source tree.
The lexer does little more than identifying all keywords and literals
recognised by the Yosys Verilog frontend.
\end{sloppypar}

The lexer keeps track of the current location in the verilog source code using
some global variables. These variables are used by the constructor of AST nodes
to annotate each node with the source code location it originated from.

\begin{sloppypar}
Finally the lexer identifies and handles special comments such as
``\lstinline[language=Verilog]{// synopsys translate_off}'' and
``\lstinline[language=Verilog]{// synopsys full_case}''. (It is recommended to
use \lstinline[language=Verilog]{`ifdef} constructs instead of the Synsopsys
translate\_on/off comments and attributes such as
\lstinline[language=Verilog]{(* full_case *)} over ``\lstinline[language=Verilog]{// synopsys full_case}''
whenever possible.)
\end{sloppypar}

\subsection{The Verilog Parser}

The Verilog Parser is written using the parser generator {\it bison} \citeweblink{bison}. Its source code
can be found in {\tt frontends/verilog/parser.y} in the Yosys source tree.

It generates an AST using the \lstinline[language=C++]{AST::AstNode} data structure
defined in {\tt frontends/ast/ast.h}. An \lstinline[language=C++]{AST::AstNode} object has
the following properties:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table}[b!]
\hfil
\begin{tabular}{>{\raggedright\arraybackslash}p{7cm}>{\raggedright\arraybackslash}p{8cm}}
AST Node Type & Corresponding Verilog Construct \\
\hline
\hline
\arrayrulecolor{gray}
{\tt AST\_NONE} & This Node type should never be used. \\
\hline
%
{\tt AST\_DESIGN} & This node type is used for the top node of the AST tree. It
has no corresponding Verilog construct. \\
\hline
%
{\tt AST\_MODULE},
{\tt AST\_TASK},
{\tt AST\_FUNCTION} &
\lstinline[language=Verilog];module;,
\lstinline[language=Verilog];task; and
\lstinline[language=Verilog];function; \\
\hline
%
{\tt AST\_WIRE} &
\lstinline[language=Verilog];input;,
\lstinline[language=Verilog];output;,
\lstinline[language=Verilog];wire;,
\lstinline[language=Verilog];reg; and
\lstinline[language=Verilog];integer; \\
\hline
%
{\tt AST\_MEMORY}  &
Verilog Arrays \\
\hline
%
{\tt AST\_AUTOWIRE} &
Created by the simplifier when an undeclared signal name is used. \\
\hline
%
{\tt AST\_PARAMETER},
{\tt AST\_LOCALPARAM} &
\lstinline[language=Verilog];parameter; and
\lstinline[language=Verilog];localparam; \\
\hline
%
{\tt AST\_PARASET} &
Parameter set in cell instanciation \\
\hline
%
{\tt AST\_ARGUMENT} &
Port connection in cell instanciation \\
\hline
%
{\tt AST\_RANGE} &
Bit-Index in a signal or element index in array \\
\hline
%
{\tt AST\_CONSTANT} &
A literal value \\
\hline
%
{\tt AST\_CELLTYPE} &
The type of cell in cell instanciation \\
\hline
%
{\tt AST\_IDENTIFIER} &
An Identifier (signal name in expression or cell/task/etc. name in other contexts) \\
\hline
%
{\tt AST\_PREFIX} &
Construct an identifier in the form {\tt <prefix>[<index>].<suffix>} (used only in
advanced generate constructs) \\
\hline
%
{\tt AST\_FCALL},
{\tt AST\_TCALL} &
Call to function or task \\
\hline
%
{\tt AST\_TO\_SIGNED},
{\tt AST\_TO\_UNSIGNED} &
The \lstinline[language=Verilog];$signed(); and
\lstinline[language=Verilog];$unsigned(); functions \\
\hline
\end{tabular}
\caption{AST node types with their corresponding Verilog constructs. \\ (continued on next page)}
\label{tab:Verilog_AstNodeType}
\end{table}

\begin{table}[t!]
\ContinuedFloat
\hfil
\begin{tabular}{>{\raggedright\arraybackslash}p{7cm}>{\raggedright\arraybackslash}p{8cm}}
AST Node Type & Corresponding Verilog Construct \\
\hline
\hline
\arrayrulecolor{gray}
{\tt AST\_CONCAT}
{\tt AST\_REPLICATE} &
The \lstinline[language=Verilog];{...}; and
\lstinline[language=Verilog];{...{...}}; operators \\
\hline
%
{\tt AST\_BIT\_NOT},
{\tt AST\_BIT\_AND},
{\tt AST\_BIT\_OR},
{\tt AST\_BIT\_XOR},
{\tt AST\_BIT\_XNOR} &
The bitwise operators \break
\lstinline[language=Verilog];~;,
\lstinline[language=Verilog];&;,
\lstinline[language=Verilog];|;,
\lstinline[language=Verilog];^; and
\lstinline[language=Verilog];~^; \\
\hline
%
{\tt AST\_REDUCE\_AND},
{\tt AST\_REDUCE\_OR},
{\tt AST\_REDUCE\_XOR},
{\tt AST\_REDUCE\_XNOR} &
The unary reduction operators \break
\lstinline[language=Verilog];~;,
\lstinline[language=Verilog];&;,
\lstinline[language=Verilog];|;,
\lstinline[language=Verilog];^; and
\lstinline[language=Verilog];~^; \\
\hline
%
{\tt AST\_REDUCE\_BOOL} &
Conversion from multi-bit value to boolian value
(equivialent to {\tt AST\_REDUCE\_OR}) \\
\hline
%
{\tt AST\_SHIFT\_LEFT},
{\tt AST\_SHIFT\_RIGHT},
{\tt AST\_SHIFT\_SLEFT},
{\tt AST\_SHIFT\_SRIGHT} &
The shift operators \break
\lstinline[language=Verilog];<<;,
\lstinline[language=Verilog];>>;,
\lstinline[language=Verilog];<<<; and
\lstinline[language=Verilog];>>>; \\
\hline
%
{\tt AST\_LT},
{\tt AST\_LE},
{\tt AST\_EQ},
{\tt AST\_NE},
{\tt AST\_GE},
{\tt AST\_GT} &
The relational operators \break
\lstinline[language=Verilog];<;,
\lstinline[language=Verilog];<=;,
\lstinline[language=Verilog];==;,
\lstinline[language=Verilog];!=;,
\lstinline[language=Verilog];>=; and
\lstinline[language=Verilog];>; \\
\hline
%
{\tt AST\_ADD},
{\tt AST\_SUB},
{\tt AST\_MUL},
{\tt AST\_DIV},
{\tt AST\_MOD},
{\tt AST\_POW} &
The binary operators \break
\lstinline[language=Verilog];+;,
\lstinline[language=Verilog];-;,
\lstinline[language=Verilog];*;,
\lstinline[language=Verilog];/;,
\lstinline[language=Verilog];%; and
\lstinline[language=Verilog];**; \\
\hline
%
{\tt AST\_POS},
{\tt AST\_NEG} &
The prefix operators
\lstinline[language=Verilog];+; and
\lstinline[language=Verilog];-; \\
\hline
%
{\tt AST\_LOGIC\_AND},
{\tt AST\_LOGIC\_OR},
{\tt AST\_LOGIC\_NOT} &
The logic operators
\lstinline[language=Verilog];&&;,
\lstinline[language=Verilog];||; and
\lstinline[language=Verilog];!; \\
\hline
%
{\tt AST\_TERNARY} &
The ternary \lstinline[language=Verilog];?:;-operator \\
\hline
%
{\tt AST\_MEMRD}
{\tt AST\_MEMWR} &
Read and write memories. These nodes are generated by
the AST simplifier for writes/reads to/from Verilog arrays. \\
\hline
%
{\tt AST\_ASSIGN} &
An \lstinline[language=Verilog];assign; statement \\
\hline
%
{\tt AST\_CELL} &
A cell instanciation \\
\hline
%
{\tt AST\_PRIMITIVE} &
A primitive cell (\lstinline[language=Verilog];and;,
\lstinline[language=Verilog];nand;,
\lstinline[language=Verilog];or;, etc.) \\
\hline
%
{\tt AST\_ALWAYS},
{\tt AST\_INITIAL} &
Verilog \lstinline[language=Verilog];always;- and \lstinline[language=Verilog];initial;-blocks \\
\hline
%
{\tt AST\_BLOCK} &
A \lstinline[language=Verilog];begin;-\lstinline[language=Verilog];end;-block \\
\hline
%
{\tt AST\_ASSIGN\_EQ}.
{\tt AST\_ASSIGN\_LE} &
Blocking (\lstinline[language=Verilog];=;) and nonblocking (\lstinline[language=Verilog];<=;)
assignments within an \lstinline[language=Verilog];always;- or \lstinline[language=Verilog];initial;-block \\
\hline
%
{\tt AST\_CASE}.
{\tt AST\_COND},
{\tt AST\_DEFAULT} &
The \lstinline[language=Verilog];case; (\lstinline[language=Verilog];if;) statements, conditions within a case
and the default case respectively \\
\hline
%
{\tt AST\_FOR} &
A \lstinline[language=Verilog];for;-loop witn an
\lstinline[language=Verilog];always;- or
\lstinline[language=Verilog];initial;-block \\
\hline
%
{\tt AST\_GENVAR},
{\tt AST\_GENBLOCK},
{\tt AST\_GENFOR},
{\tt AST\_GENIF} &
The \lstinline[language=Verilog];genvar; and
\lstinline[language=Verilog];generate; keywords and
\lstinline[language=Verilog];for; and \lstinline[language=Verilog];if; within a
generate block. \\
\hline
%
{\tt AST\_POSEDGE},
{\tt AST\_NEGEDGE},
{\tt AST\_EDGE} &
Event conditions for \lstinline[language=Verilog];always; blocks. \\
\hline
\end{tabular}
\caption{AST node types with their corresponding Verilog constructs. \\ (continuation from previous page)}
\label{tab:Verilog_AstNodeTypeCont}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{itemize}
\item {\bf The node type} \\
This enum (\lstinline[language=C++]{AST::AstNodeType}) specifies the role of the node.
Table~\ref{tab:Verilog_AstNodeType} contains a list of all node types.
\item {\bf The child nodes} \\
This is a list of pointers to all children in the abstract syntax tree.
\item {\bf Attributes} \\
As almost every AST node might have Verilog attributes assigned to it, the
\lstinline[language=C++]{AST::AstNode} has direct support for attributes. Note that the
attribute values are again AST nodes.
\item {\bf Node content} \\
Each node might have additional content data. A series of member variables exist to hold such data.
For example the member \lstinline[language=C++]{std::string str} can hold a string value and is
used e.g.~in the {\tt AST\_IDENTIFIER} node type to store the identifier name.
\item {\bf Source code location} \\
Each \lstinline[language=C++]{AST::AstNode} is automatically annotated with the current
source code location by the \lstinline[language=C++]{AST::AstNode} constructor. It is
stored in the \lstinline[language=C++]{std::string filename} and \lstinline[language=C++]{int linenum}
member variables.
\end{itemize}

The \lstinline[language=C++]{AST::AstNode} constructor can be called with up to
two child nodes that are automatically added to the list of child nodes for the new object.
This simplifies the creation of AST nodes for simple expressions a bit. For example the bison
code for parsing multiplications:

\begin{lstlisting}[numbers=left,frame=single]
        basic_expr '*' attr basic_expr {
                $$ = new AstNode(AST_MUL, $1, $4);
                append_attr($$, $3);
        } |
\end{lstlisting}

The generated AST data structure is then passed directly to the AST frontend
that performs the actual conversion to RTLIL.

Note that the Yosys command {\tt read\_verilog} provides the options {\tt -yydebug}
and {\tt -dump\_ast} that can be used to print the parse tree or abstract syntax tree
respectively.

\section{Transforming AST to RTLIL}

The {\it AST Frontend} converts a set of modules in AST representation to
modules in RTLIL representation and adds them to the current design. This is done
in two steps: {\it simplification} and {\it RTLIL generation}.

The source code to the AST frontend can be found in {\tt frontends/ast/} in the Yosys source tree.

\subsection{AST Simplification}

A full-featured AST is too complex to be transformed into RTLIL directly. Therefore it must
first be brought into a simpler form. This is done by calling the \lstinline[language=C++]{AST::AstNode::simplify()}
method of all {\tt AST\_MODULE} nodes in the AST. This initiates a recursive process that performs the following transformations
on the AST data structure:

\begin{itemize}
\item Inline all task and function calls.
\item Evaluate all \lstinline[language=Verilog]{generate}-statements and unroll all \lstinline[language=Verilog]{for}-loops.
\item Perform const folding where it is neccessary (e.g.~in the value part of {\tt AST\_PARAMETER}, {\tt AST\_LOCALPARAM},
{\tt AST\_PARASET} and {\tt AST\_RANGE} nodes).
\item Replace {\tt AST\_PRIMITIVE} nodes with appropriate {\tt AST\_ASSIGN} nodes.
\item Replace dynamic bit ranges in the left-hand-side of assignments with {\tt AST\_CASE} nodes with {\tt AST\_COND} children
for each possible case.
\item Detect array access patterns that are too complicated for the {\tt RTLIL::Memory} abstraction and replace them
with a set of signals and cases for all reads and/or writes.
\item Otherwise replace array accesses with {\tt AST\_MEMRD} and {\tt AST\_MEMWR} nodes.
\end{itemize}

In addition to these transformations, the simplifier also annotates the AST with additional information that is needed
for the RTLIL generator, namely:

\begin{itemize}
\item All ranges (width of signals and bit selections) are not only const folded but (when a constant value
is found) are also written to member variables in the {\tt AST\_RANGE} node.
\item All identifiers are resolved and all {\tt AST\_IDENTIFIER} nodes are annotated with a pointer to the AST node
that contains the declaration of the identifier. If no declaration has been found, an {\tt AST\_AUTOWIRE} node
is created and used for the annotation.
\end{itemize}

This produces an AST that is fairly easy to convert to the RTLIL format.

\subsection{Generating RTLIL}

After AST simplification, the \lstinline[language=C++]{AST::AstNode::genRTLIL()} method of each {\tt AST\_MODULE} node
in the AST is called. This initiates a recursive process that generates equivialent RTLIL data for the AST data.

The \lstinline[language=C++]{AST::AstNode::genRTLIL()} method returns an \lstinline[language=C++]{RTLIL::SigSpec} structure.
For nodes that represent expressions (operators, constants, signals, etc.), the cells needed to implement the calculation
described by the expression are created and the resulting signal is returned. That way it is easy to generate the circuits
for large expressions using depth-first recursion. For nodes that do not represent an expression (such as {\tt
AST\_CELL}), the corresponding circuit is generated and an empty \lstinline[language=C++]{RTLIL::SigSpec} is returned.

\section{Synthesizing Verilog always Blocks}

For behavioural Verilog code (code utilizing \lstinline[language=Verilog]{always}- and
\lstinline[language=Verilog]{initial}-blocks) it is necessary to also generate \lstinline[language=C++]{RTLIL::Process}
objects. This is done in the following way:

\begin{itemize}
\item Whenever \lstinline[language=C++]{AST::AstNode::genRTLIL()} encounters an \lstinline[language=Verilog]{always}-
or \lstinline[language=Verilog]{initial}-block, it creates an instance of
\lstinline[language=Verilog]{AST_INTERNAL::ProcessGenerator}. This object then generates the
\lstinline[language=C++]{RTLIL::Process} object for the block. It also calls \lstinline[language=C++]{AST::AstNode::genRTLIL()}
for all right-hand-side expressions contained within the block.
%
\begin{sloppypar}
\item First the  \lstinline[language=Verilog]{AST_INTERNAL::ProcessGenerator} creates a list of all signals assigned
within the block. It then creates a set of temporary signals using the naming scheme {\tt \$\it<number>\tt
\textbackslash\it <original\_name>} for each of the assigned signals.
\end{sloppypar}
%
\item Then an \lstinline[language=C++]{RTLIL::Process} is created that assigns all intermediate values for each left-hand-side
signal to the temporary signal in its \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree.
%
\item Finally a \lstinline[language=C++]{RTLIL::SyncRule} is created for the \lstinline[language=C++]{RTLIL::Process} that
assigns the temporary signals for the final values to the actual signals.
%
\item Calls to \lstinline[language=C++]{AST::AstNode::genRTLIL()} are generated for right hand sides as needed. When blocking
assignments are used, \lstinline[language=C++]{AST::AstNode::genRTLIL()} is configured using global variables to use
the temporary signals that hold the correct intermediate values whenever one of the previously assigned signals is used
in an expression.
\end{itemize}

Unfortunately the generation of a correct \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule}
tree for behavioural code is a non-trivial task. The AST frontend solves the problem using the approach described on the following
pages. The following example illustrates what the algorithm is supposed to do. Consider the following Verilog code:

\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
always @(posedge clock) begin
	out1 = in1;
	if (in2)
		out1 = !out1;
	out2 <= out1;
	if (in3)
		out2 <= out2;
	if (in4)
		if (in5)
			out3 <= in6;
		else
			out3 <= in7;
	out1 = out1 ^ out2;
end
\end{lstlisting}

This is translated by the Verilog and AST frontends into the following RTLIL code (attributes, cell parameters
and wire declarations not included):

\begin{lstlisting}[numbers=left,frame=single,language=rtlil]
cell $logic_not $logic_not$<input>:4$2
  connect \A \in1
  connect \Y $logic_not$<input>:4$2_Y
end
cell $xor $xor$<input>:13$3
  connect \A $1\out1[0:0]
  connect \B \out2
  connect \Y $xor$<input>:13$3_Y
end
process $proc$<input>:1$1
  assign $0\out3[0:0] \out3
  assign $0\out2[0:0] $1\out1[0:0]
  assign $0\out1[0:0] $xor$<input>:13$3_Y
  switch \in2
    case 1'1
      assign $1\out1[0:0] $logic_not$<input>:4$2_Y
    case 
      assign $1\out1[0:0] \in1
  end
  switch \in3
    case 1'1
      assign $0\out2[0:0] \out2
    case 
  end
  switch \in4
    case 1'1
      switch \in5
        case 1'1
          assign $0\out3[0:0] \in6
        case 
          assign $0\out3[0:0] \in7
      end
    case 
  end
  sync posedge \clock
    update \out1 $0\out1[0:0]
    update \out2 $0\out2[0:0]
    update \out3 $0\out3[0:0]
end
\end{lstlisting}

Note that the two operators are translated into separate cells outside the generated process. The signal
\lstinline[language=Verilog]{out1} is assigned using blocking assignments and therefore \lstinline[language=Verilog]{out1}
has been replaced with a different signal in all expressions after the initial assignment. The signal
\lstinline[language=Verilog]{out2} is assigned using nonblocking assignments and therefore is not substituted
on the right-hand-side expressions.

The \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule}
tree must be interpreted the following way:

\begin{itemize}
\item On each case level (the body of the process is the {\it root case}), first the actions on this level are
evaluated and then the switches within the case are evaluated. (Note that the last assignment on line 13 of the
Verilog code has been moved to the beginning of the RTLIL process to line 13 of the RTLIL listing.)

I.e.~the special cases deeper in the switch hierarchy override the defaults on the upper levels. The assignments
in lines 12 and 22 of the RTLIL code serve as an example for this.

Note that in contrast to this, the order within the \lstinline[language=C++]{RTLIL::SwitchRule} objects
within a \lstinline[language=C++]{RTLIL::CaseRule} is preserved with respect to the original AST and
Verilog code.
%
\item \begin{sloppypar}
The whole \lstinline[language=C++]{RTLIL::CaseRule}/\lstinline[language=C++]{RTLIL::SwitchRule} tree
describes an asynchronous circuit. I.e.~the decision tree formed by the switches can be seen independently for
each assigned signal. Whenever one assigned signal changes, all signals that depend on the changed signals
are to be updated. For example the assignments in lines 16 and 18 in the RTLIL code in fact influence the assignment
in line 12, even though they are in the ``wrong order''.
\end{sloppypar}
\end{itemize}

The only synchronous part of the process is in the \lstinline[language=C++]{RTLIL::SyncRule} object generated at line
35 in the RTLIL code. The sync rule is the only part of the process where the original signals are assigned. The
return i;
    return -1;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrRemove( Vec_Ptr_t * p, void * Entry )
{
    int i;
    // delete assuming that it is closer to the end
    for ( i = p->nSize - 1; i >= 0; i-- )
        if ( p->pArray[i] == Entry )
            break;
    assert( i >= 0 );
/*
    // delete assuming that it is closer to the beginning
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            break;
    assert( i < p->nSize );
*/
    for ( i++; i < p->nSize; i++ )
        p->pArray[i-1] = p->pArray[i];
    p->nSize--;
}

/**Function*************************************************************

  Synopsis    [Interts entry at the index iHere. Shifts other entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrInsert( Vec_Ptr_t * p, int iHere, void * Entry )
{
    int i;
    assert( iHere >= 0 && iHere < p->nSize );
    Vec_PtrPush( p, 0 );
    for ( i = p->nSize - 1; i > iHere; i-- )
        p->pArray[i] = p->pArray[i-1];
    p->pArray[i] = Entry;
}

/**Function*************************************************************

  Synopsis    [Moves the first nItems to the end.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReorder( Vec_Ptr_t * p, int nItems )
{
    assert( nItems < p->nSize );
    Vec_PtrGrow( p, nItems + p->nSize );
    memmove( (char **)p->pArray + p->nSize, p->pArray, nItems * sizeof(void*) );
    memmove( p->pArray, (char **)p->pArray + nItems, p->nSize * sizeof(void*) );
}

/**Function*************************************************************

  Synopsis    [Reverses the order of entries.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReverseOrder( Vec_Ptr_t * p )
{
    void * Temp;
    int i;
    for ( i = 0; i < p->nSize/2; i++ )
    {
        Temp = p->pArray[i];
        p->pArray[i] = p->pArray[p->nSize-1-i];
        p->pArray[p->nSize-1-i] = Temp;
    }
}

/**Function*************************************************************

  Synopsis    [Checks if two vectors are equal.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrEqual( Vec_Ptr_t * p1, Vec_Ptr_t * p2 ) 
{
    int i;
    if ( p1->nSize != p2->nSize )
        return 0;
    for ( i = 0; i < p1->nSize; i++ )
        if ( p1->pArray[i] != p2->pArray[i] )
            return 0;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Comparison procedure for two integers.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static int Vec_PtrSortComparePtr( void ** pp1, void ** pp2 )
{
    if ( *pp1 < *pp2 )
        return -1;
    if ( *pp1 > *pp2 ) 
        return 1;
    return 0; 
}

/**Function*************************************************************

  Synopsis    [Sorting the entries by their integer value.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused;
static void Vec_PtrSort( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() )
{
    if ( p->nSize < 2 )
        return;
    if ( Vec_PtrSortCompare == NULL )
        qsort( (void *)p->pArray, p->nSize, sizeof(void *), 
                (int (*)(const void *, const void *)) Vec_PtrSortComparePtr );
    else
        qsort( (void *)p->pArray, p->nSize, sizeof(void *), 
                (int (*)(const void *, const void *)) Vec_PtrSortCompare );
}

/**Function*************************************************************

  Synopsis    [Sorting the entries by their integer value.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() ) ___unused;
static void Vec_PtrUniqify( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)() )
{
    int i, k;
    if ( p->nSize < 2 )
        return;
    Vec_PtrSort( p, Vec_PtrSortCompare );
    for ( i = k = 1; i < p->nSize; i++ )
        if ( p->pArray[i] != p->pArray[i-1] )
            p->pArray[k++] = p->pArray[i];
    p->nSize = k;
}
static void Vec_PtrUniqify2( Vec_Ptr_t * p, int (*Vec_PtrSortCompare)(), void (*Vec_PtrObjFree)(), Vec_Int_t * vCounts )
{
    int i, k;
    if ( vCounts )
        Vec_IntFill( vCounts, 1, 1 );
    if ( p->nSize < 2 )
        return;
    Vec_PtrSort( p, Vec_PtrSortCompare );
    for ( i = k = 1; i < p->nSize; i++ )
        if ( Vec_PtrSortCompare(p->pArray+i, p->pArray+k-1) != 0 )
        {
            p->pArray[k++] = p->pArray[i];
            if ( vCounts )
                Vec_IntPush( vCounts, 1 );
        }
        else 
        {
            if ( Vec_PtrObjFree )
                Vec_PtrObjFree( p->pArray[i] );
            if ( vCounts )
                Vec_IntAddToEntry( vCounts, Vec_IntSize(vCounts)-1, 1 );
        }
    p->nSize = k;
    assert( vCounts == NULL || Vec_IntSize(vCounts) == Vec_PtrSize(p) );
}



/**Function*************************************************************

  Synopsis    [Allocates the array of simulation info.]

  Description [Allocates the array containing given number of entries, 
  each of which contains given number of unsigned words of simulation data.
  The resulting array can be freed using regular procedure Vec_PtrFree().
  It is the responsibility of the user to ensure this array is never grown.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Vec_Ptr_t * Vec_PtrAllocSimInfo( int nEntries, int nWords )
{
    void ** pMemory;
    unsigned * pInfo;
    int i;
    pMemory = (void **)ABC_ALLOC( char, (sizeof(void *) + sizeof(unsigned) * nWords) * nEntries );
    pInfo = (unsigned *)(pMemory + nEntries);
    for ( i = 0; i < nEntries; i++ )
        pMemory[i] = pInfo + i * nWords;
    return Vec_PtrAllocArray( pMemory, nEntries );
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Vec_PtrReadWordsSimInfo( Vec_Ptr_t * p )
{
    return (unsigned *)Vec_PtrEntry(p,1) - (unsigned *)Vec_PtrEntry(p,0);
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrCleanSimInfo( Vec_Ptr_t * vInfo, int iWord, int nWords )
{
    int i;
    for ( i = 0; i < vInfo->nSize; i++ )
        memset( (char*)Vec_PtrEntry(vInfo,i) + 4*iWord, 0, 4*(nWords-iWord) );
}

/**Function*************************************************************

  Synopsis    [Cleans simulation info of each entry beginning with iWord.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrFillSimInfo( Vec_Ptr_t * vInfo, int iWord, int nWords )
{
    int i;
    for ( i = 0; i < vInfo->nSize; i++ )
        memset( (char*)Vec_PtrEntry(vInfo,i) + 4*iWord, 0xFF, 4*(nWords-iWord) );
}

/**Function*************************************************************

  Synopsis    [Resizes the array of simulation info.]

  Description [Doubles the number of objects for which siminfo is allocated.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrDoubleSimInfo( Vec_Ptr_t * vInfo )
{
    Vec_Ptr_t * vInfoNew;
    int nWords;
    assert( Vec_PtrSize(vInfo) > 1 );
    // get the new array
    nWords = (unsigned *)Vec_PtrEntry(vInfo,1) - (unsigned *)Vec_PtrEntry(vInfo,0);
    vInfoNew = Vec_PtrAllocSimInfo( 2*Vec_PtrSize(vInfo), nWords );
    // copy the simulation info
    memcpy( Vec_PtrEntry(vInfoNew,0), Vec_PtrEntry(vInfo,0), Vec_PtrSize(vInfo) * nWords * 4 );
    // replace the array
    ABC_FREE( vInfo->pArray );
    vInfo->pArray = vInfoNew->pArray;
    vInfo->nSize *= 2;
    vInfo->nCap *= 2;
    // free the old array
    vInfoNew->pArray = NULL;
    ABC_FREE( vInfoNew );
}

/**Function*************************************************************

  Synopsis    [Resizes the array of simulation info.]

  Description [Doubles the number of simulation patterns stored for each object.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Vec_PtrReallocSimInfo( Vec_Ptr_t * vInfo )
{
    Vec_Ptr_t * vInfoNew;
    int nWords, i;
    assert( Vec_PtrSize(vInfo) > 1 );
    // get the new array
    nWords = (unsigned *)Vec_PtrEntry(vInfo,1) - (unsigned *)Vec_PtrEntry(vInfo,0);
    vInfoNew = Vec_PtrAllocSimInfo( Vec_PtrSize(vInfo), 2*nWords );
    // copy the simulation info
    for ( i = 0; i < vInfo->nSize; i++ )
        memcpy( Vec_PtrEntry(vInfoNew,i), Vec_PtrEntry(vInfo,i), nWords * 4 );
    // replace the array
    ABC_FREE( vInfo->pArray );
    vInfo->pArray = vInfoNew->pArray;
    // free the old array
    vInfoNew->pArray =