[MooreToCore] Unexpected topological cycle after importing generated verilog

[leothaud]

Hello, I'm having an issue when trying to import Verilog generated with Yosys. It leads into a combinatorial cycle that isn't present in the Verilog program.
Here is a simple example of problematic Verilog:

module outline_control_3(output [1:0] result, input arg0);
  assign result[1] = arg0;
  assign result[0] = result[1];
endmodule

When I import the Verilog into Moore with ./circt-translate --import-verilog test.sv it generates the following program:

module {
  moore.module @outline_control_3(out result : !moore.l2, in %arg0 : !moore.l1) {
    %result = moore.net wire : <l2>
    %arg0_0 = moore.net name "arg0" wire : <l1>
    %0 = moore.extract_ref %result from 1 : <l2> -> <l1>
    %1 = moore.read %arg0_0 : <l1>
    moore.assign %0, %1 : l1
    %2 = moore.extract_ref %result from 0 : <l2> -> <l1>
    %3 = moore.read %result : <l2>
    %4 = moore.extract %3 from 1 : l2 -> l1
    moore.assign %2, %4 : l1
    %5 = moore.read %result : <l2>
    moore.assign %arg0_0, %arg0 : l1
    moore.output %5 : !moore.l2
  }
}

But then, when I lower it into the comb/HW dialects with ./circt-translate --import-verilog test.sv | ./circt-opt --moore-lower-concatref --canonicalize --cse --convert-moore-to-core --llhd-sig2reg --canonicalize --cse. It generates the following program:

module {
  hw.module @outline_control_3(out result : i2, in %arg0 : i1) {
    %false = hw.constant false
    %0 = comb.concat %false, %3 : i1, i1
    %1 = comb.concat %arg0, %false : i1, i1
    %2 = comb.or %1, %0 : i2
    %3 = comb.extract %2 from 1 : (i2) -> i1
    hw.output %2 : i2
  }
}

My problem here is that %3 depends on %2, which in turn depends on %0, which also depends on %3. As the hw.module contains a graph region, it doesn't seem to be an invalid MLIR program. But is it the expected behavior? There is a combinatorial cycle that wasn't present in the imported Verilog.

[uenoku]

I think this is an artifact of dynamic comb injection.

circt/lib/Dialect/Comb/CombOps.cpp

Line 152 in 187f4e8

Value comb::createDynamicInject(OpBuilder &builder, Location loc, Value value,

I would be also much happier if this doesn't have SSA cycle as it makes it fairly challenging to analyze the design (in fact circt-synth fails when encountering SSA cycle).

One possible direction would be introducing comb level injection operator and expect canonicalization to clean up injection operator (which is similar to what array injection is doing).

[leothaud]

I'm not familiar enough with MLIR or CIRCT to know what "comb level injection operator" is. However, I believe the problematic pattern will always be similar: an or of concats, where each value is always' or'd with a constant false. A simple approach I could help with would be to match this pattern and simplify it as a concat, and then apply this pattern after lowering Moore to Core. Do you think this would be a suitable approach?

[fabianschuiki]

This is a great find! 🥳 These injection operations produced by assigning vectors, arrays, or structs field-by-field have been very annoying to optimize. We do have a few canonicalizers in the Comb dialect that look through AND/OR ops and concats and try to see if they cover mutually exclusive ranges of the final value. I remember adding something like this for AND, but we might be missing this for OR.:

%0 = comb.concat %false, %3 : i1, i1
%1 = comb.concat %arg0, %false : i1, i1
%2 = comb.or %1, %0 : i2
// canonicalized to
%2 = comb.concat %arg0, %3 : i1, i1

The AND operation does a similar thing to try and find regions that are guaranteed to be zero, and tries to lop them off. The OR op could do something similar and try to identify bit ranges that are known to be zero in all except for one of the operands, and then turn that into a concat.

[uenoku]

@leothaud I tried circt-verilog driver and it seems to work fine on your example (-cse -llhd-combine-drives eliminates the cycle so maybe youn can run circt-opt --moore-lower-concatref --canonicalize --cse --convert-moore-to-core --cse --llhd-combine-drives --llhd-sig2reg --canonicalize --cse). Though I agree SSA cycle is real issue regardless.

[leothaud]

You're right, the -llhd-combine-drives pass solves my problem. Thank you.

[fabianschuiki]

@leothaud You can also try to run your MLIR file that you get from circt-translate --import-verilog through circt-verilog. This will skip the Verilog parsing and just run the regular pass pipeline on it. 😃