Repository: intel/rohd (dart)

Issue:
Optimize `Combinational._execute` X-driving
## Motivation
The `_execute` function in `Combinational` currently drives all outputs to `x`, then executes the conditionals.  This is less efficient than it could be, since `Conditional.execute` returns a list of signals driven.

## Desired solution
Only drive signals to `x` if they are not driven by any other sub-`Conditional` as determined by the `Conditional.execute` function.

Pull request description:
<!-- Please make sure you check out the contribution guidelines before submitting a pull request! -->

## Description & Motivation

Improve the performance of `Combinational`'s `_execute` function so that it doesn't glitch extra `x`'s throughout the design unnecessarily.  For some designs this can provide a very meaningful performance boost to simulation speed.

## Related Issue(s)

Fix #106 

## Testing

Existing tests cover this.

Added new benchmarking code that covers a little bit of combinational logic via a pipeline example.

## Backwards-compatibility

> Is this a breaking change that will not be backwards-compatible?  If yes, how so?

No

## Documentation

> Does the change require any updates to documentation?  If so, where?  Are they included?

No

Patch:
diff --git a/benchmark/BENCHMARKING.md b/benchmark/BENCHMARKING.md
new file mode 100644
index 000000000..ca646cd3f
--- /dev/null
+++ b/benchmark/BENCHMARKING.md
@@ -0,0 +1,19 @@
+Benchmarking in ROHD
+====================
+
+This folder contains some benchmarking related code for estimating relative performance of certain ROHD features.  It can be used to help judge the relative performance impact with and without a change in ROHD.  Benchmarks can be microbenchmarks for a specific feature, larger benchmarks for estimating performance on more realistic designs, or comparison benchmarks for similar applications relative to other frameworks and simulators.
+
+To run all benchmarks, execute the below command:
+```
+dart run benchmark/benchmark.dart
+```
+You can run this command (or specific benchmarks) before and after a change to get a feel if any performance covered by these benchmarks has been impacted.
+
+
+----------------
+2022 September 28  
+Author: Max Korbel <<max.korbel@intel.com>>
+
+ 
+Copyright (C) 2022 Intel Corporation  
+SPDX-License-Identifier: BSD-3-Clause
diff --git a/benchmark/benchmark.dart b/benchmark/benchmark.dart
new file mode 100644
index 000000000..add1d3ed6
--- /dev/null
+++ b/benchmark/benchmark.dart
@@ -0,0 +1,15 @@
+/// Copyright (C) 2022 Intel Corporation
+/// SPDX-License-Identifier: BSD-3-Clause
+///
+/// benchmark.dart
+/// Runs benchmarks and prints values.
+///
+/// 2022 September 28
+/// Author: Max Korbel <max.korbel@intel.com>
+///
+
+import 'pipeline_benchmark.dart';
+
+void main() async {
+  await PipelineBenchmark().report();
+}
diff --git a/benchmark/benchmarks.dart b/benchmark/benchmarks.dart
new file mode 100644
index 000000000..13de7e7aa
--- /dev/null
+++ b/benchmark/benchmarks.dart
@@ -0,0 +1,4 @@
+/// Copyright (C) 2022 Intel Corporation
+/// SPDX-License-Identifier: BSD-3-Clause
+
+export 'pipeline_benchmark.dart';
diff --git a/benchmark/pipeline_benchmark.dart b/benchmark/pipeline_benchmark.dart
new file mode 100644
index 000000000..aafdc4a86
--- /dev/null
+++ b/benchmark/pipeline_benchmark.dart
@@ -0,0 +1,69 @@
+/// Copyright (C) 2022 Intel Corporation
+/// SPDX-License-Identifier: BSD-3-Clause
+///
+/// pipeline_benchmark.dart
+/// Benchmarking for pipeline simulation performance
+///
+/// 2022 September 28
+/// Author: Max Korbel <max.korbel@intel.com>
+///
+
+import 'package:benchmark_harness/benchmark_harness.dart';
+import 'package:rohd/rohd.dart';
+import 'package:rohd/src/utilities/simcompare.dart';
+import '../test/pipeline_test.dart';
+
+class PipelineBenchmark extends AsyncBenchmarkBase {
+  late RVPipelineModule _rvPipelineModule;
+
+  PipelineBenchmark() : super('Pipeline');
+
+  @override
+  Future<void> setup() async {
+    _rvPipelineModule =
+        RVPipelineModule(Logic(width: 8), Logic(), Logic(), Logic());
+    await _rvPipelineModule.build();
+  }
+
+  @override
+  Future<void> teardown() async {
+    await Simulator.reset();
+  }
+
+  @override
+  Future<void> run() async {
+    // ideally there would be more vectors in here... just copy paste from test for now
+    var vectors = [
+      Vector({'reset': 1, 'a': 1, 'validIn': 0, 'readyForOut': 1}, {}),
+      Vector({'reset': 1, 'a': 1, 'validIn': 0, 'readyForOut': 1}, {}),
+      Vector({'reset': 1, 'a': 1, 'validIn': 0, 'readyForOut': 1}, {}),
+      Vector({'reset': 0, 'a': 1, 'validIn': 1, 'readyForOut': 1},
+          {'validOut': 0}),
+      Vector({'reset': 0, 'a': 2, 'validIn': 1, 'readyForOut': 1},
+          {'validOut': 0}),
+      Vector({'reset': 0, 'a': 3, 'validIn': 1, 'readyForOut': 1},
+          {'validOut': 0}),
+      Vector({'reset': 0, 'a': 4, 'validIn': 1, 'readyForOut': 1},
+          {'validOut': 1, 'b': 4}),
+      Vector({'reset': 0, 'a': 0, 'validIn': 0, 'readyForOut': 1},
+          {'validOut': 1, 'b': 5}),
+      Vector({'reset': 0, 'a': 0, 'validIn': 0, 'readyForOut': 1},
+          {'validOut': 1, 'b': 6}),
+      Vector({'reset': 0, 'a': 0, 'validIn': 0, 'readyForOut': 1},
+          {'validOut': 1, 'b': 7}),
+      Vector({'reset': 0, 'a': 0, 'validIn': 0, 'readyForOut': 1},
+          {'validOut': 0}),
+      Vector({'reset': 0, 'a': 0, 'validIn': 0, 'readyForOut': 1},
+          {'validOut': 0}),
+    ];
+    await SimCompare.checkFunctionalVector(_rvPipelineModule, vectors,
+        enableChecking: false);
+
+    // sucks but this appears to be necessary since it runs 10x with this package
+    await Simulator.reset();
+  }
+}
+
+Future<void> main() async {
+  await PipelineBenchmark().report();
+}
diff --git a/lib/src/modules/conditional.dart b/lib/src/modules/conditional.dart
index 914ff7cc1..d2a0ebc5d 100644
--- a/lib/src/modules/conditional.dart
+++ b/lib/src/modules/conditional.dart
@@ -205,13 +205,18 @@ class Combinational extends _Always {
 
     _isExecuting = true;
 
-    // combinational must always drive all outputs or else you get X!
-    for (var element in _assignedReceiverToOutputMap.values) {
-      element.put(LogicValue.x, fill: true);
+    var drivenLogics = <Logic>{};
+    for (var element in conditionals) {
+      drivenLogics.addAll(element.execute());
     }
 
-    for (var element in conditionals) {
-      element.execute();
+    // combinational must always drive all outputs or else you get X!
+    if (_assignedReceiverToOutputMap.length != drivenLogics.length) {
+      for (var receiverOutputPair in _assignedReceiverToOutputMap.entries) {
+        if (!drivenLogics.contains(receiverOutputPair.key)) {
+          receiverOutputPair.value.put(LogicValue.x, fill: true);
+        }
+      }
     }
 
     _isExecuting = false;
@@ -441,7 +446,7 @@ abstract class Conditional {
   ///
   /// Returns a [List] of all [Logic] signals which were driven during execution.
   @protected
-  List<Logic> execute();
+  Set<Logic> execute();
 
   /// Lists *all* receivers, recursively including all sub-[Conditional]s receivers.
   List<Logic> getReceivers();
@@ -491,9 +496,9 @@ class ConditionalAssign extends Conditional {
   List<Conditional> getConditionals() => [];
 
   @override
-  List<Logic> execute() {
+  Set<Logic> execute() {
     receiverOutput(receiver).put(driverValue(driver));
-    return [receiver];
+    return {receiver};
   }
 
   @override
@@ -569,15 +574,15 @@ class Case extends Conditional {
   String get caseType => 'case';
 
   @override
-  List<Logic> execute() {
-    var drivenLogics = <Logic>[];
+  Set<Logic> execute() {
+    var drivenLogics = <Logic>{};
 
     if (!expression.value.isValid) {
       // if expression has X or Z, then propogate X's!
       for (var receiver in getReceivers()) {
         receiverOutput(receiver).put(LogicValue.x);
       }
-      return [];
+      return {};
     }
 
     CaseItem? foundMatch;
@@ -775,8 +780,8 @@ class IfBlock extends Conditional {
   IfBlock(this.iffs);
 
   @override
-  List<Logic> execute() {
-    var drivenLogics = <Logic>[];
+  Set<Logic> execute() {
+    var drivenLogics = <Logic>{};
 
     for (var iff in iffs) {
       if (driverValue(iff.condition)[0] == LogicValue.one) {
@@ -901,8 +906,8 @@ class If extends Conditional {
   List<Conditional> getConditionals() => [...then, ...orElse];
 
   @override
-  List<Logic> execute() {
-    var drivenLogics = <Logic>[];
+  Set<Logic> execute() {
+    var drivenLogics = <Logic>{};
     if (driverValue(condition)[0] == LogicValue.one) {
       for (var conditional in then) {
         drivenLogics.addAll(conditional.execute());
diff --git a/lib/src/utilities/simcompare.dart b/lib/src/utilities/simcompare.dart
index 8d5b1fe23..906878913 100644
--- a/lib/src/utilities/simcompare.dart
+++ b/lib/src/utilities/simcompare.dart
@@ -62,8 +62,13 @@ class Vector {
 }
 
 class SimCompare {
-  static Future<void> checkFunctionalVector(
-      Module module, List<Vector> vectors) async {
+  /// Runs a ROHD simulation where each of the [vectors] is executed per clock cycle
+  /// sequentially.
+  ///
+  /// If [enableChecking] is set to false, then it will drive the simulation but not
+  /// check that the outputs match.
+  static Future<void> checkFunctionalVector(Module module, List<Vector> vectors,
+      {bool enableChecking = true}) async {
     var timestamp = 1;
     for (var vector in vectors) {
       // print('Running vector: $vector');
@@ -73,33 +78,35 @@ class SimCompare {
           module.input(signalName).put(value);
         }
 
-        Simulator.postTick.first.then((value) {
-          for (var signalName in vector.expectedOutputValues.keys) {
-            var value = vector.expectedOutputValues[signalName];
-            var o = module.output(signalName);
-            var errorReason =
-                'For vector #${vectors.indexOf(vector)} $vector, expected $o to be $value, but it was ${o.value}.';
-            if (value is int) {
-              if (!o.value.isValid) {
-                // invalid value causes exception without helpful message, so throw it
-                throw Exception(errorReason);
-              }
-              expect(o.value.toInt(), equals(value), reason: errorReason);
-            } else if (value is LogicValue) {
-              if (o.width > 1 &&
-                  (value == LogicValue.x || value == LogicValue.z)) {
-                for (var oBit in o.value.toList()) {
-                  expect(oBit, equals(value), reason: errorReason);
+        if (enableChecking) {
+          Simulator.postTick.first.then((value) {
+            for (var signalName in vector.expectedOutputValues.keys) {
+              var value = vector.expectedOutputValues[signalName];
+              var o = module.output(signalName);
+              var errorReason =
+                  'For vector #${vectors.indexOf(vector)} $vector, expected $o to be $value, but it was ${o.value}.';
+              if (value is int) {
+                if (!o.value.isValid) {
+                  // invalid value causes exception without helpful message, so throw it
+                  throw Exception(errorReason);
+                }
+                expect(o.value.toInt(), equals(value), reason: errorReason);
+              } else if (value is LogicValue) {
+                if (o.width > 1 &&
+                    (value == LogicValue.x || value == LogicValue.z)) {
+                  for (var oBit in o.value.toList()) {
+                    expect(oBit, equals(value), reason: errorReason);
+                  }
+                } else {
+                  expect(o.value, equals(value));
                 }
               } else {
-                expect(o.value, equals(value));
+                throw Exception(
+                    'Value type ${value.runtimeType} is not supported (yet?)');
               }
-            } else {
-              throw Exception(
-                  'Value type ${value.runtimeType} is not supported (yet?)');
             }
-          }
-        });
+          });
+        }
       });
       timestamp += Vector.period;
     }
diff --git a/pubspec.yaml b/pubspec.yaml
index bf00b2e7b..0499c9383 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -16,4 +16,5 @@ dependencies:
   test: ^1.17.3
 
 dev_dependencies:
-  lints: ^1.0.1
\ No newline at end of file
+  lints: ^1.0.1
+  benchmark_harness: ^2.2.0
\ No newline at end of file


Test patch:
diff --git a/test/benchmark_test.dart b/test/benchmark_test.dart
new file mode 100644
index 000000000..3dc915536
--- /dev/null
+++ b/test/benchmark_test.dart
@@ -0,0 +1,18 @@
+/// Copyright (C) 2022 Intel Corporation
+/// SPDX-License-Identifier: BSD-3-Clause
+///
+/// benchmark_test.dart
+/// Tests that run benchmarks to make sure they don't break.
+///
+/// 2022 September 28
+/// Author: Max Korbel <max.korbel@intel.com>
+///
+
+import 'package:test/test.dart';
+import '../benchmark/benchmarks.dart';
+
+void main() {
+  test('pipeline benchmark', () {
+    PipelineBenchmark().measure();
+  });
+}