Rst docs conversion (#3496)

Rst docs conversion

1 files changed, 571 insertions, 0 deletions

diff --git a/docs/source/CHAPTER_Overview.rst b/docs/source/CHAPTER_Overview.rst
new file mode 100644
index 000000000..10d2ce478
--- /dev/null
+++ b/docs/source/CHAPTER_Overview.rst
@@ -0,0 +1,571 @@
+.. _chapter:overview:
+
+Implementation overview
+=======================
+
+Yosys is an extensible open source hardware synthesis tool. It is aimed at
+designers who are looking for an easily accessible, universal, and
+vendor-independent synthesis tool, as well as scientists who do research in
+electronic design automation (EDA) and are looking for an open synthesis
+framework that can be used to test algorithms on complex real-world designs.
+
+Yosys can synthesize a large subset of Verilog 2005 and has been tested with a
+wide range of real-world designs, including the `OpenRISC 1200 CPU`_, the
+`openMSP430 CPU`_, the `OpenCores I2C master`_, and the `k68 CPU`_.
+
+.. _OpenRISC 1200 CPU: https://github.com/openrisc/or1200
+
+.. _openMSP430 CPU: http://opencores.org/projects/openmsp430
+
+.. _OpenCores I2C master: http://opencores.org/projects/i2c
+
+.. _k68 CPU: http://opencores.org/projects/k68
+
+As of this writing a Yosys VHDL frontend is in development.
+
+Yosys is written in C++ (using some features from the new C++11 standard). This
+chapter describes some of the fundamental Yosys data structures. For the sake of
+simplicity the C++ type names used in the Yosys implementation are used in this
+chapter, even though the chapter only explains the conceptual idea behind it and
+can be used as reference to implement a similar system in any language.
+
+Simplified data flow
+--------------------
+
+:numref:`Figure %s <fig:Overview_flow>` shows the simplified data flow within
+Yosys. Rectangles in the figure represent program modules and ellipses internal
+data structures that are used to exchange design data between the program
+modules.
+
+Design data is read in using one of the frontend modules. The high-level HDL
+frontends for Verilog and VHDL code generate an abstract syntax tree (AST) that
+is then passed to the AST frontend. Note that both HDL frontends use the same
+AST representation that is powerful enough to cover the Verilog HDL and VHDL
+language.
+
+The AST Frontend then compiles the AST to Yosys's main internal data format, the
+RTL Intermediate Language (RTLIL). A more detailed description of this format is
+given in the next section.
+
+There is also a text representation of the RTLIL data structure that can be
+parsed using the RTLIL Frontend.
+
+The design data may then be transformed using a series of passes that all
+operate on the RTLIL representation of the design.
+
+Finally the design in RTLIL representation is converted back to text by one of
+the backends, namely the Verilog Backend for generating Verilog netlists and the
+RTLIL Backend for writing the RTLIL data in the same format that is understood
+by the RTLIL Frontend.
+
+With the exception of the AST Frontend, which is called by the high-level HDL
+frontends and can't be called directly by the user, all program modules are
+called by the user (usually using a synthesis script that contains text commands
+for Yosys).
+
+By combining passes in different ways and/or adding additional passes to Yosys
+it is possible to adapt Yosys to a wide range of applications. For this to be
+possible it is key that (1) all passes operate on the same data structure
+(RTLIL) and (2) that this data structure is powerful enough to represent the
+design in different stages of the synthesis.
+
+.. figure:: ../images/overview_flow.*
+	:class: width-helper
+	:name: fig:Overview_flow
+
+	Yosys simplified data flow (ellipses: data structures, rectangles:
+	program modules)
+
+The RTL Intermediate Language (RTLIL)
+-------------------------------------
+
+All frontends, passes and backends in Yosys operate on a design in RTLIL
+representation. The only exception are the high-level frontends that use the AST
+representation as an intermediate step before generating RTLIL data.
+
+In order to avoid reinventing names for the RTLIL classes, they are simply
+referred to by their full C++ name, i.e. including the RTLIL:: namespace prefix,
+in this document.
+
+:numref:`Figure %s <fig:Overview_RTLIL>` shows a simplified Entity-Relationship
+Diagram (ER Diagram) of RTLIL. In :math:`1:N` relationships the arrow points
+from the :math:`N` side to the :math:`1`. For example one RTLIL::Design contains
+:math:`N` (zero to many) instances of RTLIL::Module. A two-pointed arrow
+indicates a :math:`1:1` relationship.
+
+The RTLIL::Design is the root object of the RTLIL data structure. There is
+always one "current design" in memory which passes operate on, frontends add
+data to and backends convert to exportable formats. But in some cases passes
+internally generate additional RTLIL::Design objects. For example when a pass is
+reading an auxiliary Verilog file such as a cell library, it might create an
+additional RTLIL::Design object and call the Verilog frontend with this other
+object to parse the cell library.
+
+.. figure:: ../images/overview_rtlil.*
+	:class: width-helper
+	:name: fig:Overview_RTLIL
+
+	Simplified RTLIL Entity-Relationship Diagram
+
+There is only one active RTLIL::Design object that is used by all frontends,
+passes and backends called by the user, e.g. using a synthesis script. The
+RTLIL::Design then contains zero to many RTLIL::Module objects. This corresponds
+to modules in Verilog or entities in VHDL. Each module in turn contains objects
+from three different categories:
+
+-  RTLIL::Cell and RTLIL::Wire objects represent classical netlist data.
+
+-  RTLIL::Process objects represent the decision trees (if-then-else statements,
+   etc.) and synchronization declarations (clock signals and sensitivity) from
+   Verilog always and VHDL process blocks.
+
+-  RTLIL::Memory objects represent addressable memories (arrays).
+
+Usually the output of the synthesis procedure is a netlist, i.e. all
+RTLIL::Process and RTLIL::Memory objects must be replaced by RTLIL::Cell and
+RTLIL::Wire objects by synthesis passes.
+
+All features of the HDL that cannot be mapped directly to these RTLIL classes
+must be transformed to an RTLIL-compatible representation by the HDL frontend.
+This includes Verilog-features such as generate-blocks, loops and parameters.
+
+The following sections contain a more detailed description of the different
+parts of RTLIL and rationale behind some of the design decisions.
+
+RTLIL identifiers
+~~~~~~~~~~~~~~~~~
+
+All identifiers in RTLIL (such as module names, port names, signal names, cell
+types, etc.) follow the following naming convention: they must either start with
+a backslash (\) or a dollar sign ($).
+
+Identifiers starting with a backslash are public visible identifiers. Usually
+they originate from one of the HDL input files. For example the signal name
+"\\sig42" is most likely a signal that was declared using the name "sig42" in an
+HDL input file. On the other hand the signal name "$sig42" is an auto-generated
+signal name. The backends convert all identifiers that start with a dollar sign
+to identifiers that do not collide with identifiers that start with a backslash.
+
+This has three advantages:
+
+-  First, it is impossible that an auto-generated identifier collides with an
+   identifier that was provided by the user.
+
+-  Second, the information about which identifiers were originally provided by
+   the user is always available which can help guide some optimizations. For
+   example the "opt_rmunused" tries to preserve signals with a user-provided
+   name but doesn't hesitate to delete signals that have auto-generated names
+   when they just duplicate other signals.
+
+-  Third, the delicate job of finding suitable auto-generated public visible
+   names is deferred to one central location. Internally auto-generated names
+   that may hold important information for Yosys developers can be used without
+   disturbing external tools. For example the Verilog backend assigns names in
+   the form \_integer\_.
+
+Whitespace and control characters (any character with an ASCII code 32 or less)
+are not allowed in RTLIL identifiers; most frontends and backends cannot support
+these characters in identifiers.
+
+In order to avoid programming errors, the RTLIL data structures check if all
+identifiers start with either a backslash or a dollar sign, and contain no
+whitespace or control characters. Violating these rules results in a runtime
+error.
+
+All RTLIL identifiers are case sensitive.
+
+Some transformations, such as flattening, may have to change identifiers
+provided by the user to avoid name collisions. When that happens, attribute
+"hdlname" is attached to the object with the changed identifier. This attribute
+contains one name (if emitted directly by the frontend, or is a result of
+disambiguation) or multiple names separated by spaces (if a result of
+flattening). All names specified in the "hdlname" attribute are public and do
+not include the leading "\".
+
+RTLIL::Design and RTLIL::Module
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+The RTLIL::Design object is basically just a container for RTLIL::Module
+objects. In addition to a list of RTLIL::Module objects the RTLIL::Design also
+keeps a list of selected objects, i.e. the objects that passes should operate
+on. In most cases the whole design is selected and therefore passes operate on
+the whole design. But this mechanism can be useful for more complex synthesis
+jobs in which only parts of the design should be affected by certain passes.
+
+Besides the objects shown in the ER diagram in :numref:`Fig. %s
+<fig:Overview_RTLIL>` an RTLIL::Module object contains the following additional
+properties:
+
+-  The module name
+-  A list of attributes
+-  A list of connections between wires
+-  An optional frontend callback used to derive parametrized variations of the
+   module
+
+The attributes can be Verilog attributes imported by the Verilog frontend or
+attributes assigned by passes. They can be used to store additional metadata
+about modules or just mark them to be used by certain part of the synthesis
+script but not by others.
+
+Verilog and VHDL both support parametric modules (known as "generic entities" in
+VHDL). The RTLIL format does not support parametric modules itself. Instead each
+module contains a callback function into the AST frontend to generate a
+parametrized variation of the RTLIL::Module as needed. This callback then
+returns the auto-generated name of the parametrized variation of the module. (A
+hash over the parameters and the module name is used to prohibit the same
+parametrized variation from being generated twice. For modules with only a few
+parameters, a name directly containing all parameters is generated instead of a
+hash string.)
+
+.. _sec:rtlil_cell_wire:
+
+RTLIL::Cell and RTLIL::Wire
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+A module contains zero to many RTLIL::Cell and RTLIL::Wire objects. Objects of
+these types are used to model netlists. Usually the goal of all synthesis
+efforts is to convert all modules to a state where the functionality of the
+module is implemented only by cells from a given cell library and wires to
+connect these cells with each other. Note that module ports are just wires with
+a special property.
+
+An RTLIL::Wire object has the following properties:
+
+-  The wire name
+-  A list of attributes
+-  A width (buses are just wires with a width > 1)
+-  Bus direction (MSB to LSB or vice versa)
+-  Lowest valid bit index (LSB or MSB depending on bus direction)
+-  If the wire is a port: port number and direction (input/output/inout)
+
+As with modules, the attributes can be Verilog attributes imported by the
+Verilog frontend or attributes assigned by passes.
+
+In Yosys, busses (signal vectors) are represented using a single wire object
+with a width > 1. So Yosys does not convert signal vectors to individual
+signals. This makes some aspects of RTLIL more complex but enables Yosys to be
+used for coarse grain synthesis where the cells of the target architecture
+operate on entire signal vectors instead of single bit wires.
+
+In Verilog and VHDL, busses may have arbitrary bounds, and LSB can have either
+the lowest or the highest bit index. In RTLIL, bit 0 always corresponds to LSB;
+however, information from the HDL frontend is preserved so that the bus will be
+correctly indexed in error messages, backend output, constraint files, etc.
+
+An RTLIL::Cell object has the following properties:
+
+-  The cell name and type
+-  A list of attributes
+-  A list of parameters (for parametric cells)
+-  Cell ports and the connections of ports to wires and constants
+
+The connections of ports to wires are coded by assigning an RTLIL::SigSpec to
+each cell port. The RTLIL::SigSpec data type is described in the next section.
+
+.. _sec:rtlil_sigspec:
+
+RTLIL::SigSpec
+~~~~~~~~~~~~~~
+
+A "signal" is everything that can be applied to a cell port. I.e.
+
+-  | Any constant value of arbitrary bit-width
+   | 1em For example: ``1337, 16'b0000010100111001, 1'b1, 1'bx``
+
+-  | All bits of a wire or a selection of bits from a wire
+   | 1em For example: ``mywire, mywire[24], mywire[15:8]``
+
+-  | Concatenations of the above
+   | 1em For example: ``{16'd1337, mywire[15:8]}``
+
+The RTLIL::SigSpec data type is used to represent signals. The RTLIL::Cell
+object contains one RTLIL::SigSpec for each cell port.
+
+In addition, connections between wires are represented using a pair of
+RTLIL::SigSpec objects. Such pairs are needed in different locations. Therefore
+the type name RTLIL::SigSig was defined for such a pair.
+
+.. _sec:rtlil_process:
+
+RTLIL::Process
+~~~~~~~~~~~~~~
+
+When a high-level HDL frontend processes behavioural code it splits it up into
+data path logic (e.g. the expression a + b is replaced by the output of an adder
+that takes a and b as inputs) and an RTLIL::Process that models the control
+logic of the behavioural code. Let's consider a simple example:
+
+.. code:: verilog
+   :number-lines:
+
+   module ff_with_en_and_async_reset(clock, reset, enable, d, q);
+   input clock, reset, enable, d;
+   output reg q;
+   always @(posedge clock, posedge reset)
+       if (reset)
+           q <= 0;
+       else if (enable)
+           q <= d;
+   endmodule
+
+In this example there is no data path and therefore the RTLIL::Module generated
+by the frontend only contains a few RTLIL::Wire objects and an RTLIL::Process.
+The RTLIL::Process in RTLIL syntax:
+
+.. code:: RTLIL
+   :number-lines:
+
+   process $proc$ff_with_en_and_async_reset.v:4$1
+       assign $0\q[0:0] \q
+       switch \reset
+           case 1'1
+               assign $0\q[0:0] 1'0
+           case
+               switch \enable
+                   case 1'1
+                       assign $0\q[0:0] \d
+                   case
+               end
+       end
+       sync posedge \clock
+           update \q $0\q[0:0]
+       sync posedge \reset
+           update \q $0\q[0:0]
+   end
+
+This RTLIL::Process contains two RTLIL::SyncRule objects, two RTLIL::SwitchRule
+objects and five RTLIL::CaseRule objects. The wire $0\q[0:0] is an automatically
+created wire that holds the next value of \\q. The lines :math:`2 \dots 12`
+describe how $0\q[0:0] should be calculated. The lines :math:`13 \dots 16`
+describe how the value of $0\q[0:0] is used to update \\q.
+
+An RTLIL::Process is a container for zero or more RTLIL::SyncRule objects and
+exactly one RTLIL::CaseRule object, which is called the root case.
+
+An RTLIL::SyncRule object contains an (optional) synchronization condition
+(signal and edge-type), zero or more assignments (RTLIL::SigSig), and zero or
+more memory writes (RTLIL::MemWriteAction). The always synchronization condition
+is used to break combinatorial loops when a latch should be inferred instead.
+
+An RTLIL::CaseRule is a container for zero or more assignments (RTLIL::SigSig)
+and zero or more RTLIL::SwitchRule objects. An RTLIL::SwitchRule objects is a
+container for zero or more RTLIL::CaseRule objects.
+
+In the above example the lines :math:`2 \dots 12` are the root case. Here
+$0\q[0:0] is first assigned the old value \\q as default value (line 2). The
+root case also contains an RTLIL::SwitchRule object (lines :math:`3 \dots 12`).
+Such an object is very similar to the C switch statement as it uses a control
+signal (\\reset in this case) to determine which of its cases should be active.
+The RTLIL::SwitchRule object then contains one RTLIL::CaseRule object per case.
+In this example there is a case [1]_ for \\reset == 1 that causes $0\q[0:0] to
+be set (lines 4 and 5) and a default case that in turn contains a switch that
+sets $0\q[0:0] to the value of \\d if \\enable is active (lines :math:`6 \dots
+11`).
+
+A case can specify zero or more compare values that will determine whether it
+matches. Each of the compare values must be the exact same width as the control
+signal. When more than one compare value is specified, the case matches if any
+of them matches the control signal; when zero compare values are specified, the
+case always matches (i.e. it is the default case).
+
+A switch prioritizes cases from first to last: multiple cases can match, but
+only the first matched case becomes active. This normally synthesizes to a
+priority encoder. The parallel_case attribute allows passes to assume that no
+more than one case will match, and full_case attribute allows passes to assume
+that exactly one case will match; if these invariants are ever dynamically
+violated, the behavior is undefined. These attributes are useful when an
+invariant invisible to the synthesizer causes the control signal to never take
+certain bit patterns.
+
+The lines :math:`13 \dots 16` then cause \\q to be updated whenever there is a
+positive clock edge on \\clock or \\reset.
+
+In order to generate such a representation, the language frontend must be able
+to handle blocking and nonblocking assignments correctly. However, the language
+frontend does not need to identify the correct type of storage element for the
+output signal or generate multiplexers for the decision tree. This is done by
+passes that work on the RTLIL representation. Therefore it is relatively easy to
+substitute these steps with other algorithms that target different target
+architectures or perform optimizations or other transformations on the decision
+trees before further processing them.
+
+One of the first actions performed on a design in RTLIL representation in most
+synthesis scripts is identifying asynchronous resets. This is usually done using
+the proc_arst pass. This pass transforms the above example to the following
+RTLIL::Process:
+
+.. code:: RTLIL
+   :number-lines:
+
+   process $proc$ff_with_en_and_async_reset.v:4$1
+       assign $0\q[0:0] \q
+       switch \enable
+           case 1'1
+               assign $0\q[0:0] \d
+           case
+       end
+       sync posedge \clock
+           update \q $0\q[0:0]
+       sync high \reset
+           update \q 1'0
+   end
+
+This pass has transformed the outer RTLIL::SwitchRule into a modified
+RTLIL::SyncRule object for the \\reset signal. Further processing converts the
+RTLIL::Process into e.g. a d-type flip-flop with asynchronous reset and a
+multiplexer for the enable signal:
+
+.. code:: RTLIL
+   :number-lines:
+
+   cell $adff $procdff$6
+       parameter \ARST_POLARITY 1'1
+       parameter \ARST_VALUE 1'0
+       parameter \CLK_POLARITY 1'1
+       parameter \WIDTH 1
+       connect \ARST \reset
+       connect \CLK \clock
+       connect \D $0\q[0:0]
+       connect \Q \q
+   end
+   cell $mux $procmux$3
+       parameter \WIDTH 1
+       connect \A \q
+       connect \B \d
+       connect \S \enable
+       connect \Y $0\q[0:0]
+   end
+
+Different combinations of passes may yield different results. Note that $adff
+and $mux are internal cell types that still need to be mapped to cell types from
+the target cell library.
+
+Some passes refuse to operate on modules that still contain RTLIL::Process
+objects as the presence of these objects in a module increases the complexity.
+Therefore the passes to translate processes to a netlist of cells are usually
+called early in a synthesis script. The proc pass calls a series of other passes
+that together perform this conversion in a way that is suitable for most
+synthesis tasks.
+
+.. _sec:rtlil_memory:
+
+RTLIL::Memory
+~~~~~~~~~~~~~
+
+For every array (memory) in the HDL code an RTLIL::Memory object is created. A
+memory object has the following properties:
+
+-  The memory name
+-  A list of attributes
+-  The width of an addressable word
+-  The size of the memory in number of words
+
+All read accesses to the memory are transformed to $memrd cells and all write
+accesses to $memwr cells by the language frontend. These cells consist of
+independent read- and write-ports to the memory. Memory initialization is
+transformed to $meminit cells by the language frontend. The ``\MEMID`` parameter
+on these cells is used to link them together and to the RTLIL::Memory object
+they belong to.
+
+The rationale behind using separate cells for the individual ports versus
+creating a large multiport memory cell right in the language frontend is that
+the separate $memrd and $memwr cells can be consolidated using resource sharing.
+As resource sharing is a non-trivial optimization problem where different
+synthesis tasks can have different requirements it lends itself to do the
+optimisation in separate passes and merge the RTLIL::Memory objects and $memrd
+and $memwr cells to multiport memory blocks after resource sharing is completed.
+
+The memory pass performs this conversion and can (depending on the options
+passed to it) transform the memories directly to d-type flip-flops and address
+logic or yield multiport memory blocks (represented using $mem cells).
+
+See :numref:`Sec. %s <sec:memcells>` for details about the memory cell types.
+
+Command interface and synthesis scripts
+---------------------------------------
+
+Yosys reads and processes commands from synthesis scripts, command line
+arguments and an interactive command prompt. Yosys commands consist of a command
+name and an optional whitespace separated list of arguments. Commands are
+terminated using the newline character or a semicolon (;). Empty lines and lines
+starting with the hash sign (#) are ignored. See :numref:`Sec. %s
+<sec:typusecase>` for an example synthesis script.
+
+The command help can be used to access the command reference manual.
+
+Most commands can operate not only on the entire design but also specifically on
+selected parts of the design. For example the command dump will print all
+selected objects in the current design while dump foobar will only print the
+module foobar and dump \* will print the entire design regardless of the current
+selection.
+
+.. code:: yoscrypt
+
+	dump */t:$add %x:+[A] \*/w:\* %i
+
+The selection mechanism is very powerful. For example the command above will
+print all wires that are connected to the ``\A`` port of a ``$add`` cell.
+Detailed documentation of the select framework can be found in the command
+reference for the ``select`` command.
+
+Source tree and build system
+----------------------------
+
+The Yosys source tree is organized into the following top-level
+directories:
+
+-  | backends/
+   | This directory contains a subdirectory for each of the backend modules.
+
+-  | frontends/
+   | This directory contains a subdirectory for each of the frontend modules.
+
+-  | kernel/
+   | This directory contains all the core functionality of Yosys. This includes
+     the functions and definitions for working with the RTLIL data structures
+     (rtlil.h and rtlil.cc), the main() function (driver.cc), the internal
+     framework for generating log messages (log.h and log.cc), the internal
+     framework for registering and calling passes (register.h and register.cc),
+     some core commands that are not really passes (select.cc, show.cc, …) and a
+     couple of other small utility libraries.
+
+-  | passes/
+   | This directory contains a subdirectory for each pass or group of passes.
+     For example as of this writing the directory passes/opt/ contains the code
+     for seven passes: opt, opt_expr, opt_muxtree, opt_reduce, opt_rmdff,
+     opt_rmunused and opt_merge.
+
+-  | techlibs/
+   | This directory contains simulation models and standard implementations for
+     the cells from the internal cell library.
+
+-  | tests/
+   | This directory contains a couple of test cases. Most of the smaller tests
+     are executed automatically when make test is called. The larger tests must
+     be executed manually. Most of the larger tests require downloading external
+     HDL source code and/or external tools. The tests range from comparing
+     simulation results of the synthesized design to the original sources to
+     logic equivalence checking of entire CPU cores.
+
+The top-level Makefile includes frontends/\*/Makefile.inc,
+passes/\*/Makefile.inc and backends/\*/Makefile.inc. So when extending Yosys it
+is enough to create a new directory in frontends/, passes/ or backends/ with
+your sources and a Makefile.inc. The Yosys kernel automatically detects all
+commands linked with Yosys. So it is not needed to add additional commands to a
+central list of commands.
+
+Good starting points for reading example source code to learn how to write
+passes are passes/opt/opt_rmdff.cc and passes/opt/opt_merge.cc.
+
+See the top-level README file for a quick Getting Started guide and build
+instructions. The Yosys build is based solely on Makefiles.
+
+Users of the Qt Creator IDE can generate a QT Creator project file using make
+qtcreator. Users of the Eclipse IDE can use the "Makefile Project with Existing
+Code" project type in the Eclipse "New Project" dialog (only available after the
+CDT plugin has been installed) to create an Eclipse project in order to
+programming extensions to Yosys or just browse the Yosys code base.
+
+.. [1]
+   The syntax 1'1 in the RTLIL code specifies a constant with a length of one
+   bit (the first "1"), and this bit is a one (the second "1").