Yosys employs a number of optimizations to generate better and cleanerresults. This chapter outlines these optimizations.
Simple Optimizations¶
The Yosys pass opt runs a number of simple optimizations. Thisincludes removing unused signals and cells and const folding. It isrecommended to run this pass after each major step in the synthesisscript. At the time of this writing the opt pass executes thefollowing passes that each perform a simple optimization:
Once at the beginning of
opt:opt_expropt_merge -nomux
Repeat until result is stable:
opt_muxtreeopt_reduceopt_mergeopt_rmdffopt_cleanopt_expr
The following section describes each of the opt_ passes.
The opt_expr pass¶
This pass performs const folding on the internal combinational celltypes described in Chap.[chapter:celllib]. Thismeans a cell with all constant inputs is replaced with the constantvalue this cell drives. In some cases this pass can also optimize cellswith some constant inputs.
opt_expr.
A-Input
B-Input
Replacement
any
any
1
1
1
X/Z
X/Z
X
1
X/Z
X
X/Z
1
X
any
X/Z
X/Z
any
a
1
a
1
b
b
Table1.1 shows the replacement rules used foroptimizing an $_AND_ gate. The first three rules implement theobvious const folding rules. Note that ‘any’ might include dynamicvalues calculated by other parts of the circuit. The following threelines propagate undef (X) states. These are the only three cases inwhich it is allowed to propagate an undef according to Sec.5.1.10 ofIEEE Std. 1364-2005 .
The next two lines assume the value 0 for undef states. These two rulesare only used if no other substitutions are possible in the currentmodule. If other substitutions are possible they are performed first, inthe hope that the ‘any’ will change to an undef value or a 1 andtherefore the output can be set to undef.
The last two lines simply replace an $_AND_ gate with one constant-1input with a buffer.
Besides this basic const folding the opt_expr pass can replace 1-bitwide $eq and $ne cells with buffers or not-gates if one input isconstant.
The opt_expr pass is very conservative regarding optimizing $muxcells, as these cells are often used to model decision-trees andbreaking these trees can interfere with other optimizations.
The opt_muxtree pass¶
This pass optimizes trees of multiplexer cells by analyzing the selectinputs. Consider the following simple example:
1234 | module uut(a, y);input a;output [1:0] y = a ? (a ? 1 : 2) : 3;endmodule |
The output can never be 2, as this would require a to be 1 for theouter multiplexer and 0 for the inner multiplexer. The opt_muxtreepass detects this contradiction and replaces the inner multiplexer witha constant 1, yielding the logic for y = a ? 1 : 3.
The opt_reduce pass¶
This is a simple optimization pass that identifies and consolidatesidentical input bits to $reduce_and and $reduce_or cells. Italso sorts the input bits to ease identification of shareable$reduce_and and $reduce_or cells in other passes.
This pass also identifies and consolidates identical inputs tomultiplexer cells. In this case the new shared select bit is drivenusing a $reduce_or cell that combines the original select bits.
Lastly this pass consolidates trees of $reduce_and cells and treesof $reduce_or cells to single large $reduce_and or$reduce_or cells.
These three simple optimizations are performed in a loop until a stableresult is produced.
The opt_rmdff pass¶
This pass identifies single-bit d-type flip-flops ($_DFF_, $dff,and $adff cells) with a constant data input and replaces them with aconstant driver.
The opt_clean pass¶
This pass identifies unused signals and cells and removes them from thedesign. It also creates an attribute on wires with unused bits. Thisattribute can be used for debugging or by other optimization passes.
The opt_merge pass¶
This pass performs trivial resource sharing. This means that this passidentifies cells with identical inputs and replaces them with a singleinstance of the cell.
The option -nomux can be used to disable resource sharing formultiplexer cells ($mux and $pmux. This can be useful as itprevents multiplexer trees to be merged, which might preventopt_muxtree to identify possible optimizations.
FSM Extraction and Encoding¶
The fsm pass performs finite-state-machine (FSM) extraction andrecoding. The fsm pass simply executes the following other passes:
Identify and extract FSMs:
fsm_detectfsm_extract
Basic optimizations:
fsm_optopt_cleanfsm_opt
Expanding to nearby gate-logic (if called with
-expand):fsm_expandopt_cleanfsm_opt
Re-code FSM states (unless called with
-norecode):fsm_recode
Print information about FSMs:
fsm_info
Export FSMs in KISS2 file format (if called with
-export):fsm_export
Map FSMs to RTL cells (unless called with
-nomap):fsm_map
The fsm_detect pass identifies FSM state registers and marks themusing the attribute. The fsm_extract extracts all FSMs marked usingthe attribute (unless is set to "none") and replaces thecorresponding RTL cells with a $fsm cell. All other fsm_ passesoperate on these $fsm cells. The fsm_map call finally replacesthe $fsm cells with RTL cells.
Note that these optimizations operate on an RTL netlist. I.e.thefsm pass should be executed after the proc pass has transformedall RTLIL::Process objects to RTL cells.
The algorithms used for FSM detection and extraction are influenced by amore general reported technique .
FSM Detection¶
The fsm_detect pass identifies FSM state registers. It sets theattribute on any (multi-bit) wire that matches the followingdescription:
Does not already have the attribute.
Is not an output of the containing module.
Is driven by single
$dffor$adffcell.The -Input of this
$dffor$adffcell is driven by amultiplexer tree that only has constants or the old state value onits leaves.The state value is only used in the said multiplexer tree or bysimple relational cells that compare the state value to a constant(usually
$eqcells).
This heuristic has proven to work very well. It is possible to overwriteit by setting on registers that should be considered FSM state registersand setting on registers that match the above criteria but should not beconsidered FSM state registers.
Note however that marking state registers with that are not suitable forFSM recoding can cause synthesis to fail or produce invalid results.
FSM Extraction¶
The fsm_extract pass operates on all state signals marked with the(!= "none") attribute. For each state signal the followinginformation is determined:
The state registers
The asynchronous reset state if the state registers use asynchronousreset
All states and the control input signals used in the state transitionfunctions
The control output signals calculated from the state signals andcontrol inputs
A table of all state transitions and corresponding control inputs-and outputs
The state registers (and asynchronous reset state, if applicable) issimply determined by identifying the driver for the state signal.
From there the $mux-tree driving the state register inputs isrecursively traversed. All select inputs are control signals and theleaves of the $mux-tree are the states. The algorithm fails if anon-constant leaf that is not the state signal itself is found.
The list of control outputs is initialized with the bits from the statesignal. It is then extended by adding all values that are calculated bycells that compare the state signal with a constant value.
In most cases this will cover all uses of the state register, thusrendering the state encoding arbitrary. If however a design uses e.g.asingle bit of the state value to drive a control output directly, thisbit of the state signal will be transformed to a control output of thesame value.
Finally, a transition table for the FSM is generated. This is done byusing the ConstEval C++ helper class (defined inkernel/consteval.h) that can be used to evaluate parts of thedesign. The ConstEval class can be asked to calculate a given set ofresult signals using a set of signal-value assignments. It can also bepassed a list of stop-signals that abort the ConstEval algorithm ifthe value of a stop-signal is needed in order to calculate the resultsignals.
The fsm_extract pass uses the ConstEval class in the followingway to create a transition table. For each state:
Create a
ConstEvalobject for the module containing the FSMAdd all control inputs to the list of stop signals
Set the state signal to the current state
Try to evaluate the next state and control output[enum:fsm_extract_cealg_try]
Ifstep[enum:fsm_extract_cealg_try]was not successful:
Recursively gotostep[enum:fsm_extract_cealg_try]with the offending stop-signal set to 0.
Recursively gotostep[enum:fsm_extract_cealg_try]with the offending stop-signal set to 1.
Ifstep[enum:fsm_extract_cealg_try]was successful: Emit transition
Finally a $fsm cell is created with the generated transition tableand added to the module. This new cell is connected to the controlsignals and the old drivers for the control outputs are disconnected.
FSM Optimization¶
The fsm_opt pass performs basic optimizations on $fsm cells (notincluding state recoding). The following optimizations are performed (inthis order):
Unused control outputs are removed from the
$fsmcell. Theattribute (that is usually set by theopt_cleanpass) is used todetermine which control outputs are unused.Control inputs that are connected to the same driver are merged.
When a control input is driven by a control output, the control inputis removed and the transition table altered to give the sameperformance without the external feedback path.
Entries in the transition table that yield the same output and onlydiffer in the value of a single control input bit are merged and thedifferent bit is removed from the sensitivity list (turned into adon’t-care bit).
Constant inputs are removed and the transition table is altered togive an unchanged behaviour.
Unused inputs are removed.
FSM Recoding¶
The fsm_recode pass assigns new bit pattern to the states. Usuallythis also implies a change in the width of the state signal. At themoment of this writing only one-hot encoding with all-zero for the resetstate is supported.
The fsm_recode pass can also write a text file with the changesperformed by it that can be used when verifying designs synthesized byYosys using Synopsys Formality .
Logic Optimization¶
Yosys can perform multi-level combinational logic optimization ongate-level netlists using the external program ABC . The abc passextracts the combinational gate-level parts of the design, passes itthrough ABC, and re-integrates the results. The abc pass can also beused to perform other operations using ABC, such as technology mapping(see Sec.[sec:techmap_extern] for details).
