Add pmgen finish statement, return number of matches

Signed-off-by: Clifford Wolf <clifford@clifford.at>

4 files changed, 116 insertions, 82 deletions

diff --git a/passes/pmgen/README.md b/passes/pmgen/README.md
index f92445a86..be908ef0b 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`, `branch`, and
-  `subpattern` 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.
@@ -246,13 +246,13 @@ debug messages. For example:
 
     code
         stack.push_back(addAB);
-	...
+        ...
     finally
         stack.pop_back();
     endcode
 
-`accept` statements can be used inside the `finally` section, but not
-`reject`, `branch`, or `subpattern`.
+`accept` and `finish` statements can be used inside the `finally` section,
+but not `reject`, `branch`, or `subpattern`.
 
 Declaring a subpattern
 ----------------------
@@ -265,52 +265,75 @@ 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
-	...
+    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.
+
+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/pmgen.py b/passes/pmgen/pmgen.py
index 95fcd2540..6950a99c0 100644
--- a/passes/pmgen/pmgen.py
+++ b/passes/pmgen/pmgen.py
@@ -328,6 +328,7 @@ with open(outfile, "w") as f:
     print("  SigMap sigmap;", 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)
@@ -476,7 +477,8 @@ 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)
@@ -487,14 +489,15 @@ with open(outfile, "w") as f:
                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
         print("    block_{}(1);".format(patterns[current_pattern]), file=f)
         print("    log_assert(rollback_stack.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_{}() {{".format(current_pattern), file=f)
-        print("    run_{}([](){{}});".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)
 
@@ -574,7 +577,8 @@ with open(outfile, "w") as f:
         if block["type"] == "code":
             print("", file=f)
             print("#define reject do { check_blacklist(); goto rollback_label; } while(0)", file=f)
-            print("#define accept do { on_accept(); check_blacklist(); if (rollback) goto rollback_label; } while(0)", file=f)
+            print("#define accept do { accept_cnt++; on_accept(); check_blacklist(); if (rollback) goto rollback_label; } while(0)", file=f)
+            print("#define finish do { rollback = -1; rollback_stack.clean(); 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)
 
@@ -586,6 +590,7 @@ with open(outfile, "w") as f:
 
             print("#undef reject", file=f)
             print("#undef accept", file=f)
+            print("#undef finish", file=f)
             print("#undef branch", file=f)
             print("#undef subpattern", file=f)
 
@@ -594,10 +599,12 @@ with open(outfile, "w") as f:
             print("    YS_ATTRIBUTE(unused);", file=f)
 
             if len(block["fcode"]):
-                print("#define accept do { on_accept(); check_blacklist(); } while(0)", file=f)
+                print("#define accept do { accept_cnt++; on_accept(); check_blacklist(); } while(0)", file=f)
+                print("#define finish do { rollback = -1; rollback_stack.clean(); return; } while(0)", file=f)
                 for line in block["fcode"]:
                     print("  " + line, file=f)
                 print("#undef accept", file=f)
+                print("#undef finish", file=f)
 
             if len(restore_st) or len(nonconst_st):
                 print("", file=f)
@@ -631,29 +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("        if (!({})) continue;".format(expr), file=f)
             if block["semioptional"] or block["genargs"] is not None:
-                print("      found_any_match = true;", file=f)
-            print("      rollback_stack.push_back(make_pair(cells[idx], recursion));", file=f)
-            print("      block_{}(recursion+1);".format(index+1), file=f)
-            print("      if (rollback == 0) {", file=f)
-            print("        rollback_stack.pop_back();", file=f)
-            print("      } else {", 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("        found_any_match = true;", file=f)
+            print("        rollback_stack.push_back(make_pair(cells[idx], recursion));", file=f)
+            print("        block_{}(recursion+1);".format(index+1), file=f)
+            print("        if (rollback == 0) {", file=f)
+            print("          rollback_stack.pop_back();", file=f)
+            print("        } else {", 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)
 
@@ -669,14 +679,14 @@ with open(outfile, "w") as f:
             print("    {} = backup_{};".format(block["cell"], block["cell"]), file=f)
 
             if block["genargs"] is not None:
+                print("#define finish do { rollback = -1; rollback_stack.clean(); 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("      rollback_stack.clear();", file=f)
-                print("      rollback = -1;", 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
index 053dbe021..d787d49be 100644
--- a/passes/pmgen/test_pmgen.cc
+++ b/passes/pmgen/test_pmgen.cc
@@ -235,7 +235,7 @@ struct TestPmgenPass : public Pass {
 		extra_args(args, argidx, design);
 
 		for (auto module : design->selected_modules())
-			test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_chain);
+			while (test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_chain)) {}
 	}
 
 	void execute_reduce_tree(std::vector<std::string> args, RTLIL::Design *design)
diff --git a/passes/pmgen/test_pmgen.pmg b/passes/pmgen/test_pmgen.pmg
index 077d337d6..211477a62 100644
--- a/passes/pmgen/test_pmgen.pmg
+++ b/passes/pmgen/test_pmgen.pmg
@@ -41,7 +41,8 @@ code
 finally
 	chain.pop_back();
 	log_assert(chain.empty());
-	accept;
+	if (GetSize(longest_chain) > 1)
+		accept;
 endcode
 
 // ------------------------------------------------------------------
@@ -80,7 +81,7 @@ match next
 	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 50
+generate 10
 	SigSpec A = module->addWire(NEW_ID);
 	SigSpec B = module->addWire(NEW_ID);
 	SigSpec Y = port(chain.back().first, chain.back().second);