Combinational loops can cause stack overflow in SystemVerilog synthesizer stack

[mkorbel1]

Describe the bug

It is possible for a design that contains combinational loops to cause infinite recursion in the SystemVerilog synthesis stack in some cases.

Thank you to @RossComputerGuy for finding and reporting the issue. He provided some details on Discord (https://discord.com/channels/1001179329411166267/1001179329411166270/1446989110169436313) including a trace and some code in a gist (https://gist.github.com/RossComputerGuy/d371fab7c722dc94e90d1fa2e7f04ea7).

For reference from the gist:

Details

decoder.dart

import 'dart:async';

import 'package:rohd/rohd.dart';
import 'package:riscv/riscv.dart';
import 'package:river/river.dart';
import 'package:river_hdl/river_hdl.dart';
import 'package:test/test.dart';

void main() {
  tearDown(() async {
    await Simulator.reset();
  });

  test('Decode', () async {
    final clk = SimpleClockGenerator(10).clk;
    final microcode = Microcode(Microcode.buildDecodeMap([rv32i]));

    final input = Logic(width: 32);
    input <= Const(0x002081B3, width: 32);

    final decoder = InstructionDecoder(
      clk,
      input,
      microcode: microcode,
      mxlen: Mxlen.mxlen_32,
    );

    await decoder.build();

    print(decoder.generateSynth());

    Simulator.setMaxSimTime(1000);

    unawaited(Simulator.run());

    for (var i = 0; i < 10; i++) {
      await clk.nextPosedge;
    }

    await Simulator.simulationEnded;
    print(decoder.valid.value);
    print(
      Map.fromEntries(
        decoder.fields.entries.map(
          (entry) => MapEntry(entry.key, entry.value.value),
        ),
      ),
    );

    /*expect(r.opcode, equals(0x33));
      expect(r.rd, equals(3));
      expect(r.rs1, equals(1));
      expect(r.rs2, equals(2));
      expect(r.funct3, equals(0x0));
      expect(r.funct7, equals(0x00));*/
  });
}

decoder_test.dart

import 'package:rohd/rohd.dart';
import 'package:riscv/riscv.dart';

class InstructionDecoder extends Module {
  final Mxlen mxlen;
  final Microcode microcode;

  Logic get valid => output('valid');
  Map<String, Logic> get fields => Map.fromEntries(
    fieldWidths.entries.map(
      (entry) => MapEntry(entry.key, output(computeName(entry.key))),
    ),
  );

  InstructionDecoder(
    Logic clk,
    Logic input, {
    required this.microcode,
    required this.mxlen,
    super.name = 'river_instruction_decoder',
  }) {
    clk = addInput('clk', clk);
    input = addInput('instr', input, width: mxlen.size);

    addOutput('valid');

    for (final entry in fieldWidths.entries) {
      addOutput(computeName(entry.key), width: entry.value);
    }

    final decodeMap = lookupDecode(input);

    Combinational([
      If.block([
        ...decodeMap.entries
            .map(
              (entry) => Iff(entry.value, [
                valid < 1,
                ...fields.entries.map((entry) => entry.value < 0).toList(),
                ...microcode.map[entry.key]!.struct.mapping.entries.map((
                  entry,
                ) {
                  final fieldName = entry.key;
                  final fieldOutput = fields[fieldName]!;
                  final range = entry.value;
                  final value = input
                      .slice(range.end, range.start)
                      .zeroExtend(fieldOutput.width)
                      .named(fieldName);
                  return fieldOutput < value;
                }).toList(),
              ]),
            )
            .toList(),
        Else([
          valid < 0,
          ...fields.entries.map((entry) => entry.value < 0).toList(),
        ]),
      ]),
    ]);
  }

  String computeName(String input) {
    return input.replaceAll('[', '_').replaceAll(']', '').replaceAll(':', '_');
  }

  Map<String, int> get fieldWidths {
    final widths = <String, int>{};
    for (final entry in microcode.fields.entries) {
      final fieldName = entry.key;
      final patternMap = entry.value;

      int maxWidth = 0;
      for (final range in patternMap.values) {
        if (range.width > maxWidth) maxWidth = range.width;
      }

      widths[fieldName] = maxWidth;
    }
    return widths;
  }

  Map<OperationDecodePattern, Logic> lookupDecode(Logic input) =>
      Map.fromEntries(
        microcode.map.entries.map((entry) {
          var temp = Logic(width: mxlen.size);

          temp <=
              temp |
                  Const(
                    entry.key.nonZeroFields.keys
                        .map(
                          (fieldName) =>
                              entry.value.struct.mapping[fieldName]!.encode(1),
                        )
                        .fold(0, (a, b) => a | b),
                    width: mxlen.size,
                  );

          return MapEntry(
            entry.key,
            (temp & Const(entry.key.mask, width: mxlen.size)).eq(
              Const(entry.key.value, width: mxlen.size),
            ),
          );
        }),
      );
}

Stack trace

00:01 +0 -1: Decode [E]
  Stack Overflow
  dart:collection                                                                                      new LinkedHashMap.of
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:33  SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
  dart:collection                                                                                      MapBase.map
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 36:18  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 48:7   SystemVerilogSynthSubModuleInstantiation.inlineVerilog
  package:rohd/src/synthesizers/systemverilog/systemverilog_synth_sub_module_instantiation.dart 39:21  SystemVerilogSynthSubModuleInstantiation._modulePortsMapWithInline.<fn>
    dart:collection                                                                                      MapBase.map
  .                                                                                                    ...
  .                                                                                                    ...
  package:rohd/src/synthesizers/systemverilog/systemverilog_synthesis_result.dart 195:9                SystemVerilogSynthesisResult._verilogModuleContents
  package:rohd/src/synthesizers/systemverilog/systemverilog_synthesis_result.dart 81:29                new SystemVerilogSynthesisResult
  package:rohd/src/synthesizers/systemverilog/systemverilog_synthesizer.dart 150:11                    SystemVerilogSynthesizer.synthesize
  package:rohd/src/synthesizers/synth_builder.dart 104:44                                              SynthBuilder._getInstanceType
  dart:core                                                                                            Iterable.forEach
  package:rohd/src/synthesizers/synth_builder.dart 72:10                                               new SynthBuilder.multi
  package:rohd/src/synthesizers/synth_builder.dart 47:14                                               new SynthBuilder
  package:rohd/src/module.dart 1128:9                                                                  Module.generateSynth
  test/core/decoder_test.dart 30:19                                                                    main.<fn>

To Reproduce

It looks like this is related to inlining recursively

Expected behavior

No response

Actual behavior

No response

Additional: Dart SDK info

No response

Additional: pubspec.yaml

Additional: Context

Found in ROHD v0.6.6