[circt-synth] Comb Canonicalization Unexpectedly Increasing Logic Depth

[cowardsa]

Running circt-synth on an 8-bit adder with and without the carry-out we see an unexpected improvement in longest path when computing the carry-out:

hw.module @add_two_no_carry(in %a : i8, in %b : i8, out sum : i8) {
    %0 = comb.add %a, %b : i8
    hw.output %0 : i8
}

hw.module @add_two_with_carry(in %a : i8, in %b : i8, out sum : i9) {
    %false = hw.constant false
    %0 = comb.concat %false, %a : i1, i8
    %1 = comb.concat %false, %b : i1, i8
    %2 = comb.add %0, %1 : i9
    hw.output %2 : i9
}

add_two_no_carry - Maximum Path Delay = 16
add_two_with_carry - Maximum Path Delay = 14

It's reasonable to expect add_two_no_carry to have better or equal delay, since we are computing a subset of the bits. However, inspecting the designs, we see that the comb canonicalizers are greedily folding Xor operators that have very different arrival times, leading to poor lowering choices. Removing the tryFlatteningOperands pattern in XorOp::canonicalize add_two_no_carry can be made to match the depth 14 delay path.

I guess this is a challenge of mixing timing aware and timing unaware passes but any suggestions on how we might resolve this challenge in general?

[uenoku]

I think flattening in canonicalization is ok because ideally we can balance the xor more freely at later stage. I think the root cause is that xor lowering in CombToSynth doesn't look at the logic depth. Though I'm slightly reluctant to introduce timing info to CombToSynth at this point as we cannot use Conversion framework with timing info (that said maybe we eventually need to introduce somehow). So my current thought is to make LowerVariadicPass timing aware, and lower variadic XoR to binary XoR just before CombToSynth. Balancing xor is more challenging than and/or since and/maj-inv cannot represent xor in a single operation (I think that's one of primary reasons for existence of XAG/XMG representation) hence i think it's reasonable to perform balancing in that stage. I think I can work on extending LowerVariadic this week.

[cowardsa]

This seems like a good plan - agreed that making canonicalization timing aware is not going to be a sensible path - lowering variadic timing-aware would actually be really helpful in various ways e.g. xyz, then knowing which multiplier to perform first is rather useful.

Nice to learn about the XAG - hadn't encountered that in my work so far.

@uenoku - Will add that there is no rush on this just discovered it and wanted to document on the circt-synth roadmap :)

[uenoku]

Yes, I think generalization would be cool. Let me use this as a tracking issue 👍

[uenoku]

#9086 will fix the issue. add_two_no_carry will become 14 as well.