summaryrefslogtreecommitdiff
path: root/manual/CHAPTER_Optimize.tex
diff options
context:
space:
mode:
authorClifford Wolf <clifford@clifford.at>2013-07-20 15:19:12 +0200
committerClifford Wolf <clifford@clifford.at>2013-07-20 15:19:12 +0200
commit61ed6b32d1f5fbfda9c6effdaa678092f8156bfa (patch)
tree3a53692cbd93a09eabeb67eff5e9e4ace5cf1a3e /manual/CHAPTER_Optimize.tex
parent3650fd7fbe45a00792770d9ecb9397bc27ea0845 (diff)
Added Yosys Manual
Diffstat (limited to 'manual/CHAPTER_Optimize.tex')
-rw-r--r--manual/CHAPTER_Optimize.tex320
1 files changed, 320 insertions, 0 deletions
diff --git a/manual/CHAPTER_Optimize.tex b/manual/CHAPTER_Optimize.tex
new file mode 100644
index 00000000..c562650b
--- /dev/null
+++ b/manual/CHAPTER_Optimize.tex
@@ -0,0 +1,320 @@
+
+\chapter{Optimizations}
+\label{chapter:opt}
+
+Yosys employs a number of optimizations to generate better and cleaner results.
+This chapter outlines these optimizations.
+
+\section{Simple Optimizations}
+
+The Yosys pass {\tt opt} runs a number of simple optimizations. This includes removing unused
+signals and cells and const folding. It is recommended to run this pass after each major step
+in the synthesis script. At the time of this writing the {\tt opt} pass executes the following
+passes that each perform a simple optimization:
+
+\begin{itemize}
+\item Once at the beginning of {\tt opt}:
+\begin{itemize}
+\item {\tt opt\_const}
+\item {\tt opt\_share -nomux}
+\end{itemize}
+\item Repeat until result is stable:
+\begin{itemize}
+\item {\tt opt\_muxtree}
+\item {\tt opt\_reduce}
+\item {\tt opt\_share}
+\item {\tt opt\_rmdff}
+\item {\tt opt\_clean}
+\item {\tt opt\_const}
+\end{itemize}
+\end{itemize}
+
+The following section describes each of the {\tt opt\_*} passes.
+
+\subsection{The opt\_const pass}
+
+This pass performs const folding on the internal combinational cell types
+described in Chap.~\ref{chapter:celllib}. This means a cell with all constant
+inputs is replaced with the constant value this cell drives. In some cases
+this pass can also optimize cells with some constant inputs.
+
+\begin{table}
+ \hfil
+ \begin{tabular}{cc|c}
+ A-Input & B-Input & Replacement \\
+ \hline
+ any & 0 & 0 \\
+ 0 & any & 0 \\
+ 1 & 1 & 1 \\
+ \hline
+ X/Z & X/Z & X \\
+ 1 & X/Z & X \\
+ X/Z & 1 & X \\
+ \hline
+ any & X/Z & 0 \\
+ X/Z & any & 0 \\
+ \hline
+ $a$ & 1 & $a$ \\
+ 1 & $b$ & $b$ \\
+ \end{tabular}
+ \caption{Const folding rules for {\tt\$\_AND\_} cells as used in {\tt opt\_const}.}
+ \label{tab:opt_const_and}
+\end{table}
+
+Table~\ref{tab:opt_const_and} shows the replacement rules used for optimizing
+an {\tt\$\_AND\_} gate. The first three rules implement the obvious const folding
+rules. Note that `any' might include dynamic values calculated by other parts
+of the circuit. The following three lines propagate undef (X) states.
+These are the only three cases in which it is allowed to propagate an undef
+according to Sec.~5.1.10 of IEEE Std. 1364-2005 \cite{Verilog2005}.
+
+The next two lines assume the value 0 for undef states. These two rules are only
+used if no other subsitutions are possible in the current module. If other substitutions
+are possible they are performed first, in the hope that the `any' will change to
+an undef value or a 1 and therefore the output can be set to undef.
+
+The last two lines simply replace an {\tt\$\_AND\_} gate with one constant-1
+input with a buffer.
+
+Besides this basic const folding the {\tt opt\_const} pass can replace 1-bit wide
+{\tt \$eq} and {\tt \$ne} cells with buffers or not-gates if one input is constant.
+
+The {\tt opt\_const} pass is very conservative regarding optimizing {\tt \$mux} cells,
+as these cells are often used to model decision-trees and breaking these trees can
+interfere with other optimizations.
+
+\subsection{The opt\_muxtree pass}
+
+This pass optimizes trees of multiplexer cells by analyzing the select inputs.
+Consider the following simple example:
+
+\begin{lstlisting}[numbers=left,frame=single,language=Verilog]
+module uut(a, y);
+input a;
+output [1:0] y = a ? (a ? 1 : 2) : 3;
+endmodule
+\end{lstlisting}
+
+The output can never be 2, as this would require \lstinline[language=Verilog];a;
+to be 1 for the outer multiplexer and 0 for the inner multiplexer. The {\tt
+opt\_muxtree} pass detects this contradiction and replaces the inner multiplexer
+with a constant 1, yielding the logic for \lstinline[language=Verilog];y = a ? 1 : 3;.
+
+\subsection{The opt\_reduce pass}
+
+\begin{sloppypar}
+This is a simple optimization pass that identifies and consolidates identical input
+bits to {\tt \$reduce\_and} and {\tt \$reduce\_or} cells. It also sorts the input
+bits to ease identification of shareable {\tt \$reduce\_and} and {\tt \$reduce\_or} cells
+in other passes.
+\end{sloppypar}
+
+This pass also identifies and consolidates identical inputs to multiplexer cells. In this
+case the new shared select bit is driven using a {\tt \$reduce\_or} cell that combines
+the original select bits.
+
+Lastly this pass consolidates trees of {\tt \$reduce\_and} cells and trees of
+{\tt \$reduce\_or} cells to single large {\tt \$reduce\_and} or {\tt \$reduce\_or} cells.
+
+These three simple optimizations are performed in a loop until a stable result is
+produced.
+
+\subsection{The opt\_rmdff pass}
+
+This pass identifies single-bit d-type flip-flops ({\tt \$\_DFF\_*}, {\tt \$dff}, and {\tt
+\$adff} cells) with a constant data input and replaces them with a constant driver.
+
+\subsection{The opt\_clean pass}
+
+This pass identifies unused signals and cells and removes them from the design. It also
+creates an \B{unused\_bits} attribute on wires with unused bits. This attribute can be
+used for debugging or by other optimization passes.
+
+\subsection{The opt\_share pass}
+
+This pass performs trivial resource sharing. This means that this pass identifies cells
+with identical inputs and replaces them with a single instance of the cell.
+
+The option {\tt -nomux} can be used to disable resource sharing for multiplexer
+cells ({\tt \$mux}, {\tt \$pmux}, and {\tt \$safe\_pmux}). This can be useful as
+it prevents multiplexer trees to be merged, which might prevent {\tt opt\_muxtree}
+to identify possible optimizations.
+
+\section{FSM Extraction and Encoding}
+
+The {\tt fsm} pass performs finite-state-machine (FSM) extraction and recoding. The {\tt fsm}
+pass simply executes the following other passes:
+
+\begin{itemize}
+\item Identify and extract FSMs:
+\begin{itemize}
+\item {\tt fsm\_detect}
+\item {\tt fsm\_extract}
+\end{itemize}
+
+\item Basic optimizations:
+\begin{itemize}
+\item {\tt fsm\_opt}
+\item {\tt opt\_clean}
+\item {\tt fsm\_opt}
+\end{itemize}
+
+\item Expanding to nearby gate-logic (if called with {\tt -expand}):
+\begin{itemize}
+\item {\tt fsm\_expand}
+\item {\tt opt\_clean}
+\item {\tt fsm\_opt}
+\end{itemize}
+
+\item Re-code FSM states (unless called with {\tt -norecode}):
+\begin{itemize}
+\item {\tt fsm\_recode}
+\end{itemize}
+
+\item Print information about FSMs:
+\begin{itemize}
+\item {\tt fsm\_info}
+\end{itemize}
+
+\item Export FSMs in KISS2 file format (if called with {\tt -export}):
+\begin{itemize}
+\item {\tt fsm\_export}
+\end{itemize}
+
+\item Map FSMs to RTL cells (unless called with {\tt -nomap}):
+\begin{itemize}
+\item {\tt fsm\_map}
+\end{itemize}
+\end{itemize}
+
+The {\tt fsm\_detect} pass identifies FSM state registers and marks them using the
+\B{fsm\_encoding}{\tt = "auto"} attribute. The {\tt fsm\_extract} extracts all
+FSMs marked using the \B{fsm\_encoding} attribute (unless \B{fsm\_encoding} is
+set to {\tt "none"}) and replaces the corresponding RTL cells with a {\tt \$fsm}
+cell. All other {\tt fsm\_*} passes operate on these {\tt \$fsm} cells. The
+{\tt fsm\_map} call finally replaces the {\tt \$fsm} cells with RTL cells.
+
+Note that these optimizations operate on an RTL netlist. I.e.~the {\tt fsm} pass
+should be executed after the {\tt proc} pass has transformed all
+{\tt RTLIL::Process} objects to RTL cells.
+
+The algorithms used for FSM detection and extraction are influenced by a more
+general reported technique \cite{fsmextract}.
+
+\subsection{FSM Detection}
+
+The {\tt fsm\_detect} pass identifies FSM state registers. It sets the
+\B{fsm\_encoding}{\tt = "auto"} attribute on any (multi-bit) wire that matches
+the following description:
+
+\begin{itemize}
+\item Does not already have the \B{fsm\_encoding} attribute.
+\item Is not an output of the containing module.
+\item Is driven by single {\tt \$dff} or {\tt \$adff} cell.
+\item The \B{D}-Input of this {\tt \$dff} or {\tt \$adff} cell is driven by a multiplexer
+tree that only has constants or the old state value on its leaves.
+\item The state value is only used in the said multiplexer tree or by simple relational
+cells that compare the state value to a constant (usually {\tt \$eq} cells).
+\end{itemize}
+
+This heuristic has proven to work very well. It is possible to overwrite it by setting
+\B{fsm\_encoding}{\tt = "auto"} on registers that should be considered FSM state registers
+and setting \B{fsm\_encoding}{\tt = "none"} on registers that match the above criteria
+but should not be considered FSM state registers.
+
+\subsection{FSM Extraction}
+
+The {\tt fsm\_extract} pass operates on all state signals marked with the
+\B{fsm\_encoding} ({\tt != "none"}) attribute. For each state signal the following
+information is determined:
+
+\begin{itemize}
+\item The state registers
+\item The asynchronous reset state if the state registers use asynchronous reset
+\item All states and the control input signals used in the state transition functions
+\item The control output signals calculated from the state signals and control inputs
+\item A table of all state transitions and corresponding control inputs- and outputs
+\end{itemize}
+
+The state registers (and asynchronous reset state, if applicable) is simply determined
+by identifying the driver for the state signal.
+
+From there the {\tt \$mux}-tree driving the state register inputs is
+recursively traversed. All select inputs are control signals and the leaves of the
+{\tt \$mux}-tree are the states. The algorithm fails if a non-constant leaf
+that is not the state signal itself is found.
+
+The list of control outputs is initialized with the bits from the state signal.
+It is then extended by adding all values that are calculated by cells that
+compare the state signal with a constant value.
+
+In most cases this will cover all uses of the state register, thus rendering the
+state encoding arbitrary. If however a design uses e.g.~a single bit of the state
+value to drive a control output directly, this bit of the state signal will be
+transformed to a control output of the same value.
+
+Finally, a transition table for the FSM is generated. This is done by using the
+{\tt ConstEval} C++ helper class (defined in {\tt kernel/consteval.h}) that can
+be used to evaluate parts of the design. The {\tt ConstEval} class can be asked
+to calculate a given set of result signals using a set of signal-value
+assignments. It can also be passed a list of stop-signals that abort the {\tt
+ConstEval} algorithm if the value of a stop-signal is needed in order to
+calculate the result signals.
+
+The {\tt fsm\_extract} pass uses the {\tt ConstEval} class in the following way
+to create a transition table. For each state:
+
+\begin{enumerate}
+\item Create a {\tt ConstEval} object for the module containing the FSM
+\item Add all control inputs to the list of stop signals
+\item Set the state signal to the current state
+\item Try to evaluate the next state and control output \label{enum:fsm_extract_cealg_try}
+\item If step~\ref{enum:fsm_extract_cealg_try} was not successful:
+\begin{itemize}
+\item Recursively goto step~\ref{enum:fsm_extract_cealg_try} with the offending stop-signal set to 0.
+\item Recursively goto step~\ref{enum:fsm_extract_cealg_try} with the offending stop-signal set to 1.
+\end{itemize}
+\item If step~\ref{enum:fsm_extract_cealg_try} was successful: Emit transition
+\end{enumerate}
+
+Finally a {\tt \$fsm} cell is created with the generated transition table and added to the
+module. This new cell is connected to the control signals and the old drivers for the
+control outputs are disconnected.
+
+\subsection{FSM Optimization}
+
+The {\tt fsm\_opt} pass performs basic optimizations on {\tt \$fsm} cells (not including state
+recoding). The following optimizations are performed (in this order):
+
+\begin{itemize}
+\item Unused control outputs are removed from the {\tt \$fsm} cell. The attribute \B{unused\_bits}
+(that is usually set by the {\tt opt\_clean} pass) is used to determine which control
+outputs are unused.
+\item Control inputs that are connected to the same driver are merged.
+\item When a control input is driven by a control output, the control input is removed and the transition
+table altered to give the same performance without the external feedback path.
+\item Entries in the transition table that yield the same output and only
+differ in the value of a single control input bit are merged and the different bit is removed
+from the sensitivity list (turned into a don't-care bit).
+\item Constant inputs are removed and the transition table is alterered to give an unchanged behaviour.
+\item Unused inputs are removed.
+\end{itemize}
+
+\subsection{FSM Recoding}
+
+The {\tt fsm\_recode} pass assigns new bit pattern to the states. Usually this
+also implies a change in the width of the state signal. At the moment of this
+writing only one-hot encoding with all-zero for the reset state is supported.
+
+The {\tt fsm\_recode} pass can also write a text file with the changes performed
+by it that can be used when verifying designs synthesized by Yosys using Synopsys
+Formality \citeweblink{Formality}.
+
+\section{Logic Optimization}
+
+Yosys can perform multi-level combinational logic optimization on gate-level netlists using the
+external program ABC \citeweblink{ABC}. The {\tt abc} pass extracts the combinational gate-level
+parts of the design, passes it through ABC, and re-integrates the results. The {\tt abc} pass
+can also be used to perform other operations using ABC, such as technology mapping (see
+Sec.~\ref{sec:techmap_extern} for details).
+