Merge pull request #338 from YosysHQ/docs

Documentation Improvements

2 files changed, 140 insertions, 0 deletions

diff --git a/docs/coding.md b/docs/coding.md
new file mode 100644
index 00000000..e801f239
--- /dev/null
+++ b/docs/coding.md
@@ -0,0 +1,67 @@
+# nextpnr Coding Notes
+
+This document aims to provide an overview into the philosophy behind nextpnr's codebase and some tips and tricks for developers.
+
+## See also
+
+ - [FAQ](faq.md) - overview of terminology
+ - [Arch API](archapi.md) - reference for the using and implementing the Architecture API
+ - [Netlist Structure](netlist.md) - reference for the netlist data structures
+ - [Python API](python.md) - Python API overview for netlist access, constraints, etc
+ - [Generic Architecture](generic.md) - using the Python API to create architectures
+
+## nextpnr Architectures
+
+An architecture in nextpnr is described first and foremost as code. The exact details are given in the [Arch API reference](archapi.md); this aims to explain the core concept.
+
+By choosing this approach; this gives architectures significant flexibility to use more advanced database representations than a simple flat database - for example deduplicated approaches that store similar tiles only once. 
+
+Architectures can also implement custom algorithms for packing (or other initial netlist transformations) and specialized parts of placement and routing such as global clock networks. This is because architectures provide the `pack()`, `place()` and `route()` functions, although the latter two will normally use generic algorithms (such as HeAP and router1) to do most of the work. 
+
+Another important function provided by architectures is placement validity checking. This allows the placer to check whether or not a given cell placement is valid. An example of this is for iCE40, where 8 logic cells in a tile share one clock signal - this is checked here.
+
+This function allows architectures in nextpnr to do significantly less packing than in traditional FPGA CAD flows. Although `pack()` could pack entire tiles, it is more idiomatic to pack to logic cells (e.g. single LUT and FF or two LUTFFs) or even smaller units like the LUTs and FFs themselves (in this case all the "packer" would do is convert LUTs and FFs to a common type if needed.)
+
+Additionally to this; architectures provide functions for checking the availability and conflicts between resources (e.g. `checkBelAvail`, `checkPipAvail`, etc). This enables arbitrary constraints between resource availability to be defined, for example:
+
+ - where a group of Pips share bitstream bits, only one can be used at a time
+ - Pips that represent LUT permutation are not available when the LUT is in memory mode
+ - only a certain total number of Pips in a switchbox can be used at once due to power supply limitations
+
+## `IdString`s
+
+To avoid the high cost of using strings as identifiers directly; almost all "string" identifiers in nextpnr (such as cell names and types) use an indexed string pool type named `IdString`. Unlike Yosys, which has a global garbage collected pool, nextpnr has a per-Context pool without any garbage collection. 
+
+`IdString`s can be created in two ways. Architectures can add `IdString`s with constant indicies - allowing `IdString` constants to be provided too - using `initialize_add` at startup. See how `constids.inc` is used in iCE40 for an example of this. The main way to create `IdString`s, however, is at runtime using the `id` member function of `BaseCtx` given the string to create from (if an `IdString` of that string already exists, the existing `IdString` will be returned).
+
+Note that `IdString`s need a `Context` (or `BaseCtx`) pointer to convert them back to regular strings, due to the pool being per-context as described above.
+
+## Developing CAD algorithms - packing
+
+Packing in nextpnr could be done in two ways (if significant packing is done at all):
+ - replacing multiple cells with a single larger cell that corresponds to a bel
+ - combining smaller cells using relative placement constraints
+
+In flows with minimal packing the main task of the packer is to transform cells into common types that correspond to a bel (e.g. convert multiple flipflop primitives to a single common type with some extra parameters). The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades.
+
+There are several helper functions that are useful for developing packers and other passes that perform significant netlist modifications in `util.h`. It is often preferable to use these compared to direct modification of the netlist structures due to the "double linking" nextpnr does - e.g. when connecting a port you must update both the `net` field of the ports and the `driver`/`users` of the net.
+
+## Developing CAD algorithms - placement
+
+The job of the placer in nextpnr is to find a suitable bel for each cell in the design; while respecting legality and relative constraints.
+
+Placers might want to create their own indices of bels (for example, bels by type and location) to speed up the search. 
+
+As nextpnr allows arbitrary constraints on bels for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible.
+
+There are several routes for timing information in the placer:
+    - sink `PortRef`s have a `budget` value annotated by calling `assign_budget` which is an estimate of the maximum delay that an arc may have
+    - sink ports can have a criticality (value between 0 and 1 where 1 is the critical path) associated with them by using `get_criticalities` and a `NetCriticalityMap`
+    - `predictDelay` returns an estimated delay for a sink port based on placement information
+
+## Routing
+
+The job of the router is to ensure that the `wires` map for each net contains a complete routing tree; populated using the Arch functions to bind wires and pips. The ripup invariants in the [FAQ](faq.md) are important to bear in mind; as there may be complex constraints on the usage of wires and pips in some architectures.
+
+`estimateDelay` is intended for use as an A* metric to guide routing.
+
diff --git a/docs/netlist.md b/docs/netlist.md
new file mode 100644
index 00000000..0f9a8969
--- /dev/null
+++ b/docs/netlist.md
@@ -0,0 +1,73 @@
+# nextpnr netlist structures documentation
+
+The current in-memory design in nextpnr uses several basic structures. See the
+[FAQ](faq.md) for more info on terminology.
+
+See also the [Arch API reference](archapi.md) for information on developing new architectures and accessing the architecture database.
+
+ - `CellInfo`: instantiation of a physical block in the netlist (currently, all cells in nextpnr are blackboxes.)
+ - `NetInfo`: a connection between cell ports. Has at most one driver; and zero or more users
+ - `BaseCtx`: contains all cells and nets, subclassed by `Arch` and then becomes `Context`
+
+Other structures used by these basic structures include:
+ - `Property`: stores a numeric or string value - isomorphic to `RTLIL::Const` in Yosys
+ - `PortInfo`: stores the name, direction and connected net (if applicable) of cell ports
+ - `PortRef`: used to reference the source/sink ports of a net; refers back to a cell and a port name
+
+## CellInfo
+
+`CellInfo` instances have the following fields:
+
+ - `name` and `type` are `IdString`s containing the instance name, and type
+ - `ports` is a map from port name `IdString` to `PortInfo` structures for each cell port
+ - `bel` and `belStrength` contain the ID of the Bel the cell is placed onto; and placement strength of the cell; if placed. Placement/ripup should always be done by `Arch::bindBel` and `Arch::unbindBel` rather than by manipulating these fields.
+ - `params` and `attrs` store parameters and attributes - from the input JSON or assigned in flows to add metadata - by mapping from parameter name `IdString` to `Property`.
+ - The `constr_` fields are for relative constraints:
+    - `constr_parent` is a reference to the cell this cell is constrained with respect to; or `nullptr` if not relatively constrained. If not `nullptr`, this cell should be in the parent's `constr_children`.
+    - `constr_children` is a list of cells relatively constrained to this one. All children should have `constr_parent == this`. 
+    - `constr_x` and `constr_y` are absolute (`constr_parent == nullptr`) or relative (`constr_parent != nullptr`) tile coordinate constraints. If set to `UNCONSTR` then the cell is not constrained in this axis (defaults to `UNCONSTR`)
+    - `constr_z` is an absolute (`constr_abs_z`) or relative (`!constr_abs_z`) 'Z-axis' (index inside tile, e.g. logic cell) constraint
+ - `region` is a reference to a `Region` if the cell is constrained to a placement region (e.g. for partial reconfiguration or out-of-context flows) or `nullptr` otherwise.
+
+## NetInfo
+
+`NetInfo` instances have the following fields:
+
+ - `name` is the IdString name of the net - for nets with multiple names, one name is chosen according to a set of rules by the JSON frontend
+ - `driver` refers to the source of the net using `PortRef`; `driver.cell == nullptr` means that the net is undriven. Nets must have zero or one driver only. The corresponding cell port must be an output and its `PortInfo::net` must refer back to this net.
+ - `users` contains a list of `PortRef` references to sink ports on the net. Nets can have zero or more sinks. Each corresponding cell port must be an input or inout; and its `PortInfo::net` must refer back to this net.
+ - `wires` is a map that stores the routing tree of a net, if the net is routed.
+    - Each entry in `wires` maps from *sink* wire in the routing tree to its driving pip, and the binding strength of that pip (e.g. how freely the router may rip up the pip)
+    - Manipulation of this structure is done automatically by `Arch::bindWire`, `Arch::unbindWire`, `Arch::bindPip` and `Arch::unbindPip`; which should almost always be used in lieu of manual manipulation
+ - `attrs` stores metadata about the wire (which may come from the JSON or be added by passes)
+ - `clkconstr` contains the period constraint if the wire is a constrained clock; or is empty otherwise
+ - `region` is a reference to a `Region` if the net is constrained to a device region or `nullptr` otherwise (_N.B. not supported by the current router_).
+
+## BaseCtx/Context
+
+Relevant fields from a netlist point of view are:
+ - `cells` is a map from cell name to a `unique_ptr<CellInfo>` containing cell data
+ - `nets` is a map from net name to a `unique_ptr<NetInfo>` containing net data
+ - `net_aliases` maps every alias for a net to its canonical name (i.e. index into `nets`) - net aliases often occur when a net has a name both inside a submodule and higher level module
+ - `ports` is a list of top level ports, primarily used during JSON export (e.g. to produce a useful post-PnR simulation model)
+
+Context also has a method `check()` that ensures all of the contracts met above are satisfied. It is strongly suggested to run this after any pass that may modify the netlist.
+
+## Performance Improvements
+
+Two features are provided to enable performance improvements in some algorithms, generally by reducing the number of `unordered_map` accesses.
+
+The first is `udata`. This is a field of both nets and cells that can be used to give an index into algorithm-specific structures, such as a flat `vector` of cells. Placers and routers may use this for any purpose, but it should not be used to exchange data between passes.
+
+The second is `ArchCellInfo` and `ArchNetInfo`. These are provided by architectures and used as base classes for `CellInfo` and `NetInfo` respectively. They allow architectures to tag information that is needed frequently - for example the clock polarity and clock net for a flipflop are needed for placement validity checking. They should only be used inside arch-specific code, and are lost when netlists are saved/loaded thus must not be used as primary storage - usually these should mirror attributes/parameters. `assignArchInfo` should set these up accordingly.
+
+## Helper Functions - Context
+
+`Context` and its subclass `BaseCtx` provides several helper functions that are often needed inside CAD algorithms.
+
+ - `nameOfBel`, `nameOfWire`, and `nameOfPip` gets the name of an identified object as a C string, often used in conjunction with the logging functions
+ - `nameOf` is similar to above but for netlist objects that have a `name` field (e.g. cells, nets, etc)
+ - `getNetinfoSourceWire` gets the physical wire `WireId` associated with the source of a net
+ - `getNetinfoSinkWire` gets the physical wire `WireId` associated with a given sink (specified by `PortRef`)
+ - `getNetinfoRouteDelay` gets the routing delay - actual if the net is fully routed, estimated otherwise - between the source and a given sink of a net
+ - `getNetByAlias` returns the pointer to a net given any of its aliases - this should be used in preference to a direct lookup in `nets` whenever a net name is provided by the user
\ No newline at end of file