passes/pmgen/README.md

   1 Pattern Matcher Generator
   2 =========================
   3
   4 The program `pmgen.py` reads a `.pmg` (Pattern Matcher Generator) file and
   5 writes a header-only C++ library that implements that pattern matcher.
   6
   7 The "patterns" in this context are subgraphs in a Yosys RTLIL netlist.
   8
   9 The algorithm used in the generated pattern matcher is a simple recursive
  10 search with backtracking. It is left to the author of the `.pmg` file to
  11 determine an efficient cell order for the search that allows for maximum
  12 use of indices and early backtracking.
  13
  14
  15 API of Generated Matcher
  16 ========================
  17
  18 When `pmgen.py` reads a `foobar.pmg` file, it writes `foobar_pm.h` containing
  19 a class `foobar_pm`. That class is instantiated with an RTLIL module and a
  20 list of cells from that module:
  21
  22     foobar_pm pm(module, module->selected_cells());
  23
  24 The caller must make sure that none of the cells in the 2nd argument are
  25 deleted for as long as the patter matcher instance is used.
  26
  27 At any time it is possible to disable cells, preventing them from showing
  28 up in any future matches:
  29
  30     pm.blacklist(some_cell);
  31
  32 The `.run_<pattern_name>(callback_function)` method searches for all matches
  33 for the pattern`<pattern_name>` and calls the callback function for each found
  34 match:
  35
  36     pm.run_foobar([&](){
  37         log("found matching 'foo' cell: %s\n", log_id(pm.st.foo));
  38         log("          with 'bar' cell: %s\n", log_id(pm.st.bar));
  39     });
  40
  41 The `.pmg` file declares matcher state variables that are accessible via the
  42 `.st_<pattern_name>.<state_name>` members. (The `.st_<pattern_name>` member is
  43 of type `foobar_pm::state_<pattern_name>_t`.)
  44
  45 Similarly the `.pmg` file declares user data variables that become members of
  46 `.ud_<pattern_name>`, a struct of type `foobar_pm::udata_<pattern_name>_t`.
  47
  48 There are four versions of the `run_<pattern_name>()` method: Without callback,
  49 callback without arguments, callback with reference to `pm`, and callback with
  50 reference to `pm.st_<pattern_name>`.
  51
  52
  53 The .pmg File Format
  54 ====================
  55
  56 The `.pmg` file format is a simple line-based file format. For the most part
  57 lines consist of whitespace-separated tokens.
  58
  59 Lines in `.pmg` files starting with `//` are comments.
  60
  61 Declaring a pattern
  62 -------------------
  63
  64 A `.pmg` file contains one or more patterns. Each pattern starts with a line
  65 with the `pattern` keyword followed by the name of the pattern.
  66
  67 Declaring state variables
  68 -------------------------
  69
  70 One or more state variables can be declared using the `state` statement,
  71 followed by a C++ type in angle brackets, followed by a whitespace separated
  72 list of variable names. For example:
  73
  74     state <bool> flag1 flag2 happy big
  75     state <SigSpec> sigA sigB sigY
  76
  77 State variables are automatically managed by the generated backtracking algorithm
  78 and saved and restored as needed.
  79
  80 They are automatically initialized to the default constructed value of their type
  81 when `.run_<pattern_name>(callback_function)` is called.
  82
  83 Declaring udata variables
  84 -------------------------
  85
  86 Udata (user-data) variables can be used for example to configure the matcher or
  87 the callback function used to perform actions on found matches.
  88
  89 There is no automatic management of udata variables. For this reason it is
  90 recommended that the user-supplied matcher code treats them as read-only
  91 variables.
  92
  93 They are declared like state variables, just using the `udata` statement:
  94
  95     udata <int> min_data_width max_data_width
  96     udata <IdString> data_port_name
  97
  98 They are automatically initialized to the default constructed value of their type
  99 when the pattern matcher object is constructed.
 100
 101 Embedded C++ code
 102 -----------------
 103
 104 Many statements in a `.pmg` file contain C++ code. However, there are some
 105 slight additions to regular C++/Yosys/RTLIL code that make it a bit easier to
 106 write matchers:
 107
 108 - Identifiers starting with a dollar sign or backslash are automatically
 109   converted to special IdString variables that are initialized when the
 110   matcher object is constructed.
 111
 112 - The `port(<cell>, <portname>)` function is a handy alias for
 113   `sigmap(<cell>->getPort(<portname>))`.
 114
 115 - Similarly `param(<cell>, <paramname>)` looks up a parameter on a cell.
 116
 117 - The function `nusers(<sigspec>)` returns the number of different cells
 118   connected to any of the given signal bits, plus one if any of the signal
 119   bits is also a primary input or primary output.
 120
 121 - In `code..endcode` blocks there exist `accept`, `reject`, and `branch`
 122   statements.
 123
 124 - In `index` statements there is a special `===` operator for the index
 125   lookup.
 126
 127 Matching cells
 128 --------------
 129
 130 Cells are matched using `match..endmatch` blocks. For example:
 131
 132     match mul
 133         if ff
 134         select mul->type == $mul
 135         select nusers(port(mul, \Y) == 2
 136         index <SigSpec> port(mul, \Y) === port(ff, \D)
 137         filter some_weird_function(mul) < other_weird_function(ff)
 138         optional
 139     endmatch
 140
 141 A `match` block starts with `match <statevar>` and implicitly generates
 142 a state variable `<statevar>` of type `RTLIL::Cell*`.
 143
 144 All statements in the match block are optional. (An empty match block
 145 would simply match each and every cell in the module.)
 146
 147 The `if <expression>` statement makes the match block conditional. If
 148 `<expression>` evaluates to `false` then the match block will be ignored
 149 and the corresponding state variable is set to `nullptr`. In our example
 150 we only try to match the `mul` cell if the `ff` state variable points
 151 to a cell. (Presumably `ff` is provided by a prior `match` block.)
 152
 153 The `select` lines are evaluated once for each cell when the matcher is
 154 initialized. A `match` block will only consider cells for which all `select`
 155 expressions evaluated to `true`. Note that the state variable corresponding to
 156 the match (in the example `mul`) is the only state variable that may be used
 157 in `select` lines.
 158
 159 Index lines are using the `index <type> expr1 === expr2` syntax.  `expr1` is
 160 evaluated during matcher initialization and the same restrictions apply as for
 161 `select` expressions. `expr2` is evaluated when the match is calulated. It is a
 162 function of any state variables assigned to by previous blocks. Both expression
 163 are converted to the given type and compared for equality. Only cells for which
 164 all `index` statements in the block pass are considered by the match.
 165
 166 Note that `select` and `index` are fast operations. Thus `select` and `index`
 167 should be used whenever possible to create efficient matchers.
 168
 169 Finally, `filter <expression>` narrows down the remaining list of cells. For
 170 performance reasons `filter` statements should only be used for things that
 171 can't be done using `select` and `index`.
 172
 173 The `optional` statement marks optional matches. That is, the matcher will also
 174 explore the case where `mul` is set to `nullptr`. Without the `optional`
 175 statement a match may only be assigned nullptr when one of the `if` expressions
 176 evaluates to `false`.
 177
 178 Additional code
 179 ---------------
 180
 181 Interleaved with `match..endmatch` blocks there may be `code..endcode` blocks.
 182 Such a block starts with the keyword `code` followed by a list of state variables
 183 that the block may modify. For example:
 184
 185     code addAB sigS
 186         if (addA) {
 187             addAB = addA;
 188             sigS = port(addA, \B);
 189         }
 190         if (addB) {
 191             addAB = addB;
 192             sigS = port(addB, \A);
 193         }
 194     endcode
 195
 196 The special keyword `reject` can be used to reject the current state and
 197 backtrack. For example:
 198
 199     code
 200         if (ffA && ffB) {
 201             if (port(ffA, \CLK) != port(ffB, \CLK))
 202                 reject;
 203             if (param(ffA, \CLK_POLARITY) != param(ffB, \CLK_POLARITY))
 204                 reject;
 205         }
 206     endcode
 207
 208 Similarly, the special keyword `accept` can be used to accept the current
 209 state. (`accept` will not backtrack. This means it continues with the current
 210 branch and may accept a larger match later.)
 211
 212 The special keyword `branch` can be used to explore different cases. Note that
 213 each code block has an implicit `branch` at the end. So most use-cases of the
 214 `branch` keyword need to end the block with `reject` to avoid the implicit
 215 branch at the end. For example:
 216
 217     state <int> mode
 218
 219     code mode
 220         for (mode = 0; mode < 8; mode++)
 221             branch;
 222         reject;
 223     endcode
 224
 225 But in some cases it is more natural to utilize the implicit branch statement:
 226
 227     state <IdString> portAB
 228
 229     code portAB
 230         portAB = \A;
 231         branch;
 232         portAB = \B;
 233     endcode
 234
 235 There is an implicit `code..endcode` block at the end of each `.pmg` file
 236 that just accepts everything that gets all the way there.