Merge remote-tracking branch 'origin/master' into xaig_dff

24 files changed, 857 insertions, 112 deletions

diff --git a/CHANGELOG b/CHANGELOG
index 291c8d249..1324b2203 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -19,6 +19,7 @@ Yosys 0.9 .. Yosys 0.9-dev
     - Added automatic gzip compression (based on filename extension) for backends
     - Improve attribute and parameter encoding in JSON to avoid ambiguities between
       bit vectors and strings containing [01xz]*
+    - Improvements in pmgen: subpattern and recursive matches
     - Added "opt_share" pass, run as part of "opt -full"
     - Added "ice40_wrapcarry" to encapsulate SB_LUT+SB_CARRY pairs for techmapping
     - Removed "ice40_unlut"
diff --git a/Makefile b/Makefile
index 16341a268..666223076 100644
--- a/Makefile
+++ b/Makefile
@@ -487,6 +487,11 @@ define add_include_file
 $(eval $(call add_share_file,$(dir share/include/$(1)),$(1)))
 endef
 
+define add_extra_objs
+EXTRA_OBJS += $(1)
+.SECONDARY: $(1)
+endef
+
 ifeq ($(PRETTY), 1)
 P_STATUS = 0
 P_OFFSET = 0
@@ -695,6 +700,7 @@ test: $(TARGETS) $(EXTRA_TARGETS)
 	+cd tests/various && bash run-test.sh
 	+cd tests/sat && bash run-test.sh
 	+cd tests/svinterfaces && bash run-test.sh $(SEEDOPT)
+	+cd tests/proc && bash run-test.sh
 	+cd tests/opt && bash run-test.sh
 	+cd tests/aiger && bash run-test.sh $(ABCOPT)
 	+cd tests/arch && bash run-test.sh
diff --git a/README.md b/README.md
index 5b30f6bae..56f428548 100644
--- a/README.md
+++ b/README.md
@@ -417,9 +417,10 @@ Verilog Attributes and non-standard features
   port of a LUTRAM cell prevents `abc9` from interpreting any `Q` -> `D` paths
   as a combinatorial loop.
 
-- The port attribute ``abc_carry_in`` and ``abc_carry_out`` attributes mark
-  the carry-in and carry-out ports of a box. This information is necessary for
-  `abc9` to preserve the integrity of carry-chains.
+- The port attribute ``abc_carry`` marks the carry-in (if an input port) and
+  carry-out (if output port) ports of a box. This information is necessary for
+  `abc9` to preserve the integrity of carry-chains. Specifying this attribute
+  onto a bus port will affect only its most significant bit.
 
 
 Non-standard or SystemVerilog features for formal verification
diff --git a/frontends/ast/ast.cc b/frontends/ast/ast.cc
index 0d6626b19..82283fb5b 100644
--- a/frontends/ast/ast.cc
+++ b/frontends/ast/ast.cc
@@ -1502,7 +1502,10 @@ std::string AstModule::derive_common(RTLIL::Design *design, dict<RTLIL::IdString
 	rewrite_parameter:
 			para_info += stringf("%s=%s", child->str.c_str(), log_signal(RTLIL::SigSpec(parameters[para_id])));
 			delete child->children.at(0);
-			if ((parameters[para_id].flags & RTLIL::CONST_FLAG_STRING) != 0)
+			if ((parameters[para_id].flags & RTLIL::CONST_FLAG_REAL) != 0) {
+				child->children[0] = new AstNode(AST_REALVALUE);
+				child->children[0]->realvalue = std::stod(parameters[para_id].decode_string());
+			} else if ((parameters[para_id].flags & RTLIL::CONST_FLAG_STRING) != 0)
 				child->children[0] = AstNode::mkconst_str(parameters[para_id].decode_string());
 			else
 				child->children[0] = AstNode::mkconst_bits(parameters[para_id].bits, (parameters[para_id].flags & RTLIL::CONST_FLAG_SIGNED) != 0);
diff --git a/passes/pmgen/.gitignore b/passes/pmgen/.gitignore
index e52f3282f..6b319b8c3 100644
--- a/passes/pmgen/.gitignore
+++ b/passes/pmgen/.gitignore
@@ -1 +1 @@
-/*_pm.h
+/*_pm.h
\ No newline at end of file
diff --git a/passes/pmgen/Makefile.inc b/passes/pmgen/Makefile.inc
index c03606152..790811d4c 100644
--- a/passes/pmgen/Makefile.inc
+++ b/passes/pmgen/Makefile.inc
@@ -1,30 +1,29 @@
-OBJS += passes/pmgen/ice40_dsp.o
-OBJS += passes/pmgen/ice40_wrapcarry.o
-OBJS += passes/pmgen/peepopt.o
+%_pm.h: passes/pmgen/pmgen.py %.pmg
+	$(P) mkdir -p passes/pmgen && python3 $< -o $@ -p $(subst _pm.h,,$(notdir $@)) $(filter-out $<,$^)
 
 # --------------------------------------
 
-passes/pmgen/ice40_dsp.o: passes/pmgen/ice40_dsp_pm.h
-EXTRA_OBJS += passes/pmgen/ice40_dsp_pm.h
-.SECONDARY: passes/pmgen/ice40_dsp_pm.h
+OBJS += passes/pmgen/test_pmgen.o
+passes/pmgen/test_pmgen.o: passes/pmgen/test_pmgen_pm.h
+$(eval $(call add_extra_objs,passes/pmgen/test_pmgen_pm.h))
 
-passes/pmgen/ice40_dsp_pm.h: passes/pmgen/pmgen.py passes/pmgen/ice40_dsp.pmg
-	$(P) mkdir -p passes/pmgen && python3 $< -o $@ -p ice40_dsp $(filter-out $<,$^)
+# --------------------------------------
+
+OBJS += passes/pmgen/ice40_dsp.o
+passes/pmgen/ice40_dsp.o: passes/pmgen/ice40_dsp_pm.h
+$(eval $(call add_extra_objs,passes/pmgen/ice40_dsp_pm.h))
 
 # --------------------------------------
 
+OBJS += passes/pmgen/ice40_wrapcarry.o
 passes/pmgen/ice40_wrapcarry.o: passes/pmgen/ice40_wrapcarry_pm.h
-EXTRA_OBJS += passes/pmgen/ice40_wrapcarry_pm.h
-.SECONDARY: passes/pmgen/ice40_wrapcarry_pm.h
-
-passes/pmgen/ice40_wrapcarry_pm.h: passes/pmgen/pmgen.py passes/pmgen/ice40_wrapcarry.pmg
-	$(P) mkdir -p passes/pmgen && python3 $< -o $@ -p ice40_wrapcarry $(filter-out $<,$^)
+$(eval $(call add_extra_objs,passes/pmgen/test_pmgen_pm.h))
 
 # --------------------------------------
 
+OBJS += passes/pmgen/peepopt.o
 passes/pmgen/peepopt.o: passes/pmgen/peepopt_pm.h
-EXTRA_OBJS += passes/pmgen/peepopt_pm.h
-.SECONDARY: passes/pmgen/peepopt_pm.h
+$(eval $(call add_extra_objs,passes/pmgen/peepopt_pm.h))
 
 PEEPOPT_PATTERN  = passes/pmgen/peepopt_shiftmul.pmg
 PEEPOPT_PATTERN += passes/pmgen/peepopt_muldiv.pmg
diff --git a/passes/pmgen/README.md b/passes/pmgen/README.md
index 2f0b1fd5a..5f6a8ab1b 100644
--- a/passes/pmgen/README.md
+++ b/passes/pmgen/README.md
@@ -45,9 +45,9 @@ of type `foobar_pm::state_<pattern_name>_t`.)
 Similarly the `.pmg` file declares user data variables that become members of
 `.ud_<pattern_name>`, a struct of type `foobar_pm::udata_<pattern_name>_t`.
 
-There are four versions of the `run_<pattern_name>()` method: Without callback,
-callback without arguments, callback with reference to `pm`, and callback with
-reference to `pm.st_<pattern_name>`.
+There are three versions of the `run_<pattern_name>()` method: Without callback,
+callback without arguments, and callback with reference to `pm`. All versions
+of the `run_<pattern_name>()` method return the number of found matches.
 
 
 The .pmg File Format
@@ -118,8 +118,8 @@ write matchers:
   connected to any of the given signal bits, plus one if any of the signal
   bits is also a primary input or primary output.
 
-- In `code..endcode` blocks there exist `accept`, `reject`, and `branch`
-  statements.
+- In `code..endcode` blocks there exist `accept`, `reject`, `branch`,
+  `finish`, and `subpattern` statements.
 
 - In `index` statements there is a special `===` operator for the index
   lookup.
@@ -175,6 +175,9 @@ explore the case where `mul` is set to `nullptr`. Without the `optional`
 statement a match may only be assigned nullptr when one of the `if` expressions
 evaluates to `false`.
 
+The `semioptional` statement marks matches that must match if at least one
+matching cell exists, but if no matching cell exists it is set to `nullptr`.
+
 Additional code
 ---------------
 
@@ -232,5 +235,108 @@ But in some cases it is more natural to utilize the implicit branch statement:
         portAB = \B;
     endcode
 
-There is an implicit `code..endcode` block at the end of each `.pmg` file
-that just accepts everything that gets all the way there.
+There is an implicit `code..endcode` block at the end of each (sub)pattern
+that just rejects.
+
+A `code..finally..endcode` block executes the code after `finally` during
+back-tracking. This is useful for maintaining user data state or printing
+debug messages. For example:
+
+    udata <vector<Cell*>> stack
+
+    code
+        stack.push_back(addAB);
+        ...
+    finally
+        stack.pop_back();
+    endcode
+
+`accept` and `finish` statements can be used inside the `finally` section,
+but not `reject`, `branch`, or `subpattern`.
+
+Declaring a subpattern
+----------------------
+
+A subpattern starts with a line containing the `subpattern` keyword followed
+by the name of the subpattern. Subpatterns can be called from a `code` block
+using a `subpattern(<subpattern_name>);` C statement.
+
+Arguments may be passed to subpattern via state variables. The `subpattern`
+line must be followed by a `arg <arg1> <arg2> ...` line that lists the
+state variables used to pass arguments.
+
+    state <IdString> foobar_type
+    state <bool> foobar_state
+
+    code foobar_type foobar_state
+        foobar_state = false;
+        foobar_type = $add;
+        subpattern(foo);
+        foobar_type = $sub;
+        subpattern(bar);
+    endcode
+
+    subpattern foo
+    arg foobar_type foobar_state
+
+    match addsub
+        index <IdString> addsub->type === foobar_type
+        ...
+    endmatch
+
+    code
+        if (foobar_state) {
+            subpattern(tail);
+        } else {
+            foobar_state = true;
+            subpattern(bar);
+        }
+    endcode
+
+    subpattern bar
+    arg foobar_type foobar_state
+
+    match addsub
+        index <IdString> addsub->type === foobar_type
+        ...
+    endmatch
+
+    code
+        if (foobar_state) {
+            subpattern(tail);
+        } else {
+            foobar_state = true;
+            subpattern(foo);
+        }
+    endcode
+
+    subpattern tail
+    ...
+
+Subpatterns cann be called recursively.
+
+If a `subpattern` statement is preceded by a `fallthrough` statement, this is
+equivalent to calling the subpattern at the end of the preceding block.
+
+Generate Blocks
+---------------
+
+Match blocks may contain an optional `generate` section that is used for automatic
+test-case generation. For example:
+
+    match mul
+        ...
+    generate 10
+        SigSpec Y = port(ff, \D);
+        SigSpec A = module->addWire(NEW_ID, GetSize(Y) - rng(GetSize(Y)/2));
+        SigSpec B = module->addWire(NEW_ID, GetSize(Y) - rng(GetSize(Y)/2));
+        module->addMul(NEW_ID, A, B, Y, rng(2));
+    endmatch
+
+The expression `rng(n)` returns a non-negative integer less than `n`.
+
+The argument to `generate` is the chance of this generate block being executed
+when the match block did not match anything, in percent.
+
+The special statement `finish` can be used within generate blocks to terminate
+the current pattern matcher run.
diff --git a/passes/pmgen/ice40_dsp.pmg b/passes/pmgen/ice40_dsp.pmg
index 1f3590d4e..7003092bb 100644
--- a/passes/pmgen/ice40_dsp.pmg
+++ b/passes/pmgen/ice40_dsp.pmg
@@ -159,4 +159,5 @@ code clock clock_pol clock_vld
 		clock_pol = cp;
 		clock_vld = true;
 	}
+	accept;
 endcode
diff --git a/passes/pmgen/peepopt_muldiv.pmg b/passes/pmgen/peepopt_muldiv.pmg
index 06c275834..7cad759d0 100644
--- a/passes/pmgen/peepopt_muldiv.pmg
+++ b/passes/pmgen/peepopt_muldiv.pmg
@@ -32,5 +32,5 @@ code
 	log("muldiv pattern in %s: mul=%s, div=%s\n", log_id(module), log_id(mul), log_id(div));
 	module->connect(div_y, val_y);
 	autoremove(div);
-	reject;
+	accept;
 endcode
diff --git a/passes/pmgen/peepopt_shiftmul.pmg b/passes/pmgen/peepopt_shiftmul.pmg
index 6adab4e5f..d4748ae19 100644
--- a/passes/pmgen/peepopt_shiftmul.pmg
+++ b/passes/pmgen/peepopt_shiftmul.pmg
@@ -34,6 +34,7 @@ match mul
 endmatch
 
 code
+{
 	IdString const_factor_port = port(mul, \A).is_fully_const() ? \A : \B;
 	IdString const_factor_signed = const_factor_port == \A ? \A_SIGNED : \B_SIGNED;
 	Const const_factor_cnst = port(mul, const_factor_port).as_const();
@@ -90,5 +91,6 @@ code
 	shift->setParam(\B_WIDTH, GetSize(new_b));
 
 	blacklist(shift);
-	reject;
+	accept;
+}
 endcode
diff --git a/passes/pmgen/pmgen.py b/passes/pmgen/pmgen.py
index 81052afce..18c3bf5a5 100644
--- a/passes/pmgen/pmgen.py
+++ b/passes/pmgen/pmgen.py
@@ -38,7 +38,10 @@ for a in args:
 assert prefix is not None
 
 current_pattern = None
+current_subpattern = None
 patterns = dict()
+subpatterns = dict()
+subpattern_args = dict()
 state_types = dict()
 udata_types = dict()
 blocks = list()
@@ -104,9 +107,12 @@ def rewrite_cpp(s):
 
     return "".join(t)
 
-def process_pmgfile(f):
+def process_pmgfile(f, filename):
+    linenr = 0
     global current_pattern
+    global current_subpattern
     while True:
+        linenr += 1
         line = f.readline()
         if line == "": break
         line = line.strip()
@@ -119,19 +125,52 @@ def process_pmgfile(f):
             if current_pattern is not None:
                 block = dict()
                 block["type"] = "final"
-                block["pattern"] = current_pattern
+                block["pattern"] = (current_pattern, current_subpattern)
                 blocks.append(block)
             line = line.split()
             assert len(line) == 2
             assert line[1] not in patterns
             current_pattern = line[1]
+            current_subpattern = ""
             patterns[current_pattern] = len(blocks)
+            subpatterns[(current_pattern, current_subpattern)] = len(blocks)
+            subpattern_args[(current_pattern, current_subpattern)] = list()
             state_types[current_pattern] = dict()
             udata_types[current_pattern] = dict()
             continue
 
         assert current_pattern is not None
 
+        if cmd == "fallthrough":
+            block = dict()
+            block["type"] = "fallthrough"
+            blocks.append(block)
+            line = line.split()
+            assert len(line) == 1
+            continue
+
+        if cmd == "subpattern":
+            if len(blocks) == 0 or blocks[-1]["type"] != "fallthrough":
+                block = dict()
+                block["type"] = "final"
+                block["pattern"] = (current_pattern, current_subpattern)
+                blocks.append(block)
+            elif len(blocks) and blocks[-1]["type"] == "fallthrough":
+                del blocks[-1]
+            line = line.split()
+            assert len(line) == 2
+            current_subpattern = line[1]
+            subpattern_args[(current_pattern, current_subpattern)] = list()
+            assert (current_pattern, current_subpattern) not in subpatterns
+            subpatterns[(current_pattern, current_subpattern)] = len(blocks)
+            continue
+
+        if cmd == "arg":
+            line = line.split()
+            assert len(line) > 1
+            subpattern_args[(current_pattern, current_subpattern)] += line[1:]
+            continue
+
         if cmd == "state":
             m = re.match(r"^state\s+<(.*?)>\s+(([A-Za-z_][A-Za-z_0-9]*\s+)*[A-Za-z_][A-Za-z_0-9]*)\s*$", line)
             assert m
@@ -155,11 +194,15 @@ def process_pmgfile(f):
         if cmd == "match":
             block = dict()
             block["type"] = "match"
-            block["pattern"] = current_pattern
+            block["src"] = "%s:%d" % (filename, linenr)
+            block["pattern"] = (current_pattern, current_subpattern)
+
+            block["genargs"] = None
+            block["gencode"] = None
 
             line = line.split()
             assert len(line) == 2
-            assert line[1] not in state_types[current_pattern]
+            assert (line[1] not in state_types[current_pattern]) or (state_types[current_pattern][line[1]] == "Cell*")
             block["cell"] = line[1]
             state_types[current_pattern][line[1]] = "Cell*";
 
@@ -168,8 +211,10 @@ def process_pmgfile(f):
             block["index"] = list()
             block["filter"] = list()
             block["optional"] = False
+            block["semioptional"] = False
 
             while True:
+                linenr += 1
                 l = f.readline()
                 assert l != ""
                 a = l.split()
@@ -201,31 +246,60 @@ def process_pmgfile(f):
                     block["optional"] = True
                     continue
 
+                if a[0] == "semioptional":
+                    block["semioptional"] = True
+                    continue
+
+                if a[0] == "generate":
+                    block["genargs"] = list([int(s) for s in a[1:]])
+                    block["gencode"] = list()
+                    assert len(block["genargs"]) < 2
+                    while True:
+                        linenr += 1
+                        l = f.readline()
+                        assert l != ""
+                        a = l.split()
+                        if a[0] == "endmatch": break
+                        block["gencode"].append(rewrite_cpp(l.rstrip()))
+                    break
+
                 assert False
 
+            if block["optional"]:
+                assert not block["semioptional"]
+
             blocks.append(block)
             continue
 
         if cmd == "code":
             block = dict()
             block["type"] = "code"
-            block["pattern"] = current_pattern
+            block["src"] = "%s:%d" % (filename, linenr)
+            block["pattern"] = (current_pattern, current_subpattern)
 
             block["code"] = list()
+            block["fcode"] = list()
             block["states"] = set()
 
             for s in line.split()[1:]:
                 assert s in state_types[current_pattern]
                 block["states"].add(s)
 
+            codetype = "code"
+
             while True:
+                linenr += 1
                 l = f.readline()
                 assert l != ""
                 a = l.split()
                 if len(a) == 0: continue
                 if a[0] == "endcode": break
 
-                block["code"].append(rewrite_cpp(l.rstrip()))
+                if a[0] == "finally":
+                    codetype = "fcode"
+                    continue
+
+                block[codetype].append(rewrite_cpp(l.rstrip()))
 
             blocks.append(block)
             continue
@@ -234,15 +308,16 @@ def process_pmgfile(f):
 
 for fn in pmgfiles:
     with open(fn, "r") as f:
-        process_pmgfile(f)
+        process_pmgfile(f, fn)
 
 if current_pattern is not None:
     block = dict()
     block["type"] = "final"
-    block["pattern"] = current_pattern
+    block["pattern"] = (current_pattern, current_subpattern)
     blocks.append(block)
 
 current_pattern = None
+current_subpattern = None
 
 if debug:
     pp.pprint(blocks)
@@ -262,7 +337,18 @@ with open(outfile, "w") as f:
     print("struct {}_pm {{".format(prefix), file=f)
     print("  Module *module;", file=f)
     print("  SigMap sigmap;", file=f)
-    print("  std::function<void()> on_accept;".format(prefix), file=f)
+    print("  std::function<void()> on_accept;", file=f)
+    print("  bool generate_mode;", file=f)
+    print("  int accept_cnt;", file=f)
+    print("", file=f)
+
+    print("  uint32_t rngseed;", file=f)
+    print("  int rng(unsigned int n) {", file=f)
+    print("    rngseed ^= rngseed << 13;", file=f)
+    print("    rngseed ^= rngseed >> 17;", file=f)
+    print("    rngseed ^= rngseed << 5;", file=f)
+    print("    return rngseed % n;", file=f)
+    print("  }", file=f)
     print("", file=f)
 
     for index in range(len(blocks)):
@@ -276,7 +362,7 @@ with open(outfile, "w") as f:
     print("  dict<SigBit, pool<Cell*>> sigusers;", file=f)
     print("  pool<Cell*> blacklist_cells;", file=f)
     print("  pool<Cell*> autoremove_cells;", file=f)
-    print("  bool blacklist_dirty;", file=f)
+    print("  dict<Cell*,int> rollback_cache;", file=f)
     print("  int rollback;", file=f)
     print("", file=f)
 
@@ -312,39 +398,24 @@ with open(outfile, "w") as f:
     print("", file=f)
 
     print("  void blacklist(Cell *cell) {", file=f)
-    print("    if (cell != nullptr) {", file=f)
-    print("      if (blacklist_cells.insert(cell).second)", file=f)
-    print("        blacklist_dirty = true;", file=f)
+    print("    if (cell != nullptr && blacklist_cells.insert(cell).second) {", file=f)
+    print("      auto ptr = rollback_cache.find(cell);", file=f)
+    print("      if (ptr == rollback_cache.end()) return;", file=f)
+    print("      int rb = ptr->second;", file=f)
+    print("      if (rollback == 0 || rollback > rb)", file=f)
+    print("        rollback = rb;", file=f)
     print("    }", file=f)
     print("  }", file=f)
     print("", file=f)
 
     print("  void autoremove(Cell *cell) {", file=f)
     print("    if (cell != nullptr) {", file=f)
-    print("      if (blacklist_cells.insert(cell).second)", file=f)
-    print("        blacklist_dirty = true;", file=f)
     print("      autoremove_cells.insert(cell);", file=f)
+    print("      blacklist(cell);", file=f)
     print("    }", file=f)
     print("  }", file=f)
     print("", file=f)
 
-    for current_pattern in sorted(patterns.keys()):
-        print("  void check_blacklist_{}() {{".format(current_pattern), file=f)
-        print("    if (!blacklist_dirty)", file=f)
-        print("      return;", file=f)
-        print("    blacklist_dirty = false;", file=f)
-        for index in range(len(blocks)):
-            block = blocks[index]
-            if block["pattern"] != current_pattern:
-                continue
-            if block["type"] == "match":
-                print("    if (st_{}.{} != nullptr && blacklist_cells.count(st_{}.{})) {{".format(current_pattern, block["cell"], current_pattern, block["cell"]), file=f)
-                print("      rollback = {};".format(index+1), file=f)
-                print("      return;", file=f)
-                print("    }", file=f)
-        print("    rollback = 0;", file=f)
-        print("  }", file=f)
-        print("", file=f)
     current_pattern = None
 
     print("  SigSpec port(Cell *cell, IdString portname) {", file=f)
@@ -367,7 +438,7 @@ with open(outfile, "w") as f:
     print("", file=f)
 
     print("  {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f)
-    print("      module(module), sigmap(module) {", file=f)
+    print("      module(module), sigmap(module), generate_mode(false), rngseed(12345678) {", file=f)
     for current_pattern in sorted(patterns.keys()):
         for s, t in sorted(udata_types[current_pattern].items()):
             if t.endswith("*"):
@@ -405,41 +476,47 @@ with open(outfile, "w") as f:
     print("", file=f)
 
     for current_pattern in sorted(patterns.keys()):
-        print("  void run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
+        print("  int run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
+        print("    accept_cnt = 0;", file=f)
         print("    on_accept = on_accept_f;", file=f)
         print("    rollback = 0;", file=f)
-        print("    blacklist_dirty = false;", file=f)
         for s, t in sorted(state_types[current_pattern].items()):
             if t.endswith("*"):
                 print("    st_{}.{} = nullptr;".format(current_pattern, s), file=f)
             else:
                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
-        print("    block_{}();".format(patterns[current_pattern]), file=f)
+        print("    block_{}(1);".format(patterns[current_pattern]), file=f)
+        print("    log_assert(rollback_cache.empty());", file=f)
+        print("    return accept_cnt;", file=f)
         print("  }", file=f)
         print("", file=f)
-        print("  void run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
-        print("    run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
+        print("  int run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
+        print("    return run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
         print("  }", file=f)
         print("", file=f)
-        print("  void run_{}(std::function<void(state_{}_t&)> on_accept_f) {{".format(current_pattern, current_pattern), file=f)
-        print("    run_{}([&](){{on_accept_f(st_{});}});".format(current_pattern, current_pattern), file=f)
+        print("  int run_{}() {{".format(current_pattern), file=f)
+        print("    return run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
         print("  }", file=f)
         print("", file=f)
-        print("  void run_{}() {{".format(current_pattern), file=f)
-        print("    run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
-        print("  }", file=f)
+
+    if len(subpatterns):
+        for p, s in sorted(subpatterns.keys()):
+            print("  void block_subpattern_{}_{}(int recursion) {{ block_{}(recursion); }}".format(p, s, subpatterns[(p, s)]), file=f)
         print("", file=f)
+
     current_pattern = None
+    current_subpattern = None
 
     for index in range(len(blocks)):
         block = blocks[index]
 
-        print("  void block_{}() {{".format(index), file=f)
-        current_pattern = block["pattern"]
+        if block["type"] in ("match", "code"):
+            print("  // {}".format(block["src"]), file=f)
+
+        print("  void block_{}(int recursion YS_ATTRIBUTE(unused)) {{".format(index), file=f)
+        current_pattern, current_subpattern = block["pattern"]
 
         if block["type"] == "final":
-            print("    on_accept();", file=f)
-            print("    check_blacklist_{}();".format(current_pattern), file=f)
             print("  }", file=f)
             if index+1 != len(blocks):
                 print("", file=f)
@@ -449,7 +526,10 @@ with open(outfile, "w") as f:
         nonconst_st = set()
         restore_st = set()
 
-        for i in range(patterns[current_pattern], index):
+        for s in subpattern_args[(current_pattern, current_subpattern)]:
+            const_st.add(s)
+
+        for i in range(subpatterns[(current_pattern, current_subpattern)], index):
             if blocks[i]["type"] == "code":
                 for s in blocks[i]["states"]:
                     const_st.add(s)
@@ -482,6 +562,10 @@ with open(outfile, "w") as f:
             t = state_types[current_pattern][s]
             print("    {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 
+        for u in sorted(udata_types[current_pattern].keys()):
+            t = udata_types[current_pattern][u]
+            print("    {} &{} YS_ATTRIBUTE(unused) = ud_{}.{};".format(t, u, current_pattern, u), file=f)
+
         if len(restore_st):
             print("", file=f)
             for s in sorted(restore_st):
@@ -490,24 +574,38 @@ with open(outfile, "w") as f:
 
         if block["type"] == "code":
             print("", file=f)
-            print("    do {", file=f)
-            print("#define reject do {{ check_blacklist_{}(); goto rollback_label; }} while(0)".format(current_pattern), file=f)
-            print("#define accept do {{ on_accept(); check_blacklist_{}(); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
-            print("#define branch do {{ block_{}(); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
+            print("#define reject do { goto rollback_label; } while(0)", file=f)
+            print("#define accept do { accept_cnt++; on_accept(); if (rollback) goto rollback_label; } while(0)", file=f)
+            print("#define finish do { rollback = -1; goto rollback_label; } while(0)", file=f)
+            print("#define branch do {{ block_{}(recursion+1); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
+            print("#define subpattern(pattern_name) do {{ block_subpattern_{}_ ## pattern_name (recursion+1); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
 
             for line in block["code"]:
-                print("    " + line, file=f)
+                print("  " + line, file=f)
 
             print("", file=f)
-            print("      block_{}();".format(index+1), file=f)
+            print("    block_{}(recursion+1);".format(index+1), file=f)
+
             print("#undef reject", file=f)
             print("#undef accept", file=f)
+            print("#undef finish", file=f)
             print("#undef branch", file=f)
-            print("    } while (0);", file=f)
+            print("#undef subpattern", file=f)
+
             print("", file=f)
             print("rollback_label:", file=f)
             print("    YS_ATTRIBUTE(unused);", file=f)
 
+            if len(block["fcode"]):
+                print("#define accept do { accept_cnt++; on_accept(); } while(0)", file=f)
+                print("#define finish do { rollback = -1; goto finish_label; } while(0)", file=f)
+                for line in block["fcode"]:
+                    print("  " + line, file=f)
+                print("finish_label:", file=f)
+                print("    YS_ATTRIBUTE(unused);", file=f)
+                print("#undef accept", file=f)
+                print("#undef finish", file=f)
+
             if len(restore_st) or len(nonconst_st):
                 print("", file=f)
                 for s in sorted(restore_st):
@@ -524,12 +622,15 @@ with open(outfile, "w") as f:
         elif block["type"] == "match":
             assert len(restore_st) == 0
 
+            print("    Cell* backup_{} = {};".format(block["cell"], block["cell"]), file=f)
+
             if len(block["if"]):
                 for expr in block["if"]:
                     print("", file=f)
                     print("    if (!({})) {{".format(expr), file=f)
                     print("      {} = nullptr;".format(block["cell"]), file=f)
-                    print("      block_{}();".format(index+1), file=f)
+                    print("      block_{}(recursion+1);".format(index+1), file=f)
+                    print("      {} = backup_{};".format(block["cell"], block["cell"]), file=f)
                     print("      return;", file=f)
                     print("    }", file=f)
 
@@ -537,21 +638,32 @@ with open(outfile, "w") as f:
             print("    index_{}_key_type key;".format(index), file=f)
             for field, entry in enumerate(block["index"]):
                 print("    std::get<{}>(key) = {};".format(field, entry[2]), file=f)
-            print("    const vector<Cell*> &cells = index_{}[key];".format(index), file=f)
+            print("    auto cells_ptr = index_{}.find(key);".format(index), file=f)
+
+            if block["semioptional"] or block["genargs"] is not None:
+                print("    bool found_any_match = false;", file=f)
 
             print("", file=f)
-            print("    for (int idx = 0; idx < GetSize(cells); idx++) {", file=f)
-            print("      {} = cells[idx];".format(block["cell"]), file=f)
-            print("      if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
+            print("    if (cells_ptr != index_{}.end()) {{".format(index), file=f)
+            print("      const vector<Cell*> &cells = cells_ptr->second;".format(index), file=f)
+            print("      for (int idx = 0; idx < GetSize(cells); idx++) {", file=f)
+            print("        {} = cells[idx];".format(block["cell"]), file=f)
+            print("        if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
             for expr in block["filter"]:
-                print("      if (!({})) continue;".format(expr), file=f)
-            print("      block_{}();".format(index+1), file=f)
-            print("      if (rollback) {", file=f)
-            print("        if (rollback != {}) {{".format(index+1), file=f)
-            print("          {} = nullptr;".format(block["cell"]), file=f)
-            print("          return;", file=f)
+                print("        if (!({})) continue;".format(expr), file=f)
+            if block["semioptional"] or block["genargs"] is not None:
+                print("        found_any_match = true;", file=f)
+            print("        auto rollback_ptr = rollback_cache.insert(make_pair(cells[idx], recursion));", file=f)
+            print("        block_{}(recursion+1);".format(index+1), file=f)
+            print("        if (rollback_ptr.second)", file=f)
+            print("          rollback_cache.erase(rollback_ptr.first);", file=f)
+            print("        if (rollback) {", file=f)
+            print("          if (rollback != recursion) {{".format(index+1), file=f)
+            print("            {} = backup_{};".format(block["cell"], block["cell"]), file=f)
+            print("            return;", file=f)
+            print("          }", file=f)
+            print("          rollback = 0;", file=f)
             print("        }", file=f)
-            print("        rollback = 0;", file=f)
             print("      }", file=f)
             print("    }", file=f)
 
@@ -559,8 +671,22 @@ with open(outfile, "w") as f:
             print("    {} = nullptr;".format(block["cell"]), file=f)
 
             if block["optional"]:
-                print("    block_{}();".format(index+1), file=f)
+                print("    block_{}(recursion+1);".format(index+1), file=f)
 
+            if block["semioptional"]:
+                print("    if (!found_any_match) block_{}(recursion+1);".format(index+1), file=f)
+
+            print("    {} = backup_{};".format(block["cell"], block["cell"]), file=f)
+
+            if block["genargs"] is not None:
+                print("#define finish do { rollback = -1; return; } while(0)", file=f)
+                print("    if (generate_mode && !found_any_match) {", file=f)
+                if len(block["genargs"]) == 1:
+                    print("    if (rng(100) >= {}) return;".format(block["genargs"][0]), file=f)
+                for line in block["gencode"]:
+                    print("      " + line, file=f)
+                print("    }", file=f)
+                print("#undef finish", file=f)
         else:
             assert False
 
diff --git a/passes/pmgen/test_pmgen.cc b/passes/pmgen/test_pmgen.cc
new file mode 100644
index 000000000..9f42a95d0
--- /dev/null
+++ b/passes/pmgen/test_pmgen.cc
@@ -0,0 +1,330 @@
+/*
+ *  yosys -- Yosys Open SYnthesis Suite
+ *
+ *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include "kernel/yosys.h"
+#include "kernel/sigtools.h"
+
+USING_YOSYS_NAMESPACE
+PRIVATE_NAMESPACE_BEGIN
+
+// for peepopt_pm
+bool did_something;
+
+#include "passes/pmgen/test_pmgen_pm.h"
+#include "passes/pmgen/ice40_dsp_pm.h"
+#include "passes/pmgen/peepopt_pm.h"
+
+void reduce_chain(test_pmgen_pm &pm)
+{
+	auto &st = pm.st_reduce;
+	auto &ud = pm.ud_reduce;
+
+	if (ud.longest_chain.empty())
+		return;
+
+	log("Found chain of length %d (%s):\n", GetSize(ud.longest_chain), log_id(st.first->type));
+
+	SigSpec A;
+	SigSpec Y = ud.longest_chain.front().first->getPort(ID(Y));
+	auto last_cell = ud.longest_chain.back().first;
+
+	for (auto it : ud.longest_chain) {
+		auto cell = it.first;
+		if (cell == last_cell) {
+			A.append(cell->getPort(ID(A)));
+			A.append(cell->getPort(ID(B)));
+		} else {
+			A.append(cell->getPort(it.second == ID(A) ? ID(B) : ID(A)));
+		}
+		log("    %s\n", log_id(cell));
+		pm.autoremove(cell);
+	}
+
+	Cell *c;
+
+	if (last_cell->type == ID($_AND_))
+		c = pm.module->addReduceAnd(NEW_ID, A, Y);
+	else if (last_cell->type == ID($_OR_))
+		c = pm.module->addReduceOr(NEW_ID, A, Y);
+	else if (last_cell->type == ID($_XOR_))
+		c = pm.module->addReduceXor(NEW_ID, A, Y);
+	else
+		log_abort();
+
+	log("    -> %s (%s)\n", log_id(c), log_id(c->type));
+}
+
+void reduce_tree(test_pmgen_pm &pm)
+{
+	auto &st = pm.st_reduce;
+	auto &ud = pm.ud_reduce;
+
+	if (ud.longest_chain.empty())
+		return;
+
+	SigSpec A = ud.leaves;
+	SigSpec Y = st.first->getPort(ID(Y));
+	pm.autoremove(st.first);
+
+	log("Found %s tree with %d leaves for %s (%s).\n", log_id(st.first->type),
+			GetSize(A), log_signal(Y), log_id(st.first));
+
+	Cell *c;
+
+	if (st.first->type == ID($_AND_))
+		c = pm.module->addReduceAnd(NEW_ID, A, Y);
+	else if (st.first->type == ID($_OR_))
+		c = pm.module->addReduceOr(NEW_ID, A, Y);
+	else if (st.first->type == ID($_XOR_))
+		c = pm.module->addReduceXor(NEW_ID, A, Y);
+	else
+		log_abort();
+
+	log("    -> %s (%s)\n", log_id(c), log_id(c->type));
+}
+
+#define GENERATE_PATTERN(pmclass, pattern) \
+	generate_pattern<pmclass>([](pmclass &pm, std::function<void()> f){ return pm.run_ ## pattern(f); }, #pmclass, #pattern, design)
+
+void pmtest_addports(Module *module)
+{
+	pool<SigBit> driven_bits, used_bits;
+	SigMap sigmap(module);
+	int icnt = 0, ocnt = 0;
+
+	for (auto cell : module->cells())
+	for (auto conn : cell->connections())
+	{
+		if (cell->input(conn.first))
+			for (auto bit : sigmap(conn.second))
+				used_bits.insert(bit);
+		if (cell->output(conn.first))
+			for (auto bit : sigmap(conn.second))
+				driven_bits.insert(bit);
+	}
+
+	for (auto wire : vector<Wire*>(module->wires()))
+	{
+		SigSpec ibits, obits;
+		for (auto bit : sigmap(wire)) {
+			if (!used_bits.count(bit))
+				obits.append(bit);
+			if (!driven_bits.count(bit))
+				ibits.append(bit);
+		}
+		if (!ibits.empty()) {
+			Wire *w = module->addWire(stringf("\\i%d", icnt++), GetSize(ibits));
+			w->port_input = true;
+			module->connect(ibits, w);
+		}
+		if (!obits.empty()) {
+			Wire *w = module->addWire(stringf("\\o%d", ocnt++), GetSize(obits));
+			w->port_output = true;
+			module->connect(w, obits);
+		}
+	}
+
+	module->fixup_ports();
+}
+
+template <class pm>
+void generate_pattern(std::function<void(pm&,std::function<void()>)> run, const char *pmclass, const char *pattern, Design *design)
+{
+	log("Generating \"%s\" patterns for pattern matcher \"%s\".\n", pattern, pmclass);
+
+	int modcnt = 0;
+	int maxsubcnt = 4;
+	int timeout = 0;
+	vector<Module*> mods;
+
+	while (modcnt < 100)
+	{
+		int submodcnt = 0, itercnt = 0, cellcnt = 0;
+		Module *mod = design->addModule(NEW_ID);
+
+		while (modcnt < 100 && submodcnt < maxsubcnt && itercnt++ < 1000)
+		{
+			if (timeout++ > 10000)
+				log_error("pmgen generator is stuck: 10000 iterations an no matching module generated.\n");
+
+			pm matcher(mod, mod->cells());
+
+			matcher.rng(1);
+			matcher.rngseed += modcnt;
+			matcher.rng(1);
+			matcher.rngseed += submodcnt;
+			matcher.rng(1);
+			matcher.rngseed += itercnt;
+			matcher.rng(1);
+			matcher.rngseed += cellcnt;
+			matcher.rng(1);
+
+			if (GetSize(mod->cells()) != cellcnt)
+			{
+				bool found_match = false;
+				run(matcher, [&](){ found_match = true; });
+				cellcnt = GetSize(mod->cells());
+
+				if (found_match) {
+					Module *m = design->addModule(stringf("\\pmtest_%s_%s_%05d",
+							pmclass, pattern, modcnt++));
+					log("Creating module %s with %d cells.\n", log_id(m), cellcnt);
+					mod->cloneInto(m);
+					pmtest_addports(m);
+					mods.push_back(m);
+					submodcnt++;
+					timeout = 0;
+				}
+			}
+
+			matcher.generate_mode = true;
+			run(matcher, [](){});
+		}
+
+		if (submodcnt)
+			maxsubcnt *= 2;
+
+		design->remove(mod);
+	}
+
+	Module *m = design->addModule(stringf("\\pmtest_%s_%s", pmclass, pattern));
+	log("Creating module %s with %d cells.\n", log_id(m), GetSize(mods));
+	for (auto mod : mods) {
+		Cell *c = m->addCell(mod->name, mod->name);
+		for (auto port : mod->ports) {
+			Wire *w = m->addWire(NEW_ID, GetSize(mod->wire(port)));
+			c->setPort(port, w);
+		}
+	}
+	pmtest_addports(m);
+}
+
+struct TestPmgenPass : public Pass {
+	TestPmgenPass() : Pass("test_pmgen", "test pass for pmgen") { }
+	void help() YS_OVERRIDE
+	{
+		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
+		log("\n");
+		log("    test_pmgen -reduce_chain [options] [selection]\n");
+		log("\n");
+		log("Demo for recursive pmgen patterns. Map chains of AND/OR/XOR to $reduce_*.\n");
+		log("\n");
+
+		log("\n");
+		log("    test_pmgen -reduce_tree [options] [selection]\n");
+		log("\n");
+		log("Demo for recursive pmgen patterns. Map trees of AND/OR/XOR to $reduce_*.\n");
+		log("\n");
+
+		log("\n");
+		log("    test_pmgen -generate [options] <pattern_name>\n");
+		log("\n");
+		log("Create modules that match the specified pattern.\n");
+		log("\n");
+	}
+
+	void execute_reduce_chain(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header(design, "Executing TEST_PMGEN pass (-reduce_chain).\n");
+
+		size_t argidx;
+		for (argidx = 2; argidx < args.size(); argidx++)
+		{
+			// if (args[argidx] == "-singleton") {
+			// 	singleton_mode = true;
+			// 	continue;
+			// }
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		for (auto module : design->selected_modules())
+			while (test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_chain)) {}
+	}
+
+	void execute_reduce_tree(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header(design, "Executing TEST_PMGEN pass (-reduce_tree).\n");
+
+		size_t argidx;
+		for (argidx = 2; argidx < args.size(); argidx++)
+		{
+			// if (args[argidx] == "-singleton") {
+			// 	singleton_mode = true;
+			// 	continue;
+			// }
+			break;
+		}
+		extra_args(args, argidx, design);
+
+		for (auto module : design->selected_modules())
+			test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_tree);
+	}
+
+	void execute_generate(std::vector<std::string> args, RTLIL::Design *design)
+	{
+		log_header(design, "Executing TEST_PMGEN pass (-generate).\n");
+
+		size_t argidx;
+		for (argidx = 2; argidx < args.size(); argidx++)
+		{
+			// if (args[argidx] == "-singleton") {
+			// 	singleton_mode = true;
+			// 	continue;
+			// }
+			break;
+		}
+
+		if (argidx+1 != args.size())
+			log_cmd_error("Expected exactly one pattern.\n");
+
+		string pattern = args[argidx];
+
+		if (pattern == "reduce")
+			return GENERATE_PATTERN(test_pmgen_pm, reduce);
+
+		if (pattern == "ice40_dsp")
+			return GENERATE_PATTERN(ice40_dsp_pm, ice40_dsp);
+
+		if (pattern == "peepopt-muldiv")
+			return GENERATE_PATTERN(peepopt_pm, muldiv);
+
+		if (pattern == "peepopt-shiftmul")
+			return GENERATE_PATTERN(peepopt_pm, shiftmul);
+
+		log_cmd_error("Unkown pattern: %s\n", pattern.c_str());
+	}
+
+	void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
+	{
+		if (GetSize(args) > 1)
+		{
+			if (args[1] == "-reduce_chain")
+				return execute_reduce_chain(args, design);
+			if (args[1] == "-reduce_tree")
+				return execute_reduce_tree(args, design);
+			if (args[1] == "-generate")
+				return execute_generate(args, design);
+		}
+		help();
+		log_cmd_error("Missing or unsupported mode parameter.\n");
+	}
+} TestPmgenPass;
+
+PRIVATE_NAMESPACE_END
diff --git a/passes/pmgen/test_pmgen.pmg b/passes/pmgen/test_pmgen.pmg
new file mode 100644
index 000000000..211477a62
--- /dev/null
+++ b/passes/pmgen/test_pmgen.pmg
@@ -0,0 +1,106 @@
+pattern reduce
+
+state <IdString> portname
+udata <vector<pair<Cell*, IdString>>> chain longest_chain
+udata <pool<Cell*>> non_first_cells
+udata <SigSpec> leaves
+
+code
+	non_first_cells.clear();
+	subpattern(setup);
+endcode
+
+match first
+	select first->type.in($_AND_, $_OR_, $_XOR_)
+	filter !non_first_cells.count(first)
+generate
+	SigSpec A = module->addWire(NEW_ID);
+	SigSpec B = module->addWire(NEW_ID);
+	SigSpec Y = module->addWire(NEW_ID);
+	switch (rng(3))
+	{
+	case 0:
+		module->addAndGate(NEW_ID, A, B, Y);
+		break;
+	case 1:
+		module->addOrGate(NEW_ID, A, B, Y);
+		break;
+	case 2:
+		module->addXorGate(NEW_ID, A, B, Y);
+		break;
+	}
+endmatch
+
+code
+	leaves = SigSpec();
+	longest_chain.clear();
+	chain.push_back(make_pair(first, \A));
+	subpattern(tail);
+	chain.back().second = \B;
+	subpattern(tail);
+finally
+	chain.pop_back();
+	log_assert(chain.empty());
+	if (GetSize(longest_chain) > 1)
+		accept;
+endcode
+
+// ------------------------------------------------------------------
+
+subpattern setup
+
+match first
+	select first->type.in($_AND_, $_OR_, $_XOR_)
+endmatch
+
+code portname
+	portname = \A;
+	branch;
+	portname = \B;
+endcode
+
+match next
+	select nusers(port(next, \Y)) == 2
+	select next->type.in($_AND_, $_OR_, $_XOR_)
+	index <IdString> next->type === first->type
+	index <SigSpec> port(next, \Y) === port(first, portname)
+endmatch
+
+code
+	non_first_cells.insert(next);
+endcode
+
+// ------------------------------------------------------------------
+
+subpattern tail
+arg first
+
+match next
+	semioptional
+	select nusers(port(next, \Y)) == 2
+	select next->type.in($_AND_, $_OR_, $_XOR_)
+	index <IdString> next->type === chain.back().first->type
+	index <SigSpec> port(next, \Y) === port(chain.back().first, chain.back().second)
+generate 10
+	SigSpec A = module->addWire(NEW_ID);
+	SigSpec B = module->addWire(NEW_ID);
+	SigSpec Y = port(chain.back().first, chain.back().second);
+	Cell *c = module->addAndGate(NEW_ID, A, B, Y);
+	c->type = chain.back().first->type;
+endmatch
+
+code
+	if (next) {
+		chain.push_back(make_pair(next, \A));
+		subpattern(tail);
+		chain.back().second = \B;
+		subpattern(tail);
+	} else {
+		if (GetSize(chain) > GetSize(longest_chain))
+			longest_chain = chain;
+		leaves.append(port(chain.back().first, chain.back().second));
+	}
+finally
+	if (next)
+		chain.pop_back();
+endcode
diff --git a/passes/proc/proc_clean.cc b/passes/proc/proc_clean.cc
index 97f4c6573..114c6ab03 100644
--- a/passes/proc/proc_clean.cc
+++ b/passes/proc/proc_clean.cc
@@ -69,8 +69,7 @@ void proc_clean_switch(RTLIL::SwitchRule *sw, RTLIL::CaseRule *parent, bool &did
 		did_something = true;
 		for (auto &action : sw->cases[0]->actions)
 			parent->actions.push_back(action);
-		for (auto sw2 : sw->cases[0]->switches)
-			parent->switches.push_back(sw2);
+		parent->switches.insert(parent->switches.begin(), sw->cases[0]->switches.begin(), sw->cases[0]->switches.end());
 		sw->cases[0]->switches.clear();
 		delete sw->cases[0];
 		sw->cases.clear();
diff --git a/passes/techmap/abc9.cc b/passes/techmap/abc9.cc
index be2a8d50b..576fb8542 100644
--- a/passes/techmap/abc9.cc
+++ b/passes/techmap/abc9.cc
@@ -1116,25 +1116,25 @@ struct Abc9Pass : public Pass {
 				if (w->port_input) {
 					if (w->attributes.count(ID(abc_scc_break)))
 						scc_break_inputs[m->name].insert(p);
-					if (w->attributes.count(ID(abc_carry_in))) {
+					if (w->attributes.count(ID(abc_carry))) {
 						if (carry_in)
-							log_error("Module '%s' contains more than one 'abc_carry_in' port.\n", log_id(m));
+							log_error("Module '%s' contains more than one 'abc_carry' input port.\n", log_id(m));
 						carry_in = w;
 					}
 				}
 				if (w->port_output) {
-					if (w->attributes.count(ID(abc_carry_out))) {
+					if (w->attributes.count(ID(abc_carry))) {
 						if (carry_out)
-							log_error("Module '%s' contains more than one 'abc_carry_out' port.\n", log_id(m));
+							log_error("Module '%s' contains more than one 'abc_carry' input port.\n", log_id(m));
 						carry_out = w;
 					}
 				}
 			}
 			if (carry_in || carry_out) {
 				if (carry_in && !carry_out)
-					log_error("Module '%s' contains an 'abc_carry_in' port but no 'abc_carry_out' port.\n", log_id(m));
+					log_error("Module '%s' contains an 'abc_carry' input port but no output port.\n", log_id(m));
 				if (!carry_in && carry_out)
-					log_error("Module '%s' contains an 'abc_carry_out' port but no 'abc_carry_in' port.\n", log_id(m));
+					log_error("Module '%s' contains an 'abc_carry' output port but no input port.\n", log_id(m));
 				// Make carry_in the last PI, and carry_out the last PO
 				//   since ABC requires it this way
 				auto &ports = m->ports;
diff --git a/techlibs/ecp5/cells_sim.v b/techlibs/ecp5/cells_sim.v
index 864a3550f..2fcb0369e 100644
--- a/techlibs/ecp5/cells_sim.v
+++ b/techlibs/ecp5/cells_sim.v
@@ -17,10 +17,10 @@ endmodule
 // ---------------------------------------
 (* abc_box_id=1, lib_whitebox *)
 module CCU2C(
-	(* abc_carry_in *) input CIN,
+	(* abc_carry *) input CIN,
 	input  A0, B0, C0, D0, A1, B1, C1, D1,
 	output S0, S1,
-	(* abc_carry_out *) output COUT
+	(* abc_carry *) output COUT
 );
 	parameter [15:0] INIT0 = 16'h0000;
 	parameter [15:0] INIT1 = 16'h0000;
diff --git a/techlibs/ice40/cells_sim.v b/techlibs/ice40/cells_sim.v
index 5b18fec27..ab04808f4 100644
--- a/techlibs/ice40/cells_sim.v
+++ b/techlibs/ice40/cells_sim.v
@@ -143,11 +143,11 @@ endmodule
 
 (* abc_box_id = 1, lib_whitebox *)
 module \$__ICE40_FULL_ADDER (
-	(* abc_carry_out *) output CO,
+	(* abc_carry *) output CO,
 	output O,
 	input A,
 	input B,
-	(* abc_carry_in *) input CI
+	(* abc_carry *) input CI
 );
 	SB_CARRY carry (
 		.I0(A),
diff --git a/techlibs/xilinx/cells_sim.v b/techlibs/xilinx/cells_sim.v
index e5d9f480b..dd5a76752 100644
--- a/techlibs/xilinx/cells_sim.v
+++ b/techlibs/xilinx/cells_sim.v
@@ -183,9 +183,9 @@ endmodule
 
 (* abc_box_id = 4, lib_whitebox *)
 module CARRY4(
-  (* abc_carry_out *) output [3:0] CO,
+  (* abc_carry *) output [3:0] CO,
   output [3:0] O,
-  (* abc_carry_in *) input CI,
+  (* abc_carry *) input CI,
   input        CYINIT,
   input  [3:0] DI, S
 );
diff --git a/tests/proc/.gitignore b/tests/proc/.gitignore
new file mode 100644
index 000000000..397b4a762
--- /dev/null
+++ b/tests/proc/.gitignore
@@ -0,0 +1 @@
+*.log
diff --git a/tests/proc/bug_1268.v b/tests/proc/bug_1268.v
new file mode 100644
index 000000000..698ac937a
--- /dev/null
+++ b/tests/proc/bug_1268.v
@@ -0,0 +1,23 @@
+module gold (input clock, ctrl, din, output reg dout);
+	always @(posedge clock) begin
+		if (1'b1) begin
+			if (1'b0) begin end else begin
+				dout <= 0;
+			end
+			if (ctrl)
+				dout <= din;
+		end
+	end
+endmodule
+
+module gate (input clock, ctrl, din, output reg dout);
+	always @(posedge clock) begin
+		if (1'b1) begin
+			if (1'b0) begin end else begin
+				dout <= 0;
+			end
+		end
+		if (ctrl)
+			dout <= din;
+	end
+endmodule
diff --git a/tests/proc/bug_1268.ys b/tests/proc/bug_1268.ys
new file mode 100644
index 000000000..b73e94449
--- /dev/null
+++ b/tests/proc/bug_1268.ys
@@ -0,0 +1,5 @@
+read_verilog bug_1268.v
+proc
+equiv_make gold gate equiv
+equiv_induct
+equiv_status -assert
diff --git a/tests/proc/run-test.sh b/tests/proc/run-test.sh
new file mode 100755
index 000000000..44ce7e674
--- /dev/null
+++ b/tests/proc/run-test.sh
@@ -0,0 +1,6 @@
+#!/bin/bash
+set -e
+for x in *.ys; do
+  echo "Running $x.."
+  ../../yosys -ql ${x%.ys}.log $x
+done
diff --git a/tests/simple/realexpr.v b/tests/simple/realexpr.v
index 5b756e6be..74ed8faa5 100644
--- a/tests/simple/realexpr.v
+++ b/tests/simple/realexpr.v
@@ -1,4 +1,3 @@
-
 module demo_001(y1, y2, y3, y4);
 	output [7:0] y1, y2, y3, y4;
 
@@ -22,3 +21,13 @@ module demo_002(y0, y1, y2, y3);
 	assign y3 = 1 ? -1 : 'd0;
 endmodule
 
+module demo_003(output A, B);
+	parameter real p = 0;
+	assign A = (p==1.0);
+	assign B = (p!="1.000000");
+endmodule
+
+module demo_004(output A, B, C, D);
+	demo_003 #(1.0) demo_real (A, B);
+	demo_003 #(1) demo_int (C, D);
+endmodule
diff --git a/tests/various/pmgen_reduce.ys b/tests/various/pmgen_reduce.ys
new file mode 100644
index 000000000..c214d3f25
--- /dev/null
+++ b/tests/various/pmgen_reduce.ys
@@ -0,0 +1,21 @@
+test_pmgen -generate reduce
+hierarchy -top pmtest_test_pmgen_pm_reduce
+flatten; opt_clean
+
+design -save gold
+test_pmgen -reduce_chain
+design -stash gate
+
+design -copy-from gold -as gold pmtest_test_pmgen_pm_reduce
+design -copy-from gate -as gate pmtest_test_pmgen_pm_reduce
+miter -equiv -flatten -make_assert gold gate miter
+sat -verify -prove-asserts miter
+
+design -load gold
+test_pmgen -reduce_tree
+design -stash gate
+
+design -copy-from gold -as gold pmtest_test_pmgen_pm_reduce
+design -copy-from gate -as gate pmtest_test_pmgen_pm_reduce
+miter -equiv -flatten -make_assert gold gate miter
+sat -verify -prove-asserts miter