Repository: intel/rohd
Pull request #443 (2023-12-08 18:58:17)

Optimize performance of `Combinational.ssa` driver search
<!-- Please make sure you check out the contribution guidelines before submitting a pull request! -->

## Description & Motivation

For sufficiently large and complex designs, a substantial performance penalty was paid for constructing `Combinational.ssa` due to the search algorithm for potential SSA drivers.  The algorithm had to search backwards from inputs to `Conditional`s for potential SSA drivers.  This was especially expensive when using the `Pipeline` abstraction, since that chained multiple `Combinational.ssa`s together.

This PR changes the algorithm to search outwards from SSA drivers to cache signals that are driven by it.  This trades the performance glass jaws:
- originally, if you had much logic defined *before* a `Combinational.ssa`, you could pay a performance penalty proportional to the size of that logic
- now, if you have a substantial amount of unrelated logic connected to an SSA driver (at the time of `Combinational.ssa` construction, you could pay a performance penalty proportional to the size of that logic.

The latter glass jaw should be substantially smaller, less likely, and less frequent.

This PR also adds a benchmark which demonstrates a large performance improvement in a somewhat good example of common use cases.

## Related Issue(s)

N/A

## Testing

Existing tests cover functionality, new benchmark covers performance

## 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/benchmark.dart b/benchmark/benchmark.dart
index 14b04b8e..f4ee2ad8 100644
--- a/benchmark/benchmark.dart
+++ b/benchmark/benchmark.dart
@@ -12,6 +12,7 @@ import 'comb_guard_fanout_benchmark.dart';
 import 'logic_value_of_benchmark.dart';
 import 'many_seq_and_comb_benchmark.dart' as many_seq_and_comb;
 import 'pipeline_benchmark.dart';
+import 'ssa_driver_search_benchmark.dart';
 import 'wave_dump_benchmark.dart';
 
 void main() async {
@@ -21,4 +22,5 @@ void main() async {
   await WaveDumpBenchmark().report();
   await many_seq_and_comb.main();
   await CombGuardFanoutBenchmark().report();
+  SsaDriverSearchBenchmark().report();
 }
diff --git a/benchmark/ssa_driver_search_benchmark.dart b/benchmark/ssa_driver_search_benchmark.dart
new file mode 100644
index 00000000..0b93660c
--- /dev/null
+++ b/benchmark/ssa_driver_search_benchmark.dart
@@ -0,0 +1,72 @@
+// Copyright (C) 2023 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// ssa_driver_search_benchmark.dart
+// Benchmarking for searching for SSA drivers.
+//
+// 2023 December
+// Author: Max Korbel <max.korbel@intel.com>
+
+import 'package:benchmark_harness/benchmark_harness.dart';
+import 'package:rohd/rohd.dart';
+
+class LotsOfLogic extends Module {
+  Logic get c => output('c');
+  LotsOfLogic(Logic a, Logic b, int counter) {
+    a = addInput('a', a);
+    b = addInput('b', b);
+
+    addOutput('c');
+
+    if (counter == 0) {
+      c <= a ^ b;
+    } else {
+      c <=
+          List.generate(
+                  counter, (index) => a ^ b ^ LotsOfLogic(a, b, counter - 1).c)
+              .reduce((x, y) => x ^ y);
+    }
+  }
+}
+
+class LotsOfSsa extends Module {
+  Logic get c => output('c');
+
+  LotsOfSsa(Logic a, Logic b,
+      {int counter = 10, int stages = 100, int signalsCount = 100}) {
+    a = addInput('a', a);
+    b = addInput('b', b);
+
+    addOutput('c');
+
+    final signals = List.generate(signalsCount,
+        (index) => Logic(name: 's$index')..gets(LotsOfLogic(a, b, counter).c));
+
+    ReadyValidPipeline(a, a, b,
+        reset: b,
+        signals: signals,
+        stages: List.generate(
+          stages,
+          (index) => (p) => [
+                for (final signal in signals)
+                  p.get(signal) < p.get(signal) ^ LotsOfLogic(a, b, counter).c,
+              ],
+        ));
+  }
+}
+
+class SsaDriverSearchBenchmark extends BenchmarkBase {
+  SsaDriverSearchBenchmark() : super('SsaDriverSearch');
+
+  static Module _gen() =>
+      LotsOfSsa(Logic(), Logic(), counter: 5, stages: 5, signalsCount: 5);
+
+  @override
+  void run() {
+    _gen();
+  }
+}
+
+void main() async {
+  SsaDriverSearchBenchmark().report();
+}
diff --git a/lib/src/modules/conditional.dart b/lib/src/modules/conditional.dart
index 54bc09be..571bb9ca 100644
--- a/lib/src/modules/conditional.dart
+++ b/lib/src/modules/conditional.dart
@@ -263,15 +263,50 @@ class Combinational extends _Always {
       {String name = 'combinational_ssa'}) {
     final context = _ssaContextCounter++;
 
-    Logic getSsa(Logic ref) => _SsaLogic(ref, context);
+    final ssas = <_SsaLogic>[];
+
+    Logic getSsa(Logic ref) {
+      final newSsa = _SsaLogic(ref, context);
+      ssas.add(newSsa);
+      return newSsa;
+    }
 
     final conditionals = construct(getSsa);
 
+    ssas.forEach(_updateSsaDriverMap);
+
     _processSsa(conditionals, context: context);
 
+    // no need to keep any of this old info around anymore
+    _signalToSsaDrivers.clear();
+
     return Combinational(conditionals, name: name);
   }
 
+  /// A map from [_SsaLogic]s to signals that they drive.
+  ///
+  /// This only stores information temporarily during construction of a
+  /// [Combinational.ssa] and clears afterwards.
+  static final Map<Logic, Set<_SsaLogic>> _signalToSsaDrivers = {};
+
+  /// Tags each downstream [Logic] from [ssaDriver] as such in
+  /// [_signalToSsaDrivers].
+  static void _updateSsaDriverMap(_SsaLogic ssaDriver) {
+    final toParse = TraverseableCollection<Logic>()
+      ..addAll(ssaDriver.dstConnections);
+    for (var i = 0; i < toParse.length; i++) {
+      final tpi = toParse[i];
+
+      _signalToSsaDrivers.putIfAbsent(tpi, () => <_SsaLogic>{}).add(ssaDriver);
+
+      if (tpi.isInput && tpi.parentModule! is CustomSystemVerilog) {
+        toParse.addAll(tpi.parentModule!.outputs.values);
+      } else {
+        toParse.addAll(tpi.dstConnections);
+      }
+    }
+  }
+
   /// Executes the remapping for all the [conditionals] recursively.
   static void _processSsa(List<Conditional> conditionals,
       {required int context}) {
@@ -749,23 +784,12 @@ abstract class Conditional {
 
   /// Searches for SSA nodes from a source [driver] which match the [context].
   static List<_SsaLogic> _findSsaDriversFrom(Logic driver, int context) {
-    final toParse = TraverseableCollection<Logic>()..add(driver);
-    final foundSsaLogics = <_SsaLogic>{};
-    for (var i = 0; i < toParse.length; i++) {
-      if (toParse[i].srcConnection != null) {
-        toParse.add(toParse[i].srcConnection!);
-      }
-      if (toParse[i].isOutput) {
-        // ignore: invalid_use_of_protected_member
-        toParse.addAll(toParse[i].parentModule!.inputs.values);
-      }
-      if (toParse[i] is _SsaLogic &&
-          (toParse[i] as _SsaLogic)._context == context) {
-        foundSsaLogics.add(toParse[i] as _SsaLogic);
-      }
+    if (driver is _SsaLogic && driver._context == context) {
+      return [driver];
     }
 
-    return foundSsaLogics.toList(growable: false);
+    // no need to check for context on this map since it clears each time
+    return Combinational._signalToSsaDrivers[driver]?.toList() ?? const [];
   }
 
   /// Given existing [currentMappings], connects [drivers] and [receivers]
diff --git a/lib/src/signals/logic.dart b/lib/src/signals/logic.dart
index 6d852182..737fe0c6 100644
--- a/lib/src/signals/logic.dart
+++ b/lib/src/signals/logic.dart
@@ -183,13 +183,17 @@ class Logic {
   ///
   /// Note: [parentModule] is not populated until after its parent [Module],
   /// if it exists, has been built. If no parent [Module] exists, returns false.
-  bool get isInput => parentModule?.isInput(this) ?? false;
+  late final bool isInput =
+      // this can be cached because parentModule is set at port creation
+      parentModule?.isInput(this) ?? false;
 
   /// Returns true iff this signal is an output of its parent [Module].
   ///
   /// Note: [parentModule] is not populated until after its parent [Module],
   /// if it exists, has been built. If no parent [Module] exists, returns false.
-  bool get isOutput => parentModule?.isOutput(this) ?? false;
+  late final bool isOutput =
+      // this can be cached because parentModule is set at port creation
+      parentModule?.isOutput(this) ?? false;
 
   /// Returns true iff this signal is an input or output of its parent [Module].
   ///


Test patch:
diff --git a/test/benchmark_test.dart b/test/benchmark_test.dart
index aea7d9af..663d7d4a 100644
--- a/test/benchmark_test.dart
+++ b/test/benchmark_test.dart
@@ -14,34 +14,41 @@ import '../benchmark/comb_guard_fanout_benchmark.dart';
 import '../benchmark/logic_value_of_benchmark.dart';
 import '../benchmark/many_seq_and_comb_benchmark.dart';
 import '../benchmark/pipeline_benchmark.dart';
+import '../benchmark/ssa_driver_search_benchmark.dart';
 import '../benchmark/wave_dump_benchmark.dart';
 
 void main() {
-  test('pipeline benchmark', () async {
-    await PipelineBenchmark().measure();
-  });
-
-  test('logic value of benchmark', () {
-    LogicValueOfBenchmark().measure();
-  });
-
-  test('byte enable benchmark', () {
-    ByteEnableBenchmark().measure();
-  });
-
-  test('waveform benchmark', () async {
-    await WaveDumpBenchmark().measure();
-  });
-
-  group('many seq and comb benchmark', () {
-    for (final connectionType in ManySeqAndCombCombConnectionType.values) {
-      test(connectionType.name, () async {
-        await ManySeqAndCombBenchmark(connectionType).measure();
-      });
-    }
-  });
-
-  test('comb guard fanout benchmark', () async {
-    await CombGuardFanoutBenchmark().measure();
+  group('benchmark', () {
+    test('pipeline', () async {
+      await PipelineBenchmark().measure();
+    });
+
+    test('logic value of', () {
+      LogicValueOfBenchmark().measure();
+    });
+
+    test('byte enable', () {
+      ByteEnableBenchmark().measure();
+    });
+
+    test('waveform', () async {
+      await WaveDumpBenchmark().measure();
+    });
+
+    group('many seq and comb', () {
+      for (final connectionType in ManySeqAndCombCombConnectionType.values) {
+        test(connectionType.name, () async {
+          await ManySeqAndCombBenchmark(connectionType).measure();
+        });
+      }
+    });
+
+    test('comb guard fanout', () async {
+      await CombGuardFanoutBenchmark().measure();
+    });
+
+    test('ssa driver search', () {
+      SsaDriverSearchBenchmark().measure();
+    });
   });
 }
diff --git a/test/ssa_test.dart b/test/ssa_test.dart
index abdebf49..c0dc68de 100644
--- a/test/ssa_test.dart
+++ b/test/ssa_test.dart
@@ -219,11 +219,15 @@ class SsaNested extends SsaTestModule {
     final x = addOutput('x', width: 8);
     Combinational.ssa((s) => [
           s(x) < SsaModAssignsOnly(a).x + 1,
+          s(x) < SsaModAssignsOnly(s(x)).x + 1,
         ]);
   }
 
   @override
-  int model(int a) => SsaModAssignsOnly(Logic(width: 8)).model(a) + 1;
+  int model(int a) =>
+      SsaModAssignsOnly(Logic(width: 8))
+          .model(SsaModAssignsOnly(Logic(width: 8)).model(a) + 1) +
+      1;
 }
 
 class SsaMultiDep extends SsaTestModule {